sort() falls into wild state while stable_sort works fine

Discussion in 'C++' started by bill, May 25, 2004.

  1. bill

    bill Guest

    Hi,
    I just spent a loooooooong day to debug a problem, it ended up that
    sort() does not work properly on my vector!!!
    In the program I have a vector and the program dynamically add some
    new elements to the vector, but after each time an element is added, I
    call sort() against this vector, and start over again.
    Then there are some strange probelms, in debugging them, I found
    that sort() falls into some wild state, its pointers of vector element
    became pointing to some non-defined address. Then I replace sort()
    with stable_sort(), everything is OK.
    This should not be the case! I wonder if someone else ever seen
    such problem? I do not see any potential vector opration error in my
    code, just wonder...

    My code snippet is like this,

    typedef pair<int, int> AGPair;
    typedef std::vector<AGPair> AGPairVec;
    typedef AGPairVec::iterator AGPairItr;

    ...
    void myFunction(int rngLow, int rngHigh){
    vector<AGPair> ranges; // available ranges
    AGPair p = make_pair(rngLow,rngHigh);
    ranges.push_back(p);

    for (... a loop to go over another vector...){
    AGPair p1 = make_pair(0,0);
    AGPair p2 = make_pair(0,0);

    AGPairItr pairItr;
    for (pairItr = ranges.begin(); pairItr!=ranges.end(); ){
    UINT32 _rngHigh = (*pairItr).second;
    UINT32 _rngLow = (*pairItr).first;
    if ((_rngHigh - _rngLow) >= ...some value...){
    ...set p1 or p2 or both p1 and p2 values...
    break;
    }
    else{
    ++pairItr;
    }
    }
    if (pairItr != ranges.end()){
    (*pairItr).second = 0;
    (*pairItr).first = 0;
    if (p1.second >0){
    ranges.push_back(p1);
    }
    if (p2.second >0){
    ranges.push_back(p2);
    }
    sort(ranges.begin(), ranges.end(), AGPairSmaller);
    }
    }
    }
    bill, May 25, 2004
    #1
    1. Advertising

  2. bill

    Pete Becker Guest

    bill wrote:
    >
    > Then there are some strange probelms, in debugging them, I found
    > that sort() falls into some wild state, its pointers of vector element
    > became pointing to some non-defined address.
    >
    > ...
    >
    > sort(ranges.begin(), ranges.end(), AGPairSmaller);


    Every time I've heard this sort of problem description the culprit has
    been the compare function: it must define a strict weak ordering over
    all the data being sorted.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
    Pete Becker, May 25, 2004
    #2
    1. Advertising

  3. bill

    P.J. Plauger Guest

    "bill" <> wrote in message
    news:...

    > I just spent a loooooooong day to debug a problem, it ended up that
    > sort() does not work properly on my vector!!!
    > In the program I have a vector and the program dynamically add some
    > new elements to the vector, but after each time an element is added, I
    > call sort() against this vector, and start over again.
    > Then there are some strange probelms, in debugging them, I found
    > that sort() falls into some wild state, its pointers of vector element
    > became pointing to some non-defined address. Then I replace sort()
    > with stable_sort(), everything is OK.
    > This should not be the case! I wonder if someone else ever seen
    > such problem? I do not see any potential vector opration error in my
    > code, just wonder...


    You don't show the code for your comparison function, but I'll guarantee
    that it does't enforce a strict weak ordering. If there's ever a pair
    of values x and y for which compare(x, y) && compare(y, x) is true,
    you run the real risk of driving sort crazy. With stable_sort, you
    probably just lucked out.

    Our upgrade library includes an iterator debugging option that checks
    every call to a comparator to ensure that it is a strict weak ordering.
    AFAIK, it's the only library that does so. It *really* helps you find
    pernicious problems like this quickly. I've been told, in fact, that
    a rather large software company found a bug that's been lurking in
    their code for years by using this feature.

    P.J. Plauger
    Dinkumware, Ltd.
    http://www.dinkumware.com
    P.J. Plauger, May 25, 2004
    #3
    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. M O J O
    Replies:
    3
    Views:
    352
    Todd Bellamy
    Nov 4, 2003
  2. Phil Carmody
    Replies:
    13
    Views:
    529
    White Wolf
    Sep 12, 2003
  3. John Black
    Replies:
    6
    Views:
    2,055
    John Harrison
    May 28, 2004
  4. savvy
    Replies:
    1
    Views:
    369
    sloan
    May 12, 2006
  5. qa4ever
    Replies:
    3
    Views:
    239
Loading...

Share This Page