c++ - 用于 C++ 的整数区间容器，例如 RangeSet

Question

我正在尝试使用范围，就像在数字范围中一样。我的意思是integer intervals , 用数学来说。我想存储一组。我还希望这个集合能够自然地合并(或合并)我插入的范围。

让我们来看一个简单的例子，我从一个空集开始:{ }

• 我插入范围 [0,5]，现在我有 { [0,5] }
• 我插入范围 [10,15]，现在我有 { [0,5], [10,15] }
• 我插入范围 [5,7]，现在我有 { [0,7], [10,15] }
• 我插入范围 [12,17]，现在我有 { [0,7], [10,17] }
• 我插入范围 [6,13]，现在我有 { [0,17] }

我发现了 thanks to a similar question这存在于 Java as a Google Guava library and is called a RangeSet .

我最初考虑使用 std::pair 的 std::set 将在下限上排序(因此每对的第一个元素).然后在每次插入后，我将不得不手动合并任何重叠的集合。

由于这似乎是一个常见问题，是否存在由于 C++ 中“范围”的所有同义词的噪音而无法找到的良好实现？或者有人愿意分享他们自己的吗？我只想打印最终范围，但如果您有其他集合操作，则可以为通用性加分。

Answer 1

如果您将范围编码为一系列端点和步进方向，而不是开始/结束对，那么找到并集应该变得容易得多，只是一个简单的归并排序。

(0, +) (5, -)

(0, +) (5, -) (10, +) (15, -)

(0, +) (5, +) (5, -) (7, -) (10, +) (15, -)

看，重叠范围显示为嵌套范围。只保留最外面的那些。

(0, +) (5, +) (5, -) (7, -) (10, +) (15, -)
   1      2      2     1       1       1       <= depth
(0, +) (7, -) (10, +) (15, -)

(0, +) (7, -) (10, +) (12, +) (15, -) (17, -)
   1      1      1       2       2       1
(0, +) (7, -) (10, +) (17, -)


(0, +) (6, +) (7, -) (10, +) (13, -) (17, -)
   1      2      2      2       2       1
(0, +) (17, -)

我认为查找交叉点也变得简单，现在您只保留嵌套级别为 2 的端点，而不是删除它们。