为什么用户定义的函数不按照给定的顺序对相同长度的元素进行排序？

Question

我的任务是按长度递增的顺序对字符串中的单词进行排序，对于相同长度的单词，我必须按照给定的顺序对它们进行排序。例如：“成为或不成为”将变成“成为或不成为”。我首先制作字符串中所有单词的向量“v”，然后尝试使用 C++ 的 sort() 函数中的用户定义函数对向量进行排序。这是我的代码：

#include <bits/stdc++.h>
using namespace std;
static bool comparelength(string first,string second){//function to compare length
    return first.size()<second.size();
}

int main() {
    string text="Jlhvvd wfwnphmxoa qcuucx qsvqskq cqwfypww dyphntfz hkbwx xmwohi qvzegb ubogo sbdfmnyeim tuqppyipb llwzeug hrsaebveez aszqnvruhr xqpqd ipwbapd mlghuuwvec xpefyglstj dkvhhgecd kry";
    vector<string> v;
    string cur="";
    text+=" ";
    

for(int i=0;i<text.size();i++){
        if(text[i]==32){//if space is encountered then the word is inserted in the vector
            v.push_back(cur);
            cur="";
        }
        else{
            cur+=text[i];//if not space then text[i] is added to the current word
        }
    }
    sort(v.begin(),v.end(),comparelength);//sort the vector
    for(int i=0;i<v.size();i++)
    cout<<v[i]<<" ";

现在它给出了这样的输出：“Kry xqpqd ubogo hkbwx qvzegb jlhvvd xmwohi qcuucx qsvqskq llwzeug ipwbapd dyphntfz cqwfypww tuqppyipb dkvhhgecd sbdfmnyqyfcyfwcvezrgrfmygrgrxfmnyqrgrxfwcyfwcyfwcyfwcyfwcyfwcyfwcygrfm

但正确的输出应该是：“Kry hkbwx ubogo xqpqd jlhvvd qcuucx xmwohi qvzegb qsvqskq llwzeug ipwbapd cqwfypww dyphntfz tuqppyipb dkvhhgecd wfwnphmdfmxugfwfwnphmdfmxuycf xmwohi qvzegb qsvqskq llwzeug

查看位置 1,2 和 3（使用 0 索引）。

它应该给出：hkbwx ubogo xqpqd。

但它给出：xqpqd ubogo hkbwx。

这让我认为它没有按照给定的顺序对相同长度的单词进行排序。您可以找到发生这种情况的许多其他位置（例如：4、5、6 和 7）。

但是对于字符串“leetcode plus try sell geaser is cool best”，它给出了正确的输出，即：“is try plus sell cool best geaser leetcode”

任何人都可以说清楚为什么它不适用于前一个字符串但适用于后者。我试过做

static bool comparelength(string first,string second){
    if(first.size()==second.size())
    return true;
    if(first.size()<second.size())
    return true;
    else
    return false;
}

但这会引发运行时错误。

抱歉让问题变得混乱，但我真的很想理解这一点。

Answer 1

std::sort是不稳定的，即不一定要保留等效元素的顺序。如果您从中获得稳定的排序，std::sort那么这只是偶然。稳定排序更昂贵（O(N·log(N)^2)vs O(N·log(N))），因此您必须明确要求它。可以用std::stable_sort.

std::sort如果您要填充原始容器中索引std::pair<std::string,size_t>where的容器，则可以使用自定义比较器second。但是，我认为使用std::stable_sort更简单。