时间戳

首页 > 解决方案 > 为什么用户定义的函数不按给定的顺序对相同长度的元素进行排序？

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

问题描述

我的任务是按长度递增的顺序对字符串中的单词进行排序，对于相同长度的单词，我必须将它们保持在给定的顺序中。例如：“to be or not to be”将变成“to be or to be”。我首先制作字符串中所有单词的向量“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 aszqnvruah hrsaebveez w”

但正确的输出应该是：“Kry hkbwx ubogo xqpqd jlhvvd qcuucx xmwohi qvzegb qsvqskq llwzeug ipwbapd cqwfypww dyphntfz tuqppyipb dkvhhgecd wfwnphmxoa sbdfmnyeim hrsaebveez aszpefvrughr mlghuuwvec”

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

它应该给出：hkbwx ubogo xqpqd。

但它给出：xqpqd ubogo hkbwx。

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

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

但这会引发运行时错误。

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

标签： c++stringsortingvector

解决方案

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>位置的容器，则可以使用自定义比较器。second但是，我认为使用std::stable_sort更简单。

推荐阅读