c++ - split_interval_map 用法，高效查找所有区间与一个点相交

Question

#include <iostream>
#include <boost/icl/split_interval_map.hpp>

using namespace std;
using namespace boost::icl;

int main()
{
    split_interval_map<double, int> intervals;

    intervals.add(make_pair(interval<double>::closed(0.,1.),0));
    intervals.add(make_pair(interval<double>::closed(1.,2.),1));
    intervals.add(make_pair(interval<double>::closed(3.,4.),2));
    intervals.add(make_pair(interval<double>::closed(2.,4.),3));
    intervals.add(make_pair(interval<double>::closed(1.5,3.5),4));

    std::vector<double> probes = { 0.23, 1., 1.33 , 1.57, 3.49, 3.51 };

    for(auto probe : probes)
    {
        std::cout << std::endl<< "probe " << probe << std::endl;
        auto lower = intervals.lower_bound(interval<double>::closed(probe, probe));
        auto upper = intervals.upper_bound(interval<double>::closed(probe, probe));
        while(lower != upper)
        {
            std::cout << lower->second << " ";
            ++lower;
        }
    }
}

1. 我得到的是指数相加。但我正在寻找包含“探针”的区间的所有值(int s)。 (十字路口？)
2. 我可以用 std::set<int> 来实现作为值(value)，但在文档中指出，这对性能有巨大影响。 split_interval_map 似乎包含该信息，但我不知道如何检索它。
3. 我只需要像本例中那样的高效查找。我不再需要相交的间隔范围。 boost icl 对这个来说太重了吗？

Answer 1

1. What i get are the indices added up. But i'm looking for all the values (ints) of the interval containing 'probe'. (intersection?)

您可以使用您选择的组合器组合获得所有值(共同域值)。对于算术类型，这意味着求和。

如果你的共同域是一个索引，显然求和是没有意义的组合器，你应该选择别的东西。

I could achieve this with std::set<int> as value, but in the documentation it is stated, that this has a huge impact on performance.

一如既往，正确先于表现。如果这是您需要的，那就是您需要的。

Seems like split_interval_map contains that information but i don't know how to retrieve it it.

不适用于所选的共同域:如果间隔重叠(并且您使用 add，而不是 set)，组合器将丢失原始信息。

I need only a highly efficient lookup like in this example. I don't need the intersecting interval ranges anymore. Is boost icl too heavy for this?

你可以使用 equal_range而不是 lower_bound/upper_bound :

Live On Coliru

for (auto probe : { 0.23, 1., 1.33, 1.57, 3.49, 3.51 }) {
    std::cout << "\nprobe " << probe << ": ";

    for (auto& p : boost::make_iterator_range(m.equal_range(Ival::closed(probe, probe)))) {
        std::cout << p.second << " ";
    }
}

打印

probe 0.23: 
probe 1: 1 
probe 1.33: 1 
probe 1.57: 4 
probe 3.49: 4 
probe 3.51: 3 

观察:

m.add({Ival::closed(0., 1.), 0});
m.add({Ival::closed(1., 2.), 1});
m.add({Ival::closed(3., 4.), 2});

这些间隔巧妙地重叠。 [0, 1]和 [1, 2]有[1,1]共同点。你真的是说 left_open ？ ([0, 1) 和 [1, 2) 没有重叠)。

m.add({Ival::closed(2., 4.), 3});
m.add({Ival::closed(1.5, 3.5), 4});

如果您对这结合了重叠区间中已有的值这一事实感到惊讶，您是要替换它们吗？

m.set({Ival::closed(2., 4.), 3});
m.set({Ival::closed(1.5, 3.5), 4});

备选方案、想法:

1. 您可以一次与一组探针进行交集:

   Live On Coliru

   Set probes;
   probes.insert(0.23);
   probes.insert(1.);
   probes.insert(1.33);
   probes.insert(1.57);
   probes.insert(3.49);
   probes.insert(3.51);
   std::cout << std::endl << "all: " << (m & probes) << "\n";
   

   打印:

   all: {([1,1]->1)([1.33,1.33]->1)([1.57,1.57]->4)([3.49,3.49]->4)([3.51,3.51]->3)}
   

2. (也许？)稍微优化一下:

   Live On Coliru

   using Map  = icl::split_interval_map<double, boost::container::flat_set<int> >;
   

3. 如果集要变小，请考虑为该 flat_set 的序列类型指定 small_vector:

   icl::split_interval_map<double,
       boost::container::flat_set<int, std::less<int>, 
           boost::container::small_vector<int, 4>
       > >;
   

   其他一切仍然有效: Live On Coliru

4. 完全开箱即用:您正在为几何区域建模吗？像时间轴上的间隔？或者只是轴上的线段？在这种情况下，请考虑 boost::geometry::index::rtree<>