c++ - 存储一组非重叠范围并严格查找值是否存在于任何一个范围中

Question

我有一组范围:

范围 1 ---- (0-10)

范围 2 ---- (15-25)

Range3 ---- (100-1000) 同理。我想只存储边界，因为存储大范围，这样会很有效。

现在我需要搜索一个数字，比如 14。在这种情况下，14 不存在于任何范围内，而(比如一个数字)16 存在于其中一个范围内。

我需要一个函数

bool search(ranges, searchvalue)
{
    if searchvalues present in any of the ranges
        return true;
    else
        return false;
}

如何做到最好？这严格来说是非重叠的，重要的标准是搜索必须是最有效的。

Answer 1

一种可能性是将范围表示为一对值并定义合适的比较函数。如果边界较小且没有重叠，则以下内容应考虑一个范围小于另一个范围。作为副作用，此比较函数不允许您在集合中存储重叠范围。

要查找一个整数n，它可以被视为一个范围[n, n]

#include <set>
#include <iostream>

typedef std::pair<int, int> Range;
struct RangeCompare
{
    //overlapping ranges are considered equivalent
    bool operator()(const Range& lhv, const Range& rhv) const
    {   
        return lhv.second < rhv.first;
    } 
};

bool in_range(const std::set<Range, RangeCompare>& ranges, int value)
{
    return ranges.find(Range(value, value)) != ranges.end();
}

int main()
{
    std::set<Range, RangeCompare> ranges;
    ranges.insert(Range(0, 10));
    ranges.insert(Range(15, 25));
    ranges.insert(Range(100, 1000));
    std::cout << in_range(ranges, 14) << ' ' << in_range(ranges, 16) << '\n';
}