Использование 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. То, что я получаю, это сложенные индексы. Но я ищу все ценности (ints) интервала, содержащего "щуп". (Пересечение?)
2. Я мог бы достичь этого с std::set<int> как значение, но в документации указано, что это оказывает огромное влияние на производительность. Похоже, что split_interval_map содержит эту информацию, но я не знаю, как ее получить.
3. Мне нужен только очень эффективный поиск, как в этом примере. Мне больше не нужны пересекающиеся интервалы. Буст ICL слишком тяжел для этого?

Answer 1

1. То, что я получаю, это сложенные индексы. Но я ищу все значения (целые) интервала, содержащего "зонд". (Пересечение?)

Вы получаете все значения (значения в совместной области), используя выбранный вами комбинатор. Для арифметического типа это подразумевает суммирование.

Если ваш совместный домен является индексом, очевидно, что суммирование не имеет смысла для объединителя, и вам следует выбрать что-то другое.

Я мог бы достичь этого с std::set<int> как значение, но в документации указано, что это оказывает огромное влияние на производительность.

Как всегда, правильно идет перед выступлением. Если это то, что вам нужно, это то, что вам нужно.

Похоже, что split_interval_map содержит эту информацию, но я не знаю, как ее получить.

Не с выбранным совместным доменом: объединитель теряет исходную информацию, если интервалы перекрываются (и вы используете add не set).

Мне нужен только очень эффективный поиск, как в этом примере. Мне больше не нужны пересекающиеся интервалы. Буст ICL слишком тяжел для этого?

Вы могли бы использовать equal_range вместо lower_bound / upper_bound:

Жить на Колиру

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. Вы можете сделать пересечение с набором зондов сразу:

   Жить на Колиру

   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. Чтобы (возможно?) Немного оптимизировать это:

   Жить на Колиру

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

3. Если наборы будут маленькими, рассмотрите возможность указания small_vector для типа последовательности этого flat_set:

   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<>