我可以使用 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

我认为您可以使用 interval_map; > >。每当您想要添加间隔 I 时，只需将 make_pair(I, II) 添加到地图，其中 II 是一个 集合 仅包含I。因此，对于上面的示例，您可以这样做：

#include <iostream>
#include <boost/icl/interval_map.hpp>

using namespace boost::icl;

typedef std::set<discrete_interval<int> > intervals;

intervals singleton(const discrete_interval<int> &value) {
    intervals result = { value };
    return result;
}

int main() {
    interval_map<int, intervals> mymap;
    discrete_interval<int> i1 = discrete_interval<int>(2, 7);
    discrete_interval<int> i2 = discrete_interval<int>(3, 8);
    mymap.add(make_pair(i1, singleton(i1)));
    mymap.add(make_pair(i2, singleton(i2)));

    for (int i = 0; i < 10; ++i) {
        std::cout << "i: " << i << ", intervals: " << mymap(i) << std::endl;
    }
}

请注意，boost 文档表明 std::set 的 interval_map 并不是特别有效，位于 此页面。因此，这表明您可能想要编写自己的集合概念的实现，或者使用与 std::set 不同的实现。

Answer 2

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

此示例解释了逻辑：

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 确实允许您选择 间隔组合样式。因此，如果您想强制采用一种更难找到重叠的结构，您可以这样做。

Answer 3

我尝试了升压interval_map和interval_set。他们效率很低。设置成本非常高，因为实现基本上将每个子区间（交叉点）映射到包含它的所有区间。

我认为CLRS《算法导论》中基于红黑树的实现要好得多。奇怪的是，尽管 std::set 和 std::map 基于 RB 树，但没有允许增强的红黑树实现。