Error : malloc():memory corruption in Comparison function for sort

Question

The following code is to print the largest number from a list of integers. I am getting:

 *** Error in `./a.out': malloc(): memory corruption: 0x0000000000bfe070 ***

on the list (20 zeros):

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

However in the above if I put some non zero elements I do not get the error.

This is my code for the comparison function :

bool comp(int a,int b)
{
     if(a == b)
         return true;
     stringstream ss;
     ss << a;
     string a1 = ss.str();
     stringstream sss;
     sss << b;
     string b1 = sss.str();
     int i = 0;
     int l1 = a1.length();
     int l2 = b1.length();
     while(i < l1 && i < l2)
     {
         if(a1[i] > b1[i])
             return true;
         if(a1[i] < b1[i])
             return false;
         i++;
     }
     if(l1 == l2)
         return true;
     if(l1 < l2)
         if(b1[l1] > a1[0])
             return false;
         else
             return true;
     else
         if(a1[l2] > b1[0])
             return true;
         else
             return false;
}

I am using the stl

 sort(nums.begin(),nums.end(),comp);

where nums is a vector of integers.

EDIT 1 :

This is the entire code:

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

using namespace std;
bool comp(int a,int b)
{
if(a == b)
    return true;
stringstream ss;
ss << a;
string a1 = ss.str();
stringstream sss;
sss << b;
string b1 = sss.str();
int i = 0;
int l1 = a1.length();
int l2 = b1.length();
while(i < l1 && i < l2)
{
    if(a1[i] > b1[i])
        return true;
    if(a1[i] < b1[i])
        return false;
    i++;
}
if(l1 == l2)
    return true;
if(l1 < l2)
    if(b1[l1] > a1[0])
        return false;
    else
        return true;
else
    if(a1[l2] > b1[0])
        return true;
    else
        return false;
}
void largestNumber(vector<int>& nums)
{

sort(nums.begin(),nums.end(),comp);
/*string s = "";
vector<int>::iterator it = nums.begin();
while(it != nums.end())
{
    stringstream ss;
    ss << *it;
    s = s+ss.str();
    it++;
}
return s;*/
}



int main()
{
int n;
cin>>n;
vector<int> arr(n);
for(int i = 0;i<n;i++)
    cin>>arr[i];

largestNumber(arr);/*
string s = largestNumber(arr);
cout<<s<<endl;*/
}

Answer 1

Your comp function violates the strict weak ordering rule. Sort requires that the compare function should meet the strict weak ordering rule. If that promise is broken, so is the promise of std::sort to behave correctly. Infact when I compile this under MSVC (VS2015) I get a assertion failure that the compare function doesn't meets the ordering condition. For eg this line:

 if(a == b)
     return true;

clearly violates the condition. Check this post for more insights.

BTW if you just want to sort the integers in lexicographic order you can just do

bool comp(int a,int b)
{
    return to_string(a) < to_string(b);
}

If you want the equivalent of "bigger number first", just swap the < with >

Answer 2

I have used your comp function and created a sample case-study to examine the error. However, I didn't get any error for the array of zeros case. Please check sample program.

Error

However, below scenario causes run-time error.

// Pay attention: Array stores numbers in descending order.
// If we stored in ascending order, there won't be a problem.
for(int i=20; i>0; ++i)
    v.push_back(i);

I hope this would be helpful to find solution.

Sample program

#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <iterator>

using namespace std;

bool comp(int a,int b)
{
     if(a == b)
         return true;
     stringstream ss;
     ss << a;
     string a1 = ss.str();
     stringstream sss;
     sss << b;
     string b1 = sss.str();
     int i = 0;
     int l1 = a1.length();
     int l2 = b1.length();
     while(i < l1 && i < l2)
     {
         if(a1[i] > b1[i])
             return true;
         if(a1[i] < b1[i])
             return false;
         i++;
     }
     if(l1 == l2)
         return true;
     if(l1 < l2)
         if(b1[l1] > b1[l1-1])
             return false;
         else
             return true;
     else
         if(a1[l2] > a1[l2-1])
             return true;
         else
             return false;
}

int main(int argc, const char *argv[])
{
    vector<int> v;
    for(int i=0; i<20; ++i)
        v.push_back(0);
    sort(v.begin(), v.end(), comp);
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    return 0;
}