cómo se implementa boost multi_index

Question

Tengo algunas dificultades para entender cómo se implementa Boost.MultiIndex. Digamos que tengo el 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 realmente almacena los objetos employee, y dos mapas

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

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

Answer 1

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

La aplicación se basa en nodos interconectados con los punteros, tal como dice su std::set aplicación favorita.Voy a elaborar un poco en esto: Un std::set se implementa normalmente como un árbol donde rb-nodos se ven como

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

Bueno, un nodo multi_index_container 's es básicamente un 'varios nodos' con la mayor cantidad de cabeceras como índices como así como la carga útil. Por ejemplo, un multi_index_container con dos de las llamadas ordenó índices utiliza un nodo interno que se parece a

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 algún metaprogramming etc, pero se entiende la idea) [. ..]

Answer 2

Conceptualmente, sí.

Por lo que entiendo de Boost.MultiIndex (lo he usado, pero que no se ve la puesta en práctica), su ejemplo con dos índices ordered_unique será de hecho 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 sólo una vez en el recipiente de múltiples indexadas, mientras que una combinación de map<string,employee> y map<int,employee> almacenaría cada empleado dos veces.

puede muy bien ser que no es de hecho un (dinámico) matriz dentro de algunos contenedores multi-indexado, pero hay no guarantee que esto es cierto:

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

Además, Boost.Bimap is based on Boost.MultiIndex y el anterior permite diferentes representaciones de su estructura "troncal".

Answer 3

En realidad, no creo que sea así.

Según lo que se encuentra en detail/node_type.hpp. Me parece que al igual que 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 del nodo realmente diferirá según el índice que esté siguiendo.

No estoy seguro acerca de esto, sin embargo, aumentar las cabeceras son sin duda difícil de analizar, sin embargo, tendría sentido si se piensa en términos de memoria:

• menos asignaciones: más rápido asignación/desasignación
• mejor cache localidad

Agradecería una respuesta definitiva, si alguien sabe acerca de la sangre derramada.