有没有可以存储离散区间的集合？

Question

我需要在一个集合中存储离散区间，插入时将相邻的区间合并。STL中是否有已经具备这种功能的数据结构？

我尝试过使用boost::intervals，但它对我所需的功能来说比较复杂且过于臃肿。

例如，假设该集合为空，插入以下元素：

[64, 96]
[0, 4]
[11, 15]
[5, 10]

预期的区间集应包含以下内容：

[0, 15]
[64, 96]

- sklopec

---

没有现成的容器可以为您处理所有事情。对于容器本身，您可能可以使用std::set和std::pair。但是，对于范围的合并，您需要自己处理。 - Some programmer dude

我喜欢 DIET trees，但我不认为我曾经见过 C++ 实现。 - Shawn

Answer 1

如果要合并的区间是相邻的，那么这个任务比提出的区间树方法要容易得多。

相反，你可以使用一些程序员提出的数据结构，并很快实现自己的代码。下面是一个可能的实现：

class IntervalSet {
    std::map<int, int> _intervals;

public:
    void Add(int smaller, int bigger) {
        const auto next = _intervals.upper_bound(smaller);
        if (next != _intervals.cbegin()) {
            const auto prev = std::prev(next);
            if (next != _intervals.cend() && next->first <= bigger + 1) {
                bigger = next->second;
                _intervals.erase(next);
            }
            if (prev->second + 1 >= smaller) {
                smaller = prev->first;
                _intervals.erase(prev);
            }
        }
        _intervals[smaller] = bigger;
    }

    const auto& Intervals() const { return _intervals; }

    bool IsInsideInterval(int v) const {
        const auto suspectNext = _intervals.upper_bound(v);
        const auto suspect = std::prev(suspectNext);
        return suspect->first <= v && v <= suspect->second;
    }
};

小测试：

IntervalSet is;
is.Add(64, 96);
is.Add(0, 4);
is.Add(11, 15);
is.Add(5, 10);
for (const auto p : is.Intervals()) std::cout << "(" << p.first << ", " << p.second << ") ";

(0, 15) (64, 96)

它同样适用于交叉区间：

IntervalSet is;
is.Add(0, 10);
is.Add(5, 15);
is.Add(10, 20);
for (const auto p : is.Intervals()) std::cout << "(" << p.first << ", " << p.second << ") ";

(0,20)

- Yola

---

is.Add(64, 96); is.Add(11, 15); is.Add(5, 9); is.Add(0, 128);这段代码好像缺少一个循环。 - undefined

Answer 2

这是一个众所周知的问题。有一个wikipedia页面介绍了可能的解决方案。当然，在C++ STL中，您可以实现一个基于Naive方法的解决方案，该方法在维基百科中有解释，并使用std::map，因为map是红黑树，是二叉搜索树的一种类型。

- Max