This post is a follow-up of the previous post about pool memory allocators for STL sets, and basically applies the same concepts to another well-known STL container: std::unordered_map.

In the last post, we saw how to implement a pool memory allocator specifically designed to store the kind of objects allocated by std::sets, which ultimately turned out being just one type: _Rbnode<T>, where T is the same as std::set<T> mySet. This allocator allowed us to significantly reduce the calls to malloc() and to reduce the risk of external fragmentation, as well as zero-ing the internal fragmentation.

Now, if we want to accomplish the same things with a std::unordered_map, we need to be careful about some more things:

  1. Differently from STL sets, an STL unordered map allocates three types of objects during its lifetime;
  2. While sets allocates only one RB node at a time, unordered maps tend to allocate much more data, possibly exceeding the size of the memory buckets implemented by the allocators.

Defining the memory pool

Following the last post implementation, we define a memory pool as a unique tuple of memory buckets with different sizes. In particular, for an unordered map we need to allocate three kinds of objects:

  • Cached hash nodes: these are implemented as structs of type std::__detail::_Hash_node<pair_type, true>, where pair_type is an alias for std::pair<TKey const, TValue> for a map from TKey to TValue.
  • Uncached hash nodes: these are implemented as structs of type std::__detail::_Hash_node<pairType, false>, same as the previous type but with a false as second template argument. An unordered map needs to allocate