modalità di implementazione spinta multi_index

Question

Ho qualche difficoltà a capire come Boost.MultiIndex è implementato. 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 oggetti employee, e due mappe

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

con il nome e l'età come chiavi. Ogni mappa ha valore employee* che indica l'oggetto memorizzato nella matrice. È questo ok?

Answer 1

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

L'applicazione si basa su nodi interconnessi con i puntatori, proprio come dire che l'implementazione std::set preferito. 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;
};

Bene, il nodo di un multi_index_container è fondamentalmente un "più nodi" con il maggior numero di intestazioni come indici, così come il carico utile. Ad esempio, un multi_index_container con due cosiddetti indici ordinati 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 indici ordered_unique sarà davvero creare due ordinato contenitori associativi (come std::map) che immagazzinano puntatori / riferimenti / indici in un insieme comune di employees.

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

Può ben essere che esiste effettivamente un (dinamica) matrice all'interno alcuni contenitori multi-indicizzati, ma v'è nessuna garanzia che questo è vero:

  

[indici accesso casuale] non forniscono la memoria contiguità,   una proprietà di std::vectors da cui   gli elementi sono memorizzati adiacente ad una   un altro in un unico blocco di memoria.

Inoltre, Boost.Bimap si basa su Boost.MultiIndex e l'ex consente per le diverse rappresentazioni della sua 'struttura portante'.

Answer 3

In realtà non credo che 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 e l'indice. Solo che in questo caso i vari indici differiscono l'uno dall'altro e quindi il nodo di interleaving sarebbe in realtà variare in base all'indice che stai seguendo.

Non sono sicuro di questo, però, le intestazioni Boost sono sicuramente difficili da analizzare, ma avrebbe senso se si pensa in termini di memoria:

• meno allocazioni: più veloce di allocazione / deallocazione
• migliore della cache località

Gradirei una risposta definitiva, però, se qualcuno conosce il gore.