función de ordenación C++ falla de segmentación

Question

En este código, para el tamaño del vector, n> = 32767, da error de segmentación, pero hasta 32766, funciona bien. ¿Cuál podría ser el error? Este es el código completo.

#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

Esto puede estar relacionado con el fallo de segmentación, pero ...

En C++, el predicado "comparar" debe ser un strict weak ordering. En particular, "compare (X, X)" debe devolver "falso" para cualquier X. En su función de comparación, si ambos pares son idénticos, se aplica la prueba (p1.first <= p2.first), y se devuelve "verdadero". Por lo tanto, este predicado de "comparación" no impone un orden débil estricto, y el resultado de pasarlo a "ordenar" no está definido.

Answer 2

Trate de usar todos los valores de n = 32766 hasta 32770. Sospecho que descubrirá que está experimentando algún tipo de desbordamiento. Esto se debe a que 2^15 (32768) es el número más grande que puede representarse utilizando 16 bits (suponiendo que también permita números negativos). Deberá usar un tipo de datos diferente.

Sugerencia:

conseguir que la salida maxsize del vector:

cout << p.max_size(); 

vamos a saber lo que hace. Como todo es normal, espero que sea de cientos de millones (536870911 en mi computadora). Pero si se parece más a 32768, ese podría ser el problema.