Do the iterator invalidation rules mean thread safety?

Question

Here in this Stack Overflow answer it is listed the iterator invalidation rules for the standard containers in C++11. Particularly, there are for insertion:

1. [multi]{set,map}: all iterators and references unaffected [23.2.4/9]

2. unordered_[multi]{set,map}: all iterators invalidated when rehashing occurs, but references unaffected [23.2.5/8]. Rehashing does not occur if the insertion does not cause the container's size to exceed z * B where z is the maximum load factor and B the current number of buckets. [23.2.5/14]

   erasure:

3. [multi]{set,map} and unordered_[multi]{set,map}: only iterators and references to the erased elements are invalidated

Do these rules mean I can safely do insertion and erasure in one thread, and safely in another thread access, look for (using find) elements as long as these elements are not the ones being inserted and erased in the first thread, and make sure that rehashing is not happening?

If not, what do these rules exactly mean?

Answer 1

The fact that iterators to elements of the container are not invalidated in no way implies thread safety on the container itself. For example, the size member variable would need to be modified atomically which is a totally separate issue from iterators being invalidated (or not) on insertion/deletion.

tl;dr; No.

These rules simply tell you when an iterator to an element is invalidated by an operation. For example, when a vector resizes, the underlying array is reallocated elsewhere so if you had an iterator (or pointer) to an element, it would no longer be valid after the resize (because it would be pointing to deleted elements of the old array).

Answer 2

There are two kinds of operations on C++ std containers. Reader and Writer operations (these are not the terms the standard uses, but this reads easier). In addition, there are operations on elements in the container.

A const method is a Reader method, as are "lookup" functions that are only non-const because they return a non-const reference to an element (or similar). There is a complete list in the standard, but common sense should work. vector::operator[], begin(), map::find() are all "Readers". map::operator[] is not a "Reader".

You can have any number of threads engaging in Reader operations at the same time no problem.

If you have any thread engaged in a Writer operation, no other access can occur on the container.

You cannot safely have one Reader and one Writer at the same time. If you have any Writers, you must have excluded all other access.

You can safely have 1337 readers at once.

Operations on elements is somewhat similar, except that Writing to an element need only exclude other access to that element. And you are responsible for making your const method play nice with each other. (the std guarantees that the const methods of the container will only call const methods of the elements)

Note that changing sorting order in a std:: associative container is UB without modifying the container.

An iterator that is not invalidated, where you just operate on the element, will (I believe) count as operations on the element. Only synchronization on that element is required.

Note that std::vector<bool> does not follow the above rules.

---

If you violate the above rules, the C++ std library does not stop you. It just states there is a race condition -- aka, undefined behavior. Anything can happen. In C++ std library, if you don't need something, you don't pay for it: and a single-threaded use of those containers would not need the weight of synchronization. So you don't get it by default.

A std::shared_timed_mutex or std::experimental::shared_mutex can both be useful to guarantee the above holds. unique_lock for Writing, and shared_lock for Reading. Write access to elements has to be shared_locked on the container guarded, and somehow guarded against overlapping access to the same element without deadlock.

---

Iterator invalidation rules are relatively orthogonal to the thread-safety rules.

Answer 3

Using find implies traversal, at least over a subset of the elements. insert and erase on [multi]{set,map} results in rebalancing the underlying tree, which impacts the links between the nodes. If a rebalance happens at the same time as a find, bad things will happen.

Similarly bad things will happen if you attempt a find during unordered_[multi]{set,map} insert or erase. insert can cause rehashing. And both insert and erase need to link/unlink elements from a list. If a find is searching over a list during a link/unlink, you lose.

[] on [unordered][multi]{set,map} is shorthand for "find and insert if not found". at is shorthand for find. So no, these are not safe to use either.

If you have an existing iterator into a [multi]{set,map}, you can continue to dereference (but not increment/decrement) that iterator while another element is inserted or erased. For unordered_[multi]{set,map}, this is true only if you can guarantee that rehashing won't happen under the insert (it never happens under the erase).

Answer 4

There are other answers here who go into the thread safety issue. So if these rules don't mean thread safety where does that leaves us?

If not, what do these rules exactly mean?

They tell you when you can't use an iterator anymore.

Lets take a (deceptive innocent) example:

auto v = std::vector<int>{....};
//v.reserve(...);

for (auto it = std::begin(v); it != std::end(v); ++it) {
   if (*it == ...)
     std::insert(it, ...);
}

Here you traverse a vector and for each element that tests a condition, you insert something into that position.

Now is this code valid? The iterator invalidation rules tells you that if the vector's capacity is big enough the insertion invalidates only iterator after the insert position. So if you can prove that the reserve (commented line) is big enough, then yes, the code is valid. If not, the code is invalid, as the insert invalidates all the iterators of the vector, which means that it is invalidated, which means that you cannot use it anymore. You'd have to have to reacquire it:

auto idx = std::distance(std::begin(v), it);
std::insert(it, ...);
it = std::begin(v) + idx;