使用自定义排序函数对向量中的字符串进行排序时出现分段错误<string>

Question

我正在尝试对包含字符串的向量进行排序。我有以下主要功能代码

int size;
cin >> size;
vector<string> s;
cout << "READ" << endl;
for (int i = 0; i<size; i++)
{
    string str;
    cin >> str;
    s.push_back(str);
}
cout << "READ" << endl;

cout << "Passed" << endl;
sort(s.begin(), s.end(), comp);

for (int i = 0; i<size; i++)
{
    string st = s.at(I);
    cout << st << endl;
}


return 0;

comp函数代码为

bool comp(string s1, string s2)
{
    if (s1.empty() or s2.empty())
        return false;

    int l = s1.length();
    for (int i = 0; i<l; i++)
    {
        if (s1[i] > s2[i])
            return true;
    }
    return false;
}

但是对于这个输入我遇到了分段错误

46
lnpxeemwlqlzpxrmrmwbseqfnpkzaafdnukixaopcfvhqw
dhfhhoyhhzleldljmirjbqagcleivzomlpanqzsmqnrzij
zcsrvgqlmrgknqhwtcqzyldjanlczysnspvusziqtazjlu
idiknfqdygrwhvdzperlvgueqhuezsrwzztlodqgipnqzb
zjfyxbghvdecpzhvoxzojcpciaspyoeaetimmoccjqxtmv
mxwnhdyjutecwbrxdjmrbdjvbzprgnekvnvhxnuvekoflo
jjbjxzuaafatzdwlnzcorkiagrwzvrmjqqbdlmgyewzsea
bmvyqojhnbfrypiiwvtgifmqqdcuilohbfvkqjhlcwsfyo
zrbjhsrxnllmsdfqurkjfomwsvgfepwttohojxmrhexpmy
hcdxtucpeptgqhckpdxdcgpvhkiuucvwbuhtmbskqdlasw
rtocxkyrsrbluwvpfkekqkdwncvozfgmcrswpksiqmfnnl
xawlpinqjstxvrqvsugbvszhibbcmbdwktgwjlezakyqrr
cfghwolkahdafrcuufklziipmtkhuxdrxqlavcrxavxuas
plcsutiemkgfunhpyeiuvxwjppzsopglcyhgidsyhjnutp
vyyrbmfyfwpcowlpytmkvsyrzgiausrulsxtwysjgpgtqi
bsoknggdytplubxzjczatotnpovriwibeamjfnyxibvama
imkshtavbjpnkafuxwbzpiqlnnotrxmjepzeuwtuewtqab
ttjzqrcdcofkljaevmauexsxlkrxuanxgrsmsrxckixpoz
aocndkatjggduuyiksgmovthyoomrfsaxlnjouszxxoqtc
ahmkgizkvsbrqyricbtnpvpnibvgvnnrnqphkstvcjsbli
biasqbcofwdgabnipodjkriiyqlhaddpegkmydutcyoksk
avyaodwtgbdsnhheoearlinfcadeteiiudobbvqdqizcry
mhdekyvubghealrenyshjcjuhxxzimsgvukcdfdbjramzq
ayrzjanrebdgowsngullkgyvlgqzjexebleigxvgwjnbyf
vcpnclkhoawabjlhfnrncxfswjjmpxqcwoeqpyaitwdrjf
ghngenuvshwuaubahlzazwmgnsmtzyqfvvoxnhiufhxpac
ljrwslmgjilvdommuvpebcznjalxuazyujtzpewdbxjnwj
jqirnjnheowbioheyleyhkrcyfxuweyipumfojetmvomuz
vnnlsozyplofqkxfwcmlyntfrhspvbscocodlejqrymdeu
lgjcimksyragrhhagkmlnaysfxzswxfkhqzrhjlgkemmhp
weoxhopddcyiiikwblqvvcxcuxkebhywdacpmjrlkosxmw
bwcxxsytqdpybjxyqgmggitkgpkiytnwprsnxrygryxigo
qtwyleqxqflmaudekmdmgscfvjfwkchacxmokxrcfgwnhl
dgcmvhgnzigmrxougsbhwdhugyvloaqlliybbzkttmolln
jqmrfoyhwxbiyvzntvxozfswwjbeybahggfjrrzzhbapyi
oxbjadgrttqnfbevqolflhdpmgwgudhwfeebauqhhygvnt
kwmqirrljycddqcvjanibiarpcjjqiuvkdbdyzogbcixah
yyykebcfsnixcjdbkxtqvqynafmtuvoepeayiaqinvmjen
lsyxwgpfxlfkxckzsjzonxkhullkatmnwwfuicgjzbnvzf
vihglfapunknuitwtcxzdwjyfwqurvsydacylgcyohrbou
olmojrovoqseuqausssdupqzhbmyblomlbbqzwgbtgyiwq
tcshhbdgxsrtxywgqahqfimbnckwdhtbzlpwevuqjyqrbd
vjmcknagopzpwrmrianbgyhyginqduwdfjgmdqttcqroof
srmfsjigydlqlgsmvgqddpqmqkjzptzwdfpjmpnvgaezlx
yphbhtrmqcnrfklqmkblvginnhxxtlnnwcfuwujdqwkvaq
jahvrihhicrqvttmdzwbemjjqnstvtudvifdvrbjxalirj

