Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is order of iteration over the elements of std::unordered_set guaranteed to be always the same?

If iterate over the elements of std::unordered_set multiple times without changing the contents of the set (but potentially reading from it, calculating its size, etc.), is it guaranteed that the elements will be visited in the same order each time?

like image 566
quant_dev Avatar asked Mar 26 '16 23:03

quant_dev


People also ask

Does STD set iterate in order?

Per the C++ standard, iteration over the elements in an std::set proceeds in sorted order as determined by std::less or by the optional comparison predicate template argument.

How does unordered_set work?

Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value. In an unordered_set, the value of an element is at the same time its key, that identifies it uniquely.

Does unordered set preserve order?

Use unordered_set when We need to keep a set of distinct elements and no ordering is required.

What is the time complexity of unordered_set?

The time complexity of set operations is O(log n) while for unordered_set, it is O(1).


1 Answers

In the specific case you mention, yes. Because the standard is explicit about when re-hashing (and therefore re-ordering) takes place.

It only happens during an insert.

§ 23.2.5 [unord.req]

9 The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound. Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. For unordered_multiset and unordered_multimap, rehashing preserves the relative ordering of equivalent elements.

like image 176
Richard Hodges Avatar answered Nov 02 '22 23:11

Richard Hodges