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

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.

Answer 2

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.