c++boostmulti-indexboost-multi-index

how boost multi_index is implemented


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?


Solution

  • 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) [...]