Как реализовано повышение multi_index

Question

У меня есть некоторые трудности с пониманием того, как реализован Boost.MultiIndex. Допустим, у меня есть следующее:

typedef multi_index_container<
    employee,
    indexed_by<    
        ordered_unique<member<employee, std::string, &employee::name> >,
        ordered_unique<member<employee, int, &employee::age> >
    > 
> employee_set;

Я представляю, что у меня есть один массив, Employee[], который на самом деле хранит employee объекты и две карты

map<std::string, employee*>
map<int, employee*>

с именем и возрастом в качестве ключей. Каждая карта имеет employee* значение, которое указывает на сохраненный объект в массиве. Это нормально?

Answer 1

Краткое объяснение базовой структуры дается здесь, цитируется ниже:

Реализация основана на узлах, связанных с указателями, как говорят ваши любимые std::set реализация. Я немного уточню это: std::set обычно реализуется как RB-дерево, где узлы выглядят как

struct node
{
  // header
  color      c;
  pointer    parent,left,right;
  // payload
  value_type value;
};

Ну а multi_index_containerУзел по сути является "мультиузлом" с таким же количеством заголовков, как и индексов, и полезной нагрузки. Например, multi_index_container с двумя так называемыми упорядоченными индексами использует внутренний узел, который выглядит как

struct node
{
  // header index #0
  color      c0;
  pointer    parent0,left0,right0;
  // header index #1
  color      c1;
  pointer    parent1,left1,right2;
  // payload
  value_type value;
};

(Реальность более сложна, эти узлы генерируются с помощью некоторого метапрограммирования и т. Д., Но вы поняли идею) [...]

Answer 2

Концептуально да.

Из того, что я понимаю, Boost.MultiIndex (я использовал его, но не видел реализацию), ваш пример с двумя ordered_unique Индексы действительно создадут два отсортированных ассоциативных контейнера (например, std::map) которые хранят указатели / ссылки / индексы в общем наборе employees.

В любом случае каждый employee хранится только один раз в многоиндексированном контейнере, тогда как комбинация map<string,employee> а также map<int,employee> будет хранить каждого сотрудника дважды.

Вполне возможно, что внутри некоторых многоиндексированных контейнеров действительно есть (динамический) массив, но нет никакой гарантии, что это так:

[Индексы произвольного доступа] не обеспечивают смежность памяти, свойство std::vectorс помощью которого элементы хранятся рядом друг с другом в одном блоке памяти.

Кроме того, Boost.Bimap основан на Boost.MultiIndex, а первый допускает различные представления своей структуры "магистрали".

Answer 3

На самом деле я не думаю, что это так.

На основании того, что находится в detail/node_type.hpp, Мне кажется, что как std::map узел будет содержать как значение, так и индекс. За исключением того, что в этом случае различные индексы отличаются друг от друга, и, следовательно, чередование узлов будет фактически отличаться в зависимости от индекса, за которым вы следите.

Я не уверен в этом, хотя заголовки Boost определенно трудно анализировать, однако это будет иметь смысл, если подумать с точки зрения памяти:

• меньше распределений: более быстрое распределение / освобождение
• лучшая локальность кэша

Я был бы признателен за окончательный ответ, если кто-нибудь знает о крови.