我可以使用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适合我的目的吗？

- Nullptr

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确实允许您选择时间段组合风格。因此，如果您想强制使用使查找重叠更困难的结构，则可以这样做。

- David Schwartz

---

谢谢，但我需要保持原始间隔。所有支持的连接操作都会破坏原始间隔。还是谢谢！ - Nullptr

原始的时间间隔仍然存在。如果您查看示例，可以轻松地看到'Mary'的时间间隔为20-22。它们只是以一种使重叠更有效的方式进行编码。 - David Schwartz

我看到这个满足了OP的要求，但是有人能解释一下为什么Boost文档会说：注意我们使用字符串集合的区间映射来引入interval_maps，因为它具有教学优势。party示例用于立即访问interval_maps和重叠聚合的基本思想。对于实际应用，不建议使用字符串集合的interval_map。它具有与std::map of std::sets相同的效率问题。 - Ryan

Answer 2

我尝试过使用boost interval_map和interval_set，但它们非常低效。因为实现基本上将每个子区间（交集）映射到包含它的所有区间中，所以设置成本非常高。

我认为CLRS《算法导论》中基于红黑树的实现要好得多。奇怪的是，即使std::set和std::map基于RB树，也没有可用于增强的红黑树实现。

- user723145

Answer 3

我认为你可以使用一个 interval_map<int, set<discrete_interval<int> > >。每当你想要添加一个区间 I 时，只需将 make_pair(I,II) 添加到 map 中，其中 II 是仅包含 I 的 set。因此，对于上面的示例，你可以执行以下操作：

#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文档建议在this page的底部，使用std::set的interval_map并不特别高效。因此，这表明您可能需要编写自己的集合概念实现，或者使用不同于std::set的其他实现。

- Erik P.

---

我尝试了这段代码，但好像无法编译。错误信息如下： no match for ‘operator+=’ (operand types are ‘boost::icl::interval_map<int, boost::icl::closed_interval<int> >’ and ‘std::pair<boost::icl::closed_interval<int>, boost::icl::closed_interval<int> >’) mymap += make_pair(i1, i1); - user1701545

实际上，如果有一个编译示例，我会非常感激。请查看我的问题：https://dev59.com/f3nZa4cB1Zd3GeqPvuOW#20388063?noredirect=1#comment30444819_20388063 - user1701545

嗯 - 你点名批评我，我也该。我假设页面上方的代码实际上能够工作，并进行了适应性修改；但现在我已经重写了示例并编译并运行它。 - Erik P.

成功。使用gcc 4.6.3，通过g++ -std=c++0x -g -I boost_1_55_0 -L boost_1_55_0/libs/ foo.cpp进行调用。然后通过./a.out运行。这是在Ubuntu 12.04上完成的。 - Erik P.

没问题。原来使用离散、闭区间时，interval_map在添加区间时会创建交叉的开区间。lower和upper函数将返回开区间的开边界，但是first和last函数将返回闭区间的闭边界，意味着lower+1和closed-1。 - user1701545