использование split_interval_map, эффективный поиск всех интервалов, пересекающих точку

Question

использование split_interval_map, эффективный поиск всех интервалов, пересекающих точку

#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;
}
}
}

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

1

boost boost-icl c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

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

Я мог бы достичь этого с 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});

Альтернативы, Идеи:

Вы можете сделать пересечение с набором зондов сразу:

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

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

Чтобы (возможно?) Немного оптимизировать это:

Жить на Колиру
```
using Map  = icl::split_interval_map<double, boost::container::flat_set<int> >;
```
Если наборы будут маленькими, рассмотрите возможность указания small_vector для типа последовательности этого flat_set:
```
icl::split_interval_map<double,
boost::container::flat_set<int, std::less<int>,
boost::container::small_vector<int, 4>
> >;
```
Все остальное просто еще работает: Жить на Колиру
Полностью Вне коробки: вы моделируете геометрические области? Как интервалы на временной шкале? Или просто отрезки на оси? В этом случае рассмотрим boost::geometry::index::rtree<>

0