come viene implementato il multi_index

Question

Ho alcune difficoltà a capire come è implementato Boost.MultiIndex. Diciamo che ho il seguente:

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

immagino che ho una matrice, Employee[], che memorizza in realtà gli employee oggetti, e due mappe

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

con il nome e l'età come chiavi. Ogni mappa ha il valore employee* che punta all'oggetto memorizzato nell'array. Va bene?

Answer 1

una breve spiegazione sulla struttura sottostante è dato here, citato qui di seguito:

L'implementazione è basata su nodi interconnessi con i puntatori, proprio come dice il tuo std::set implementazione preferita.Io elaborare un po 'su questo: Un std::set di solito è implementato come un RB-albero in cui i nodi sembrano

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

Beh, un nodo multi_index_container s' è fondamentalmente un 'più nodi' con il maggior numero di intestazioni come indici come così come il carico utile. Per esempio, un multi_index_container con due cosiddetti indici ordinato utilizza un nodo interno che assomiglia

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 realtà è più complicata, questi nodi vengono generati attraverso alcuni metaprogrammazione ecc, ma si ottiene l'idea) [. ..]

Answer 2

Concettualmente, sì.

Da quello che ho capito di Boost.MultiIndex (ho usato, ma non si vede l'implementazione), il vostro esempio con due ordered_unique indici sarà davvero creare due contenitori associativi ordinate (come std::map) che memorizzano puntatori/riferimenti/indici in un set comune di employee s.

In ogni caso, ogni employee è memorizzato soltanto una volta nel contenitore multi-indicizzato, mentre una combinazione di map<string,employee> e map<int,employee> sarebbe memorizzare ogni impiegato due volte.

Può essere benissimo che esiste effettivamente un (dinamica) matrice all'interno alcuni contenitori multi-indicizzato, ma c'è no guarantee che questo è vero:

[indici Accesso Casuale] non forniscono memoria contiguità , una proprietà di std::vector s con cui gli elementi vengono memorizzati adiacenti a uno un altro in un singolo blocco di memoria.

Inoltre, Boost.Bimap is based on Boost.MultiIndex e il primo consente diverse rappresentazioni della sua struttura "backbone".

Answer 3

In realtà non penso che lo sia.

In base a ciò che si trova in detail/node_type.hpp. Mi sembra che come un std::map il nodo conterrà sia il valore che l'indice. Tranne che in questo caso i vari indici differiscono l'uno dall'altro e quindi l'interleaving dei nodi sarebbe effettivamente diverso a seconda dell'indice che stai seguendo.

io non sono sicuro di questo, però, Boost intestazioni sono sicuramente difficile da analizzare, ma avrebbe senso se si pensa in termini di memoria:

• meno allocazioni: più veloce di allocazione/deallocazione
• meglio cache locality

Gradirei una risposta definitiva però, se qualcuno sa del gore.