c++ - boost multi_index_container 搜索落在由两个字段定义的间隔内的记录

Question

考虑下表:

id F1 F2    
0 0 10    
1 5 20    
2 20 30    
3 8 13    
4 13 17    
5 50 65    
6 15 26    
7 8 15

搜索包含 x 的记录，其中 F1 <= x && x <= F2。例如，搜索 x = 10 的记录将产生 ID 为 0,1,3,7 的记录。

如何使用 boost multi_index_container 在 C++ 中实现此功能以避免线性搜索？

Answer 1

您正在尝试相交间隔。为什么不使用适合域的表示？参见例如http://www.boost.org/doc/libs/1_60_0/libs/icl/doc/html/index.html

另一种方法似乎是使用几何查询。您可以将间隔表示为线段(或框，以获得更多维度)并查询它们。参见例如http://www.boost.org/doc/libs/1_60_0/libs/geometry/doc/html/geometry/reference/spatial_indexes.html

Live On Coliru

@cv_and_he:是的，这就是我所说的 rtree 方法:

#include <iostream>
#include <initializer_list>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>

#include <boost/range/algorithm.hpp>
#include <boost/range/adaptor/map.hpp>

struct record {
    int id;
    int f1, f2;
};

namespace bg  = boost::geometry;
namespace bgi = boost::geometry::index;
typedef bg::model::point<int, 2, bg::cs::cartesian> point;
typedef bg::model::segment<point> segment;

struct interval_finder
{
    typedef std::pair<segment, int> value;
    bgi::rtree<value, bgi::quadratic<16> > rt;

    interval_finder(std::initializer_list<record> l) {
        for(const record& rec : l)
            rt.insert(value { {point(rec.f1), point(rec.f2)}, rec.id});
    }

    auto find(int val) const {
        return boost::copy_range<std::vector<int> >(rt 
                | bgi::adaptors::queried(bgi::intersects(point(val))) 
                | boost::adaptors::map_values
            );
    }
};

int main() {
    interval_finder finder{
        { 0, 0,  10 },
        { 1, 5,  20 },
        { 2, 20, 30 },
        { 3, 8,  13 },
        { 4, 13, 17 },
        { 5, 50, 65 },
        { 6, 15, 26 },
        { 7, 8,  15 }
    };

    for (auto& p : finder.rt)
        std::cout << p.second << "\t" << bg::wkt(p.first) << "\n";

    for(auto range : finder.find(10))
        std::cout << range << " ";
}

出于演示目的，我打印了索引的元素，因此您可以理解它如何将区间表示为段:

0   LINESTRING(0 0,10 0)
1   LINESTRING(5 0,20 0)
2   LINESTRING(20 0,30 0)
3   LINESTRING(8 0,13 0)
4   LINESTRING(13 0,17 0)
5   LINESTRING(50 0,65 0)
6   LINESTRING(15 0,26 0)
7   LINESTRING(8 0,15 0)
0 1 3 7