sort() falls into wild state while stable_sort works fine

[bill]

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);
}
}
}

 

[Pete Becker]

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.

 

[P.J. Plauger]

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