使用std::less<char>作为比较器异常，自定义函数仍无效

你的问题出在gather_sort函数中逆序比较器的实现上，直接对comp_func取反的方式违反了std::stable_sort要求的严格弱序规则，导致排序行为异常。

为什么原实现无效？ #

以你传入的std::less<char>{}为例，!comp_func(a, b)等价于a >= b。这个表达式存在两个致命问题：

1. 违反不可反身性：当a == b时，!comp_func(a, b)返回true，但严格弱序要求比较函数对相同元素必须返回false；
2. 违反不对称性：如果a > b，那么!comp_func(a, b)和!comp_func(b, a)都会返回true，这不符合排序算法对比较逻辑的要求。

这两个问题会让std::stable_sort进入未定义行为，最终输出不符合预期的结果。

正确的实现方式 #

要生成有效的逆序比较器，应该交换比较函数的参数位置，而不是直接取反。对于严格弱序comp(a, b)，其合法的逆序逻辑是comp(b, a)——这相当于把排序规则完全反转，同时保持严格弱序的特性。

修正后的gather_sort函数如下：

template <typename It, typename F>
void gather_sort(It first, It last, It gather_pos, F comp_func)
{
    // 正确的逆序比较器：交换参数位置
    auto inv_comp_func = [&](const auto& a, const auto& b) {
        return comp_func(b, a);
    };
    std::stable_sort(first, gather_pos, inv_comp_func);
    std::stable_sort(gather_pos, last, comp_func);
}

修正后完整代码 #

#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <utility>

using namespace std;

template <typename It, typename F>
pair<It, It> gather(It first, It last, It gather_pos, F predicate)
{
    return { std::stable_partition(first, gather_pos, not_fn(predicate)),
             std::stable_partition(gather_pos, last, predicate) };
}

template <typename It, typename F>
void gather_sort(It first, It last, It gather_pos, F comp_func)
{
    auto inv_comp_func = [&](const auto& a, const auto& b) {
        return comp_func(b, a);
    };
    std::stable_sort(first, gather_pos, inv_comp_func);
    std::stable_sort(gather_pos, last, comp_func);
}

int main()
{
    auto is_a([](char c) { return c == 'a'; });
    string a{ "a_a_a_a_a_a_a_a_a_a_a" };

    auto middle(begin(a) + a.size() / 2);
    gather(begin(a), end(a), middle, is_a);
    cout << a << '\n';

    gather(begin(a), end(a), begin(a), is_a);
    cout << a << '\n';

    gather(begin(a), end(a), end(a), is_a);
    cout << a << '\n';

    // 现在这个调用会正常工作
    gather(begin(a), end(a), middle, is_a);
    cout << a << '\n';

    string b{ "_9_2_4_7_3_8_1_6_5_0_" };
    gather_sort(begin(b), end(b), begin(b) + b.size() / 2, std::less<char>{});
    cout << b << '\n';
}

新手注意事项 #

std::sort和std::stable_sort对比较函数有严格要求，必须满足严格弱序：

• 不能对自身返回true（不可反身性）；
• 如果comp(a,b)为true，则comp(b,a)必须为false（不对称性）；
• 传递性和等价传递性也要满足。

直接取反比较函数的方式几乎都会破坏这些规则，是排序时的常见误区。

内容的提问来源于stack exchange，提问作者MurodI