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);

每当集合的元素以连续块出现时，使用 interval_sets 和 interval_maps 可能会有所帮助：intervals。在许多问题领域，尤其是在处理与日期和时间相关的计算的领域中，情况显然如此。

可加性和可减性

与 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 提供的主要类模板。

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

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 中。