Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > sort() falls into wild state while stable_sort works fine

Reply
Thread Tools

sort() falls into wild state while stable_sort works fine

 
 
bill
Guest
Posts: n/a
 
      05-24-2004
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);
}
}
}
 
Reply With Quote
 
 
 
 
Pete Becker
Guest
Posts: n/a
 
      05-25-2004
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)
 
Reply With Quote
 
 
 
 
P.J. Plauger
Guest
Posts: n/a
 
      05-25-2004
"bill" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...

> 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


 
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
DVD Verdict reviews: THE WILD, WILD WEST: THE COMPLETE FIRST SEASON and more! DVD Verdict DVD Video 0 06-14-2006 08:22 AM
The Wild Wild West fredman DVD Video 6 03-04-2006 04:21 PM
Wild Wild West in R1? Kishin DVD Video 1 07-11-2005 06:16 PM
looking for CH Wild Wild West discs... Darrel Christenson DVD Video 0 11-26-2004 10:23 PM
Lynne Cheney's Wild, Wild West =?iso-8859-1?Q?=B1?= Digital Photography 6 08-16-2004 07:26 AM



Advertisments