用于整数间隔的容器，例如C ++的RangeSet [英] A container for integer intervals, such as RangeSet, for C++

问题描述

我正在尝试使用范围，例如数字范围.我的意思是说整数间隔，在数学上来说.我想存储其中的一组.我还希望该集合自然合并(或合并)我插入的范围.

I am trying to work with ranges, as in ranges of numbers. By that I mean integer intervals, in maths speak. And I want to store a set of them. I also want this set to naturally merge (or coalesce) ranges I insert.

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

Let's go for a simple example, I start with an empty set: { }

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

I found out thanks to a similar question that this exists in Java as a Google Guava library and is called a RangeSet.

我最初是考虑使用std::set的std::pair，将其下限排序(因此是每对的第一个元素).然后，在每次插入之后，我都必须手动合并所有重叠的集合.

I was initially thinking of using a std::set of std::pairs that would be sorted on the lower bound (so the first element of each pair). Then after each insertion I would have to manually merge any overlapping sets.

由于这似乎是一个普遍的问题，由于C ++中"range"的所有同义词的杂音，我找不到一个好的实现吗?还是有人愿意分享自己的东西?我只想打印最终范围，但是如果您还有其他设置操作，则可以得到一般性的加分.

As this seems a common problem, is a good implementation I couldn't find due to the noise with all the synonyms of "range" in C++ ? Or does anyone care to share his own? I only want to print the final ranges but bonus points for generality if you have other set operations.

推荐答案

如果将范围编码为一系列端点和步长方向，而不是起点/终点对，那么查找并集应该变得容易得多，只需一个简单的mergesort.

If you encode ranges as a sequence of endpoints and step direction, instead of start/end pairs, then finding union should become much easier, just a simple mergesort.

(0, +) (5, -)

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

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

看，重叠范围显示为嵌套范围.只保留最外层的.

Look, the overlapping range appears as nested ranges. Just preserve only the outermost ones.

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

I think that finding intersections becomes simple also, now you preserve only endpoints with a nesting level of 2, instead of deleting them.

这篇关于用于整数间隔的容器，例如C ++的RangeSet的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！