Поиск реализации алгоритма дерева интервалов C++

Question

Я пытаюсь найти эффективную реализацию дерева интервалов C++ (в основном, вероятно, на основе красных черных деревьев) без вирусной или ограничительной лицензии. Любые указатели на легкую автономную реализацию? Для случая использования я имею в виду, что набор интервалов известен с самого начала (скажем, миллион), и я хочу иметь возможность быстро получить список интервалов, которые перекрывают данный интервал. Таким образом, дерево, когда-то построенное, не изменится - просто нужны быстрые запросы.

Answer 1

Стандартная библиотека C++ предлагает красные/черные деревья std::map, std::multimap, std::set и std::multiset.

Действительно, я не могу думать о какой-либо способ справиться с этим более эффективно, чем держать std::map пар итераторов, и передает эти пары итераторов для upper_bound() и lower_bound(). Вы хотите, чтобы пары итераторов содержались в самой карте, чтобы вы могли легко получить нуль, в зависимости от того, какие пары, вероятно, будут в интервале (если начальный итератор в «промежутке-кандидате» приходит после окончания данного интервала вы смотрите, тогда вы можете пропустить проверку того, что - и все последующие - пары итераторов).

Answer 2

Я написал шаблон дерева интервалов на основе шаблонов в C++, https://github.com/ekg/intervaltree. Лицензия MIT. Наслаждаться.

Answer 3

Существует также реализация C# интервала дерева по адресу this link. Достаточно легко перевести на C++ для нуждающихся