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

Question

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

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

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

Answer 1

У меня была точно такая же потребность. Я не смог найти подходящих (простых, современных, переносимых) реализаций, поэтому я использовал реализацию Python от Brent Pedersen в качестве руководства и написал базовые версии C ++ . 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 2

Boost-like? Повышение ICL !

Библиотека контейнеров интервала повышения

Answer 3

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

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

Answer 4

В NCBI C ++ Toolkit появляется , равный одному .

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

Answer 5

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