Parallel append and iteration without locks in std::list

Question

I am using a std::list in a multithreaded program. Elements are only added to the end of the list and only removed from the beginning of the list. There exists a writer lock to guarantee mutual exclusion for writes. Readers access the list without obtaining the lock. The readers maintain iterators which cannot be invalidated by erase() as I guarantee that elements are only erased if the readers have passed them. The only possible data race I can imagine is if an element is appended, and one of the readers accesses that element before the inserter has written the element itself.

With a single writer, appending (insert at the end) should be atomic as a single write is needed to insert the new element.

std::list apparently gives no guarantees whatsoever, can somebody confirm that above usage should work without data races. If not, is there an alternative (e.g. boost) which gives such a guarantee?

• Stack Exchange Broke The Law: "std::list apparently gives no guarantees whatsoever" - you said it yourself. If it gives no guarantees, you can't rely on it only accessing the last node when you insert at the end (because it doesn't guarantee that). You certainly can't rely on appending being atomic (because it doesn't guarantee that either).
• hlitz: thats why I am asking for alternatives. Also it might very well be that my use case is supported, the documentation just doesn't state it due to the sheer number of use cases.

Answer 1

As you wrote, a race condition can happen:

The only possible data race I can imagine is if an element is appended, and one of the readers accesses that element before the inserter has written the element itself.

Also std::list is a doubly-linked list, so while removing the first element the second is accessed and while adding a new element the old last element is written to. So your iterators must be constant (no ++iter or --iter).

You may want to have a look at boost::lockfree::queue — it might be exactly what you are looking for.

• hlitz: Yes with a doubly-linked list insertion is not atomic but for my purpose it is as I m only forward iterating through the list. boost::lockfree does not work for me as I need to iterate over the container, also it uses expensive atomic instructions to support multiple writers which I don't need.

Answer 2

I used boost::intrusive::list which solves the problem when disabling the size counter, which became inconsistent when simultaneously removing and inserting elements. Without this the boost list sets four pointers and nothing else when removing/inserting elements which is what I need.