我需要在一个集合中存储离散区间,插入时将相邻的区间合并。STL中是否有已经具备这种功能的数据结构?
我尝试过使用boost::intervals,但它对我所需的功能来说比较复杂且过于臃肿。
例如,假设该集合为空,插入以下元素:
[64, 96]
[0, 4]
[11, 15]
[5, 10]
预期的区间集应包含以下内容:
[0, 15]
[64, 96]
如果要合并的区间是相邻的,那么这个任务比提出的区间树方法要容易得多。
相反,你可以使用一些程序员
提出的数据结构,并很快实现自己的代码。下面是一个可能的实现:
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)
is.Add(64, 96); is.Add(11, 15); is.Add(5, 9); is.Add(0, 128);
这段代码好像缺少一个循环。 - undefinedstd::map
,因为map是红黑树,是二叉搜索树的一种类型。
std::set
和std::pair
。但是,对于范围的合并,您需要自己处理。 - Some programmer dude