C++ - 区间树实现

Question

有人知道interval treeC++中的任何好的实现吗？

显然,模板驱动的东西,更好的类似boost风格.

另一个问题 - 如果有人测试过,在std::vector实践中,基于分类的基本区间树实现是否可以击败通用区间树(使用O(lg)操作)？

Answer 1

我有完全相同的需求.我找不到任何合适的(简单,现代,可移植)实现,所以我使用了Brent Pedersen的python实现作为指南并编写了一个准系统C++版本.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

Answer 2

像Boost一样？提升ICL!

Boost Interval容器库