std::sort(stable_sort)比较函数返回值的混乱结果

Question

我有以下简单的程序。在test1和test2中，我尝试对两个字符串"2"one_answers"1"进行排序，在下面的示例中，函数compare将始终返回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函数将返回false，这表明这两个元素应该交换它们的位置。但很明显，它们并没有改变，仍然在原来的位置。

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

我不太了解它的内部结构，它对待字符的方式与整数不同吗？

Answer 1

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

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

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

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

我似乎对分类功能有一些错误的错觉，谢谢你的指出。

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

Caleth在评论中指出，严格的弱命令没有得到执行，但如果违反，行为将是不明确的。更新了我对该部分的描述。谢谢

Answer 2

看起来"compare"与您所写的完全一样：如果第二个字符串的第一个字符是数字，则返回false。

顺便说一句，这个compare函数在一般情况下不会像预期的那样工作(不管你对它有什么期望，我都不知道(。在C++中，排序比较器应该实现严格的弱排序。换言之，当‘a<b'和'b<a’同时。