"invalid comparator" : error when overloading the "<" operator

Question

I have a class that needs to be sorted. Using a vector of this class, I get the error "invalid comparator" while sorting.

I have overloaded the "<" operator in my class and followed strict weak ordering.

As mentioned in this post.

sort requires a strict weak ordering. Your comparator isn't one. Among many other things, for a strict weak ordering, comp(x, x) must be false.

This is my Code:

bool outlierScore::operator<(const outlierScore& other) {
    if (score < other.score)
        return score < other.score;
    else if (coreDistance < other.coreDistance)
        return coreDistance < other.coreDistance;
    else if (id < other.id)
        return id < other.id;
    else
        return false;
}

this is the overloaded operator function, what it does essentially is trying to sort in ascending order by outlier score, with core distances used to break outlier score ties, and ids used to break core distance ties.

Stack Trace revealed the error coming at this stage.

template <class _Pr, class _Ty1, class _Ty2>
constexpr bool _Debug_lt_pred(_Pr&& _Pred, _Ty1&& _Left, _Ty2&& _Right) _NOEXCEPT_COND(
    noexcept(_Pred(_Left, _Right))
    && noexcept(_Pred(_Right, _Left))) { // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
    const auto _Result = static_cast<bool>(_Pred(_Left, _Right));
    if (_Result) {
        _STL_VERIFY(!_Pred(_Right, _Left), "invalid comparator");
    }

    return _Result;
}

I am unable to find the issue. Any help would be great.

The minimal reproducible example:

class outlierScore
{
private:
    double coreDistance;
public:
    double score;
    int id;
}
vector <vector<double>> x = {
                {0,0.889528896739179,0.536626916823739},
                {1,1.30766765703343,0.684794721931497},
                {2,0.936505261432846,0.559870334496815}
            };
vector<outlierScore> test;
test.push_back(outlierScore(x[0][2], x[0][1], x[0][0]));
test.push_back(outlierScore(x[1][2], x[1][1], x[1][0]));
test.push_back(outlierScore(x[2][2], x[2][1], x[2][0]));

contains outlierScore Objects which look like {id, coreDistance, score}

Where it gives an error: sort(test.begin(), test.end());

Pls provide a minimal reproducible example. And en.cppreference.com/w/cpp/language/operator_comparison => should be const — Martin Morterol
– Martin Morterol, Commented Jun 20, 2019 at 6:57
By minimal reproducible example, I mean "pls provide a code that I can copy-past that reproduce your error without any other work for me". Here where are the outlierScore implementation ? — Martin Morterol
– Martin Morterol, Commented Jun 20, 2019 at 7:04
@RohanMohapatra -- I am unable to find the issue -- You didn't look hard enough. If you look at the stack trace, you see what the compiler's code is doing. It is calling your predicate with (Left, Right), getting the result, and then seeing if your predicate makes sense by switching the order and calling it again, (Right, Left) and checking that return result. All you really needed was to see what the values of Right and Left are, and thus you would understand the error. Your predicate is returning inconsistent / impossible scenario when Right and Left are used. — PaulMcKenzie
– PaulMcKenzie, Commented Jun 20, 2019 at 10:10
Your code only returns true when all 3 conditions are false. I'd that intended? I'm not familiar with strict weak ordering. — user10957435
– user10957435, Commented Jun 20, 2019 at 12:11

DAle · Accepted Answer · 2019-06-20 07:01:26Z

13

Your implementation is not correct.

bool outlierScore::operator<(const outlierScore& other) const {
    return (score < other.score) ||
           (score == other.score && coreDistance < other.coreDistance) ||
           (score == other.score && coreDistance == other.coreDistance && id < other.id);
}

Or

bool outlierScore::operator<(const outlierScore& other) const {
    return std::tie(score, coreDistance, id) < std::tie(other.score, other.coreDistance, other.id);
}

edited Jun 20, 2019 at 7:01

answered Jun 20, 2019 at 6:58

DAle

9,1922 gold badges28 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

BoBTFish Over a year ago

Can I suggest some parentheses in the first example? For the humans, not the compilers!

Bathsheba Over a year ago

That's the one - my answer was incomplete - I've deleted. And personally I prefer it without the parentheses.

BoBTFish Over a year ago

@Bathsheba I can't quite resist the temptation to get into opinionated debate in the comments :p Perhaps as an experienced C++ expert you find it easy to follow the precedence rules, and therefore find superfluous parens noisy, even leading you to waste mental effort looking for how they change the logic. But perhaps for someone less comfortable with the rules (as I suspect this answer is a relative beginner), the parens help?

Michael Veksler Over a year ago

@Bathsheba I'm with you on this. For me ut's like writing (a * b) + c instead of a * b +c. Having said that, we are not lone programmers, and have to follow whatever most people find more readable, even if it is slightly less readable for us.

Bathsheba Over a year ago

@BoBTFish: Neither can I ;-). To me the order of attainment is almost (i) learn to type, (ii) learn to use a debugger, (iii) learn your precedence tables, (iv) learn the syntax. I strongly discourage excess parentheses in my shop. They are occasionally harmful: e.g. bonus = salary * (9 / 10) .

|

Michael Veksler · Accepted Answer · 2019-06-20 07:00:15Z

11

Other than the method is not const, this operator does not satisfy strict weak ordering.

bool outlierScore::operator<(const outlierScore& other) {
    if (score < other.score)
        return score < other.score;
    else if (coreDistance < other.coreDistance)
        return coreDistance < other.coreDistance;
    else if (id < other.id)
        return id < other.id;
    else
        return false;
}

For example, if all fields are are integers.

a.score = 0 ; a.coreDistance = 1
b.score = 1 ; b.coreDistance = 0

For these values, the following should be false, but a true is returned:

a < b && b < a

You should also check equality:

bool outlierScore::operator<(const outlierScore& other) {
    if (score != other.score)
        return score < other.score;
    else if (coreDistance != other.coreDistance)
        return coreDistance < other.coreDistance;
    else 
        return id < other.id;
}

answered Jun 20, 2019 at 7:00

Michael Veksler

8,5101 gold badge24 silver badges37 bronze badges

1 Comment

Rohan Mohapatra Over a year ago

Oh, Thank you for the clarification. May have missed such case.

Collectives™ on Stack Overflow

"invalid comparator" : error when overloading the "<" operator

This is my Code:

2 Answers 2

7 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

This is my Code:

2 Answers 2

7 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related