c++ - std::sort (stable_sort) 比较函数返回值的混淆结果

Question

我有以下简单程序。在 test1 和 test2 中，我尝试对 2 个字符串“2”和“1”进行排序，在下面的示例中，函数 compare 将始终返回错误。

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

但是，我得到以下输出

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

我很困惑，因为据我所知，test1 和 test2 中的 compare 函数将返回 false，这表明这 2 个元素应该交换它们的位置.但很明显，它们并没有改变，仍然在原来的位置。

我是否误解了比较函数的返回值？但是在test3中确实是降序排列的。

我不太了解它的内部结构，它处理字符的方式是否与整数不同？

Answer 1

我将回答我自己的问题，但非常感谢 PaulMckenzie 在讨论中提供的帮助以及 Victor Istomin 的回答。

事实证明排序并没有按照我认为应该的方式工作。它需要strict-weak-order，这意味着 a > b和 b > a 不能同时为真，否则行为未定义。另外，它判断2个元素是否相等的方法是使用!(a < b) && !(b > a)因为它只使用 <运算符而不是 ==运营商。

我的代码中的错误是在这种情况下我总是返回 false，所以表达式 !(a < b) && !(b > a)将为真，并且 sort 认为它们相等，因此不会交换它们。

正如 PaulMckenzie 指出的那样，正确的解决方案是使用 stable_partiion (或 partition 如果不需要相对顺序)。原则是只有当我们有明确的元素比较规则时才使用排序，如果我们只是想将相同的元素组合在一起，partition很好。

看来我对排序函数有一些错误的错觉，谢谢指出。

----------------更新----------------

Caleth 在评论中指出，strict-weak-order 并未强制执行，但如果违反，行为将是未定义的。更新了我对该部分的描述。谢谢。