查找C++区间树算法实现

Question

我试图找到一个有效的C++间隔树实现(很可能基于红黑树)没有病毒或限制性许可证.任何指向干净的轻量级独立实现的指针？对于我想到的用例,一开始就知道了一组区间(可能会有一百万个),我希望能够快速获得一个与给定区间重叠的区间列表.因此,一旦构建的树将不会改变 - 只需要快速查询.

Answer 1

我已经用 C++ 编写了一个基于模板的区间树实现，https://github.com/ekg/intervaltree。麻省理工学院执照。享受。

Answer 2

C++ 标准库提供红/黑树std::map、std::multimap和std::set。std::multiset

真的，我想不出任何比保留 astd::map迭代器对并将这些迭代器对传递给 和upper_bound()更有效的方法来处理这个问题lower_bound()。您希望迭代器对本身保存在映射中，以便您可以轻松地将哪些对可能位于间隔中进行归零（如果“候选间隔”中的开始迭代器出现在给定间隔结束之后）如果你正在查看，那么你可以跳过检查——以及后面的所有——迭代器对）。