用于 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 that this exists in Java as a Google Guava library and is called a RangeSet。

我最初考虑使用 std::set 的 std::pairs 将在下限（因此每对的第一个元素）上排序。然后在每次插入后我必须手动合并任何重叠的集合。

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

Answer 1

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

(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

事实证明，实现您的第一个想法相当简单。

要插入：

使用 lower_bound 找到前面的范围，但通过比较新范围的下限与旧范围的上限。

这只是因为上限与下限的顺序完全相同，所以我们保留了正确的顺序
如果你重叠返回的范围，就地合并（只是改变它），否则插入
当您当前的范围（无论是就地突变还是新插入）与后续范围重叠时，合并它们

即只需要向一个方向合并

请注意，这需要一个不寻常的比较，它不是严格的弱排序（如果范围 A 完全包含在范围 B 中，您可能会得到 A < B < A），所以我不确定是否将其放入in a std::set 会起作用——不过只维护一个排序的 list 或 vector 应该很容易。

Answer 3

Boost 有 Interval Container Library (ICL)。如果你想对时间间隔进行计算，例如代表一个区间I的sin(I)，在boost中也有一个Interval Arthmetic Library.

Answer 4

感谢 Arne Vogel 注意到在第一个元素上索引的一组对实际上是一个映射。

因此非常接近我最初的想法和无用的答案（除了简单的比较边界）；我们得到这个：

typedef std::pair<int, int> Range;

class RangeSet : public std::map<int, int> {
public:

std::pair<RangeSet::iterator, bool> insert(const Range& range) {
    assert(range.first <= range.second);

    RangeSet::iterator after = upper_bound(range.first), insert_range;

    if (after == begin() or std::prev(after)->second < range.first) {
        insert_range = std::map<int, int>::insert(after, range);
    }   
    else {
        insert_range = std::prev(after);
        if (insert_range->second >= range.second) {
            return std::pair<RangeSet::iterator, bool>(insert_range, false);
        }   
        else {
            insert_range->second = range.second;
        }   
    }   

    while (after != end() and range.second >= after->first) {
        insert_range->second = std::max(after->second, insert_range->second);
        after = erase(after);
    }   

    return std::pair<RangeSet::iterator, bool>(insert_range, true);
}   

};

当且仅当至少有一个元素被添加到总集合中时，返回的布尔值才为真。

Answer 5

Here 是一个 GPL-v2 许可的 class 我很久以前写过它做间隔。它实际上是一个 2D 区域 class。它还支持flood-fill。

编程风格有些特殊，它所做的比您要求的要多得多，但您可能会发现它很有帮助。

Answer 6

我已经编写了这样一个库供我使用，它已经过广泛测试，可在此处获取：https://github.com/hl037/rangeset.hpp

它与 STL 兼容，使用起来非常简单。它基于 Ben Voigt 的想法，但没有子范围部分。

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

A container for integer intervals, such as RangeSet, for C++

c++

c++11

rangeset