Is erasing and inserting in a single linked list thread safe?

Question

Using std::forward_list are there any data races when erasing and inserting? For example I have one thread that does nothing but add new elements at the end of the list, and I have another thread that walks the (same) list and can erase elements from it.

From what I know of linked lists, each element holds a pointer to the next element, so if I erase the last element, at the same time that I am inserting a new element, would this cause a data race or do these containers work differently (or do they handle that possibility)?

If it is a data race, is there a (simple and fast) way to avoid this? (Note: The thread that inserts is the most speed critical of the two.)

Answer 1

There are thread-safety guarantees for the standard C++ library containers but they tend not to be of the kind people would consider thread-safety guarantees (that is, however, an error of people expecting the wrong thing). The thread-safety guarantees of standard library containers are roughly (the relevant section 17.6.5.9 [res.on.data.races]):

1. You can have as many readers of a container as you want. What exactly qualifies as reader is a bit subtly but roughly amounts to users of const member functions plus using a few non-const members to only read the data (the thread safety of the read data isn't any of the containers concern, i.e., 23.2.2 [container.requirements.dataraces] specifies that the elements can be changed without the containers introducing data races).
2. If there is one writer of a container, there shall be no other readers or writes of the container in another thread.

That is, reading one end of a container and writing the other end is not thread safe! In fact, even if the actual container changes don't affect the reader immediately, you always need synchronization of some form when communicating a piece of data from one thread to another thread. That is, even if you can guarantee that the consumer doesn't erase() the node the producer currently insert()s, there would be a data race.

Answer 2

No, neither forward_list nor any other STL containers are thread-safe for writes. You must provide synchronization so that no other threads read or write to the container while a write is occurring. Only simultaneous reads are safe.

The simplest way to do this is to use a mutex to lock access to the container while an insert is occurring. Doing this in a portable way requires C++ 11 (std::mutex) or platform-specific features (mutexes in Windows, perhaps pthreads in Linux/Unix).