std::stable_sort vs std::sort [repicate] [重复]。

Question

这个问题在这里已经有了答案:

是什么原因导致std::sort()访问地址超出范围？ (2个答案)

封闭 上月.

https:/leetcode.comproblemslargest-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;
    }
};

TestCase:

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

这其实是一个非常有趣的bug! 我还没有测试这是否是一个leetcode特有的问题，但是在运行这段代码时，用 sort() 在leetcode上，我们得到以下错误。

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保留了等值元素的相对顺序 "这一事实有关(http:/www.cplusplus.comreferencealgorithmstable_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（一个奇怪的数字）。