c++ - cómo se implementa el impulso multi_index

boost multi-index

Question

Tengo algunas dificultades para entender cómo se implementa Boost.MultiIndex. Digamos que tengo lo siguiente:

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

Me imagino que tengo una matriz, Employee[] , que almacena los objetos de los employee , y dos mapas

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

Con nombre y edad como claves. Cada mapa tiene un valor de employee* que apunta al objeto almacenado en la matriz. ¿Esta bien?

Answer 1

Conceptualmente, sí.

Por lo que entiendo de Boost.MultiIndex (lo he usado, pero no he visto la implementación), su ejemplo con dos índices de ordered_unique creará dos contenedores asociativos ordenados (como std::map ) que almacenan punteros / referencias / índices en un conjunto común de employee s.

En cualquier caso, cada employee se almacena solo una vez en el contenedor multi-indexado, mientras que una combinación de map<string,employee> y map<int,employee> almacenaría cada empleado dos veces.

Puede muy bien ser que exista una matriz (dinámica) dentro de algunos contenedores multi-indexados, pero no hay garantía de que esto sea cierto:

[Los índices de acceso aleatorio] no proporcionan contigüidad de memoria, una propiedad de std::vector s por la cual los elementos se almacenan adyacentes entre sí en un solo bloque de memoria.

Además, Boost.Bimap se basa en Boost.MultiIndex y el primero permite diferentes representaciones de su estructura "troncal".

Answer 2

En realidad no creo que lo sea.

Basado en lo que se encuentra en detail/node_type.hpp . Me parece que, como un std::map el nodo contendrá tanto el valor como el índice. Excepto que, en este caso, los distintos índices difieren entre sí y, por lo tanto, el entrelazado de nodos diferiría en función del índice que esté siguiendo.

Sin embargo, no estoy seguro de esto, los encabezados de Boost son definitivamente difíciles de analizar, sin embargo, tendría sentido si piensas en términos de memoria:

• Menos asignaciones: asignación / desasignación más rápida
• mejor localidad de caché

Sin embargo, agradecería una respuesta definitiva, si alguien sabe sobre el gore.

Answer 3

Una breve explicación sobre la estructura subyacente se da here , citada a continuación:

La implementación se basa en nodos interconectados con punteros, al igual que su implementación std::set . Elaboraré un poco sobre esto: un std::set generalmente se implementa como un árbol rb donde los nodos se ven como

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

Bueno, el multi_index_container un multi_index_container es básicamente un "multinodo" con tantos encabezados como índices y la carga útil. Por ejemplo, un multi_index_container con dos denominados índices ordenados utiliza un nodo interno que 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;
};

(La realidad es más complicada, estos nodos se generan a través de alguna metaprogramación, etc. pero se tiene la idea) [...]