STL sort problem

Discussion in 'C++' started by Nomak, Jul 26, 2004.

  1. Nomak

    Nomak Guest

    Hello,

    i have a bug i can't find. I hope somebody will have some ideas...

    Here is the bad peace of code:


    int compare_sentence(sentence * s1, sentence * s2)
    {
    assert(s1);
    assert(s2);

    return s1->similarity_ >= s2->similarity_;
    }

    ....
    // check
    {
    sentences_list_type::iterator it, end = ds->doc.sentences_.end();
    for (it = ds->doc.sentences_.begin(); it != end; it++)
    {
    sentence * s = *it;

    assert(s);
    assert(s->similarity_ < INT_MAX);
    assert(s->sentence_.size() > 0);
    }
    }

    // sort
    if (ds->doc.sentences_.size() >= 2)
    {
    cerr << "&ds.doc.sentences_ = " << &ds->doc.sentences_ << endl;
    cerr << "ds.doc.sentences_.size() = " << ds->doc.sentences_.size() <<
    endl;

    std::sort(ds->doc.sentences_.begin(),
    ds->doc.sentences_.end(),
    compare_sentence);

    sentence * s1 = *ds->doc.sentences_.begin(),
    * s2 = *(++(ds->doc.sentences_.begin()));

    assert(s1->similarity_ >= s2->similarity_);
    }
    ....


    The types:
    typedef vector< sentence * > sentences_list_type;
    sentences_list_type sentences_;


    The output:
    &ds.doc.sentences_ = 0x80550a0
    ds.doc.sentences_.size() = 852
    sim: sim.cc:125: int compare_sentence(sentence*, sentence*): Assertion
    `s1' failed.
    make: *** [check] Aborted


    Valgrind 2.1.1 memcheck:
    &ds.doc.sentences_ = 0x3c3690b8
    ds.doc.sentences_.size() = 852
    ==32628==
    ==32628== Conditional jump or move depends on uninitialised value(s)
    ==32628== at 0x8049356: compare_sentence(sentence*, sentence*)
    (sim.cc:125)
    ==32628== by 0x804CBB4:
    _ZSt21__unguarded_partitionIN9__gnu_cxx17__normal_iteratorIPP8sentenceSt6vectorIS3_SaIS3_EEEES3_PFiS3_S3_EET_SB_SB_T0_T1_
    (stl_algo.h:1912)
    ==32628== by 0x804C46B:
    _ZSt16__introsort_loopIN9__gnu_cxx17__normal_iteratorIPP8sentenceSt6vectorIS3_SaIS3_EEEEiPFiS3_S3_EEvT_SB_T0_T1_
    (stl_algo.h:2149)
    ==32628== by 0x804C481:
    _ZSt16__introsort_loopIN9__gnu_cxx17__normal_iteratorIPP8sentenceSt6vectorIS3_SaIS3_EEEEiPFiS3_S3_EEvT_SB_T0_T1_
    (stl_algo.h:2150)
    sim: sim.cc:125: int compare_sentence(sentence*, sentence*): Assertion
    `s1' failed.


    Valgrind doesn't show any error before the sort call.

    I must be doing something bad but i'm lost now...

    The check block checks for null pointer and also use a pointer to
    access data (since linux doesn't have a IsBadPointer).

    So i'm lost. How can i find the bug?

    NB: sorry for the > 80 columns
    --
    Nomak
     
    Nomak, Jul 26, 2004
    #1
    1. Advertising

  2. > sentence * s1 = *ds->doc.sentences_.begin(),
    > * s2 = *(++(ds->doc.sentences_.begin()));


    I'm not sure if you can do that.
    Try:
    sentence *s1 = &*ds->doc.sentences_.begin();
    sentence *s2=s1;
    std::advance(s2, 1);

    HTH,

    --
    -Gernot
    int main(int argc, char** argv) {printf
    ("%silto%c%cf%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}

    ________________________________________
    Looking for a good game? Do it yourself!
    GLBasic - you can do
    www.GLBasic.com
     
    Gernot Frisch, Jul 26, 2004
    #2
    1. Advertising

  3. Nomak wrote:
    > i have a bug i can't find. I hope somebody will have some ideas...
    >
    > Here is the bad peace of code:
    >
    >
    > int compare_sentence(sentence * s1, sentence * s2)
    > {
    > assert(s1);
    > assert(s2);
    >
    > return s1->similarity_ >= s2->similarity_;
    > }


    No bug here. If it compiles, it should be fine.

    As you indicate below, the assert(s1) is failing. That means 's1'
    is NULL when it's passed here. The only valid possibility of that
    is that your vector contains NULL pointers. Can it? Sure it can.
    Unless you disallow that yourself, that is. Do you? No way to tell
    from the code you posted.

    >
    > ...
    > // check
    > {
    > sentences_list_type::iterator it, end = ds->doc.sentences_.end();
    > for (it = ds->doc.sentences_.begin(); it != end; it++)


    The potential problem here is that 'end' may become invalid during
    the loop execution. That's why it's often better to always check
    against a value returned from the function .end() _every_ time,
    instead of remembering the 'end' and checking against it.

    I know, I know, in this particular case the loop does not cause any
    mutation of the sequence. So, it's not critical.

    > {
    > sentence * s = *it;
    >
    > assert(s);
    > assert(s->similarity_ < INT_MAX);
    > assert(s->sentence_.size() > 0);
    > }
    > }
    >
    > // sort
    > if (ds->doc.sentences_.size() >= 2)
    > {
    > cerr << "&ds.doc.sentences_ = " << &ds->doc.sentences_ << endl;
    > cerr << "ds.doc.sentences_.size() = " << ds->doc.sentences_.size() <<
    > endl;
    >
    > std::sort(ds->doc.sentences_.begin(),
    > ds->doc.sentences_.end(),
    > compare_sentence);


    Somewhere during this call the assertion "assert(s1)" fails inside the
    'compare_sentence' function. Is it possible that the check is OK but
    the 'compare_sentence' somehow gets called with a NULL? Doesn't sound
    like it, but I'd put a breakpoint into 'compare_sentence' to see who
    is calling it with NULL.

    >
    > sentence * s1 = *ds->doc.sentences_.begin(),
    > * s2 = *(++(ds->doc.sentences_.begin()));
    >
    > assert(s1->similarity_ >= s2->similarity_);
    > }
    > ...
    >
    >
    > The types:
    > typedef vector< sentence * > sentences_list_type;
    > sentences_list_type sentences_;
    >
    >
    > The output:
    > &ds.doc.sentences_ = 0x80550a0
    > ds.doc.sentences_.size() = 852
    > sim: sim.cc:125: int compare_sentence(sentence*, sentence*): Assertion
    > `s1' failed.
    > make: *** [check] Aborted


    That's the most important information. The first argument is NULL. How
    can that happen?

    Since you don't provide the full source or input data, we can't tell. It
    is up to you to find the cause.

    > [...]
    > I must be doing something bad but i'm lost now...
    >
    > The check block checks for null pointer and also use a pointer to
    > access data (since linux doesn't have a IsBadPointer).
    >
    > So i'm lost. How can i find the bug?


    Try a debugger.

    Victor
     
    Victor Bazarov, Jul 26, 2004
    #3
  4. "Nomak" <> wrote in message
    news:ce318v$i6j$...
    > Hello,
    >
    > i have a bug i can't find. I hope somebody will have some ideas...
    >
    > Here is the bad peace of code:
    >
    >
    > int compare_sentence(sentence * s1, sentence * s2)
    > {
    > assert(s1);
    > assert(s2);
    >
    > return s1->similarity_ >= s2->similarity_;
    > }
    >

    [snip]
    >
    > Valgrind doesn't show any error before the sort call.
    >
    > I must be doing something bad but i'm lost now...
    >
    > The check block checks for null pointer and also use a pointer to
    > access data (since linux doesn't have a IsBadPointer).
    >
    > So i'm lost. How can i find the bug?
    >


    Your comparison function returns true for equal sentences. That is not
    allowed. Try this

    int compare_sentence(sentence * s1, sentence * s2)
    {
    assert(s1);
    assert(s2);

    return s1->similarity_ > s2->similarity_;
    }

    john
     
    John Harrison, Jul 26, 2004
    #4
  5. John Harrison wrote:
    > "Nomak" <> wrote in message
    > news:ce318v$i6j$...
    >
    >>Hello,
    >>
    >>i have a bug i can't find. I hope somebody will have some ideas...
    >>
    >>Here is the bad peace of code:
    >>
    >>
    >>int compare_sentence(sentence * s1, sentence * s2)
    >>{
    >> assert(s1);
    >> assert(s2);
    >>
    >> return s1->similarity_ >= s2->similarity_;
    >>}
    >>

    >
    > [snip]
    >
    >>Valgrind doesn't show any error before the sort call.
    >>
    >>I must be doing something bad but i'm lost now...
    >>
    >>The check block checks for null pointer and also use a pointer to
    >>access data (since linux doesn't have a IsBadPointer).
    >>
    >>So i'm lost. How can i find the bug?
    >>

    >
    >
    > Your comparison function returns true for equal sentences. That is not
    > allowed.


    Why should that be a problem? Apparently, the 'compare_sentence' gets
    called with s1 == 0. How would what 'compare_sentence' returns cause
    that?

    I am not contending the validity of your suggestion. I am simply trying
    to understand how changing the >= to > would fix the OP's problem.

    > Try this
    >
    > int compare_sentence(sentence * s1, sentence * s2)
    > {
    > assert(s1);
    > assert(s2);
    >
    > return s1->similarity_ > s2->similarity_;
    > }
     
    Victor Bazarov, Jul 26, 2004
    #5
  6. Nomak

    Nomak Guest

    John Harrison wrote:

    > Your comparison function returns true for equal sentences. That is
    > not allowed. Try this
    >
    > int compare_sentence(sentence * s1, sentence * s2)
    > {
    > assert(s1);
    > assert(s2);
    >
    > return s1->similarity_ > s2->similarity_;
    > }


    Thank you SOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
    much, you even can't imagine how much :))))

    No segfault any more :)

    --
    Nomak
     
    Nomak, Jul 26, 2004
    #6
  7. "Victor Bazarov" <> wrote in message
    news:x%7Nc.150$09.us.to.verio.net...
    > John Harrison wrote:
    > > "Nomak" <> wrote in message
    > > news:ce318v$i6j$...
    > >
    > >>Hello,
    > >>
    > >>i have a bug i can't find. I hope somebody will have some ideas...
    > >>
    > >>Here is the bad peace of code:
    > >>
    > >>
    > >>int compare_sentence(sentence * s1, sentence * s2)
    > >>{
    > >> assert(s1);
    > >> assert(s2);
    > >>
    > >> return s1->similarity_ >= s2->similarity_;
    > >>}
    > >>

    > >
    > > [snip]
    > >
    > >>Valgrind doesn't show any error before the sort call.
    > >>
    > >>I must be doing something bad but i'm lost now...
    > >>
    > >>The check block checks for null pointer and also use a pointer to
    > >>access data (since linux doesn't have a IsBadPointer).
    > >>
    > >>So i'm lost. How can i find the bug?
    > >>

    > >
    > >
    > > Your comparison function returns true for equal sentences. That is not
    > > allowed.

    >
    > Why should that be a problem?


    Because it breaks the strict weak ordering requirement that std::sort
    imposes.

    > Apparently, the 'compare_sentence' gets
    > called with s1 == 0. How would what 'compare_sentence' returns cause
    > that?
    >


    The OP's compare function was undefined behaviour. compare_sentence being
    called with NULL is one possible symptom.

    I saw one error and I pointed it out, I didn't claim it was the only problem
    with the OP's code (though apparently it was).

    john
     
    John Harrison, Jul 26, 2004
    #7
  8. Nomak

    Pete Becker Guest

    Victor Bazarov wrote:
    >
    > > Your comparison function returns true for equal sentences. That is not
    > > allowed.

    >
    > Why should that be a problem? Apparently, the 'compare_sentence' gets
    > called with s1 == 0. How would what 'compare_sentence' returns cause
    > that?


    When the predicate doesn't define a strict weak ordering sort typically
    walks off the end of the data structure, so it passes garbage to the
    predicate. Sometimes that garbage is a null pointer.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
     
    Pete Becker, Jul 27, 2004
    #8
    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. nobody
    Replies:
    0
    Views:
    565
    nobody
    Jun 1, 2004
  2. Rachel Forder
    Replies:
    2
    Views:
    381
    Rachel Forder
    Oct 12, 2003
  3. JerryJ
    Replies:
    11
    Views:
    1,428
    Dave Moore
    Apr 28, 2004
  4. alice

    Problem with STL sort.

    alice, Oct 20, 2007, in forum: C++
    Replies:
    3
    Views:
    376
    Andre Kostur
    Oct 20, 2007
  5. Navin
    Replies:
    1
    Views:
    761
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page