Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

std::unordered_map pointers/reference invalidation

I have the following code:

std::unordered_map<std::string, std::string> map;

map["k1"] = "v1";
auto& v1 = map["k1"];
map["k2"] = "v2";

After reading http://en.cppreference.com/w/cpp/container/unordered_map

Notes

The swap functions do not invalidate any of the iterators inside the container, but they do invalidate the iterator marking the end of the swap region.

References and pointers to either key or data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.

It looks like v1 can be safely used after inserting new values, even if re-hashing might occur during insertion.

Is my interpretation of this quote correct? May I use references/pointers of the values from the map after modifying the map (obviously erasing the value itself would invalidate the reference/pointer)?

like image 244
Mircea Ispas Avatar asked Oct 05 '16 08:10

Mircea Ispas


People also ask

What does unordered_map return if key not found?

Return value The unordered_map::find() returns one of the two values: Iterator: An iterator to the element when the key exists in the unordered map. Iterator: An iterator to the end of the map when the key does not exist in the unordered map.

Does unordered map allow duplicate keys?

We have discussed unordered_map in our previous post, but there is a limitation, we can not store duplicates in unordered_map, that is if we have a key-value pair already in our unordered_multimap and another pair is inserted, then both will be there whereas in case of unordered_map the previous value corresponding to ...

How do you know if two unordered maps are equal?

The comparison between unordered_map objects is not affected by the arbitrary order in which they store their elements. Two unordered_maps are equal if they have the same number of elements and the elements in one container are a permutation of the elements in the other container. Otherwise, they are unequal.

Does unordered_map use separate chaining?

std::unordered_map is (in)famous for having an API that basically forces implementers to use “buckets with linked lists”, also known as separate chaining.


1 Answers

It looks like v1 can be safely used after inserting new values, even if re-hashing might occur during insertion.

Yes, std::unordered_map::operator[] doesn't invalidate references, even rehashing happens.

(emphasis mine)

If an insertion occurs and results in a rehashing of the container, all iterators are invalidated. Otherwise iterators are not affected. References are not invalidated.

From the standard, [unord.req]/9:

(emphasis mine)

Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements.

like image 164
songyuanyao Avatar answered Sep 22 '22 20:09

songyuanyao