CODEWITHSUNDEEP
c++segmentation-fault
Akash Garg
Akash Garg

Reputation: 51

segmentation fault because of comparison function

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 enter image description here

enter image description here enter image description here The codes

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.

Upvotes: 3

Views: 2073

Answers (2)

Danh
Danh

Reputation: 6016

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);
    }
};

Upvotes: 5

M.M
M.M

Reputation: 141628

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.

Upvotes: 0

Related Questions