Как осуществляется внедрение multi_index

У меня есть некоторые трудности с пониманием того, как внедрен 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*, которое указывает на сохраненный объект в массиве. Это нормально?

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

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

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

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