傳給 std:sort 的比較函式注意事項

在網路上看到這個問題, 其實很有趣, 要仔細檢查才會發現問題, 我把它簡化成近似的版本如下：

using namespace std;
#include <vector>
#include <algorithm>

static bool comp(const int &a, const int &b)
{
    return a >= b;
}

vector<int> nums = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

int main()
{
    sort(nums.begin(), nums.end(), comp);
    return 0;
}

執行以上的程式, 可能會因為無窮迴圈或是耗盡系統資源被強制結束。主要就是因為傳給 std::sort 的 comp 參數是 Compare 型別, 必須滿足嚴格的弱排序關係, 也就是：

1. comp(x, x) 一定是 false。
2. 若 comp(a, b) 為 true, 那 comp(b, a) 就一定是 false。
3. 若 comp(a, b) 是 true, 且 comp(b, c) 也是 true, 那 comp(a, c) 就一定是 true。

std::sort 是基於以上的規則設計的, 如果傳入的 comp 不符合以上規則, 就可能會導致 std::sort 陷入無窮迴圈無法結束, 剛剛看到的範例就是這樣的情況。由於是以 a >= b 為比較結果, 所以並不符合上述 1,2 項的條件, 只要改用 a > b 或是 a < b 即可。