So, you’ve been working on some piece of code that employs STL containers, specifically a map. Perhaps you’ve also added some multi-threaded flavoring to pack a punch. Great.
Suddenly, you see this:
Debug Assertion Failed!
Program: C:\….\Test.exe
File: C:\Program Files\Microsoft Visual Studio 8\VC\include\xtree
Line: 293Expression: map/set iterators incompatible
Strange. What just happened? Did you just mix the iterators of different classes together? No, you’re certain you used map iterators, not set iterators. Everything SEEMS well…
Ah, that’s right. You have an iterator that points to the map’s items, and are indeed iterating over them. The map is protected by a mutex, but – so as to not block for too long – you release and reacquire the mutex every iteration. Another thread then executes and clear()’s the map, rendering your iterator useless. You now compare it to the end() iterator, and voila – crash!
The solution? Make sure you don’t invalidate your iterators while using them. That means – don’t modify the STL container from another thread (even if you are using synchronization mechanisms) if you’re not absolutely certain that you can and that you will not invalidate existing iterators. Operations like insert, erase and clear can invalidate iterators – read the details at each container’s documentation page.
According to STL doc, Map and Set both have the “important property that inserting a new element into a set does not invalidate iterators that point to existing elements. Erasing an element from a set also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.”
So I would think that this is only true for clear() and erase(), and that it would be safe to insert() from another thread.
It’s only safe it is from the same thread. Since a map is implementation defined, the inserting thread could be setting pointers to a newly created object. Because the reading thread doesn’t use a lock, it could be reading a stale pointer to another node and end up walking off the map.
There is another scenario where some processor (Intel’s IA series) in which memory synchonrization happens out of order. This means that a pointer to a newly constructed object could be made visible to the reading thread before the memory bits for that object is made visible.
There is no way around it, either use a lock, a semaphore or make sure to use an operation that is guaranteed to be atomic.