CODEWITHSUNDEEP
c++c
Steg Verner
Steg Verner

Reputation: 913

sorting large vectors using user defined function in c/c++

I wrote the following code for sorting two vectors according to my sorting criteria:

typedef pair<unsigned, pair<vector<unsigned>, vector<unsigned> > > Elem;
bool bucketComparator(const Elem& a, const Elem& b) {
    //find the min and max of "a" and "b"
    // return true if a should go before b in the sort
    unsigned minA,maxA;
    unsigned minB,maxB;
    if((a.second.first).size()<=1){
        minA=maxA=*((a.second.first).begin());
    } else{
        minA=*std::min_element((a.second.first).begin(),(a.second.first).end());
        maxA=*std::max_element((a.second.first).begin(),(a.second.first).end());
    }
    if((b.second.first).size()<=1){
        minB=maxB=*((b.second.first).begin());
    } else{
        minB=*std::min_element((b.second.first).begin(),(b.second.first).end());
        maxB=*std::max_element((b.second.first).begin(),(b.second.first).end());
    }
    if((minA<=minB)&&(maxA<=maxB)){
        return true;
    } else{
        return false;
    }
}
main()
{
   vector<Elem> A;
   //initializing vector A with values
   std::sort(A.begin(), A.end(), bucketComparator);
   //further computation using vector A
}

Error: Segmentation fault for large data.

I find that I am getting segmentation fault when size of vector A is 223080 or greater. But when the size of vector A is less than 100 then the code works well. I am unable to understand the reason for this as the I am running the code on 64GB RAM. Can some one please help me with this a bit.

Also when I run top command on linux I find that the program does not even consume 0.1% (of 64GB) available RAM before stopping because of segmentation fault.

I even tried to find max and min by first sorting the vectors using std::sort and bubble sort -- but I am still getting the same error.

I am running the following version of gcc: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

Is there some way in which I can write my program such that it sorts large vectors according to the sorting criteria which I have used in:bucketComparator. I am fine with both c and c++.

Additionally, the code does not give segmentation fault when I do a simple std:: sort:

std::sort(A.begin(), A.end());

Upvotes: 3

Views: 224

Answers (3)

clcto
clcto

Reputation: 9648

The documentation for std::sort describes the comparator properties:

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.

The function shall not modify any of its arguments.

This can either be a function pointer or a function object.

Strict weak ordering is defined by the following traits (source):

Irreflexivity                   f(x, x) must be false.
Antisymmetry                    f(x, y) implies !f(y, x)
Transitivity                    f(x, y) and f(y, z) imply f(x, z).
Transitivity of equivalence     Equivalence (as defined above) is transitive: if x is equivalent to y and y is equivalent to z, then x is equivalent to z.

Where two elements, x and y, are considered equivalent if both f(x,y) and f(y,x) are false.

The function you define does not follow these rules, specifically it violates irreflexivity and antisymmetry; when minA == minB && maxA == maxB, bucketComparator(a,b) and bucketComparator(b,a) both result in a true value. Since the functor is invalid, it results in undefined behavior.

You need to update your functor to provide strict weak ordering. One solution may be to change the statement:

if((minA<=minB)&&(maxA<=maxB))

to

if( minA <= minB && maxA < maxB )

Upvotes: 1

Alexander Ohohonin
Alexander Ohohonin

Reputation: 74

if vectors a.second.first or b.second.first are empty then program will crash on dereferencing iterator taken from begin() call.

bool bucketComparator(const Elem& a, const Elem& b) {
    //find the min and max of "a" and "b"
    // return true if a should go before b in the sort
    unsigned minA,maxA;
    unsigned minB,maxB;

    const vector<unsigned> &vecA = a.second.first;
    const vector<unsigned> &vecB = b.second.first;

    //check if vectors empty
    if (vecA.empty()){
        return true;
    }
    if (vecB.empty()){
        return false;
    }

    if((vecA).size()==1){
        minA=maxA=*((vecA).begin());
    } else{
        minA=*std::min_element((vecA).begin(),(vecA).end());
        maxA=*std::max_element((vecA).begin(),(vecA).end());
    }
    if((vecB).size()==1){
        minB=maxB=*((vecB).begin());
    } else{
        minB=*std::min_element((vecB).begin(),(vecB).end());
        maxB=*std::max_element((vecB).begin(),(vecB).end());
    }
    if((minA<=minB)&&(maxA<=maxB)){
        return true;
    } else{
        return false;
    }
}

I also recommend to use local const reference variables to improve code readability and performance.

Upvotes: 1

djhaskin987
djhaskin987

Reputation: 10107

The only thing I can see that might be wrong is that you are dereferencing what is returned by std::min_element and std::max_element, without checking to see if what they return are <vector>.end(), which is possible. Seg faults almost always happen when a pointer somewhere is dereferenced when it wasn't supposed to be dereferenced.

For example, if the vector is empty, std::min_element and std::max_element will return <vector>.end(), which you're dereferencing.

Upvotes: 1

Related Questions