我正在尝试使用范围,就像在数字范围中一样。我的意思是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++ 中“范围”的所有同义词的噪音而无法找到的良好实现?或者有人愿意分享他们自己的吗?我只想打印最终范围,但如果您有其他集合操作,则可以为通用性加分。
最佳答案
如果您将范围编码为一系列端点和步进方向,而不是开始/结束对,那么找到并集应该变得容易得多,只是一个简单的归并排序。
(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 的端点,而不是删除它们。
关于c++ - 用于 C++ 的整数区间容器,例如 RangeSet,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32869247/