c ++ 11 — контейнер для целочисленных интервалов, например RangeSet, для переполнения стека

Question

c ++ 11 — контейнер для целочисленных интервалов, например RangeSet, для переполнения стека

Я пытаюсь работать с диапазонами, как в диапазонах чисел. Я имею в виду целочисленные интервалы, в математике говорят. И я хочу хранить их набор. Я также хочу, чтобы этот набор естественным образом объединял (или объединял) диапазоны, которые я вставлял.

Давайте рассмотрим простой пример, я начну с пустого набора: {}

Я вставляю диапазон [0,5], теперь у меня есть {[0,5]}
Я вставляю диапазон [10,15], теперь у меня есть {[0,5], [10,15]}
Я вставляю диапазон [5,7], теперь у меня есть {[0,7], [10,15]}
Я вставляю диапазон [12,17], теперь у меня есть {[0,7], [10,17]}
Я вставляю диапазон [6,13], теперь у меня есть {[0,17]}

я узнал благодаря похожему вопросу что это существует в Java как библиотека Google Guava и называется RangeSet.

Я изначально думал об использовании std::set из std::pairs, которые будут отсортированы по нижней границе (таким образом, первый элемент каждой пары). Затем после каждой вставки мне пришлось бы вручную объединять любые перекрывающиеся наборы.

Поскольку это кажется распространенной проблемой, является ли хорошая реализация, которую я не смог найти из-за шума со всеми синонимами «range» в C ++? Или кто-нибудь хочет поделиться своим? Я хочу напечатать окончательные диапазоны, но бонусные баллы за общность, если у вас есть другие операции над множествами.

10

c++c++11 rangeset

Решение

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

Повышение имеет Интервальная контейнерная библиотека (ICL). Если вы хотите делать вычисления с интервалами, например, представляет грех (I) для интервала I, также есть Интервальная арифметическая библиотека в надстройке.

4

Оказывается, достаточно просто реализовать вашу первую идею.

Вставить:

использование lower_bound чтобы найти предыдущий диапазон, но сравнивая нижнюю границу нового диапазона с верхними границами старого диапазона.

Это работает только потому, что верхние границы имеют точно такой же порядок, что и нижние, поэтому мы сохраняем правильную последовательность
если вы перекрываете возвращаемый диапазон, объединяйте на месте (просто измените его), в противном случае вставьте
в то время как текущий диапазон (мутированный на месте или вновь вставленный) перекрывает последующий диапазон, объедините их

то есть вам нужно только объединиться в одном направлении.

Обратите внимание, что это требует необычного сравнения, которое не является строгим слабым порядком (если диапазон A целиком содержится в диапазоне B, вы, вероятно, получите A < B < A), так что я не уверен, что положить его в std::set будет работать — просто поддерживая отсортированный list или же vector должно быть достаточно легко, хотя

1

Вот класс под лицензией GPL-v2, который я написал давно и который делает интервалы. Это на самом деле класс 2D-региона. Он также поддерживает заливку.

Стиль программирования несколько своеобразен, и он делает намного больше, чем вы просили, но вы можете найти его полезным.

1

Кредит для Арне Фогель для того, чтобы отметить, что набор пар, проиндексированных на их первом элементе, действительно является картой.

Следовательно, довольно близко к моим первоначальным мыслям и к бесполезному ответу (кроме простого сравнения границ); мы получаем это:

typedef std::pair<int, int> Range;

class RangeSet : public std::map<int, int> {
public:

std::pair<RangeSet::iterator, bool> insert(const Range& range) {
assert(range.first <= range.second);

RangeSet::iterator after = upper_bound(range.first), insert_range;

if(after == begin() or std::prev(after)->second < range.first) {
insert_range = std::map<int, int>::insert(after, range);
}
else {
insert_range = std::prev(after);
if(insert_range->second >= range.second) {
return std::pair<RangeSet::iterator, bool>(insert_range, false);
}
else {
insert_range->second = range.second;
}
}

while(after != end() and range.second >= after->first) {
insert_range->second = std::max(after->second, insert_range->second);
after = erase(after);
}

return std::pair<RangeSet::iterator, bool>(insert_range, true);
}

};

С возвращаемым логическим значением true, если в общий набор добавлен хотя бы один элемент.

0

Источник

Accepted Answer

Если вы кодируете диапазоны в виде последовательности конечных точек и направления шага вместо пар начала / конца, то поиск объединения должен стать намного проще, просто простая сортировка слиянием.

(0, +) (5, -)

(0, +) (5, -) (10, +) (15, -)

(0, +) (5, +) (5, -) (7, -) (10, +) (15, -)

Посмотрите, перекрывающийся диапазон отображается в виде вложенных диапазонов. Просто сохрани только самые внешние.

(0, +) (5, +) (5, -) (7, -) (10, +) (15, -)
1      2      2     1       1       1       <= depth
(0, +) (7, -) (10, +) (15, -)

(0, +) (7, -) (10, +) (12, +) (15, -) (17, -)
1      1      1       2       2       1
(0, +) (7, -) (10, +) (17, -)(0, +) (6, +) (7, -) (10, +) (13, -) (17, -)
1      2      2      2       2       1
(0, +) (17, -)

Я думаю, что поиск пересечений также становится простым, теперь вы сохраняете только конечные точки с уровнем вложенности 2 вместо их удаления.

6