cómo se implementa impulso multi_index

Question

Tengo algunas dificultades para comprender 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 en realidad se almacenan los objetos employee, y dos mapas

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

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

Answer 1

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

La aplicación se basa en nodos interconectados con los punteros, al igual que decir que su aplicación std::set favorito. Voy a elaborar un poco en esto: Un std::set normalmente se implementa como un RB-árbol donde los nodos se parecen

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

Bueno, el nodo de un multi_index_container es básicamente un "varios nodos" con la mayor cantidad de cabeceras como índices, así como la carga útil. Por ejemplo, un multi_index_container con dos llamados índices ordenados 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 employees.

En cualquier caso, cada employee se almacena sólo una vez en el recipiente de múltiples indexada, mientras que una combinación de map<string,employee> y map<int,employee> almacenaría cada empleado dos veces.

Se puede muy bien ser que no es de hecho un (dinámico) matriz dentro de algunos contenedores multi-indexadas, pero hay hay garantía que esto es cierto:

  

[índices de acceso aleatorio] no proporcionan la contigüidad de memoria,   una propiedad de std::vectors por el cual   elementos se almacenan adyacente a uno   otro en un solo bloque de memoria.

También, Boost.Bimap se basa en Boost.MultiIndex y el primero permite para diferentes representaciones de su 'estructura principal'.

Answer 3

En realidad no creo que es.

Sobre la base de lo que se encuentra en detail/node_type.hpp. Me parece que como un std::map el nodo contendrá tanto el valor y el índice. Excepto que en este caso los diversos índices difieren entre sí y por lo tanto el nodo entrelazado en realidad serían diferentes dependiendo del índice que está siguiendo.

No estoy seguro acerca de esto, sin embargo, las cabeceras de Boost 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 caché localidad

Le agradecería una respuesta definitiva, sin embargo, si alguien sabe acerca de la sangre derramada.