vector sort: sort() vs stable_sort()

[John Black]

I have a sort statement for vectr like this,

sort(vec.begin(), vec.end(), EleSmaller);

in running I find that the sort procedure falls into an endless loop, by
adding some debug statement I see sort is endlessly doing some
comparision on non-exist number!

Then I replace sort() with stable_sort(), it works fine. This really
confuses me, what might be the reason of such problem? The vector seems
fine, as I can go over it specifically to print out all its elements.

Thanks!

[John Harrison]

"John Black" <bl***@eed.com> wrote in message
news:40***************@eed.com...

I have a sort statement for vectr like this,

sort(vec.begin(), vec.end(), EleSmaller);

in running I find that the sort procedure falls into an endless loop, by
adding some debug statement I see sort is endlessly doing some
comparision on non-exist number!

Then I replace sort() with stable_sort(), it works fine. This really
confuses me, what might be the reason of such problem? The vector seems
fine, as I can go over it specifically to print out all its elements.

Almost certainly that your EleSmaller function is bugged.

EleSmaller must be defined so that

1) a < a is never true

2) a < b and b < c implies a < c

3) its never the case that a < b and b > a are both true

If your EleSmaller function does not satisfy those conidtions then sort can
loop forever. If you are not sure, why not post the code of EleSmaller.

john

[Michiel Salters]

John Black <bl***@eed.com> wrote in message news:<40***************@eed.com>...

I have a sort statement for vectr like this,

sort(vec.begin(), vec.end(), EleSmaller);

in running I find that the sort procedure falls into an endless loop, by
adding some debug statement I see sort is endlessly doing some
comparision on non-exist number!

Then I replace sort() with stable_sort(), it works fine. This really
confuses me, what might be the reason of such problem? The vector seems
fine, as I can go over it specifically to print out all its elements.

Perhasps EleSmaller(a,b) and EleSmaller(b,a) are both true for some
a,b in vec? Or in general, there might be loop such that v1 > v2 > vn
but vn > v1.

Whether this loop is discovered can depend on the exact comparisions
made.

Regards,
Michiel Salters

[John Black]

John Harrison wrote:

"John Black" <bl***@eed.com> wrote in message
news:40***************@eed.com...

I have a sort statement for vectr like this,

sort(vec.begin(), vec.end(), EleSmaller);

in running I find that the sort procedure falls into an endless loop, by
adding some debug statement I see sort is endlessly doing some
comparision on non-exist number!

Then I replace sort() with stable_sort(), it works fine. This really
confuses me, what might be the reason of such problem? The vector seems
fine, as I can go over it specifically to print out all its elements.

Almost certainly that your EleSmaller function is bugged.

EleSmaller must be defined so that

1) a < a is never true

2) a < b and b < c implies a < c

3) its never the case that a < b and b > a are both true

If your EleSmaller function does not satisfy those conidtions then sort can
loop forever. If you are not sure, why not post the code of EleSmaller.

john

This makes sense, but I wonder how this applies to my problem: in the vector I
am sorting I know there are some elements are equal to each other, for
example, the vector is a collection of 2 type objects, I want type 1 objects
are before type 2 objects, so in my element comparision function, I do this,

bool EleSmaller(Type o1, Type o2){
if (...o1 is of Type2...){
return false;
}
else{
return true;
}
}

Then if in the vector all the objects are of same type, then that is a>b and
b>a, this violates Strict Less Ordering, but I can not think of another way to
define the comparision. Is stable_sort the only solution here? Does
stable_sort not care Strict Less Ordering?

Thanks.

[Pete Becker]

John Black wrote:

This makes sense, but I wonder how this applies to my problem: in the vector I
am sorting I know there are some elements are equal to each other, for
example, the vector is a collection of 2 type objects, I want type 1 objects
are before type 2 objects, so in my element comparision function, I do this,

bool EleSmaller(Type o1, Type o2){
if (...o1 is of Type2...){
return false;
}
else{
return true;
}
}

When you're working with anything that isn't a numeric type you have to
be extra careful. Lots of people get this sort of thing wrong. Make sure
you've analysed all of the cases.

In this case, it sounds like if o1 and o2 are of the same type, they're
equal. If not, then if o1 is of Type1 (hence o2 is of Type2) o1 < o2,
otherwise o2 < o1.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Joe Gottman]

"John Black" <bl***@eed.com> wrote in message
news:40***************@eed.com...

This makes sense, but I wonder how this applies to my problem: in the vector I am sorting I know there are some elements are equal to each other, for
example, the vector is a collection of 2 type objects, I want type 1 objects are before type 2 objects, so in my element comparision function, I do this,
bool EleSmaller(Type o1, Type o2){
if (...o1 is of Type2...){
return false;
}
else{
return true;
}
}

Then if in the vector all the objects are of same type, then that is a>b and b>a, this violates Strict Less Ordering, but I can not think of another way to define the comparision. Is stable_sort the only solution here? Does
stable_sort not care Strict Less Ordering?

In this case, I don't think you need to use sort() at all. There is
another STL algorithm called partition() that is much better suited to your
purposes.

bool isType1(const Type &o)
{
return (... o is of Type1 ...);
}

Then if you call
partition(vec.begin(), vec.end(), isType1);

all Type1 elements will be placed before all Type2 elements. Note that
partition returns an iterator that points to the end of the range containing
all the elements that evaluate to true; thus if you stored the result of the
above call in the iterator mid, then
[vec.begin(), mid) will contain all Type1 elements and [mid, vec.end())
will contain all Type2 elements. Also, there is a variation
stable_partition which ensures that the relative positions of two elements
that either both evaluate to true or both evaluate to false are unchanged.

Joe Gottman

[John Harrison]

"John Black" <bl***@eed.com> wrote in message
news:40***************@eed.com...

John Harrison wrote:

"John Black" <bl***@eed.com> wrote in message
news:40***************@eed.com...

I have a sort statement for vectr like this,

sort(vec.begin(), vec.end(), EleSmaller);

in running I find that the sort procedure falls into an endless loop, by adding some debug statement I see sort is endlessly doing some
comparision on non-exist number!

Then I replace sort() with stable_sort(), it works fine. This really
confuses me, what might be the reason of such problem? The vector seems fine, as I can go over it specifically to print out all its elements.

Almost certainly that your EleSmaller function is bugged.

EleSmaller must be defined so that

1) a < a is never true

2) a < b and b < c implies a < c

3) its never the case that a < b and b > a are both true

If your EleSmaller function does not satisfy those conidtions then sort can loop forever. If you are not sure, why not post the code of EleSmaller.

john

This makes sense, but I wonder how this applies to my problem: in the

vector I am sorting I know there are some elements are equal to each other, for
example, the vector is a collection of 2 type objects, I want type 1 objects are before type 2 objects, so in my element comparision function, I do this,
bool EleSmaller(Type o1, Type o2){
if (...o1 is of Type2...){
return false;
}
else{
return true;
}
}

Then if in the vector all the objects are of same type, then that is a>b and b>a, this violates Strict Less Ordering, but I can not think of another way to define the comparision.
bool eleSmaller(Type o1, Type o2)
{
return o1 is of Type1 && o2 is of Type2;
}

That's works doesn't it? Essentially you must return false for the case
where o1 and o2 are equal.

Is stable_sort the only solution here? Does
stable_sort not care Strict Less Ordering?

I think any total sort algorithm would require strict weak ordering.
Otherwise a total ordering isn't necessarilly defined. But I think you have
a strict weak ordering, you just haven't defined it correctly in your
comparison function.

john