在 Boost 多索引容器中搜索位域数据

Question

我正在寻找从多索引容器中检索基于位域的对象的最佳解决方案。为简单起见，数据为：

enum Bit
{
    b0 = 1,
    b1 = 2,
    b2 = 4
};

struct Item
{
    int field; // contains Bit values
    int info;
};

据我所知有两种可能：

在 equal_range 调用中使用自定义谓词（此示例不起作用，因为我不知道如何定义谓词）：

struct MyTag;

using boost::multi_index_container;
using namespace boost::multi_index;

typedef composite_key<Item,   
    member<Item, int, &Item::field>,
    member<Item, int, &Item::info> > CompositeKey;
typedef hashed_non_unique< tag<MyTag>, CompositeKey> Index1;
typedef boost::multi_index_container<Item, indexed_by<Index1> > Container;

struct Predicate: public Index1::pred_type
{
    /// what to put here?
};

void f()
{
    Item item1 = { int( b0 | b1), 123};
    Item item2 = { int( b1 | b2), 123};
    Item item3 = { int( b2), 123};

    Container c;
    c.insert( item1);
    c.insert( item2);
    c.insert( item3);

    auto result = c.get<MyTag>().equal_range( boost::make_tuple( int( b2), 123), Index1::hash_type(), Predicate());
    for( auto i = result.first; i != result.second; ++i)
    {
        std::cout << i->field << ' ';
        // expect item2 and item3
    }
}

为枚举中的每个位添加 Item 中的访问器和多索引容器中的索引：

struct Item
{
    int field;
    int info;

    bool isB0() const { return ( field & b0) != 0; }
    bool isB1() const { return ( field & b1) != 0; }
    bool isB2() const { return ( field & b2) != 0; }
};


struct MyTag1;
struct MyTag2;
struct MyTag3;

using boost::multi_index_container;
using namespace boost::multi_index;

typedef composite_key<Item,   
    const_mem_fun<Item, bool, &Item::isB0>,
    member<Item, int, &Item::info> > CompositeKeyB0;
typedef composite_key<Item,   
    const_mem_fun<Item, bool, &Item::isB1>,
    member<Item, int, &Item::info> > CompositeKeyB1;
typedef composite_key<Item,   
    const_mem_fun<Item, bool, &Item::isB2>,
    member<Item, int, &Item::info> > CompositeKeyB2;
typedef hashed_non_unique< tag<MyTag1>, CompositeKeyB0> Index1;
typedef hashed_non_unique< tag<MyTag2>, CompositeKeyB1> Index2;
typedef hashed_non_unique< tag<MyTag3>, CompositeKeyB2> Index3;
typedef boost::multi_index_container<Item, indexed_by<Index1, Index2, Index3> > Container;

void f()
{
    Item item1 = { int( b0 | b1), 123};
    Item item2 = { int( b1 | b2), 123};
    Item item3 = { int( b2), 123};

    Container c;
    c.insert( item1);
    c.insert( item2);
    c.insert( item3);

    auto result = c.get<MyTag2>().equal_range( boost::make_tuple( true, 123));
    for( auto i = result.first; i != result.second; ++i)
    {
        std::cout << i->field << ' ';
        // expect item2 and item3
    }
}

Answer 1

我认为思考这个问题的方式是：

"how would I create these indexes without boost?"

会是这样的：

#include <unordered_map>
#include <list>
#include <functional>
#include <iostream>

enum Bit
{
    b0 = 1,
    b1 = 2,
    b2 = 4
};

struct Item
{
    int field;
    int info;

    bool isB0() const { return ( field & b0) != 0; }
    bool isB1() const { return ( field & b1) != 0; }
    bool isB2() const { return ( field & b2) != 0; }
};

template<int bit>
struct ItemHash
{
  bool operator()(const Item& item) const {
    auto accum = std::hash<int>()(item.info);
    if ((item.field & bit) == bit)
      accum += 1234567;
    return accum;
  }
};

template<int bit>
  struct ItemEqual
  {
    bool operator()(const Item& l, const Item& r) const 
    {
      auto lt = std::make_tuple((l.field & bit) == bit, l.info);
      auto rt = std::make_tuple((r.field & bit) == bit, r.info);
      return lt == rt;
    }
  };

struct Items
{
  Item& insert(Item item)
  {
    // store object
    auto i = _storage.insert(_storage.end(), item);

    // update indeces
    _by_b0.emplace(item, *i);
    _by_b1.emplace(item, *i);
    _by_b2.emplace(item, *i);

    _by_b2_and_b1.emplace(item, *i);

    return *i;
  };



  // object storage
  std::list<Item> _storage;

