how boost multi_index is implemented

Question

I have some difficulties understanding how Boost.MultiIndex is implemented. Lets say I have the following:

typedef multi_index_container<     employee,     indexed_by<             ordered_unique<member<employee, std::string, &employee::name> >,         ordered_unique<member<employee, int, &employee::age> >     >  > employee_set; 

I imagine that I have one array, Employee[], which actually stores the employee objects, and two maps

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

with name and age as keys. Each map has employee* value which points to the stored object in the array. Is this ok?

Answer 1

A short explanation on the underlying structure is given here, quoted below:

The implementation is based on nodes interlinked with pointers, just as say your favorite std::set implementation. I'll elaborate a bit on this: A std::set is usually implemented as an rb-tree where nodes look like

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

Well, a multi_index_container's node is basically a "multinode" with as many headers as indices as well as the payload. For instance, a multi_index_container with two so-called ordered indices uses an internal node that looks like

struct node {   // header index #0   color      c0;   pointer    parent0,left0,right0;   // header index #1   color      c1;   pointer    parent1,left1,right2;   // payload   value_type value; }; 

(The reality is more complicated, these nodes are generated through some metaprogramming etc. but you get the idea) [...]