如何实现boost multi_index

对其基本结构作了简要说明 here ,引用如下:

该实现基于与指针链接的节点,正如您最喜欢的那样 std::set 实施。我将详细说明一下:a 标准::集 通常实现为一个rb树,其中节点看起来像

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

嗯,A 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;
};

(实际情况更复杂,这些节点是通过一些元编程等生成的,但您可以理解这个想法)[…]

从概念上讲,是的。

根据我对Boost.MultiIndex的理解(我使用过,但没有看到实现),您的示例有两个 ordered_unique 索引确实会创建两个排序的关联容器(如 std::map )将指针/引用/索引存储到 employee s。

无论如何 雇员 只在多索引容器中存储一次,而 map<string,employee> 和 map<int,employee> 每一个员工都会储存两次。

很可能在一些多索引容器中确实有一个(动态)数组,但是 no guarantee 这是真的:

[随机访问索引]不提供内存连续性, 财产 std::vector 通过它 元素存储在 一块内存中的另一个。

也, Boost.Bimap is based on Boost.MultiIndex 前者允许其“主干”结构的不同表示。

其实我不这么认为。

基于 detail/node_type.hpp . 在我看来 std::map 节点将包含值和索引。除此之外,在这种情况下,不同的索引彼此不同,因此节点交错实际上会根据您所遵循的索引而有所不同。

不过,我不确定这一点,Boost头文件确实很难解析,不过,如果从内存的角度考虑,这是有意义的:

• 更少的分配:更快的分配/释放
• 更好的缓存位置

不过,如果有人知道戈尔的事,我希望能有一个明确的答案。