在網路上看到這個問題, 其實很有趣, 要仔細檢查才會發現問題, 我把它簡化成近似的版本如下：
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 型別, 必須滿足嚴格的弱排序關係, 也就是：
-
comp(a, a)一定是false。 - 若
comp(a, b)為true, 那comp(b, a)就一定是false。 - 若
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)