cómo se implementa impulso multi_index
-
25-09-2019 - |
Pregunta
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?
Solución
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) [...]
Otros consejos
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 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::vector
s 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'.
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.