对于很多其他输入它给出了正确的结果但是对于上面的结果我得到了这个结果

READ
READ
Passed

我搜索了很多，但找不到我的 comp 函数中的错误。

Answer 1

这个条件：

 if (s1.empty() or s2.empty())
    return false;

不满足 comp 函数的严格弱排序要求（来自 https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings）

If x < y, then for all z, either x < z or z < y or both.

在你的例子中，如果 z 是空字符串而 x 和 y 不是，它既不满足 x < z 也不满足 z < y

可能的实现是：

if( s2.empty() ) return !s1.empty();
if( s1.empty() ) return false;

但我不明白为什么你不能使用 std::greater std::string::compare 或 std::string::operator>() 而不是手动实施

Answer 2

你的补偿方法有问题。

对于这两个字符串 "ac" 和 "ca"，comp("ac", "ca") 与 comp("ac", "ca") 一样为真。因为你在 s1[i] < s2[i] 时尝试下一个位置，而你应该 return 立即为 false。

正如您在评论中所说，您应该使用较短的长度来处理不同长度的字符串，以避免访问过去的字符串长度时出错。

所以你的comp方法应该是：

bool comp(string s1,string s2)
{
    // empty string comes last
    if(s1.empty()) return false;
    if(s2.empty()) return true;

    // limit to shorter string length
    unsigned int l = s1.length();
    if (s2.length() < l) l = s2.length();
    for(unsigned int i=0;i<l;i++)
    {
        // if chars are different at position i return immediately
        if(s1[i] > s2[i])
            return true;        
        if(s1[i] < s2[i])
            return false;        
    }
    // shorter string comes last
    return(s1.length() >= s2.length());
}

Answer 3

正如其他人所指出的，您的比较功能 is/was 已损坏。

下面是一个使用 std::greater<std::string>() 作为比较函数的例子：

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

int main() {
    int size;
    if (!(std::cin >> size)) return -1;

    std::vector<std::string> v;
    for (int i = 0; i < size; i++) {
        std::string str;
        if (!(std::cin >> str)) return -1;
        v.push_back(str);
    }

    std::sort(v.begin(), v.end(), std::greater<std::string>());

    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i] << std::endl;
    }

    return 0;
}

输出按降序排列（test.txt 包含以上输入）：

