提问者:小点点

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


我的任务是按照长度的递增顺序对字符串中的单词进行排序,对于相同长度的单词,我必须按照给定的顺序进行排序。 “to be or not to be”将变成“to be or to be not”。 我首先对字符串中的所有单词创建一个向量'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 sbdfmnyeim xpefyglstj mlghuuwvec aszqnvruhr hrsaebveez wfwnphmxoa”

但正确的输出应该是:“kry hkbwx ubogo xqpqd jlhvvd qcuucx xmwohi qvzegb qsvqskq llwzeug ipwbapd cqwfypww dyphntfz tuqppyipb dkvhhgecd wfwnphmxoa sbdfmnyeim hrsaebveez aszqnvruhr mlhuuwvec xpefyglstj”

参见位置1,2和3(使用0索引)。

它应该给出:hkbwx ubogo XQPQD。

但它给出了:xqpqd ubogo hkbwx。

这使我认为它不是按照给定的顺序对相同长度的单词进行排序。 你可以找到许多其他位置发生这种情况(例如:4,5,6和7)。

但是对于字符串“leetcode plus try suck geaser is cool best”,它给出的正确输出是:“is try plus suck 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;
}

但这会引发运行时错误。

很抱歉把问题弄得一团糟,但我真的很想弄明白这一点。


共1个答案

匿名用户

std::sort不稳定,即不一定保留等价元素的顺序。 如果您从std::sort中得到稳定的排序,那么这只是偶然。 稳定排序的开销更大(O(N·log(N)^2)vsO(N·log(N))),因此您必须显式地要求它。 可以使用std::stable_sort来完成。

如果要填充std::pair的容器,其中second是原始容器中的索引,则可以将std::sort与自定义比较器一起使用。 但是,我认为使用std::stable_sort更简单。