Como o boost multi_index é implementado
-
25-09-2019 - |
Pergunta
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?
Solução
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_container
O 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) [...
Outras dicas
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 employee
s.
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::vector
s 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".
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.