CODEWITHSUNDEEP
c++c++11memory-managementunordered-mapstd
Nicholas
Nicholas

Reputation: 1462

Memory allocations when using unordered_map

If a std::unordered_map<int,...> was to stay roughly the same size but continually add and remove items, would it continually allocate and free memory or cache and reuse the memory (ie. like a pool or vector)? Assuming a modern standard MS implementation of the libraries.

Upvotes: 1

Views: 6099

Answers (1)

paul-g
paul-g

Reputation: 3877

The standard is not specific about these aspects, so they are implementation defined. Most notably, a caching behaviour like you describe is normally achieved by using a custom allocator (e.g. for a memory pool allocator) so it should normally be decoupled from the container implementation.

The relevant bits of the standard, ~p874 about unordered containers:

The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound.

and insert:

The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container’s bucket count, and z is the container’s maximum load factor

You could read between the lines and assume that since iterator validity is not affected, probably no memory allocations will take place. Though this is by no means guaranteed (e.g. if the bucket data structure is a linked list, you can append to it without invalidating iterators). The standard doesn't seem to specify what should happen when an element is removed, but since it couldn't invalidate the constraint above I don't see a reason to deallocate memory.

The easiest way to find out for sure for your specific implementation is to read the source or profile your code. Alternatively you can try to take control of this behaviour (if you really need to) by using the rehash and resize methods and tuning the map's load_factor.

Upvotes: 3

Related Questions