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

Question

我有一组范围:

Range1 ----(0-10)

Range2 ----(15-25)

范围3 ----(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';
}