$ g++ test.cc && ./a.out < test.txt
zrbjhsrxnllmsdfqurkjfomwsvgfepwttohojxmrhexpmy
zjfyxbghvdecpzhvoxzojcpciaspyoeaetimmoccjqxtmv
zcsrvgqlmrgknqhwtcqzyldjanlczysnspvusziqtazjlu
yyykebcfsnixcjdbkxtqvqynafmtuvoepeayiaqinvmjen
yphbhtrmqcnrfklqmkblvginnhxxtlnnwcfuwujdqwkvaq
xawlpinqjstxvrqvsugbvszhibbcmbdwktgwjlezakyqrr
weoxhopddcyiiikwblqvvcxcuxkebhywdacpmjrlkosxmw
vyyrbmfyfwpcowlpytmkvsyrzgiausrulsxtwysjgpgtqi
vnnlsozyplofqkxfwcmlyntfrhspvbscocodlejqrymdeu
vjmcknagopzpwrmrianbgyhyginqduwdfjgmdqttcqroof
vihglfapunknuitwtcxzdwjyfwqurvsydacylgcyohrbou
vcpnclkhoawabjlhfnrncxfswjjmpxqcwoeqpyaitwdrjf
ttjzqrcdcofkljaevmauexsxlkrxuanxgrsmsrxckixpoz
tcshhbdgxsrtxywgqahqfimbnckwdhtbzlpwevuqjyqrbd
srmfsjigydlqlgsmvgqddpqmqkjzptzwdfpjmpnvgaezlx
rtocxkyrsrbluwvpfkekqkdwncvozfgmcrswpksiqmfnnl
qtwyleqxqflmaudekmdmgscfvjfwkchacxmokxrcfgwnhl
plcsutiemkgfunhpyeiuvxwjppzsopglcyhgidsyhjnutp
oxbjadgrttqnfbevqolflhdpmgwgudhwfeebauqhhygvnt
olmojrovoqseuqausssdupqzhbmyblomlbbqzwgbtgyiwq
mxwnhdyjutecwbrxdjmrbdjvbzprgnekvnvhxnuvekoflo
mhdekyvubghealrenyshjcjuhxxzimsgvukcdfdbjramzq
lsyxwgpfxlfkxckzsjzonxkhullkatmnwwfuicgjzbnvzf
lnpxeemwlqlzpxrmrmwbseqfnpkzaafdnukixaopcfvhqw
ljrwslmgjilvdommuvpebcznjalxuazyujtzpewdbxjnwj
lgjcimksyragrhhagkmlnaysfxzswxfkhqzrhjlgkemmhp
kwmqirrljycddqcvjanibiarpcjjqiuvkdbdyzogbcixah
jqmrfoyhwxbiyvzntvxozfswwjbeybahggfjrrzzhbapyi
jqirnjnheowbioheyleyhkrcyfxuweyipumfojetmvomuz
jjbjxzuaafatzdwlnzcorkiagrwzvrmjqqbdlmgyewzsea
jahvrihhicrqvttmdzwbemjjqnstvtudvifdvrbjxalirj
imkshtavbjpnkafuxwbzpiqlnnotrxmjepzeuwtuewtqab
idiknfqdygrwhvdzperlvgueqhuezsrwzztlodqgipnqzb
hcdxtucpeptgqhckpdxdcgpvhkiuucvwbuhtmbskqdlasw
ghngenuvshwuaubahlzazwmgnsmtzyqfvvoxnhiufhxpac
dhfhhoyhhzleldljmirjbqagcleivzomlpanqzsmqnrzij
dgcmvhgnzigmrxougsbhwdhugyvloaqlliybbzkttmolln
cfghwolkahdafrcuufklziipmtkhuxdrxqlavcrxavxuas
bwcxxsytqdpybjxyqgmggitkgpkiytnwprsnxrygryxigo
bsoknggdytplubxzjczatotnpovriwibeamjfnyxibvama
bmvyqojhnbfrypiiwvtgifmqqdcuilohbfvkqjhlcwsfyo
biasqbcofwdgabnipodjkriiyqlhaddpegkmydutcyoksk
ayrzjanrebdgowsngullkgyvlgqzjexebleigxvgwjnbyf
avyaodwtgbdsnhheoearlinfcadeteiiudobbvqdqizcry
aocndkatjggduuyiksgmovthyoomrfsaxlnjouszxxoqtc
ahmkgizkvsbrqyricbtnpvpnibvgvnnrnqphkstvcjsbli

供参考：

使用自定义排序函数对向量中的字符串进行排序时出现分段错误<string>

segmentation fault while using custom sorting function to sort strings in a vector<string>

c++

sorting

stl

stdvector