Пользовательские распределители в STL только распределяют фактические данные?

Question

Допустим, я создаю связанный список в STL:

list<int, my_allocator<int> > data;

Тогда я могу использовать более эффективный распределитель, скажем, пул памяти.Но не нужно ли списку выделять внутреннюю память, такую ​​как указатели вперед и назад, чтобы пройти по списку?Как они будут распределены?Используя обычный new или как-то используя my_allocator?

Answer 1

Контейнер действительно перераспределяет ваш распределитель для размещения его собственного бухгалтерского материала. (Не то, чтобы это имело значение для std::list, но в целом это так. *) Вот почему стандартные требования к распределителю предписывают существование шаблона rebind:

typedef typename Alloc::template rebind<MyInternalStuff>::other internal_allocator;

Если ваш распределитель Alloc = my_allocator<T>, то internal_allocator становится my_allocator<MyInternalStuff>.

Я полагаю, что это было одним из недостатков, которые испытал Electronic Arts со стандартной библиотекой C ++, поэтому в их библиотеке EASTL используется другое соглашение для распределителей, обеспечивающее более жесткий контроль.

_{*) Как правило, каждый узел будет одним монолитным объектом некоторого типа Node<T>, поэтому я предполагаю, что std::list<T, Alloc> только когда-либо использует Alloc::rebind<Node<T>>::other в качестве распределителя.}

[Извините за множественные правки; Я исказил вывод и не правильно его интерпретировал; Теперь я пошел и распечатал каждый контейнер отдельно и исправил вывод соответственно. std::list действительно требует только один распределитель.]

---

Обновление: Только для хихиканья, я написал небольшой распределитель распаковки, который печатает свое собственное имя при создании. Вот входные данные:

#include <unordered_map>
#include <set>
#include <deque>
#include <list>
#include <vector>
#include <map>

#include <iostream>

int main()
{
  std::cout << "----- unordered_map<int, double> -----------" << std::endl;
  std::unordered_map<int, double, std::hash<int>, std::equal_to<int>, funky_allocator<std::pair<const int, double>>> m { {1, 1.2} };
  std::cout << "----- set<int> -----------------------------" << std::endl;
  std::set<int, std::less<int>, funky_allocator<int>> s;
  std::cout << "----- deque<int> ---------------------------" << std::endl;
  std::deque<int, funky_allocator<int>> d;
  std::cout << "----- list<int> ----------------------------" << std::endl;
  std::list<int, funky_allocator<int>> l;
  std::cout << "----- vector<int> --------------------------" << std::endl;
  std::vector<int, funky_allocator<int>> c;
  std::cout << "----- map<int, bool> -----------------------" << std::endl;
  std::map<int, bool, std::less<int>, funky_allocator<std::pair<const int, bool>>> n { { 1, true } };
}

А вот и вывод:

----- unordered_map<int, double> -----------
Default-construct: funky_allocator<std::pair<int const, double> >
Copy-construct:    funky_allocator<std::__detail::_Hash_node<std::pair<int const, double>, false> >
Copy-construct:    funky_allocator<std::__detail::_Hash_node<std::pair<int const, double>, false>*>

----- set<int> -----------------------------
Default-construct: funky_allocator<std::_Rb_tree_node<int> >

----- deque<int> ---------------------------
Default-construct: funky_allocator<int>
Copy-construct:    funky_allocator<int*>

----- list<int> ----------------------------
Default-construct: funky_allocator<std::_List_node<int> >

----- vector<int> --------------------------
Default-construct: funky_allocator<int>

----- map<int, bool> -----------------------
Default-construct: funky_allocator<std::_Rb_tree_node<std::pair<int const, bool> > >

Детали варьируются в зависимости от того, какой конструктор используется: такие контейнеры, как set и map, могут создавать «правильный» распределитель только в одном вызове, тогда как в другом они могут сначала создать объект указанного распределителя. В любом случае, указанный распределитель никогда не используется вообще для пары контейнеров, и только используется версия восстановления.