Как выделить внутренний узел RB_tree std :: map в пуле памяти в C ++ 11?

Question

std::map определение скопировано ниже:

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

На основе определения std::map мы можем предоставить настраиваемый распределитель для его Ключа и Значение .

Вопросы:

1. В большинстве случаев std::map реализуется с помощью дерева RB. Как мы можем предоставить настроенный распределитель для узла дерева RB? Боюсь, что мы не сможем это сделать.
2. Если ответ на первый вопрос заключается в том, что мы можем НЕ предоставить настраиваемый распределитель для узла дерева RB, мы можем НЕ предоставить настраиваемый распределитель для других узловых контейнеров (например, std::lis t и std::set), либо. Пожалуйста, подтвердите, если мое понимание верно.

Answer 1

IIRC, тип распределителя, который вы указываете в качестве аргумента шаблона map, используется также для распределения узлов (а именно его функции-члена allocate). Вы можете наблюдать это, например, в исходном коде 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;

Исходный параметр распределителя _Alloc из std::map равен отскок втип значения карты и передается в качестве аргумента шаблона в _Rb_tree. Там распределитель снова возвращается к типу узла _Rb_tree_node<_Val>:

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

---

Типичным использованием этого механизма является использование некоторого пула памяти на основе распределителя, который может значительно ускорить распределение узлов. Однако следует помнить, что этот метод, как правило, не прост. Например, при std::unordered_map тип распределителя (отскока) используется как для распределения узлов, так и для выделения массива сегментов. В функции-члене allocate необходимо различать оба типа выделения и использовать пул памяти только для выделения узлов.

При std::map массив массивов отсутствует, поэтому теоретически распределительследует использовать только для выделения узлов. Однако я не уверен, гарантируется ли это Стандартом.