时间戳

首页 > 解决方案 > C++ stable_sort 不稳定？

c++ - C++ stable_sort 不稳定？

问题描述

我正在使用 C++ stable_sort 使用比较器函数按升序对类对象的向量进行排序，但排序不稳定。一个可行的解决方法是反向迭代并反转比较器中的逻辑。但无法理解为什么它不应该正常工作。代码：

using namespace std;
class Pair{
    string str;
    int num;
public:
    Pair(string s, int n):str(s), num(n)
    {}
    Pair(const Pair &a)
    {
        str = a.str;
        num = a.num;
    }
    int Num()
    {
        return num;
    }
    string Str() const{
        return str;
    }
    void set(string s, int n)
    {
        str = s;
        num=n;
    }
    void print() const{
        cout<<"\n"<<num<<" "<<str;
    }
};

bool comparator( Pair a,  Pair b)
{
    return a.Num()<=b.Num();
}

int main() {
    int n;
    cin >> n;
    vector<Pair> arr;
    for(int a0 = 0; a0 < n; a0++){
        int x;
        string s;
        cin >> x >> s;
        if((a0+1)<=n/2)
            s="-";
        Pair p(s, x);
        arr.push_back(p);
    }
    cout<<"\n Before sort";
    for(auto i:arr)
        i.print();

    stable_sort(arr.begin(), arr.end(), comparator);
    cout<<"\n\n After sort";
    for(auto i:arr)
        i.print();

    return 0;
}

结果：在排序 0 - 6 - 0 - 6 - 4 - 0 - 6 - 0 - 6 - 0 - 4 之前 3 是 0 到 1 是 5 问题 1 或 2 不是 4 是 2 到 4

在排序 0 到 0 - 0 - 0 - 0 - 0 - 1 或 1 是 2 到 2 不是 3 是 4 后 4 是 4 那 4 - 5 问题 6 - 6 - 6 - 6 -

标签： c++stlstable-sort

解决方案

comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second.

from stable_sort. The comparator must implement a strict weak ordering. See also here for a table of the exact requirements.

Your comparator is wrong, it also returns true for equal elements.

推荐阅读