提高:: multi_index组合键效率 [英] boost::multi_index composite keys efficiency

问题描述

很长一段时间的读者第一次海报！我用了boost :: multi_index容器的东西玩耍，并有相当深入的疑问，希望升压或C ++容器专家可能知道（在C我所知++容器是pretty基本）。作为参考，对复合键升压文件可以在这里找到：的boost::multi_index组合键。

Long time reader first time poster! I'm playing around with the boost::multi_index container stuff and have a rather in-depth question that hopefully a boost or C++ container expert might know (my knowledge in C++ containers is pretty basic). For reference, the boost documentation on composite keys can be found here: boost::multi_index composite keys.

在使用复合键，文档指出组合键，通过字典顺序排序，即排序是由第一个键，然后是第二个关键，如果第一个是平等的，等演出。这是否意味着结构存储，从而为特定的两部分组合键查找需要O（N = 1）时间，即是容器进行排序，这样有直接的指针，每个项目，或不升压容器检索该复合密钥的第一部分相匹配列表，然后需要执行匹配密钥的第二部分的项目搜索并因而是慢？

When using a composite key, the documentation states that "Composite keys are sorted by lexicographical order, i.e. sorting is performed by the first key, then the second key if the first one is equal, etc". Does this mean that the structure is stored such that a lookup for a specific 2-part composite key will take O(n=1) time, i.e. is the container sorted such that there is a pointer directly to each item, or does the boost container retrieve a list that matches the first part of the composite key and then need to perform a search for items matching the second part of the key and thus is slower?

例如，如果我是要保持使用两种不同的指标手动两个容器，并希望能找到匹配特定的两部分查询我可能会筛选符合查询的第一部分中的所有项目的第一个容器项目，然后筛选匹配查询的第二部分的项目的结果。所以这个手动的方法能有效地涉及两个搜索。是否有效提振做这做它通过使用组合键的某种方式对效率的提高？

For example, if I was to maintain two containers manually using two different indices and wanted to find items that matched a specific 2-part query I would probably filter the first container for all items matching the 1st part of the query, and then filter the result for items that match the 2nd part of the query. So this manual method would effectively involve two searches. Does boost effectively do this or does it improve on efficiency somehow via the use of composite keys?

希望我在这里介绍自己，但请提问，我会尽我所能澄清正是我的意思！

Hopefully I've explained myself here but please ask questions and I will try my best to clarify exactly what I mean!

推荐答案

查找涉及组合键你描述不通过任何两阶段的过程去。 composite_key 诱导的排序是正常的排序，它是对两个或两个以上的元素键而不是一个依赖的唯一特别的事情。

Lookups involving composite keys do not go through any two-stage process as you describe. composite_key-induced orderings are normal orderings, the only special thing about it being its dependence on two or more element keys rather than one.

也许一个例子来阐明。考虑这种使用 composite_key ：

Maybe an example will clarify. Consider this use of composite_key:

struct element
{
  int x,y,z;
};

typedef multi_index_container<
  element,
  indexed_by<
    ordered_unique<
      composite_key<
        element,
        member<element,int,&element::x>,
        member<element,int,&element::y>,
        member<element,int,&element::z>
      >
    >
  >
> multi_t;

得到的容器在某种意义上等同于这样的：

The resulting container is in a sense equivalent to this:

struct element_cmp
{
  bool operator()(const element& v1, const element& v2)const
  {
    if(v1.x<v2.x)return true;
    if(v2.x<v1.x)return false;
    if(v1.y<v2.y)return true;
    if(v2.y<v1.y)return false;
    return v1.z<v2.z;
  }
};

typedef std::set<element,element_cmp> set_t;

composite_key 自动生成相当于code，以在 element_cmp ::运算符（），另外还允许为查找关于刚刚的前n项，但底层的数据结构不就使用改变的情况下的std ::设置。

composite_key automatically generates equivalent code to that in element_cmp::operator(), and additionally allows for lookup on just the first n keys, but the underlying data structure does not change with respect to the case using std::set.

这篇关于提高:: multi_index组合键效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！