Como o boost multi_index é implementado

Question

Tenho algumas dificuldades para entender como o boost.MultiIndex é implementado. Digamos que eu tenha o seguinte:

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

Eu imagino que tenho uma matriz, Employee[], que realmente armazena o employee objetos e dois mapas

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

com nome e idade como chaves. Cada mapa tem employee* valor que aponta para o objeto armazenado na matriz. Está tudo bem?

Answer 1

Uma breve explicação sobre a estrutura subjacente é dada aqui, citado abaixo:

A implementação é baseada em nós interligados por ponteiros, assim como, digamos, seu favorito std::set implementação. Vou elaborar um pouco sobre isso: um std::set geralmente é implementado como uma árvore rb onde os nós parecem

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

Bem, a multi_index_containerO nó é basicamente um "multinodo" com tantos cabeçalhos quanto os índices e a carga útil. Por exemplo, um multi_index_container Com dois chamados índices ordenados, usa um nó interno que se parece

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

(A realidade é mais complicada, esses nós são gerados através de alguma metaprogramação etc. Mas você entendeu) [...

Answer 2

Conceitualmente, sim.

Pelo que entendi de boost.multiIndex (eu o usei, mas não vi a implementação), seu exemplo com dois ordered_unique Os índices realmente criarão dois recipientes associativos classificados (como std::map) que armazenam ponteiros/referências/índices em um conjunto comum de employees.

De qualquer forma, todo employee é armazenado apenas uma vez no recipiente multi-indexado, enquanto uma combinação de map<string,employee> e map<int,employee> armazenaria todos os funcionários duas vezes.

Pode muito bem ser que exista realmente uma matriz (dinâmica) dentro de alguns recipientes multi-indexados, mas há nenhuma garantia que isso é verdade:

Índices de acesso aleatório] não fornecem contiguidade de memória, uma propriedade de std::vectors pelos quais os elementos são armazenados adjacentes entre si em um único bloco de memória.

Também, Boost.bimap é baseado no boost.multiIndex e o primeiro permite diferentes representações de sua estrutura "backbone".

Answer 3

Na verdade, eu não acho que seja.

Com base no que está localizado em detail/node_type.hpp. Parece -me que como um std::map O nó conterá o valor e o índice. Exceto que, neste caso, os vários índices diferem um do outro e, portanto, a intercalação do nó realmente diferiria, dependendo do índice que você está seguindo.

Porém, não tenho certeza disso, os cabeçalhos do Boost são definitivamente difíceis de analisar, mas faria sentido se você pense em termo de memória:

• Menos alocações: alocação/desalocação mais rápida
• Melhor localidade de cache

Eu apreciaria uma resposta definitiva, se alguém souber sobre o sangue.