6

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

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

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

[10, 20], [15, 25]

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

我目前正在编写基于 Red-Black Tree 的区间树（参考：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]插入，则生成的映射将具有[2, 3)、[3, 7]和(7, 8]。也就是说，当插入新的区间时，会自动完成拆分。

我可以关闭这个功能吗？或者，Boostinterval_map适合我的目的？

4

3 回答 3

5

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

这个例子解释了逻辑：

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

于 2011-11-02T02:32:30.960 回答
2

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

我认为基于红黑树的CLRS“算法介绍”中的实现要好得多。奇怪的是，没有允许扩充的红黑树实现，即使 std::set 和 std::map 基于 RB 树。

于 2012-07-12T17:55:10.597 回答
1

我认为您可以使用interval_map<int, set<discrete_interval<int> > >. 每当您想添加区间I时，只需添加make_pair(I, II)到地图中，其中II仅set包含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 文档表明 an interval_mapof s 并不是特别有效。因此，这表明您可能想要编写自己的 set 概念实现，或者使用与.std::setstd::set

于 2011-11-02T14:56:50.477 回答