如何实现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<std::string, employee*>
map<int, employee*>

以姓名和年龄为键。每张地图有 employee* 值，指向数组中的存储对象。这样可以吗？

Answer 1

关于底层结构的简单解释如下 此处，下面引用。

它的实现是基于节点与指针的相互连接 就像你最喜欢的那个 "我 "一样。std::set 实施。我再详细说一下。A std::set 通常以rb树的形式实现，其中节点看起来像

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

嗯，一个 multi_index_container'的节点基本上是一个 "多节点"，有多少个头和指数以及有效载荷。例如，一个 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;
};

现实情况比较复杂，这些节点是通过一些元编程等方式生成的，但你懂的）[...]

Answer 2

概念上，是的。

根据我对Boost.MultiIndex的理解（我用过它，但没有看到它的实现），你的例子中有两个 ordered_unique 索引确实会创建两个排序的关联容器（如 std::map)，它们将指针参考指数存储到一组通用的 employees.

在任何情况下，每 employee 在多索引容器中只存储一次，而一个组合的 map<string,employee> 和 map<int,employee> 会将每个员工存储两次。

很有可能在一些多索引容器中确实存在一个（动态）数组，但在一些多索引容器中却存在一个 无保证 这是真的。

[随机访问索引]不提供内存连续，这是一个属性。std::vector的方式，将元素相邻地存储在一个存储器块中。

另外： Boost.Bimap是基于Boost.MultiIndex的。 而前者可以对其 "骨干 "结构进行不同的表述。

Answer 3

其实我认为并非如此。

根据位于 detail/node_type.hpp. 在我看来，就像一个 std::map 的节点将同时包含值和索引。只不过在这种情况下，各种索引是不同的，因此节点交错实际上会根据你所遵循的索引而有所不同。

不过我不确定这一点，Boost头肯定是很难解析的，不过如果你从内存的角度考虑，就会有意义了。

• 更少的分配： 更快的分配deallocation
• 更好的缓存位置

不过，如果有人知道这些血腥的事情，我希望得到一个明确的答案。