That's what I'm talking about though.

    foreach(datastructure){
        datastructure.what-functions-are-legal() ??
    }

Vector: Inserts are allowed as long as element fits in vector.capacity(). Erase (which "shifts" the elements down) are allowed at the end of the vector (specifically: all locations "after" the erase are invalidated. So pop_back() is always legal)

List: All operations allowed, except for reading from an erased element.

map: All operations allowed, except for reading from an erased element.

unordered_map: ??? Under debate right now.

-------

So even if you had assurances that unordered_map.insert would work (ex: Robinhood hash, you check size() and compare to capacity(), much like a vector), the movement of data means that your iterator is basically invalidated on any insert.

So unordered_map(Robin-hood): Nothing. No erases, no insertions allowed during the foreach loop at all.

-------

This comes up in practice. The minute you have 2 threads, and a 2nd thread _might_ insert while the 1st thread _might_ be in a foreach loop, you suddenly have to have assurances for what is or isn't legal from an iterator-invalidation perspective.

I guess you could just have the entire for-each loop inside of a lock, but that seems a bit inefficient?

> So unordered_map(Robin-hood): Nothing. No erases, no insertions allowed during the foreach loop at all.

Yes, but this applies to any hashtable that might rehash on inseration (= most). In practice this is not a big problem. For example, you can just put the new elements / to be deleted keys on a std::vector and only insert/erase after the for-loop.

I don't see how this makes iteration itself problematic. You can still iterate over a std::unordered_map perfectly fine. Just don't erase/insert elements while iterating.

> I guess you could just have the entire for-each loop inside of a lock, but that seems a bit inefficient?

Yes, you would have to lock the whole for-loop. It's the same with any other data structures where the iterators can get invalidated on inseration/deletion, e.g. std::vector.

Even for containers where iterators are not invalidated, you have to be careful with fain-grained locks. For example, you can only increment the iterator while holding the lock!