c++ - boost multi_index 是如何实现的

Question

我很难理解 Boost.MultiIndex 是如何实现的。假设我有以下内容:

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

我想我有一个数组，Employee[]，它实际上存储 employee 对象，以及两个 map

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

以姓名和年龄为键。每个映射都有 employee* 值，该值指向数组中存储的对象。这样可以吗？

Answer 1

给出了底层结构的简短解释here ，引述如下:

该实现基于与指针互连的节点，就像您最喜欢的 std::set 实现一样。我将对此进行详细说明:std::set 通常实现为节点看起来像的 rb-tree

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

嗯，multi_index_container 的节点基本上是一个“多节点”，其 header 与索引以及有效负载一样多。例如，具有两个所谓的有序索引的 multi_index_container 使用的内部节点看起来像

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

(现实更复杂，这些节点是通过一些元编程等生成的，但你明白了)[...]