Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > segmentation fault due to comparison function

Reply
Thread Tools

segmentation fault due to comparison function

 
 
rhfcwjm
Guest
Posts: n/a
 
      03-28-2011
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

 
Reply With Quote
 
 
 
 
Michael Doubez
Guest
Posts: n/a
 
      03-28-2011
On 28 mar, 16:37, rhfcwjm <(E-Mail Removed)> wrote:
> 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.

--
Michael
 
Reply With Quote
 
 
 
 
rhfcwjm
Guest
Posts: n/a
 
      03-28-2011
On 28 mrt, 16:55, Michael Doubez <(E-Mail Removed)> wrote:
> On 28 mar, 16:37, rhfcwjm <(E-Mail Removed)> wrote:
>
>
>
>
>
>
>
>
>
> > 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.
>
> --
> Michael


But could that lead to a segmentation fault ???
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      03-28-2011
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

 
Reply With Quote
 
Michael Doubez
Guest
Posts: n/a
 
      03-29-2011
On 28 mar, 21:29, rhfcwjm <(E-Mail Removed)> wrote:
> On 28 mrt, 16:55, Michael Doubez <(E-Mail Removed)> wrote:
>
>
>
>
>
>
>
>
>
> > On 28 mar, 16:37, rhfcwjm <(E-Mail Removed)> wrote:

>
> > > 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.

>
> 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.

--
Michael
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
winclicker.rb:232 segmentation fault due to data corruption Robert Wiley Ruby 0 12-07-2010 08:20 PM
Segmentation Fault using the srand function jtagpgmr C Programming 11 06-27-2006 06:59 PM
Function pointer results in segmentation fault. Chris Van Extergem C Programming 5 05-02-2006 08:28 PM
Segmentation fault when function ends... Stefan Strasser C++ 14 03-30-2005 07:48 PM
x86_64 segmentation fault due to forgotten extern directive Geert Fannes Ruby 2 03-09-2005 05:22 PM



Advertisments