Duplicate items in std::map

There's a certain piece of code in our product which uses an std::map to store data, the key for which is boost::make_tuple(std::string, std::string). While debugging an issue, I found that after inserting a key-value pair in the map, find for that key in the map resulted in negative, and another attempt to insert the key-value1 pair succeeded.

This illustrates the sequence of operations:

Flow A:

Key k = boost::make_tuple(str1, str2);
bool added = temp_map_.insert(std::make_pair(k, val)).second;

Flow B:

TempMap::iterator itr = temp_map_.find(k);
if (itr != temp_map_.end()) {
    Key k = boost::make_tuple(str1, str2);
    bool added = temp_map_.insert(std::make_pair(k, val1)).second;
}

Please note that Flow B begins after Flow A is completed.

The first 'insert' succeeds. The 'find' does not find the key, and the second 'insert' also succeeds. Eventually, the 'erase' operation on the key succeeds, and the subsequent 'find' finds the key in the map.

I don't have a reproducer for this, but this happens in our product when a certain test is run repeatedly, say about 6-7 times.

Any thoughts on how this can happen?