我可以使用Boost interval_map来做到这一点吗？

Question

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

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

间隔是封闭的和整数,有些间隔可能会过度.我想找到重叠的区间给定的查询效率.例如,如果[16, 22]给出:

[10, 20], [15, 25]

应将上述间隔计算为整数间隔.

我目前正在编写一个基于红黑树的区间树(参考:CLRS,算法简介).虽然找到所有重叠间隔可以是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]被插入,然后将得到的地图将有[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"}

当添加两个重叠的间隔时，实际上会创建三个具有不同属性的间隔。重叠在两个原始间隔中，使其与两个原始间隔中的一个逻辑上不同。现在，两个原始间隔跨越了具有不同属性的时间（有些与原始间隔重叠，有些没有重叠）。由于分割是地图中自己的间隔，因此这种分割使查找重叠非常有效。

无论如何，Boost允许您选择间隔合并样式。因此，如果您想强制使用一种结构，使其很难发现重叠，则可以这样做。