comment multi_index boost est mis en œuvre
https://stackoverflow.com/questions/4206349
-
25-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai quelques difficultés à comprendre comment Boost.MultiIndex est mis en œuvre. Disons que je suit:
typedef multi_index_container<
employee,
indexed_by<
ordered_unique<member<employee, std::string, &employee::name> >,
ordered_unique<member<employee, int, &employee::age> >
>
> employee_set;
Je suppose que j'ai un tableau, Employee[], qui stocke en fait les objets employee, et deux cartes
map<std::string, employee*>
map<int, employee*>
avec le nom et l'âge en tant que clés. Chaque carte a une valeur employee* qui pointe vers l'objet stocké dans le réseau. Est-ce ok?
La solution
Une brève explication sur la structure sous-jacente est donnée ici , cité ci-dessous:
La mise en œuvre est basée sur des noeuds reliés entre eux avec des pointeurs, tout comme que votre mise en œuvre de std::set favori. Je vais élaborer un peu sur ce point: Un std::set est généralement mis en œuvre comme un rb-arbre où les nœuds ressemblent
struct node
{
// header
color c;
pointer parent,left,right;
// payload
value_type value;
};
Eh bien, un nœud de multi_index_container est essentiellement un « multi-nœuds » avec autant de têtes que les indices ainsi que la charge utile. Par exemple, un multi_index_container avec deux soi-disant indices ordonnés utilise un noeud interne qui ressemble à
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 réalité est plus complexe, ces noeuds sont générés par une etc. metaprogramming mais vous voyez l'idée) [...]
Autres conseils
Conceptuellement, oui.
D'après ce que je comprends de Boost.MultiIndex (je l'ai utilisé, mais pas vu la mise en œuvre), votre exemple avec deux indices de ordered_unique sera en effet créer deux conteneurs associatifs (comme std::map triés) qui stockent des pointeurs / références / indices en un ensemble commun de employees.
Dans tous les cas, chaque employee est stockée une seule fois dans le conteneur multi-indexé, alors qu'une combinaison de map<string,employee> et map<int,employee> stockerait chaque employé deux fois.
Il se peut très bien qu'il y a en effet un tableau (dynamique) à l'intérieur des conteneurs multi-indexés, mais il y a aucune garantie que cela est vrai:
[indices d'accès aléatoire] ne fournissent pas contiguïté mémoire, une propriété de
std::vectors par lequel les éléments sont stockés adjacente à une l'autre dans un seul bloc de mémoire.
