寻找 C++ 区间树算法实现
我正在尝试找到一种高效的 C++ 区间树实现（很可能基于红黑树），而无需病毒式或限制性许可证。 有没有指向干净的轻量级独立实现的指针？ 对于我想到的用例，间隔集一开始就已知（可能有一百万个），并且我希望能够快速获取与给定间隔重叠的间隔列表。 因此，树一旦构建就不会改变——只需要快速查询。
I'm trying to find an efficient C++ interval tree implementation (mostly likely based on red black trees) without a viral or restrictive license. Any pointers to a clean lightweight standalone implementation? For the use case I have in mind, the set of intervals is known at the outset (there would be say a million) and I want to be able to quickly obtain a list of intervals that overlap a given interval. Thus the tree once built will not change -- just needs rapid queries.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我用 C++ 编写了一个基于模板的间隔树实现，https://github.com/ekg/intervaltree。 麻省理工学院许可证。 享受。
I've written a template-based interval tree implementation in C++, https://github.com/ekg/intervaltree. MIT license. Enjoy.
C++ 标准库提供红/黑树
std::map、std::multimap、std::set和std: ：多重集。真的，我想不出比保留迭代器对的
std::map并将这些迭代器对传递给upper_bound()更有效的方法。和lower_bound()。 您希望将迭代器对保留在映射本身中，以便您可以轻松地将哪些对可能位于间隔中进行归零（如果“候选间隔”中的开始迭代器出现在给定间隔结束之后）如果你正在查看，那么你可以跳过检查——以及后面的所有——迭代器对）。The C++ standard library offers red/black trees
std::map,std::multimap,std::setandstd::multiset.Really, I can't think of any way to handle this more efficiently than to keep a
std::mapof iterator pairs, and passing those iterator pairs toupper_bound()andlower_bound(). You'd want the iterator pairs to be kept in a map themselves so that you could easily zero in on which pairs are likely to be in the interval (if the beginning iterator in the "candidate interval" comes after the end of the given interval you're looking at, then you can skip checking that -- and all later -- iterator pairs).此链接还提供了间隔树的 C# 实现。 对于有需要的人来说，很容易翻译成 C++
There's also a C# implementation of Interval tree at this link. It's easy enough to translate to C++ for those in need