c++ - std::stable_sort 与 std::sort

Question

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





What causes std::sort() to access address out of range

(2 个回答)


1年前关闭。




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 特定的问题，但是使用 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.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(一个奇怪的数字)。