Boost具有复合键，自定义比较器和部分索引搜索的multi_index容器 [英] Boost multi_index container with composite key, custom comparer and partial index search

问题描述

我有这样的类（简化示例）：

I have a class like this (simplified example):

class A {
  public:
    typedef boost::shared_ptr<A> Ptr;
    const std::string& getID() const;
    const std::string& getLabel() const;
    bool getFlag() const;
    float getValue() const;
  private:
  ...
};

我需要一个容器，由（id，标签），以及（label，flag，value）的唯一组合。我还需要它按照第二个索引按标签先排序，后跟标志，如果标志为真，则减少值，如果标志为假，则增加值。所以在创建键提取器之后，我正在做这样的事情：

I need a container that is indexed by a unique combination of (id, label) and also a unique combination of (label, flag, value). I also need it to be sorted by the second index by label first followed by flag followed by decreasing values if flag is true and increasing values if flag is false. So after creating key extractors I'm doing something like this:

typedef boost::multi_index::composite_key<
  Ptr, extractor_id, extractor_label
> id_label_key;
typedef boost::multi_index::composite_key<
  Ptr, extractor_label, extractor_flag, extractor_value
> label_flag_value_key;
...
typedef boost::multi_index_container<Ptr,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_unique<
      boost::multi_index::tag<by_id_label
      id_label_key
    >,
    boost::multi_index::ordered_unique<
      boost::multi_index::tag<by_label_flag_value>,
      label_flag_value_key,
      Compare
    >,
  >
> Items;
typedef Items::index<by_label_flag_value>::type Items_by_label_flag_value;

其中Compare定义为：

where Compare is defined as:

