std::stable_sort 对比 std::sort

Question

https://leetcode.com/problems/largest-number/

我在解决上述问题的时候遇到过std::sort()报错的情况，换成std::stable_sort()就没有报错了。为什么？

行用右边的箭头符号突出显示

代码：

class Solution {
public:
    string reverse(string str)
    {
        int n=str.length();
        for(int i=0;i<n/2;i++)
        {
            swap(str[i],str[n-i-1]);
        }
        return str;
    }

    static bool comp(string s1,string s2)
    {
        int min_val=min(s1.length(),s2.length());
        int i=0;
        bool flag=false;
        for(;i<min_val;i++)
        {
            if((s1[i]-'0')==(s2[i]-'0'))
            {
                flag=true;
                continue;
            }

            return (s1[i]-'0')>(s2[i]-'0');
        }

        if(flag==true && s1.length()==s2.length())
        {
            return s1==s2;
        }

        string s1_temp=s1;
        string s2_temp=s2;
        s1_temp+=s2;
        s2_temp+=s1;

        return s1_temp>s2_temp;
    }

    string largestNumber(vector<int>& nums)
    {
        string str="";
        vector<string> inp;

        for(int i=0;i<nums.size();i++)
        {
            string temp="";
            long long int num=nums[i];
            if(num!=0)
            {
                while(num!=0)
                {
                    temp+=((num%10)+'0');
                    num/=10;
                }
            }
            else
            {
                temp+=(num+'0');
            }

            inp.push_back(reverse(temp));
        }

        stable_sort(inp.begin(),inp.end(),comp); // <-- This Line

        string res="";

        for(int i=0;i<inp.size();i++)
        {
            res+=inp[i];
        }
        cout<<"yes"<<endl;
        if(res[0]=='0')
        {
            return "0";
        }

        return res;
    }
};

测试用例：

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

任何人都可以告诉我发生这种情况的原因吗？

Answer 1

这实际上是一个非常有趣的错误！我没有测试过这是否是 leetcode 特定问题，但是运行这段代码在 leetcode 上使用 sort()，我们得到以下错误：

Line 431: Char 55: runtime error: pointer index expression with base 0xbebebebebebebebe overflowed to 0x7d7d7d7d7d7d7d7c (basic_string.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/basic_string.h:440:55

这似乎表明我们运行由于某种原因内存不足。该代码适用于 stable_sort() 但不适用于 sort() 的事实表明这可能与 "stable_sort preserves the relative order of the elements with equivalent values" (http://www.cplusplus.com/reference/algorithm/stable_sort/).

这一事实有关

相关的代码行在这里

if(flag==true && s1.length()==s2.length())
{
    return s1==s2;
}

确实，如果我们将其更改为

if(flag==true && s1.length()==s2.length())
{
    return s1!=s2;
}

这不会影响结果，因为如果此时 flag == true 和两个字符串的长度相同，那么它们都是等价的，并且交换字符串位置不会影响结果。

但是我们绕过了这个错误。 @Vikram Keswani 我希望这能解决您的问题。就我个人而言，我也会将 comp() 函数中的代码替换为 return s1 > s2;，它应该提供与您拥有的代码相同的行为。

p.s。我将把拼图的碎片留在这里，但是如果有经验的人（或者当我找到更多时间）想进一步调查这个神秘的记忆问题，那就太好了。

顺便说一句，在 leetcode 上重现此错误所需的最小长度输入是 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]，即 17 个 0（一个奇怪的数字）。

std::stable_sort 对比 std::sort

std::stable_sort vs std::sort

c++

sorting

string

stl

stable-sort