  // indexes we want to keep
  std::unordered_map<Item, std::reference_wrapper<Item>, ItemHash<b0>, ItemEqual<b0> > _by_b0;
  std::unordered_map<Item, std::reference_wrapper<Item>, ItemHash<b1>, ItemEqual<b1> > _by_b1;
  std::unordered_map<Item, std::reference_wrapper<Item>, ItemHash<b2>, ItemEqual<b2> > _by_b2;

  // multiple bits?
  std::unordered_map<Item, std::reference_wrapper<Item>, ItemHash<b2|b1>, ItemEqual<b2|b1> > _by_b2_and_b1;
};


int main()
{
    Item item1 = { int( b0 | b1), 123};
    Item item2 = { int( b1 | b2), 123};
    Item item3 = { int( b2), 123};

    Items c;
    c.insert( item1);
    c.insert( item2);
    c.insert( item3);

    auto result = c._by_b2.equal_range( Item { b2, 123 });
    for( auto i = result.first; i != result.second; ++i)
    {
        std::cout << i->second.get().field << ' ' << i->second.get().info << std::endl;
        // expect item2 and item3
    }
}

看到这里，我们开始意识到 field 中的这些位实际上是属性。我们真的要为每个属性组合创建索引吗？将我们的 Item 简单地存储在 vector 中并在 for 循环中使用谓词真的会更有效且更容易维护吗？

例如：

#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>

enum Bit
{
    b0 = 1,
    b1 = 2,
    b2 = 4
};

struct Item
{
    int field;
    int info;

    bool isB0() const { return ( field & b0) != 0; }
    bool isB1() const { return ( field & b1) != 0; }
    bool isB2() const { return ( field & b2) != 0; }
};

struct matches_bits_and_info {

    constexpr matches_bits_and_info(int bits, int info) : _bits(bits), _info(info) {}

    bool operator()(const Item& item) const {
        return std::make_tuple((item.field & _bits) , item.info)
        == std::tie(_bits, _info);
    }
    int _bits, _info;
};

int main()
{
    std::vector<Item> c;
    c.push_back({b0 | b1, 123});
    c.push_back({b0 | b2, 123});
    c.push_back({b2, 123});

    for (auto& item : c) {
        if (matches_bits_and_info(b2, 123)(item)) {
            std::cout << item.field << ' ' << item.info << std::endl;
        }
    }

}

预期结果：

5 123
4 123

要使其效率低于多索引容器解决方案（或手动解决方案），数据集需要大量.

Answer 2

选项 2 非常好，实际上您的解决方案按预期工作。至于选项 1，无论您的 Predicate class 多么聪明，您都无法使其工作，解释如下：非唯一哈希索引 groups （意味着它将）元素根据一些等价标准，在您的情况下， field 和 info 数据成员具有相同的值。让我们暂时忘记 info，假装所有元素都具有相同的值，并专注于 field：六个等价 classes（元素簇）是

0、1、2、3、4、5、6、7

这只是field的三个位0、1、2可以组合取的不同值（这些簇不一定按上面显示的顺序出现）。现在，如果您尝试执行一个 equal_range 检索所有带有 b2 的元素，将您想要的操作设置为 return 粗体中显示的那些簇中的元素下面的字母:

0, 1, 2, 3, 4, 5, 6, 7

一般来说没有排列在一起，所以没办法equal_range可以return 几个遍历 这些且仅这些 个元素的迭代器。

Answer 3

考虑到field成员的可能取值其实没有那么多（8个），可以考虑1的替代方案，就是一个一个的去取具有给定位集的相应 field 值，请参阅以下示例中的 for_each_value：

Live Coliru Demo

#include <algorithm>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>

enum Bit
{
  b0 = 1,
  b1 = 2,
  b2 = 4
};

struct Item
{
  int field;
  int info;
};

struct MyTag;

using boost::multi_index_container;
using namespace boost::multi_index;

typedef composite_key<
  Item,   
  member<Item, int, &Item::field>,
  member<Item, int, &Item::info> > CompositeKey;
typedef hashed_non_unique< tag<MyTag>, CompositeKey> Index1;
typedef boost::multi_index_container<Item, indexed_by<Index1> > Container;

template<typename F>
F for_each_value(const Container& c,Bit b,int info,F f)
{
  for(auto field:{0,1,2,3,4,5,6,7}){
    if(field&b){
      auto r=c.equal_range(std::make_tuple(field,info));
      std::for_each(r.first,r.second,f);
    }
  }
  return f;
}

#include <iostream>

int main()
{
  Item item1 = { int( b0 | b1), 123};
  Item item2 = { int( b1 | b2), 123};
  Item item3 = { int( b2), 123};

  Container c;
  c.insert( item1);
  c.insert( item2);
  c.insert( item3);

  for_each_value(c,b2,123,[](const Item& i){
    std::cout << i.field << ' ';
  });
}

输出

4 6

在 Boost 多索引容器中搜索位域数据

Searching bit-field data in Boost multi index container

c++

boost

bit-fields

boost-multi-index