segmentation fault due to comparison function

[rhfcwjm]

Hello All,

In order to be able to sort instances according to a certain criterion
I have created a struct in C++.
E.g, in my .hh file I defined the struct as follow

// code in .hh file //
struct myStructType
{
int number;
int i;
int j;

friend bool compare( const myStructType& a, const myStructType& b);
};

// code in .cc file

friend bool compare( const myStructType& a, const myStructType& b)
{
if (a.number >= b.number)
{
return true;
}
else
{
return false;
}
}

Now in one of my function I define an stl vector of instances of type
myStructType (say std::vector<myStructType> myStructTypeVector. I
filled the "myStructTypeVector" with n number of myStructType
instances, and I also, initialised properly all the members. Then I
called

std::sort( myStructTypeVector.begin(), myStructTypeVector.end(),
compare );

My program compiles (using g++ 4.1) and it runs also. The std:sort I
call several times with no problem, but at the end the program exits
with a segmentation fault.

I searched on the internet and I decided to reimplement my compare
function as follow: I removed it from the struct "myStructType" and I
created another struct in my .hh file

struct byNumber
{
bool operator()(myStructType const &a, myStructType const &b) {
return a.number < b.number;
}
};

And in my .cc file I now call the sorting function as

std::sort( myStructTypeVector.begin(), myStructTypeVector.end(),
byNumber() );

Now my program runs without giving any segmentation fault. Of course
my problem is resolved and I am happy, however I am kind of wondering
what I did wrong in the previous implementation.

regards,

rhfcwjm

 

[Michael Doubez]

Hello All,

In order to be able to sort instances according to a certain criterion
I have created a struct in C++.
E.g, in my .hh file I defined the struct as follow

// code in .hh file //
struct myStructType
{
   int number;
   int i;
   int j;

   friend bool compare( const myStructType& a, const myStructType& b);

};

// code in .cc file

friend bool compare( const myStructType& a, const myStructType& b)
{
        if (a.number >= b.number)
        {
            return true;
        }
        else
        {
            return false;
        }

}

Now in one of my function I define an stl vector of instances of type
myStructType (say std::vector<myStructType> myStructTypeVector. I
filled the "myStructTypeVector" with n number of myStructType
instances, and I also, initialised properly all the members. Then I
called

std::sort( myStructTypeVector.begin(), myStructTypeVector.end(),
compare );

My program compiles (using g++ 4.1) and it runs also. The std:sort I
call several times with no problem, but at the end the program exits
with a segmentation fault.

I searched on the internet and I decided to reimplement my compare
function as follow: I removed it from the struct "myStructType" and I
created another struct in my .hh file

struct byNumber
{
    bool operator()(myStructType const &a, myStructType const &b) {
        return a.number < b.number;
    }

};

And in my .cc file I now call the sorting function as

std::sort( myStructTypeVector.begin(), myStructTypeVector.end(),
byNumber() );

Now my program runs without giving any segmentation fault. Of course
my problem is resolved and I am happy, however I am kind of wondering
what I did wrong in the previous implementation.

You didn't define a strict ordering as required by std::sort.

Your first version was defined as:
return a.number >= b.number;

Which mean that for equal values you have
compare(a,b) == compare(b,a) == true

Which is interpreted by the algorithm as the mathematical equivalent
of
a<b and b<a

Not possible under strict ordering precondition.

 

[rhfcwjm]

You didn't define a strict ordering as required by std::sort.

Your first version was defined as:
return a.number >= b.number;

Which mean that for equal values you have
compare(a,b) == compare(b,a) == true

Which is interpreted by the algorithm as the mathematical equivalent
of
a<b and b<a

Not possible under strict ordering precondition.

But could that lead to a segmentation fault ???

 

[Kai-Uwe Bux]

rhfcwjm wrote:


[about passing a predicate to sort() that is not a strict order]

But could that lead to a segmentation fault ???

Sure can: It's undefined behavior according to the standard, thus anything
is allowed to happen. Some implementations of sort() take advantage of the
guarantees afforded by a strict order. Under some circumstances that can
result in out-of-bounds access into the sequence to be sorted. Such access,
in turn, may segfault.


Best,

Kai-Uwe Bux

 

[Michael Doubez]

But could that lead to a segmentation fault ???

It did on one occasion for me. That helped me locate a logic error in
my code but it took me some time to locate it.