wie boost multi_index implementiert
-
25-09-2019 - |
Frage
ich einige Schwierigkeiten zu verstehen, wie Boost.Multiindex umgesetzt wird. Sagen wir ich folgendes haben:
typedef multi_index_container<
employee,
indexed_by<
ordered_unique<member<employee, std::string, &employee::name> >,
ordered_unique<member<employee, int, &employee::age> >
>
> employee_set;
Ich stelle mir vor, dass ich ein Array haben, Employee[]
, die die employee
Objekte tatsächlich speichert, und zwei Karten
map<std::string, employee*>
map<int, employee*>
mit Namen und Alter als Schlüssel. Jede Karte hat employee*
Wert, der in dem Array zu dem gespeicherten Objekt zeigt. Ist das ok?
Lösung
Eine kurze Erklärung über die darunter liegende Struktur ist hier , zitiert unter:
Die Implementierung basiert auf Knoten mit Zeigern miteinander verknüpft, wie sagen Sie Ihre Lieblings std::set
Implementierung. Ich werde ein wenig näher auf diesem: Ein std::set
in der Regel als rb-Baum implementiert ist, wo Knoten aussehen
struct node
{
// header
color c;
pointer parent,left,right;
// payload
value_type value;
};
Nun, Knoten A multi_index_container
der ist im Grunde ein „Mehrfachknoten“ mit so vielen Header als Indizes sowie die Nutzlast. Zum Beispiel kann ein multi_index_container
mit zwei sogenannten geordneten Indizes verwendet einen internen Knoten, der aussieht wie
struct node
{
// header index #0
color c0;
pointer parent0,left0,right0;
// header index #1
color c1;
pointer parent1,left1,right2;
// payload
value_type value;
};
(Die Realität ist komplizierter, werden diese Knoten erzeugt durch einige metaprogramming etc., aber Sie erhalten die Idee) [...]
Andere Tipps
Konzeptionell, ja.
Von dem, was ich verstehe, von Boost.Multiindex (ich habe es verwendet, aber nicht die Umsetzung zu sehen ist), Ihr Beispiel mit zwei ordered_unique
Indizes wird in der Tat schafft zwei assoziative Container (wie std::map
), die Speicher-Zeiger / Referenzen / Indizes sortierte in ein gemeinsamer Satz von employee
s.
Auf jedem Fall wird jeder employee
nur einmal in den Multi-indizierte Behältern gespeichert, während eine Kombination von map<string,employee>
und map<int,employee>
würde zweimal jeden Mitarbeiter speichern.
Es kann sehr gut sein, dass es tatsächlich ein (dynamischer) Array innerhalb einiger Multi-indizierte Container, aber es ist keine Garantie dass dies wahr ist:
[Random Access Indizes] bieten keine Speicher Kontiguität, eine Eigenschaft von
std::vector
s von denen Elemente sind benachbart zu einem gespeicherten ein anderer in einem einzigen Speicherblock.