DEV Community

Cover image for 傳給 std:sort 的比較函式注意事項
codemee
codemee

Posted on

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

#cpp

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

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;
}
Enter fullscreen mode Exit fullscreen mode

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

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

意義上就是在你期望的排列順序上 如果 a 絕對是排在 b 前面, 那 comp(a, b) 就是 true。std::sort 是基於以上的規則設計的, 如果傳入的 comp 不符合以上規則, 就可能會導致本來把兩個項目對調順序, 之後卻又對調回來, 一直調來調去使得 std::sort 陷入無窮迴圈無法結束。只要滿足上述嚴格的弱排序關係, 就只會在有明確前後順序的情況下調動項目位置, 避免無窮無盡地調整順序了。

剛剛看到的範例就是這樣的情況。由於是以 a >= b 為比較結果, 所以並不符合上述 1,2 項的條件, 只要改用 a > b 或是 a < b 即可。

Top comments (0)