DEV Community

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

Posted on

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

執行以上的程式, 可能會因為無窮迴圈或是耗盡系統資源被強制結束。主要就是因為傳給 std::sortcomp 參數是 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) 就是 truestd::sort 是基於以上的規則設計的, 如果傳入的 comp 不符合以上規則, 就可能會導致本來把兩個項目對調順序, 之後卻又對調回來, 一直調來調去使得 std::sort 陷入無窮迴圈無法結束。只要滿足上述嚴格的弱排序關係, 就只會在有明確前後順序的情況下調動項目位置, 避免無窮無盡地調整順序了。

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

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More