segmentation fault due to comparison function

Discussion in 'C++' started by rhfcwjm, Mar 28, 2011.

  1. rhfcwjm

    rhfcwjm Guest

    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
     
    rhfcwjm, Mar 28, 2011
    #1
    1. Advertising

  2. On 28 mar, 16:37, rhfcwjm <> 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
     
    Michael Doubez, Mar 28, 2011
    #2
    1. Advertising

  3. rhfcwjm

    rhfcwjm Guest

    On 28 mrt, 16:55, Michael Doubez <> wrote:
    > On 28 mar, 16:37, rhfcwjm <> 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 ???
     
    rhfcwjm, Mar 28, 2011
    #3
  4. rhfcwjm

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Mar 28, 2011
    #4
  5. On 28 mar, 21:29, rhfcwjm <> wrote:
    > On 28 mrt, 16:55, Michael Doubez <> wrote:
    >
    >
    >
    >
    >
    >
    >
    >
    >
    > > On 28 mar, 16:37, rhfcwjm <> 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
     
    Michael Doubez, Mar 29, 2011
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stefan Strasser

    Segmentation fault when function ends...

    Stefan Strasser, Mar 30, 2005, in forum: C++
    Replies:
    14
    Views:
    1,631
    Victor Bazarov
    Mar 30, 2005
  2. Chris Van Extergem

    Function pointer results in segmentation fault.

    Chris Van Extergem, May 1, 2006, in forum: C Programming
    Replies:
    5
    Views:
    867
    Chris Van Extergem
    May 2, 2006
  3. Fresh
    Replies:
    2
    Views:
    641
    Bo Persson
    Apr 22, 2008
  4. Geert Fannes
    Replies:
    2
    Views:
    114
  5. Robert Wiley
    Replies:
    0
    Views:
    105
    Robert Wiley
    Dec 7, 2010
Loading...

Share This Page