wie boost multi_index implementiert wird

Question

Ich habe einige Schwierigkeiten zu verstehen, wie Boost.MultiIndex implementiert ist. Sagen wir, ich habe das folgende:

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 Feld habe, Employee[] die eigentlich die employee Objekte und zwei Karten

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

mit Name und Alter als Schlüssel. Jede Karte hat employee* Wert, der auf das gespeicherte Objekt im Array zeigt. Ist das in Ordnung?

Answer 1

Eine kurze Erläuterung der zugrunde liegenden Struktur wird gegeben aquí , zitiert nachstehend:

Die Implementierung basiert auf Knoten, die mit Zeigern verknüpft sind, genau wie Ihre Lieblings std::set Umsetzung. Ich werde dies ein wenig näher erläutern: A std::set wird normalerweise als rb-Baum implementiert, wobei die Knoten wie folgt aussehen

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

Nun, ein multi_index_container Der Knoten ist im Grunde ein "Multiknoten" mit so vielen Kopfzeilen wie Indizes sowie der Nutzlast. Zum Beispiel kann ein multi_index_container mit zwei so genannten geordneten Indizes verwendet einen internen Knoten, der wie folgt aussieht

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, diese Knoten werden durch Metaprogrammierung usw. generiert, aber Sie verstehen die Idee) [...]

Answer 2

Konzeptionell, ja.

Nach dem, was ich von Boost.MultiIndex verstehe (ich habe es verwendet, aber nicht die Implementierung gesehen), ist Ihr Beispiel mit zwei ordered_unique Indizes werden in der Tat zwei sortierte assoziative Container erstellt (wie std::map ), die Zeiger/Referenzen/Indizes in einem gemeinsamen Satz von employee s.

In jedem Fall ist jeder employee wird nur einmal in dem mehrfach indizierten Container gespeichert, während eine Kombination von map<string,employee> y map<int,employee> würde jeden Mitarbeiter zweimal speichern.

Es kann durchaus sein, dass sich in einigen mehrfach indizierten Containern tatsächlich ein (dynamisches) Array befindet, aber es gibt keine Garantie dass dies der Fall ist:

[Random-Access-Indizes] bieten keine Speicherkontiguität, eine Eigenschaft von std::vector s Elemente nebeneinander gespeichert werden nebeneinander in einem einzigen Speicherblock gespeichert werden.

Auch, Boost.Bimap basiert auf Boost.MultiIndex und ersteres erlaubt verschiedene Darstellungen seiner "Backbone"-Struktur.

Answer 3

Ich glaube nicht, dass es so ist.

Ausgehend von dem, was sich in detail/node_type.hpp . Es scheint mir, dass wie eine std::map enthält der Knoten sowohl den Wert als auch den Index. Allerdings unterscheiden sich in diesem Fall die verschiedenen Indizes voneinander, so dass die Knotenverschachtelung je nach dem Index, dem Sie folgen, unterschiedlich ausfallen würde.

Ich bin mir da nicht sicher, Boost-Header sind definitiv schwer zu analysieren, aber es würde Sinn machen, wenn man an den Speicher denkt:

• weniger Zuweisungen: schnellere Zuweisung/Deallokation
• bessere Cache-Lokalität

Ich wäre jedoch dankbar für eine endgültige Antwort, wenn jemand etwas über die Blutspuren weiß.