sort function C++ segmentation fault

Question

In this code, for vector size, n >=32767, it gives segmentation fault, but upto 32766, it runs fine. What could be the error? This is full code.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<utility>
#include<algorithm>
#include<sys/time.h>
using namespace std;
#define MAX 100000

bool compare(pair<int,int> p1,pair<int,int> p2) {
    if(p1.second < p2.second)
     return 1;
    else if(p1.second > p2.second)
     return 0;
    if(p1.first <= p2.first)
     return 1;
    else
     return 0;
}

int main() {
    freopen("randomin.txt","r",stdin);
    int n;
    scanf("%d",&n);
    vector< pair<int,int> > p(n);
    for(int i=0;i<n;i++)
     scanf("%d%d",&p[i].first,&p[i].second);
    **printf("%d\n",(int)p.max_size()); // prints 536870911**
    sort(p.begin(),p.begin()+n,compare);

    //for(int i=0;i<n;i++)
     //printf("%d %d\n",p[i].first,p[i].second);
        printf("%.6f\n",(p[n-1].second+p[n-2].second)/(20.0+p[n-1].first+p[n-2].first));

    return 0;
}

Answer 1

Try using all the values from n = 32766 up to 32770. I suspect you'll find that you are experiencing some sort of overflow. This is because 2^15 (32768) is the biggest number that can be represented using 16 bits (assuming you also allow negative numbers). You will have to use a different data type.

Suggestion:

Get it to output the vector's maxsize:

cout << p.max_size();

Let us know what that does. All things being normal, I'd expect it to be in the hundreds of millions (536870911 on my computer). But if it's more like 32768, then that could be the problem.

Answer 2

This may be unrelated to your segmentation fault, but...

In C++, your "compare" predicate must be a strict weak ordering. In particular, "compare(X,X)" must return "false" for any X. In your compare function, if both pairs are identical, you hit the test (p1.first <= p2.first) , and return "true". Therefore, this "compare" predicate does not impose a strict weak ordering, and the result of passing it to "sort" is undefined.