Sort vs stable_sort and comparators.

[PankajAhuja]

I have an input vector of vectors as
I use sort with a comparator function as:

vector<vector<int> > numbers = {{3,3,4},{2,1,2},{2,2,8},{2,3,4},{5,5,6},{1,2,1},{4,4,5},{1,1,4},{2,2,3}}

bool compare(const vector<int> &a, const vector<int> &b) {
  return a[0] > b[0] && a[1] > b[1] && a[2] > b[2];
}
sort(numbers.begin(), numbers.end(), compare);

This gives me the output as
5 5 6
3 3 4
3 2 3
2 1 2
2 2 8
4 4 5
2 3 4
1 2 1
1 1 4
2 2 3

whereas

stable_sort(numbers.begin(), numbers.end(), compare);

returns this as the output
5 5 6
4 4 5
3 3 4
3 2 3
2 1 2
2 2 8
2 3 4
1 2 1
1 1 4
2 2 3

My understanding was if the compare function returns true it means that the first parameter of the compare function has to be placed before the second one.
I expected 4,4,5 to be the second entry in the result.
I've read about the weak ordering in sort vs stable_sort, but that would be for equivalent elements but in this case there are elements before 4,4,5 which if called as the second argument in the compare function with 4,4,5 would return true.

[Duthomhas]

Your comparitor is working as you wrote it: for example:

  5 5 6 > 3 3 4  (all LHS are strictly larger than corresponding RHS elements)

but

  3 3 4 ≤ 3 2 3  (not all LHS are strictly larger than corresponding RHS elements)

In other words, (3 3 4) and (3 2 3) do not have a strict less-than or greater-than ordering.

You need to rethink how you want the elements to sort if they are not ordering the way you would like.

Hope this helps.

[helios]

Your compare() function doesn't do what you probably intended. I suspect this is what you were looking for:

bool compare(const vector<int> &a, const vector<int> &b) {
    if (a[0] > b[0])
        return true;
    if (a[0] < b[0])
        return false;
    if (a[1] > b[1])
        return true;
    if (a[1] < b[1])
        return false;
    return a[2] > b[2];
}

You may be tempted to reorder and group the comparisons, but if you do the function will stop working.

[PankajAhuja]

@Duthomhas
that is exactly what i understood
for 4 4 5 vs 3 3 4 all lhs are strictly larger than rhs, so 4 4 5 should be before 3 3 4 in the result, right? this is the part that i do not understand.

@helios
this somehow works.
My intent of sort is that if element a as all values greater than the other element b then it should be before b in the final ordering, else i do not care what the ordering is.
That is why I expected 4 4 5 to be ahead of 3 3 4 or 3 2 3 or 2 1 2.

[helios]

My intent of sort is that if element a as all values greater than the other element b then it should be before b in the final ordering, else i do not care what the ordering is.

So, "any of the elements of x is greater than all of the elements of y" is equivalent to "x < y". The first statement is equivalent to "the maximum of x is greater than the maximum of y".

[PankajAhuja]

My intent of sort is that if element a as all values greater than the other element b then it should be before b in the final ordering, else i do not care what the ordering is.

I'll try to phrase it better.
If all corresponding elements of x are greater than corresponding elements of y then x should be placed before y ( x0 > y0 && x1 > y1 ...) else either can be placed before each other.

[helios]

I believe your sort criterion is missing transitivity of incomparability. For the sake of readability, let's say that x == y if !(x < y) && !(y < x). In a strict weak ordering, if x == y and y == z, then x == z must be true.
However, according to your function {2, 2, 2} == {1, 1, 2}, and {1, 1, 2} == {1, 1, 1}, but {2, 2, 2} < {1, 1, 1}.

[PankajAhuja]

@helios. Thanks for that explanation, turns out this was more of a maths query rather than a c++ one :). Also correct me if I am wrong here, since stable_sort also requires strict weak ordering, there would be cases where stable_sort would display result different than the one when using the compare function you suggested.

[helios]

Correct. Since the comparison function doesn't meet the requirements for the function, the function cannot guarantee any final result.