segmentation fault because of comparison function

Question

I tried solving this probblem on spoj. http://www.spoj.com/problems/BUSYMAN/

Although I was able to solve it but I got a very strange error. I tried understanding the cause of it but failed. I have two codes.

///////////////////////////////////////////////////

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class activity
{
    public:
    int start,end;
};

bool comp(activity p, activity q)
{
    if(p.end<q.end)return true;
    if(p.end==q.end&&p.start<=q.start)return true;
    return false;
}

int main()
{
    int t;
    cin>>t;
    vector<activity> v;
    for(int i=0;i<t;i++)
    {
        int n;
        cin>>n;

        v.resize(n);
        for(int j=0;j<n;j++)cin>>v[j].start>>v[j].end;
        sort(v.begin(),v.end(),comp);
        int ans=0,currend=0;
        for(int j=0;j<n;j++)
        {
            if(v[j].start>=currend){ans++;currend=v[j].end;
        }

    }
    cout<<ans<<endl;
    }
}

/////////////////////////////////////////////

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class activity
{
    public:
    int start,end;
};

bool comp(activity p, activity q)
{
    if(p.end<q.end)return true;
    if(p.end==q.end&&p.start>=q.start)return true;
    return false;
}

int main()
{
    int t;
    cin>>t;
    int n;
    vector<activity> v;
    for(int i=0;i<t;i++)
    {
        cin>>n;
        v.resize(n);
        for(int j=0;j<n;j++)
            cin>>v[j].start>>v[j].end;
        sort(v.begin(),v.end(),comp);
        int ans=0,currend=0;
        for(int j=0;j<n;j++)
        {
            if(v[j].start>=currend)
            {
                ans++;currend=v[j].end;
            }
        }
        cout<<ans<<endl;
    }
}

//////////////////////////////

My problem is that the first one gives segmentation fault on spoj while second one does not. The only difference between the two is the comparison function. I just happen to define the second statement of the comparison function in two different ways which are similar. But it gives me segmentation fault in the first case but not in second case.

enter image description here

In the two images above there are two codes with respective submission ids and in the third it shows seg fault for one while not for other. You can verify with the submission ids on my spoj profile as well.

Danh · Accepted Answer · 2015-12-24T10:41:35.337

5

Because bool comp(activity p, activity q) doesn't meet requirements of Compare see std::sort

It should be this:

bool comp(const activity& p, const activity& q)
{
    return p.end < q.end || (p.end ==q.end && p.start < q.start);
}

or

struct comp {
    bool operator()(const activity& p, const activity& q) const
    {
        return p.end < q.end || (p.end ==q.end && p.start < q.start);
    }
};

or

struct comp {
    bool operator()(const activity& p, const activity& q) const
    {
        return std::tie(p.end, p.start) < std::tie(q.end, q.start);
    }
};

edited Dec 24 '15 at 10:41

answered Dec 24 '15 at 02:37

Danh

5,916
7
30
45

But it works in the second case. which is similar to the first case except for the comparison operator in second line. I have been using it in similar manner for a long time and it always works. Except for the comparison operator in second line of the function everything is same but one works while other does not. Can you please tell why it works in the second case. – Akash Garg Dec 24 '15 at 03:19
For me, both 2 of yours work fine. The standard doesn't say anything about the behavior if `Compare` doesn't induce a strict weak ordering on the values. – Danh Dec 24 '15 at 03:47
@M.M Can you point out which statement in standard said that it's undefined behavior? – Danh Dec 24 '15 at 04:00
Have you tried on spoj. On my pc it works fine but give segmentation fault on spoj only. On my pc both of them gives correct answer. But one gives segmentation fault on spoj while other doesn't. – Akash Garg Dec 24 '15 at 06:39
@AkashGarg No, I haven't. However, if the comparer is strict weak ordering, the `std::sort` should work fine – Danh Dec 24 '15 at 06:41
It works fine for non-strict weak ordering as well. But just doesn't works in case of one side while works for other. And the code gives no error on my pc atleast. But it gives on spoj. – Akash Garg Dec 24 '15 at 06:48
When your code don't follow standard strictly, compiler is free to behave. It's depended on which kind of algorithm your compiler used to sort. We don't know which compiled used by spoj, hence we don't know what happen then – Danh Dec 24 '15 at 06:52

score 0 · Answer 2 · edited May 23 '17 at 10:34

0

The rules of C++ are that the comparator for std::sort must give a strict weak ordering.

So, the comparator must return false for equal elements. However this test:

if(p.end<q.end)return true;
if(p.end==q.end&&p.start<=q.start)return true;
return false;

returns true if the elements are equal, so this is an invalid comparator.

In your second attempt:

if(p.end<q.end)return true;
if(p.end==q.end&&p.start>=q.start)return true;
return false;

This has the same problem, also causing undefined behaviour.

You can't infer anything from the observed behaviour when the code had undefined behaviour, it is just chance (perhaps depending on some detail about your compiler's particular choice of sort algorithm) as to what behaviour you get.

Changing <= to < in the first comparator would yield a valid comparator with sort order of both end and start ascending.

edited May 23 '17 at 10:34

Community

1
1

answered Dec 24 '15 at 03:52

M.M

138,810
21
208
365

I have seen in the past a compiler giving a warning when the comparator was invalid, but can't find anything about it now – M.M Dec 24 '15 at 03:58
But the second attempt works. That is the explanantion I am asking for. Why is the second working. If none of them works then clearly I wouldn't have asked for it. I would have gone straight for strict weak ordering. – Akash Garg Dec 24 '15 at 06:50
@AkashGarg when [undefined behaviour](http://stackoverflow.com/a/4105123/1505939) occurs, anything can happen – M.M Dec 24 '15 at 07:04

segmentation fault because of comparison function

2 Answers2