Can I access a C++11 std::map entry while inserting/erasing from another thread?

Question

Can I access (without locking) an std::map entry while another thread inserts/erases entrys?

example pseudo C++:

typedef struct {
   int value;
   int stuff;
}some_type_t;

std::map<char,some_type_t*> my_map;   

//thread 1 does:
my_map.at('a')->value = 1;

//thread 2 does:
some_type_t* stuff = my_map.at('b');

//thread 3 does:
my_map.erase('c');

//I'm not modifying any elements T is a pointer to an previously allocated "some_type_t" 

std C++11 says that all members should be thread safe (erase() is not const).

Answer 1

No. And yes.

Two or more threads can perform const operations on a map, where a few non-const operations also count (operations that return non-const iterators, hence are not const, like begin and similar stuff).

You can also modify the non-key component of an element of a map or set while other operations that do not read/write/destroy said element's non-key component run (which is most of them, except stuff like erase or =).

You cannot erase or insert or other similar non-const map operations while doing anything with const and similar map operations (like find or at). Note that [] can be similar to erase if the element is added.

The standard has an explicit list of non-const operations that count as const for the purposes of thread safety -- but they are basically lookups that return iterator or &.

Answer 2

No no no no no!

map::erase modifies the links between the map entries and that messes with the search algorithm used in map::at. You can use the elements during an erase, but you can not execute the searching algorithm itself!

I've created an illustration program. On my machine this program sometimes print OK, sometimes throws a map exception - that means that the search is gone wrong. Increasing the number of reading threads make the exception appear more often.

#include <iostream>
#include <thread>
#include <map>
#include <cassert>

std::map<int, int> m;

// this thread uses map::at to access elements
void foo()
{
  for (int i = 0; i < 1000000; ++i) {
    int lindex = 10000 + i % 1000;
    int l = m.at(lindex);
    assert(l == lindex);
    int hindex = 90000 + i % 1000;
    int h = m.at(hindex);
    assert(h == hindex);
  }
  std::cout << "OK" << std::endl;
}

// this thread uses map::erase to delete elements
void bar()
{
  for (int i = 20000; i < 80000; ++i) {
    m.erase(i);
  }
}

int main()
{
  for (int i = 0; i < 100000; ++i) {
    m[i] = i;
  }

  std::thread read1(foo);
  std::thread read2(foo);
  std::thread erase(bar);

  read1.join();
  read2.join();
  erase.join();

  return 0;
}