CODEWITHSUNDEEP
c++dictionarydata-structuresunordered-map
Just another person
Just another person

Reputation: 437

How to initialize an empty unordered map in C++?

I have to run a loop (the looping on t) on an unordered map in C++ and each time the loop is run, the unordered map gets updated. But what I want to do is, start with an empty map each time the loop is run. How do I initialise an empty unordered map?

while (t--){
        unordered_map<int, int> freq;
        //perform  various insertions and deletions in the map
        //print all the elements in the map
        }

Upvotes: 1

Views: 2421

Answers (1)

Jorge Bellon
Jorge Bellon

Reputation: 3106

Unordered maps are a bit tricky in the sense that they use two things:

  1. A chain of {key,value} pairs (STL uses a std::forward_list).
  2. An array of positions to the chain elements (hash table).

When you insert elements to the map, the array gets filled (load factor increases) and hash collisions start to become frequent. This ends up in that array being resized, and all its elements (positions to the chain of pairs) being re-created (this is called rehashing).

That being said, your code does exactly what you are asking for: declaring a variable of type std::unordered_map<int,int> initialises it by default. When the program loops back, the map gets out of scope before the following iteration (destructor is called) and a new variable is initialised when the new iteration begins.

However, you might consider using another alternative: calling clear() instead, at the beginning of your loop, and declare your map outside the loop:

std::unordered_map<int, int> freq;
while (t--) {
   freq.clear();
   // do something with freq
}

If all the iterations are similar (you introduce a similar amount of pairs in freq), the first iteration will find the appropriate size of the hash table (rehashing takes place), but subsequent iterations won't see this effect as often: during clear() we erase all the chain's elements but we keep the array, which will be reused during the whole loop.

Upvotes: 3

Related Questions