我试图找到一个没有病毒或限制性许可的有效 C++ 区间树实现（很可能基于红黑树）。任何指向干净的轻量级独立实现的指针？对于我想到的用例，一开始就知道一组间隔（比如说一百万），我希望能够快速获得与给定间隔重叠的间隔列表。因此树一旦构建就不会改变——只需要快速查询。
Christophe Lambert
问问题
13321 次
3 回答
5
我用 C++ 编写了一个基于模板的区间树实现，https://github.com/ekg/intervaltree。麻省理工学院许可证。享受。
于 2011-11-17T14:02:00.740 回答
3
C++ 标准库提供红/黑树std::map、std::multimap和.std::setstd::multiset
真的，我想不出比保留 a std::mapof 迭代器对并将这些迭代器对传递给upper_bound()and更有效地处理这个问题的任何方法lower_bound()。您希望迭代器对本身保存在映射中，以便您可以轻松地将哪些对可能在区间内归零（如果“候选区间”中的开始迭代器出现在给定区间结束之后您正在查看，然后您可以跳过检查 - 以及以后 - 迭代器对）。
于 2008-10-17T18:31:22.043 回答
1
在这个链接上还有一个区间树的 C# 实现。为有需要的人翻译成 C++ 很容易
于 2012-07-24T23:34:37.837 回答