modalità di implementazione spinta multi_index
-
25-09-2019 - |
Domanda
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?
Soluzione
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) [...]
Altri suggerimenti
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 employee
s.
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::vector
s 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'.
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.