Как реализован Boost Multi_index

Question

У меня есть некоторые трудности, понимая, как Asost.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) который хранит указатели / ссылки / индексы в общий набор employeeс.

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

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

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

Также, Boost.Bimap основан на Boost.multiindex И первые допускают разные представления его «позвоночника» структуры.

Answer 3

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

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

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

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

Хоть я был бы признателен за определенный ответ, если кто-то знает о горе.