Кто-нибудь знает какую-либо хорошую реализацию interval tree в С++?
Очевидно, что что-то с шаблоном, лучше в стиле boost -like.
И еще один вопрос - если кто-то тестировал, реализует ли базовая реализация дерева интервалов на основе std::vector с сортировкой, может ли на практике обычное древовидное дерево (с операциями O (lg)?
Boost-like? Boost ICL!
Библиотека контейнеров интервалов ускорения
У меня была такая же потребность. Я не мог найти подходящих (простых, современных, переносимых) реализаций, поэтому я использовал реализацию 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
Появится в качестве в NCBI С++ Toolkit.
Жюри по-прежнему говорит о том, является ли оно "хорошим", хотя (и даже ли оно связано с шаблонами, я все еще несколько новичок в С++, поэтому я не совсем уверен, что это так, но я подозреваю, что это так).
Я загрузил простую реализацию дерева интервалов в github: https://github.com/coolsoftware/ITree
Посмотрите класс itree в itree.h.
если вы не возражаете переводить реализацию aС# на С++, goto http://code.google.com/p/intervaltree/. основываясь на дереве самобалансировки avl.