algorithm - c++ std::sort 意外行为(运行时错误)

Question

谁能告诉我为什么 std::sort 会出现这种意外行为。

此代码给出运行时错误

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

inline bool compare(string a, string b){
    return a.size() <= b.size();
}

int main(){

        int n = 100;

        string a = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

        vector<string>v;
        for(int i=0; i<n; i++){
            v.push_back(a);
        }

        sort(v.begin(), v.end(), compare);

}

但是当我替换 return a.size() <= b.size(); 时与 return a.size() < b.size(); ，它工作得很好。

Answer 1

比较函数不满足使用std::sort 排序对象的要求.改成

inline bool compare(string a, string b){
    return a.size() < b.size(); // Not <= just <
}

为什么使用 <=不工作？

向量的所有元素都是大小相等的字符串。因此，我们的排序工作方式几乎与对数字列表进行排序相同。

给定两个数字，std::sort必须弄清楚一个小于另一个、大于另一个还是相等。

给定n1和 n2 ,

1. 如果comp(n1, n2)返回 true , 然后 n1小于 n2 .
2. 如果comp(n1, n2)返回 false和 comp(n2, n1)返回 false , 然后 n1等于n2 .
3. 如果comp(n1, n2)返回 false和 comp(n2, n1)返回 true , 然后 n1大于 n2 .

如果您使用 <=在比较函数中，comp(n1, n2)返回 true 和 comp(n2, n1)返回 true .鉴于此，排序算法根本无法对您的对象进行排序，并在尝试这样做时进入无限递归。