CODEWITHSUNDEEP
c++sortingoperator-overloading
Rohan Mohapatra
Rohan Mohapatra

Reputation: 163

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

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());

Upvotes: 7

Views: 1199

Answers (2)

DAle
DAle

Reputation: 9117

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);
}

Upvotes: 13

Michael Veksler
Michael Veksler

Reputation: 8475

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;
}

Upvotes: 11

Related Questions