Myujth

I have the following simple program. In test1 and test2 I tried to sort 2 strings "2" and "1", and in the example below, the function compare will always return false.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>

static inline bool compare(const std::string& a, const std::string& b)

 if (isdigit(b[0]))
 return false;

 assert(isdigit(a[0]));
 return true;


static inline void test1()

 std::cout << "test1:n";
 std::vector<std::string> arr = 
 "2", "1"
 ;
 std::stable_sort(arr.begin(), arr.end(), compare);
 for (auto e: arr)
 std::cout << e << std::endl;


static inline void test2()

 std::cout << "test2:n";
 std::vector<std::string> arr = 
 "1", "2"
 ;
 std::stable_sort(arr.begin(), arr.end(), compare);
 for (auto e: arr)
 std::cout << e << std::endl;


static inline bool compare_int(const int& a, const int& b)

 return a > b;


static inline void test3()

 std::cout << "test3:n";
 std::vector<int> arr = 
 9, 3, 13, 7
 ;
 std::stable_sort(arr.begin(), arr.end(), compare_int);
 for (auto e: arr)
 std::cout << e << ' ';
 std::cout << std::endl;


int main()

 test1();
 test2();
 test3();

 return 0;

However, I get the following output

test1:
2
1
test2:
1
2
test3:
13 9 7 3 

I'm confused, because as far as I know, the compare function in test1 and test2 will return false, which indicates that these 2 elements should swap their location. But obviously, they do not change and are still in their original location.

Am I misinterpreting the return value of compare function? But in test3 it is indeed sorted in descending order.

I don't quite understand its internals, does it treat characters in a different way from integers?

I'm going to answer my own question but many thanks to PaulMckenzie for his help in the discussion and Victor Istomin's answer.

It turns out that sort does not work in the way I thought it should be. It expects strict-weak-order, which means a > b and b > a cannot be true at the same time, otherwise the behavior is undefined. Also, its way to judge if 2 elements equal is using !(a < b) && !(b > a) because it only uses the < operator instead of == operator.

The mistake in my code is that I always return false in this case, so that the expression !(a < b) && !(b > a) will be true, and sort considers them to equal, thus not swapping them.

The right solution as PaulMckenzie points out, is using stable_partiion (or partition if relative order is not needed). The principle is to use sort only when we have clear rule of comparing elements, if we just want to group same elements together, partition is good.

It seems I had some false delusions about sort function, thanks for pointing out.

----------------- update ----------------

Caleth points out in the comment that the strict-weak-order is not enforced, but the behavior will be undefined if violated. Updated my description of that part. Thanks.

It looks like 'compare' works exactly as you wrote: returns false if first char of second string is digit.

By the way, this compare function won't work as expected (whatever you expect from it, I have no idea) in general case. In C++, sort comparator should implement strict weak ordering. In other words, there should be no case when 'a < b' and 'b < a' at the same time.