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

Answer 2

Conceptually, yes.

From what I understand of Boost.MultiIndex (I've used it, but not seen the implementation), your example with two ordered_unique indices will indeed create two sorted associative containers (like std::map) which store pointers/references/indices into a common set of employees.

In any case, every employee is stored only once in the multi-indexed container, whereas a combination of map<string,employee> and map<int,employee> would store every employee twice.

It may very well be that there is indeed a (dynamic) array inside some multi-indexed containers, but there is no guarantee that this is true:

[Random access indices] do not provide memory contiguity, a property of std::vectors by which elements are stored adjacent to one another in a single block of memory.

Also, Boost.Bimap is based on Boost.MultiIndex and the former allows for different representations of its "backbone" structure.

Answer 3

Actually I do not think it is.

Based on what is located in detail/node_type.hpp. It seems to me that like a std::map the node will contain both the value and the index. Except that in this case the various indices differ from one another and thus the node interleaving would actually differ depending on the index you're following.

I am not sure about this though, Boost headers are definitely hard to parse, however it would make sense if you think in term of memory:

• less allocations: faster allocation/deallocation
• better cache locality

I would appreciate a definitive answer though, if anyone knows about the gore.