c++ - 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

类似升压？提升 ICL！

Boost Interval 容器库

Answer 3

我上传了区间树的简单实现到github：https ://github.com/coolsoftware/ITree

在 itree.h 中查看 itree 类。

Answer 4

NCBI C++ Toolkit中似乎有一个。

尽管如此，陪审团仍然不确定它是否“好”（甚至它是否是模板驱动的；我对 C++ 还有些陌生，所以我不完全确定它是不是，但我也很怀疑）。

Answer 5

如果您不介意将 ac# 实现转换为 c++，请转到http://code.google.com/p/intervaltree/。基于 avl 自平衡树。