Boost C++ 库

区间容器库 (ICL) 提供了 区间 (intervals) 和两种区间容器：区间集合 (interval_sets) 和 区间映射 (interval_maps)。

两个方面

区间集合 (Interval_sets) 和 区间映射 (interval_maps) 在它们的接口中暴露了两个不同的方面：(1) 集合或映射的功能，这是更 抽象的方面。以及 (2) 区间容器的功能，这是更具体且 与实现相关的方面。实际上，这两个方面都有用，因此都得到了支持。

第一个方面，被称为 基本 方面，是最重要的。这意味着我们可以像使用 元素 的集合或映射一样使用 interval_set 或 interval_map。它暴露了相同的功能。

interval_set<int> mySet;
mySet.insert(42);
bool has_answer = contains(mySet, 42);

第二个方面，被称为 分段 方面，允许利用 interval_sets 和 interval_maps 的元素被 聚集 在 区间 或 分段 中，我们可以迭代遍历这些区间或分段。

// Switch on my favorite telecasts using an interval_set
interval<seconds>::type news(make_seconds("20:00:00"), make_seconds("20:15:00"));
interval<seconds>::type talk_show(make_seconds("22:45:30"), make_seconds("23:30:50"));
interval_set<seconds> myTvProgram;
myTvProgram.add(news).add(talk_show);

// Iterating over elements (seconds) would be silly ...
for(interval_set<seconds>::iterator telecast = myTvProgram.begin();
    telecast != myTvProgram.end(); ++telecast)
    //...so this iterates over intervals
   TV.switch_on(*telecast);

当集合的元素以连续块的形式出现时（区间 (intervals)），使用 interval_sets 和 interval_maps 会很有益。这显然是许多问题领域的普遍情况，特别是在涉及日期和时间计算的领域。

可加性和可减性

与 std::sets 和 maps 不同，interval_sets 和 interval_maps 实现 Addable 和 Subtractable 概念。因此，interval_sets 定义了一个 operator +=，它自然地实现为 集合并集，以及一个 operator -=，它相应地实现为 集合差集。在 Icl 中，interval_maps 也是可加和可减的。将添加或减法传播到 interval_map 的关联值中，在插入区间值对到 interval_map 时导致与已存在的区间值对发生冲突的情况下，已经被证明是一个非常有益的概念。这种操作传播称为 重叠时聚合 (aggregate on overlap)。

重叠时聚合

这是一个初步的激励性示例，展示了一个非常小的派对，演示了 interval_maps 上的 重叠时聚合 原理。

在示例中，玛丽最先进入派对。她待在时间区间 [20:00,22:00) 内。哈利后来进入。他待在 [21:00,23:00) 内。

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"}

当区间重叠时，相应的姓名集合会被 累加。在 重叠点，区间会被 分割。通过 operator += 来实现区间重叠时的内容累加，该运算符必须为 interval_map 的关联值实现。在示例中，关联值是 访客 集合。因此，访客 集合 必须实现 operator += 作为集合并集。

从示例中可以看出，interval_map 既有 分解行为（在时间维度上），也有 累加行为（在关联值上）。

在 interval_maps 上，可加性和重叠时聚合是通过 add 函数和 operator += 实现的有用的功能。但您也可以使用 传统 的 插入语义，它类似于 std::map::insert，但对区间插入进行了泛化。

除了区间容器，我们还可以使用 行为上等价 于区间容器的元素容器：在基本方面，它们具有完全相同的功能。STL 中的 std::set 就是这样一种等价的集合实现。由于 icl 的区间映射具有聚合功能，std::map 在基本功能上与 interval_map 并不完全等价。因此，在 icl 中还有一个额外的 icl::map 类模板用于元素映射。

下表提供了 icl 提供的主要类模板的概述。

静态有界区间总是具有相同类型的区间边界，例如，对于 right_open_interval，右开边界为 [a..b)。动态有界区间可以具有不同的边界。有关详细信息，请参阅关于 区间 的章节。

Std::set 放在括号中，因为它不是 ICL 的类模板。但它可以用作元素容器，在基本方面与 ICL 的区间集合行为等价。 样式 列指的是区间容器组合添加区间的不同方式。这些 组合样式 在下一节中描述。

当我们向区间容器添加区间或区间值对时，区间可以以不同的方式添加：区间可以合并、分割或保持分离。不同的区间组合样式将在下表中通过示例进行说明。

  {[1      3)          }
+       [2      4)
+                 [4 5)
= {[1                5)}

  {[1      3)}         }
+       [2      4)
+                 [4 5)
= {[1           4)[4 5)}

  {[1      3)          }
+       [2      4)
+                 [4 5)
= {[1 2)[2 3)[3 4)[4 5)}

  {[1      3)->1          }
+       [2      4)->1
+                 [4 5)->1
= {[1 2)[2 3)[3      5)   }
  | ->1  ->2     ->1      |

  {[1      3)->1          }
+       [2      4)->1
+                 [4 5)->1
= {[1 2)[2 3)[3 4)[4 5)   }
  | ->1  ->2  ->1  ->1    |

请注意，interval_sets A、B 和 C 代表相同的元素集合 {1,2,3,4}，而 interval_maps D 和 E 代表相同的元素映射 {1->1, 2->2, 3->1, 4->1}。有关其他演示，请参阅示例程序 区间容器。

合并区间容器

Interval_set 和 interval_map 始终处于 最小表示 状态。这在插入点或区间交集不重要的许多情况下很有用。因此，在大多数情况下，interval_set 和 interval_map 将是区间容器的首选。

分割区间容器

Split_interval_set 和 split_interval_map 相反，它们具有 插入记忆。它们会累加来自添加和交集的区间边界。这尤其有用，如果我们想用特定的时间网格（例如，月份或日历周，或两者）来丰富区间容器。请参阅示例 月份和周的时间网格。

分离区间容器

Separate_interval_set 实现分离样式。此样式保留了从未被重叠区间通过的边界。因此，如果插入到 separate_interval_set 中的所有区间都来自某个永不通过月份边界的网格，那么这些边界就会保留在 separate_interval_set 中。