как реализовано повышение multi_index - PullRequest
Новая
       24

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

20 голосов
/ 17 ноября 2010

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

Ответы [ 3 ]

30 голосов
/ 17 ноября 2010

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

Реализация основана на узлах, связанных с указателями, как, скажем, ваша любимая 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;
};

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

4 голосов
/ 17 ноября 2010

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

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

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

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

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

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

2 голосов
/ 17 ноября 2010

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

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

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

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

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

...