wie boost multi_index implementiert
https://stackoverflow.com/questions/4206349
-
25-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
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 employees.
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::vectors von denen Elemente sind benachbart zu einem gespeicherten ein anderer in einem einzigen Speicherblock.
