当前位置：文江博客话题详情

C++ - 区间树的实现

发布于 2024-10-26 13:31:17 字数 197 浏览 8 评论 0原文

有人知道 C++ 中任何好的间隔树实现吗？

显然，模板驱动的东西，更好的boost风格。

还有一个问题 - 如果有人测试过，基于 std::vector 的基本间隔树实现与排序是否可以击败通用间隔树（具有 O(lg) 操作）在实践中？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

疑心病 2024-11-02 13:31:17

我有完全相同的需求。我找不到任何合适的（简单的、现代的、可移植的）实现，所以我使用了 python 实现由 Brent Pedersen 作为指导，并编写了一个简单的 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

I had exactly the same need. I couldn't find any suitable (simple, modern, portable) implementations, so I used a python implementation by Brent Pedersen as a guide and wrote a barebones C++ version. The IntervalTree behaves like a standard STL container, with some caveats due to its simplicity (no iterators, for instance). You use it like this ("T" is an arbitrary type):

vector<Interval<T> > intervals;
// ... make intervals!
IntervalTree<T> tree(intervals);

And you query it like this:

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

回复收藏 0 原文