logo标签列表

C++ - 区间树实现

c++data-structuresinterval-tree
37

有人知道C++中实现良好的区间树吗？

显然，需要一些模板驱动、类似于boost的实现。

另外一个问题——如果有人测试过，基于std::vector的排序的区间树实现在实践中是否能击败通用的区间树(具有O(lg)操作)？

5个回答
22

我有完全相同的需求。我找不到任何合适（简单，现代，便携）的实现方式，因此我使用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
嗨，Erik，感谢您指出这一点。我正在查看您的代码并尝试与理论联系起来（请记住我是新手）。sanityIntervals.push_back(interval(60, 80, true));和for (int i = 0; i < 10000; ++i) { intervals.push_back(randomInterval<bool>(100000, 1000, 100000 + 1, true)); }。我一直在研究具有id、event配对的fork-event-join模型。您能详细说明一下这些数字 - 60、80等是如何得出的，以及为什么选择了bool值对象吗？假设我有一个分布式系统 - 一个服务器和多个客户端，我该如何利用您的代码？ - enthusiasticgeek
不幸的是，查找函数返回内部迭代器的副本，这意味着每次查询操作都需要进行复制操作。在大型应用程序中，这非常缓慢。虽然代码可以工作，但速度很慢。 - ABCD
@SmallChess 绝对不是这样。在像这样的非流分合函数中通过值返回整个要点，就是为了确保 NRVO（命名返回值优化）。更不用说在某些情况下，复制省略是符合标准的强制性操作。 - v.oddou
18

类似于Boost的？Boost ICL！

Boost区间容器库

嗯，boost 的时机很好。我以为当前版本是1.45，我不知道自己这么幸运。谢谢。 - Yippie-Ki-Yay
@Yippie：我最近才发现它（我想是由@ybungalobill介绍的）。 :) - Matthieu M.
如果有人知道为什么这个答案在几个月的不活跃后今天收到了一个赞和一个踩，我会非常高兴了解一下！ - Matthieu M.
17
我提供了一个反对意见，因为该问题涉及区间树，但是这个回答只提供了一个链接到boost中的区间容器库，它没有一个查询树实现。这封邮件在boost邮件列表中表明了这个缺陷，但是截至今天还没有解决方案。当然，问题作者似乎对这个回答很满意，所以也许我只需要回答一个新问题 :) - Erik Garrison
@Erik：谢谢你提醒我！我承认我从未使用过区间树（除了在游乐场上...），并且在阅读《算法导论》时自己编写了它们。值得注意的是，操作中存在各种需求。 - Matthieu M.
2

看起来有一个在NCBI C++ Toolkit中。

但是对于它是否“好”还没有定论（甚至是否基于模板驱动；我对C++仍然有些陌生，所以我并不完全确定它是否是，但我怀疑它是）。

1
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接