用于C++的整数区间的容器,例如RangeSet

Question

我正在尝试使用范围,如数字范围.我的意思是整数区间,在数学中说.我想存储一组它们.我也希望这个集合自然地合并(或合并)我插入的范围.

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

• 我插入范围[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]}

我发现了一个类似的问题,它在Java中作为Google Guava库存在,并被称为RangeSet.

我最初想的是使用一个将在下限排序std::set的std::pairs(所以每对的第一个元素).然后在每次插入后,我将不得不手动合并任何重叠集.

因为这似乎是一个常见问题,由于C++中"range"的所有同义词的噪音,我找不到一个好的实现方法？或者有人关心分享他自己的？如果您有其他设置操作,我只想打印最终范围,但是要获得一般性的奖励积分.

Answer 1

如果您将范围编码为一系列端点和步进方向,而不是开始/结束对,那么查找联合应该变得更加容易,只需一个简单的mergesort.

(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的端点,而不是删除它们.

Answer 2

Boost具有间隔容器库（ICL）。如果要对间隔进行计算，例如表示一个间隔I的sin（I），则还可以使用间隔算法库。