std::sort (stable_sort) 比较函数 return 值的混淆结果

Question

我有以下简单的程序。在 test1 和 test2 中，我尝试对 2 个字符串“2”和“1”进行排序，在下面的示例中，函数 compare 将始终 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;
}

但是，我得到以下输出

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

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

我是否误解了比较函数的 return 值？但是在test3里面确实是降序排列的

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

Answer 1

看起来 'compare' 与您写的完全一样：returns 如果第二个字符串的第一个字符是数字，则为 false。

顺便说一下，这个比较函数在一般情况下不会按预期工作（无论你期望它是什么，我都不知道）。在 C++ 中，排序比较器应该实现严格的弱排序。换句话说，不应该有 'a < b' 和 'b < a' 同时出现的情况。

Answer 2

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

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

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

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

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

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

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

std::sort (stable_sort) 比较函数 return 值的混淆结果

Confusing result of std::sort (stable_sort) compare function return value

c++

sorting

std

c++-standard-library