How does insertion in an unordered_map in C++ work?

Question

int main() { auto n=0, sockNumber=0, pairs=0; unordered_map<int, int> numberOfPairs; cin >> n; for(int i=0; i<n; ++i) { cin >> sockNumber; numberOfPairs.insert({sockNumber, 0}); // >>>>>> HERE <<<<<< numberOfPairs.at(sockNumber) += 1; if(numberOfPairs.at(sockNumber) % 2 == 0) { pairs += 1; } } cout << pairs; return 0; }

This code counts the number of pairs in the given input and prints it. I want to know how the insert method of an unordered_map works. Every time I see a number, I've inserted it with a value '0'.

Does the insert method skip inserting the value '0' when it sees the same number again? How does it work?

Input -

9

10 20 20 10 10 30 50 10 20

Output -

3

Edgar Rokjān · Accepted Answer · 2016-12-04 08:58:03Z

Does the insert method skip inserting the value '0' when it sees the same number again?

Yes, it does.

From the cpp.reference.com unordered_map :

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.

And from the cpp.reference.com unordered_map::insert :

Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

How does it work?

I suppose that certain work principles depend much on the particular STL implementation.

Basically unordered_map is implemented as a hash table where elements are organized into the buckets corresponding to the same hash. When you try to insert a key-value pair key hash is computed. If there is no such hash in the hash table or there is no such key-value pair in the bucket corresponding to the computed hash then the new pair is inserted into the unordered_map.

Steve Deng Zishi · Accepted Answer · 2016-12-04 08:37:45Z

unordered_map does not allow key duplicates, so if you are trying to use the .insert() method to insert the same key it will fail and skip that operation. However if you use unorderedMap[key] = value to insert a duplicate key, it will not skip but updating the value matching the key to the new value.

PaulMcKenzie · Accepted Answer · 2016-12-04 07:46:08Z

A std::unordered_map holds unique keys as values. If you want to keep inserting the same key, then use std::unordered_multimap.

Also, you should realize that std::unordered_map::insert returns a value that denotes whether the insertion was successful.

if ( !numberOfPairs.insert({sockNumber, 0}).second ) { // insertion didn't work }

You could have used the above to confirm that the item wasn't inserted, since the same key existed already in the map.

Collectives™ on Stack Overflow

How does insertion in an unordered_map in C++ work?

3 Answers 3

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Related