c++ - 我可以用 Boost interval_map 做到这一点吗？

Question

我想做的是有效地处理间隔。例如，在我的示例中，间隔如下所示:

[10, 20], [15, 25], [40, 100], [5, 14]

区间是封闭的整数，有些区间可能重叠。我想高效 为给定查询找到重叠间隔。例如，如果给出 [16, 22]:

[10, 20], [15, 25]

上述区间应计算为重叠区间。

我目前正在写一个基于红黑树的区间树(引用:CLRS，Introduction to Algorithms)。虽然找到所有 重叠间隔可以是 O(n)，但运行时间应该更快。请注意，可以删除和插入间隔。

---

不过，我刚刚发现Boost有interval_map和interval_set: http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html

我试过了，但这种行为对我来说很奇怪。例如，如果先插入 [2, 7]，然后插入 [3, 8]，则生成的 map 将具有 [2, 3) 、[3, 7]、(7, 8]。即插入新的区间时，自动进行拆分。

我可以关闭这个功能吗？或者，Boost 的 interval_map 是否适合我的目的？

Answer 1

您需要一种可以有效找到重叠的数据结构。这是通过在数据结构中存储重叠来实现的。现在你似乎在提示它已经这样做了。

这个例子解释了逻辑:

typedef std::set<string> guests;
interval_map<time, guests> party;
party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")),
guests("Mary"));
party += make_pair(interval<time>::right_open(time("21:00"), time("23:00")),
guests("Harry")); 
// party now contains
[20:00, 21:00)->{"Mary"} 
[21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
[22:00, 23:00)->{"Harry"}

当您添加两个重叠区间时，您实际上创建了三个具有不同属性的区间。重叠在两个原始间隔中，使其成为与任一原始间隔在逻辑上不同的间隔。两个原始间隔现在跨越具有不同属性的时间(一些与原始间隔重叠，一些不重叠)。这种拆分使得查找重叠变得高效，因为它们在 map 中是它们自己的间隔。

无论如何，Boost 允许您选择 interval combining style .因此，如果您想强制采用一种难以找到重叠的结构，您可以这样做。