21

我很难理解 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*指向数组中存储对象的值。这个可以吗？

4

3 回答 3

33

这里给出了关于底层结构的简短解释，引用如下：

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

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

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

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

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

于 2010-11-17T19:32:12.830 回答
4

从概念上讲，是的。

根据我对 Boost.MultiIndex 的理解（我使用过它，但没有看到实现），您的带有两个ordered_unique索引的示例确实会创建两个排序的关联容器（如std::map），它们将指针/引用/索引存储到一组公共的employees .

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

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

[随机访问索引] 不提供内存连续性，这是std::vectors 的一种属性，通过该属性，元素彼此相邻地存储在单个内存块中。

此外，Boost.Bimap 基于 Boost.MultiIndex，前者允许其“主干”结构的不同表示。

于 2010-11-17T16:09:35.540 回答
2

其实我不这么认为。

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

不过，我不确定这一点，Boost 标头肯定很难解析，但是如果您从内存的角度考虑，这将是有道理的：

  • 更少的分配：更快的分配/释放
  • 更好的缓存局部性

不过，如果有人知道血腥，我将不胜感激。

于 2010-11-17T16:39:24.540 回答