Boost C++ 库

区间容器库 (ICL) 提供了 区间 和两种区间容器：区间集合 (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);

当集合的元素以连续块出现时，使用 interval_sets 和 interval_maps 可能是有益的：区间。这显然在许多问题域中都适用，特别是在处理日期和时间相关的计算领域。

可加性和可减性

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

重叠时聚合

这是一个关于一个小聚会的第一个激励性示例，它演示了 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 的相关值实现。在示例中，相关值是 guest sets。因此，guest set 必须将 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 container。

连接区间容器

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

分割区间容器

相反，Split_interval_set 和 split_interval_map 具有 插入记忆。它们累积来自添加和交集的区间边界。这在希望用特定的时间网格（例如，月份或日历周或两者）丰富区间容器时特别有用。请参阅示例 time grids for months and weeks。

分离区间容器

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