c++ - 范围内匹配点的比较器

Question

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

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

在此结构中，start/end 对标识每个范围。 pr 标识该范围的优先级。这意味着如果一个点落入 2 个不同的范围，我喜欢用较小的 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 返回一个与参数比较等效的元素。 等效 表示它在提供给 std::set 的严格弱排序中比较既不大于也不小于。

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

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

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

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

然而，这不是一个可以给你想要的东西的命令。

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