boost::multi_index复合键范围查询结果不符合预期求助

问题描述 #

尝试在boost::multi_index容器上执行复合范围查询，期望获取满足one∈[1,3]且two∈[1,2]的元素，但当前代码返回了不符合two条件的Obj{1,5,6}。示例代码如下：

// This is my object
struct Obj {
  int one;
  int two;
  int three;
};

typedef boost::multi_index_container<
  Obj,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_non_unique<
      boost::multi_index::composite_key<
        Obj,
        boost::multi_index::member<Obj, int, &Obj::one>,
        boost::multi_index::member<Obj, int, &Obj::two>
      >
    >
  >
> object_multi;

int main() {
    object_multi objects;

    // For example
    objects.insert({1, 1, 3});
    objects.insert({1, 5, 6});
    objects.insert({2, 2, 4});
  
    auto& index = objects.get<0>();
    // get elements where one = [1, 3] AND two [1, 2]
    auto lower = index.lower_bound(boost::make_tuple(1, 1));
    auto upper = index.lower_bound(boost::make_tuple(3, 2));

    for (auto it = lower; it != upper; ++it) 
        std::cout << it->one << ", " << it->two << ", " << it->three << std::endl;
    
  
  return 0;
}

问题原因 #

复合键的排序逻辑是先按第一个成员one排序，再按第二个成员two排序，字典序的范围查询无法直接实现“两个成员独立范围的逻辑与”。你当前的范围(1,1)到(3,2)会包含所有满足以下条件的元素：

• one < 3（无论two的值是多少），或者
• one == 3且two < 2

因此Obj{1,5,6}因为one=1 <3，被错误地包含在结果中。

解决方案 #

方案一：范围遍历后筛选 #

先获取one∈[1,3]的所有元素，再遍历筛选出two∈[1,2]的元素：

#include <limits> // 用于numeric_limits

int main() {
    object_multi objects;
    objects.insert({1, 1, 3});
    objects.insert({1, 5, 6});
    objects.insert({2, 2, 4});
  
    auto& index = objects.get<0>();
    // 构造one∈[1,3]的范围
    auto one_lower = index.lower_bound(boost::make_tuple(1, 0));
    auto one_upper = index.upper_bound(boost::make_tuple(3, std::numeric_limits<int>::max()));

    // 遍历并筛选符合two条件的元素
    for (auto it = one_lower; it != one_upper; ++it) {
        if (it->two >= 1 && it->two <= 2) {
            std::cout << it->one << ", " << it->two << ", " << it->three << std::endl;
        }
    }
  
    return 0;
}

方案二：使用过滤索引（Filtered Index） #

利用Boost.MultiIndex的filtered索引特性，直接定义符合条件的视图：

#include <boost/multi_index/filtered_index.hpp>

// 定义过滤谓词
struct QueryPredicate {
    bool operator()(const Obj& o) const {
        return o.one >= 1 && o.one <= 3 && o.two >= 1 && o.two <= 2;
    }
};

// 扩展multi_index容器定义，添加过滤索引
typedef boost::multi_index_container<
  Obj,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_non_unique<
      boost::multi_index::composite_key<
        Obj,
        boost::multi_index::member<Obj, int, &Obj::one>,
        boost::multi_index::member<Obj, int, &Obj::two>
      >
    >,
    // 添加过滤索引，绑定谓词
    boost::multi_index::filtered<
      boost::multi_index::tag<filtered_tag>,
      QueryPredicate
    >
  >
> object_multi;

int main() {
    object_multi objects;
    objects.insert({1, 1, 3});
    objects.insert({1, 5, 6});
    objects.insert({2, 2, 4});
  
    // 获取过滤索引视图，直接遍历符合条件的元素
    auto& filtered_index = objects.get<filtered_tag>();
    for (const auto& o : filtered_index) {
        std::cout << o.one << ", " << o.two << ", " << o.three << std::endl;
    }
  
    return 0;
}

方案三：分区间精确查询 #

针对每个one的取值，单独查询two∈[1,2]的范围，合并结果：

int main() {
    object_multi objects;
    objects.insert({1, 1, 3});
    objects.insert({1, 5, 6});
    objects.insert({2, 2, 4});
  
    auto& index = objects.get<0>();

    // 查询one=1，two∈[1,2]
    auto range1_start = index.lower_bound(boost::make_tuple(1, 1));
    auto range1_end = index.upper_bound(boost::make_tuple(1, 2));
    for (auto it = range1_start; it != range1_end; ++it) {
        std::cout << it->one << ", " << it->two << ", " << it->three << std::endl;
    }

    // 查询one=2，two∈[1,2]
    auto range2_start = index.lower_bound(boost::make_tuple(2, 1));
    auto range2_end = index.upper_bound(boost::make_tuple(2, 2));
    for (auto it = range2_start; it != range2_end; ++it) {
        std::cout << it->one << ", " << it->two << ", " << it->three << std::endl;
    }

    // 查询one=3，two∈[1,2]
    auto range3_start = index.lower_bound(boost::make_tuple(3, 1));
    auto range3_end = index.upper_bound(boost::make_tuple(3, 2));
    for (auto it = range3_start; it != range3_end; ++it) {
        std::cout << it->one << ", " << it->two << ", " << it->three << std::endl;
    }
  
    return 0;
}

内容的提问来源于stack exchange，提问作者Santiago