Iterating over unordered_map C++

Question

Is it true that keys inserted in a particular order in an unordered_map, will come in the same order while iterating over the map using iterator?

Like for example: if we insert (4,3), (2, 5), (6, 7) in B. And iterate like:

for(auto it=B.begin();it!=B.end();it++) {
    cout<<(it->first); 
}

will it give us 4, 2, 6 or keys may come in any order?

It's called "unordered" because the order in which inserted elements are stored and iterated isn't generally something client code can utilise for its own purpose. If you want ordering by insertion order, you might be better off using a `vector` if you don't need to erase elements, or a `std::map` keyed on an insertion timestamp (of sufficient resolution to guarantee uniqueness) or an incrementing insertion counter. — Tony Delroy, Jun 16 '18 at 02:00
In current implementations, `unordered_map` is just a hashmap, so no insertion ordered is preserved: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119 — Ciro Santilli OurBigBook.com, Jan 08 '20 at 18:09

score 94 · Accepted Answer · answered Jun 15 '18 at 07:37

94

From the cplusplus.com page about the begin member function of unordered_map (link):

Notice that an unordered_map object makes no guarantees on which specific element is considered its first element.

So no, there is no guarantee the elements will be iterated over in the order they were inserted.

FYI, you can iterate over an unordered_map more simply:

for (auto& it: B) {
    // Do stuff
    cout << it.first;
}

answered Jun 15 '18 at 07:37

Aimery

7

or even better, since c++17 you can use structured binding: `for (auto& [key, value]: B) { std::cout << key << " " << value; }` – Adham Nov 27 '22 at 22:41

score 1 · Answer 2 · answered Jun 25 '20 at 06:47

Information added to the answer provided by @Aimery,

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

Internally, the elements are not sorted in any particular order but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements since once the hash is computed, it refers to the exact bucket the element is placed into.

See the ref. from https://en.cppreference.com/w/cpp/container/unordered_map.
According to Sumod Mathilakath gave an answer in Quora

If you prefer to keep intermediate data in sorted order, use std::map<key,value> instead std::unordered_map. It will sort on key by default using std::less<> so you will get result in ascending order.

std::unordered_map is an implementation of hash table data structure, so it will arrange the elements internally according to the hash value using by std::unordered_map. But in case std::map it is usually a red black binary tree implementation.

See the ref. from What will be order of key in unordered_map in c++ and why?.

So, I think we got the answer more clearly.

this does not answer the question whether the iteration order is the same as the insertion order - which as @Aimery pointed out two years before you is not the case — Onno Rouast, Apr 02 '22 at 13:01

2 Answers2