Thread: Unordered map behavior on clear and reserve

Originally Posted by golfinguy4

While clear removes items, does it release the memory the unordered_map used to store them?

It is not required to, no.

But the standard doesn't dictate that it shouldn't either, correct? Ie, the release of memory is implementation-defined?

Basically, I have a large unordered_map of POD pairs that is repeatedly cleared and refilled. I want to make sure that calling clear won't result in a ton of memory allocations on the next fill.

Originally Posted by MutantJohn

Why don't you just use valgrind and look at the amount of allocations/deallocations? That's what I do when I'm unsure of stl stuff.

Or just peek inside the class with a debugger or just step through the source code since valgrind only exists for linux.

Visual Studio has a lot of the tools valgrind offers. To my knowledge, there is no port of valgrind. I don't really pay attention to it, though, since it's a command-based tool.

Originally Posted by golfinguy4

But the standard doesn't dictate that it shouldn't either, correct? Ie, the release of memory is implementation-defined?

Sure.

Originally Posted by golfinguy4

Basically, I have a large unordered_map of POD pairs that is repeatedly cleared and refilled. I want to make sure that calling clear won't result in a ton of memory allocations on the next fill.

If you want a guarantee, however, you're out of luck. And should look either into using a different container, or using a container differently.

Originally Posted by golfinguy4

Oops, my mistake. I meant reserve. Good to know that reserve doesn't release memory. While clear removes items, does it release the memory the unordered_map used to store them?

I think it does, yes. (Turns out, this is wrong. See edit)

This is some code I ran :

Code:

#include <iostream>
#include <unordered_map>
#include <utility>


int main(void)
{
    const int n = 50;


    std::unordered_map<int, int> map;
    map.reserve(n);


    for (int j = 0; j < 5; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            map.insert({ i, i });
        }


        map.clear();
    }


    return 0;
}

Compiled in 64 bit Linux with gcc 4.9.2 and : g++ -std=c++11 -Wall -Wextra -pedantic -O3

Here's my valgrind results :

HEAP SUMMARY:
in use at exit: 0 bytes in 0 blocks
total heap usage: 252 allocs, 252 frees, 8,112 bytes allocated

All heap blocks were freed -- no leaks are possible

As you can see, I iterate 5 * 50 = 250 times.

Edit : I did some more testing and it seems like clear is fine. I was wrong before. But even when I get rid of the clear line, it's like using insert() or emplace() 'cause the individual allocations. Am I just inserting/emplacing elements wrong?

That's not the same, John.

What you're seeing is because the map ceases to exist (i.e. the destructor invoked). Before that happens, the "map.clear()" does not guarantee cleanup.

It is possible to get close by calling something like this after the map.clear() calls.

Code:

void cleanup(std::unordered_map<int, int> &map)
{
     std::unordered_map<int, int> temp(map.begin(), map.end(), 0);    //  0 is the initially requested (lower bound for) bucket size
     std::swap(temp, map);
   
     // temp now holds the original contents of map, so that will be released by the destructor as the function returns
}

The catch is that the value for the bucket count (the third argument for the constructor when creating temp) is a lower bound - an implementation is still permitted to reserve more.

The other trade-off of this is that it creates a complete copy of the existing map, before cleaning up.


As I said previously, if there is actually a requirement to clear/fill the map repeatedly and to keep memory down, different strategies (or different container types) are needed. However, I doubt this is a genuine requirement - it is more likely just something golfinguy has decided is a "nice to have" i.e. another form of premature optimisation.

main() provides a scope. When main() returns, your map passes out of scope and its destructor is invoked. It's actions are included in the statistics reported by valgrind.

The details of the particular numbers depends on the implementation of insert() - and other functions related to unordered_map