STL Sort - Debug Assertion Failed

Question

Program in C++. I sorted a vector using STL sort and the boolean comparator (here, cmp1 and cmp2 functions). However, upon running the program and reading the values of the vector, it returns: Debug Assertion Failed!, Line:1618, Expression: invalid comparator. Here, the function that returns the error from the algorithm library is:

// FUNCTION TEMPLATE _Debug_lt_pred
template <class _Pr, class _Ty1, class _Ty2,
    enable_if_t<is_same_v<_Remove_cvref_t<_Ty1>, _Remove_cvref_t<_Ty2>>, int> = 0>
constexpr bool _Debug_lt_pred(_Pr&& _Pred, _Ty1&& _Left, _Ty2&& _Right) noexcept(
    noexcept(_Pred(_Left, _Right)) && noexcept(_Pred(_Right, _Left))) {
    // test if _Pred(_Left, _Right) and _Pred is strict weak ordering, when the arguments are the cv-same-type
    const auto _Result = static_cast<bool>(_Pred(_Left, _Right));
    if (_Result) {
        _STL_VERIFY(!_Pred(_Right, _Left), "invalid comparator");
    }

    return _Result;
}

template <class _Pr, class _Ty1, class _Ty2,
    enable_if_t<!is_same_v<_Remove_cvref_t<_Ty1>, _Remove_cvref_t<_Ty2>>, int> = 0>
constexpr bool _Debug_lt_pred(_Pr&& _Pred, _Ty1&& _Left, _Ty2&& _Right) noexcept(noexcept(_Pred(_Left, _Right))) {
    // test if _Pred(_Left, _Right); no debug checks as the types differ
    return static_cast<bool>(_Pred(_Left, _Right));
}

This is my program:

#include <iostream>
#include <algorithm>
#define DIM 10006
using namespace std;

bool cmp1(int st, int dr) {
    return (st >= dr);
}

bool cmp2(int st, int dr) {
    return (st <= dr);
}

void Scan(int& n, int& m, char& c, int v[])
{
    cin >> n >> m >> c;
    for (int i = 0; i < n * m; i++)
        cin >> v[i];
}

void Print(int n, int m, int v[])
{
    int k = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << v[k] << ' ';
            k++;
        }
        cout << '\n';
    }
}

int main()
{
    int v[DIM];
    int n, m;
    char c;
    Scan(n, m, c, v);
    if (c == '+')
        sort(v, v + n * m, cmp1);
    else //c == '-'
        sort(v, v + n * m, cmp2);
    Print(n, m, v);
    return 0;
}

The operators `<=` and `>=` don't defined a strict weak order as `cmp(a, a)` is `true`. — Dietmar Kühl, Dec 27 '20 at 17:47
The rules for a [strict weak order](https://en.wikipedia.org/wiki/Weak_ordering) are: irreflexive: `cmp(a, a) == false`, asymmetry: `cmp(a, b) == true` implies `cmp(b, a) == false`, transitive: `cmp(a, b) == true && cmp(b,c) == true` implies `cmp(a, c) == true`, transitivity of incomparable: `cmp(a, b) == false && cmp(b, a) == false && cmp(b, c) == false && cmp(c, b) == false` implies `cmp(a, c) == false && cmp(c, a) == false`. The comparator of `std::sort()` has to define a strict weak ordering on the sequence of elements. — Dietmar Kühl, Dec 27 '20 at 17:53

score 3 · Accepted Answer · answered Dec 27 '20 at 17:47

Comparators must return false for equal elements. Change

bool cmp1(int st, int dr) {
    return (st >= dr);
}

bool cmp2(int st, int dr) {
    return (st <= dr);
}

to

bool cmp1(int st, int dr) {
    return (st > dr);
}

bool cmp2(int st, int dr) {
    return (st < dr);
}

A comparator should only return true when the first argument must be placed before the second argument in the sort. If they return true for equal arguments then some algorithms are going to get into a loop endlessly swapping equal elements.

Second time I've seen this question today.

STL Sort - Debug Assertion Failed

1 Answers1