struct Compare {
  bool operator() (const boost::multi_index::composite_key_result<label_flag_value_key>& k, const boost::tuple<float,bool>& q) const {
    return compare(k.value->getLabel(), k.value->getFlag(), k.value->getValue(),
      q.get<0>(), q.get<1>(), q.get<2>()
  }
  bool operator() (const boost::tuple<float,bool>& q, const boost::multi_index::composite_key_result<label_flag_value_key>& k) const {
    return compare(q.get<0>(), q.get<1>(), q.get<2>(), 
      k.value->getLabel(), k.value->getFlag(), k.value->getValue(),
  }
  bool operator() (const boost::multi_index::composite_key_result<label_flag_value_key>& k1, const boost::multi_index::composite_key_result<label_flag_value_key>& k2) const {
    return compare(k1.value->getLabel(), k1.value->getFlag(), k1.value->getValue(),
      k2.value->getLabel(), k2.value->getFlag(), k2.value->getValue())
  }
  bool compare(const std::string& l1, bool f1, float v1, const std::string& l2, bool f2, float v2) const {
    if (l1 != l2) return l1 < l2;
    if (f1 != f2) return f1;
    return f1 ? (v1 > v2) : (v1 < v2);
  }
};

现在，我可以执行这样的查询：

Now, I can perform queries like this:

Items_by_label_flag_value::const_iterator it = items_by_label_flag_value.find(boost::make_tuple("A", true, 0.1));

但是，如果我尝试执行部分查询 - 比如，检索具有相同标签的所有项目 - 我的代码不会编译：

However, if I try to perform a partial query - say, retrieve all items that have the same label - my code won't compile:

std::pair<Items_by_label_flag_value::const_iterator, Items_by_label_flag_value::const_iterator> range = items_by_label_flag_value.equal_range(boost::make_tuple("A"));

我知道为什么它不编译：在比较器中我明确使用。 get< 0>（）， .get< 1>（）和 .get& code>但部分搜索元组没有< 1> 和< 2> 元素。我不知道是如何创建正确的比较器。如果我试图添加两个更多的函数，它只需要一个元素的元组，然后编译器抱怨在 operator（）调用中的歧义。

I know why it does not compile: in the comparer I explicitly use .get<0>(), .get<1>() and .get<2>() but partial search tuple does not have <1> and <2> elements. What I do not know is how to create the correct comparer. If I try to add two more functions to it that takes tuples of one element only then the compiler complains of ambiguity in operator() call.

我也理解， composite_key_result 应该是一个不透明的对象，我不应该使用它的内部。

I also understand that composite_key_result is supposed to be an opaque object and I should not be using its insides.

所以我的问题是如何创建所需的索引和正确的比较器？

So my question is how to create the required index and the correct comparer?

推荐答案

解决方案，您不需要为您的第二个索引使用复合键，因为您的比较提取器基本上试图替换由 composite_key / composite_key_compare 。以下已经（轻松）测试工作：

As for your original solution, you need not use composite keys for your second index as your Compare extractor is basically trying to replace the machinery automatically generated by composite_key/composite_key_compare. The following has been (lightly) tested to work:

struct LBFCompare
{
  bool operator() (const A& x, const A& y) const {
    return compare(
      x.getLabel(), x.getFlag(), x.getValue(),
      y.getLabel(), y.getFlag(), y.getValue());
  }
  bool operator() (const std::string& x, const A& y) const{
    return compare(x,y.getLabel());
  }
  bool operator() (const A& x, const std::string& y) const{
    return compare(x.getLabel(),y);
  }
  template<typename T0>
  bool operator() (const boost::tuple<T0>& x, const A& y) const{
    return compare(x.get<0>(),y.getLabel());
  }
  template<typename T0>
  bool operator() (const A& x, const boost::tuple<T0>& y) const{
    return compare(x.getLabel(),y.get<0>());
  }
  template<typename T0,typename T1>
  bool operator() (const boost::tuple<T0,T1>& x, const A& y) const{
    return compare(x.get<0>(),x.get<1>(),y.getLabel(),y.getFlag());
  }
  template<typename T0,typename T1>
  bool operator() (const A& x, const boost::tuple<T0,T1>& y) const{
    return compare(x.getLabel(),x.getFlag(),y.get<0>(),y.get<1>());
  }
  template<typename T0,typename T1,typename T2>
  bool operator() (const boost::tuple<T0,T1,T2>& x, const A& y) const{
    return compare(x.get<0>(),x.get<1>(),x.get<2>(),y.getLabel(),y.getFlag(),y.getValue());
  }
  template<typename T0,typename T1,typename T2>
  bool operator() (const A& x, const boost::tuple<T0,T1,T2>& y) const{
    return compare(x.getLabel(),x.getFlag(),x.getValue(),y.get<0>(),y.get<1>(),y.get<2>());
  }
  bool compare(const std::string& l1, const std::string& l2) const {
    return l1 < l2;
  }
  bool compare(const std::string& l1, bool f1, const std::string& l2, bool f2) const {
    if (l1 != l2) return l1 < l2;
    return f1 < f2;
  }
  bool compare(const std::string& l1, bool f1, float v1, const std::string& l2, bool f2, float v2) const {
    if (l1 != l2) return l1 < l2;
    if (f1 != f2) return f1;
    return f1 ? (v1 > v2) : (v1 < v2);
  }
};

struct by_id_label{};
struct by_label_flag_value{};

typedef boost::multi_index_container<
  Ptr,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_unique<
      boost::multi_index::tag<by_id_label>,
      id_label_key
    >,
    boost::multi_index::ordered_unique<
      boost::multi_index::tag<by_label_flag_value>,
      boost::multi_index::identity<A>,
      LBFCompare
    >
  >
> Items;
typedef Items::index<by_label_flag_value>::type Items_by_label_flag_value;

int main()
{
  Items c;
  c.insert(Ptr(new A("id","label",true,1.0)));
  Items_by_label_flag_value& i=c.get<by_label_flag_value>();
  i.find("id");
  i.find(boost::make_tuple("id"));
  i.find(boost::make_tuple("id",true));
  i.find(boost::make_tuple("id",true,1.0));
}

你提到的歧义问题是由于你可能看通过传递 const char * 而不是完全形成的元组 std :: string 是隐式转换，看似1，2和3大小的元组是同样好的候选者（元组IMHO的一个实现问题。）解决方案是模板化 LBFCompare :: operator（）用元组。

The ambiguity problems you mention are due to the fact that you're probably looking up by passing tuples with const char*s rather than fully-formed std::strings: in this situation there are implicit conversions and seemingly 1-, 2- and 3-sized tuples are equally good candidates (an implementation problem with tuples IMHO.) The solution is to templatize those LBFCompare::operator()s that take tuples.

这篇关于Boost具有复合键，自定义比较器和部分索引搜索的multi_index容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！