CODEWITHSUNDEEP
c++c++11insertunordered-map
Troskyvs
Troskyvs

Reputation: 8047

C++11: does unordered_map/set guarantees traversing order as insert order?

I wrote some code like this:

unordered_map<int, int> uii;
uii.insert(make_pair(12,4));
uii.insert(make_pair(3,2));
uii.insert(make_pair(6,1));
uii.insert(make_pair(16,9));
....

When I use a for loop to visit this map, it prints key in the right order of my insertion. I tested unordered_set, with same result.

So my question is, does the C++ standard guarantee the visiting order as insert order, just like Java's LinkedHashMap?

Upvotes: 4

Views: 1869

Answers (1)

Yola
Yola

Reputation: 19033

No, it is unordered, there is no such guarantee.

Elements in an unordered associative container are organized into buckets, keys with the same hash will end up in the same bucket. The number of buckets is increased when the size of the container increases to keep the average number of elements in each bucket under a certain value.

Rehashing invalidates iterator and might cause the elements to be re-arranged in different buckets but it doesn't invalidate references to the elements.

This is valid for both unordered_map and unordered_set.

You might also want to check this question Keep the order of unordered_map as we insert a new key

But, internally an implementation of unordered container might use list or other ordered container to store elements and store only references to sublists in its buckets, that would make iteration order to coincide with the insertion order until enough elements are inserted to cause list rearranging. That is the case with VS implementation.

Upvotes: 8

Related Questions