CODEWITHSUNDEEP
c++11unordered-map
Sonu Patidar
Sonu Patidar

Reputation: 791

Iterating over unordered_map C++

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?

Upvotes: 64

Views: 163007

Answers (2)

Shudipta Sharma
Shudipta Sharma

Reputation: 5852

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.

Upvotes: 3

Aimery
Aimery

Reputation: 1773

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;
}

Upvotes: 112

Related Questions