CODEWITHSUNDEEP
c++sortingsegmentation-fault
avd
avd

Reputation: 14461

sort function C++ segmentation fault

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

Upvotes: 18

Views: 14047

Answers (3)

Jim Lewis
Jim Lewis

Reputation: 45115

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.

Upvotes: 72

moi
moi

Reputation: 537

Your overflow is possibly related to the stack overrun due to passing two vectors by value.

std::vector &vec - this is how you pass a vector by reference.

Change bool compare(pair<int,int> p1,pair<int,int> p2) to bool compare(pair<int,int> &p1,pair<int,int> &p2)

If you think this through, passing by reference will change the size of stack data from size (2*n*4)*2 bytes to 2x8 byte pointers

For n == 32767 you are reducing the stack frame by approx (2*32767*4)*2

As a rule of thumb, pass by reference unless your design requires otherwise.

Upvotes: 1

Smashery
Smashery

Reputation: 59703

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.

Upvotes: 4

Related Questions