How to allocate std::map's internal RB_tree node in memory pool in C++11?

user_4127047 0
Viewed 494

std::map definition is copied below: 

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

Based on std::map definition, we can provider customized allocator for its Key and Value.

Questions:

  1. In most situations, std::map is implemented by RB tree. How can we provide customized allocator for RB tree node? I am afraid that we can not do it.
  2. If the answer to the first question is that we can NOT provide customized allocator for RB tree node, we can NOT provide customized allocator for other node-based containers (for example, std::list and std::set), either. Please confirm if my understanding is correct.
allocator stdmap c++11 c++
1 Answers

IIRC, the allocator type that you provide as a map template argument is used also for allocation of nodes (namely its allocate member function). You can observe this, for example, in the source code of libstdc++:

typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
   rebind<value_type>::other _Pair_alloc_type;

typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
    key_compare, _Pair_alloc_type> _Rep_type;

The original allocator parameter _Alloc of std::map is rebound to a map's value type and passed as a template argument to _Rb_tree. There, the allocator is again rebound to the node type _Rb_tree_node<_Val>:

typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
   rebind<_Rb_tree_node<_Val> >::other _Node_allocator;

A typical usage of this mechanism is to exploit some memory pool-based allocator, which might considerably speed-up node allocations. However, beware that this technique is, generally, not straightforward. For instance, with std::unordered_map, the (rebound) allocator type is used both for allocation of nodes and allocation of the array of buckets. In the allocate member function, one then needs to distinguish both allocation types and use memory pooling just for allocation of nodes.

With std::map, there is no array of buckets, so, theoretically, the allocator should be used only for allocation of nodes. However, I am not sure whether this is guaranteed by the Standard.

user_5800830
Related