С++ - реализация интервального дерева

Кто-нибудь знает какую-либо хорошую реализацию interval tree в С++?

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

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

Ответы

Ответ 1

Boost-like? Boost ICL!

Библиотека контейнеров интервалов ускорения

Ответ 2

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

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

Ответ 3

Появится в качестве в NCBI С++ Toolkit.

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

Ответ 4

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

Посмотрите класс itree в itree.h.

Ответ 5

если вы не возражаете переводить реализацию aС# на С++, goto http://code.google.com/p/intervaltree/. основываясь на дереве самобалансировки avl.