CODEWITHSUNDEEP
c++c++14
Afshin
Afshin

Reputation: 9173

Comparator for matching point in a range

I need to create a std::set of ranges for finding matching points in these ranges. Each range is defined as follows:

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

In this structure start/end pair identify each range. pr identifies the priority of that range. It means if a single point falls into 2 different ranges, I like to return range with smaller pr. I like to create a std::set with a transparent comparator to match points like this:

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

I know my comparators are wrong. I wonder how I can write these 3 comparators to answer these queries correctly? Is it possible at all?

Upvotes: 3

Views: 240

Answers (1)

user17732522
user17732522

Reputation: 76824

find returns an element that compares equivalent to the argument. Equivalent means that it compares neither larger nor smaller in the strict weak ordering provided to the std::set.

Therefore, to make your use case work, you want all points in a range to compare equivalent to the range.

If two ranges overlap, then the points shared by the two ranges need to compare equivalent to both ranges. The priority doesn't matter for this, since the equivalence should presumably hold if only one of the ranges is present.

However, one of the defining properties of a strict weak ordering is that the property of comparing equivalent is transitive. Therefore in this ordering the two ranges must then also compare equal in order to satisfy the requirements of std::set.

Therefore, as long as the possible ranges are not completely separated, the only valid strict weak ordering is the one that compares all ranges and points equivalent.

This is however not an order that would give you what you want.

This analysis holds for all standard library associative containers, since they have the same requirements on the ordering.

Upvotes: 1

Related Questions