ошибка сегментации из-за функции сравнения

Question

Я пробовал решить эту проблему на спой. http://www.spoj.com/problems/BUSYMAN/

Хотя я был в состоянии решить проблему, но у меня была очень странная ошибка. Я попытался понять причину этого, но потерпел неудачу. У меня есть два кода.

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

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

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

Моя проблема заключается в том, что первый дает ошибку сегментации на spoj, а второй - нет. Единственная разница между ними - это функция сравнения. Я просто могу определить второй оператор функции сравнения двумя разными способами, которые похожи. Но это дает мне ошибку сегментации в первом случае, но не во втором случае.

введите описание изображения здесь

В двух изображениях выше, существует два кода с соответствующими идентификаторами представления и в третьем он показывает сегментный вину за один, а не для других , Вы также можете проверить с помощью идентификаторов представления в моем профиле spoj.

Answer 1

Поскольку bool comp(activity p, activity q) не отвечает требованиям Compare см std::sort

Это должно быть так:

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

или

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

или

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

Answer 2

Правила C++ заключаются в том, что компаратор для std::sort должен дать strict weak ordering.

Итак, компаратор должен вернуть false для равных элементов. Однако этот тест:

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

возвращает true, если они равны, так что это является недопустимым компаратор.

В вашей второй попытки:

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

Это та же самая проблема, которая также приводит к неопределенному поведению.

Вы не можете ничего сделать из наблюдаемого поведения, когда код имел неопределенное поведение, это просто шанс (возможно, в зависимости от некоторых деталей о конкретном выборе алгоритма сортировки вашего компилятора) относительно того, какое поведение вы получите.

Изменение <= до < в первом компараторе даст действительный компаратор с порядком сортировки обоих концов и начнется по возрастанию.