范围内匹配点的比较器

Question

我需要创建一个 std::set 范围以在这些范围内查找匹配点。每个范围定义如下：

struct Range {
    uint32_t start;
    uint32_t end;
    uint32_t pr;
};

在此结构中，start/end 对标识每个范围。 pr 标识该范围的优先级。这意味着如果一个点落入 2 个不同的范围，我喜欢 return 范围较小 pr。我喜欢创建一个带有透明比较器的 std::set 来匹配这样的点：

struct RangeComparator {
    bool operator()(const Range& l, const Range& r) const {
        if (l.end < r.start)
            return true;
        if (l.end < r.end && l.pr >= r.pr)
            return true;
        return false;
    }

    bool operator()(const Range& l, uint32_t p) const {
        if (p < l.start)
            return true;
        return false;
    }

    bool operator()(uint32_t p, const Range& r) const {
        if (p < r.start)
            return true;
        return false;
    }

    using is_transparent = int;
};

std::set<Range, RangeComparator> ranges;
ranges.emplace(100,250,1);
ranges.emplace(200,350,2);
auto v1 = ranges.find(110);  // <-- return range 1
auto v2 = ranges.find(210);  // <-- return range 1 because pr range 1 is less
auto v3 = ranges.find(260);  // <-- return range 2

我知道我的比较对象是错误的。我想知道如何编写这 3 个比较器来正确回答这些查询？有可能吗？

Answer 1

find returns 将等价与参数进行比较的元素。 Equivalent 表示它在提供给 std::set.

的严格弱排序中既不比较大也不比较小

因此，为了使您的用例有效，您希望一个范围内的所有点都与该范围进行比较。

如果两个范围重叠，则两个范围共享的点需要与两个范围比较等价。优先级对此无关紧要，因为如果仅存在一个范围，则等价性应该成立。

但是，严格弱排序的定义属性之一是比较等价物的属性是可传递的。因此，在此排序中，两个范围也必须比较相等才能满足 std::set.

的要求

因此，只要可能的范围没有完全分开，唯一有效的严格弱排序是比较所有范围和点等价的排序。

然而，这不是一个可以满足您需求的订单。

此分析适用于所有标准库关联容器，因为它们对排序有相同的要求。

范围内匹配点的比较器

Comparator for matching point in a range

c++

c++14