C++ - реализация дерева интервалов

Question

Кто-нибудь знает что-нибудь хорошее interval tree реализация в C++?

Очевидно, что-то на основе шаблонов, лучше в boost стиль

И еще один вопрос - если кто-то проверял, делает ли основной std::vector реализация интервального дерева с сортировкой может превзойти общее интервальное дерево (с операциями O(lg)) на практике?

Answer 1

Boost-как? Повысьте ICL!

Интервальная библиотека Boost Interval

Answer 2

У меня была точно такая же потребность. Я не смог найти подходящих (простых, современных, переносимых) реализаций, поэтому я использовал в качестве руководства реализацию Python от Brent Pedersen и написал версию C++ для barebones. IntervalTree ведет себя как стандартный контейнер STL, с некоторыми оговорками из-за своей простоты (например, без итераторов). Вы используете это так ("Т" - произвольный тип):

vector<Interval<T> > intervals;
// ... make intervals!
IntervalTree<T> tree(intervals);

И вы запрашиваете это так:

vector<Interval<T> > results;
tree.findContained(start, stop, results);
// results now contains Intervals which are fully contained in the query interval
results.clear();
tree.findOverlapping(start, stop, results);
// results now contains Intervals which overlap the query interval

Answer 3

Похоже, что он есть в NCBI C++ Toolkit.

Жюри до сих пор не знает, хорошо ли это (и даже не зависит ли это от шаблонов; я все еще немного новичок в C++, так что я не совсем уверен, что это так, но я подозреваю, что это так).

Answer 4

Я загрузил простую реализацию Interval Tree в github: https://github.com/coolsoftware/ITree

Посмотри класс в этом древе.

Answer 5

Если вы не против перевести реализацию aC# на C++, перейдите на страницу http://code.google.com/p/intervaltree/.base на базе самобалансирующегося дерева avl.