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

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 мы можем предоставить настраиваемый распределитель для его Key и Value.

Вопросы:

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

c++ c++11 stdmap allocator
person Zhongkun Ma    schedule 17.10.2019    source источник
comment
Я не уверен, правильно ли я понял ваш вопрос, но если вы предоставите собственный распределитель, все узлы будут выделены с использованием предоставленного распределителя.   -  person wychmaster    schedule 18.10.2019
comment
Спасибо за вашу помощь. Мне нужно знать размер узла, чтобы рассчитать размер пула памяти. Они используют один и тот же распределитель, но он выделяет память размером _Rb_tree_node вместо std::pair‹const Key, T›.   -  person Zhongkun Ma    schedule 24.10.2019
comment
Размер узла карты зависит от реализации STL. Если я правильно помню, в моей системе это был размер пары плюс 3 * sizeof(std::size_t), который исходит от указателей node. Возможно, поможет следующая ссылка: -use-with" title="как вы определяете размер узлов, созданных stdmap для использования с"> stackoverflow.com/questions/22951378/   -  person wychmaster    schedule 24.10.2019
comment
спасибо, гораздо безопаснее использовать _Rb_tree_node вместо размера пары плюс 3 * sizeof(std::size_t)   -  person Zhongkun Ma    schedule 25.10.2019

Ответы (1)


arrow_upward
4
arrow_downward

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 тип распределителя (rebound) используется как для выделения узлов, так и для выделения массива сегментов. Затем в функции-члене allocate необходимо различать оба типа распределения и использовать пул памяти только для выделения узлов.

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

person Daniel Langr    schedule 18.10.2019
comment
Спасибо за вашу помощь, я пробовал, работает, мне нужно знать размер узла std::map для предварительного расчета размера памяти опроса. - person Zhongkun Ma; 24.10.2019