C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Problem with STL sort()

 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated)
View previous topic :: View next topic  
Author Message
phgod
Guest
PostPosted: Tue Jan 20, 2004 11:29 am    Post subject: Problem with STL sort() Reply with quote


Hello,

Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}

I use a vector Then I sort the objectiveClass objects in A using:

sort(A.begin(), A.end());

During the sorting I notice that every comparison between two
objectiveClass objectives gives a correct result, but not every two
objectiveClass objects are compared with each other. This is believed
to have led to an incorrect result:

Quote:
#0| = #( 0.0000 0.0010 )
#1| = #( 0.0416 0.1766 )
#2| = #( 0.3646 0.0913 )
#3| = #( 0.0923 0.4872 )
#4| = #( 0.5268 0.4544 ) <-- look at this one...
#5| = #( 0.2332 0.8313 )
#6| = #( 0.5561 0.0508 )
#7| = #( 0.7671 0.0189 )
#8| = #( 0.2524 0.2982 ) <-- ... and this one.
#9| = #( 0.9317 0.5681 )

In the 10 objectiveClass objects above, |#8| has smaller values (
0.2524 0.2982 ) than |#4| ( 0.5268 0.4544 ), so it is expected to be
in front of |#4|. I have compared |#4| and |#8| explicitly and
objectiveClass::operator< tells me that |#8| < |#4|. I have also
checked that the sort() has not made any attempt to compare between
Quote:
#4| and |#8|.

I'm not familiar with computer algorithms. My question is: Does it
mean that the sort algorithm provided by STL cannot be applied to my
case? Or have I done anything wrong above? Does STL provide other sort
algorithms?

Thanks in advance.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Matthew Watson
Guest
PostPosted: Tue Jan 20, 2004 2:34 pm    Post subject: Re: Problem with STL sort() Reply with quote


"phgod" <ho.yin (AT) alumni (DOT) ust.hk> wrote

Quote:
I use a vector<objectiveClass> A to store the objectiveClass objects.
Then I sort the objectiveClass objects in A using:

sort(A.begin(), A.end());

During the sorting I notice that every comparison between two
objectiveClass objectives gives a correct result, but not every two
objectiveClass objects are compared with each other. This is believed
to have led to an incorrect result:

|#0| = #( 0.0000 0.0010 )
|#1| = #( 0.0416 0.1766 )
|#2| = #( 0.3646 0.0913 )
|#3| = #( 0.0923 0.4872 )
|#4| = #( 0.5268 0.4544 ) <-- look at this one...
|#5| = #( 0.2332 0.8313 )
|#6| = #( 0.5561 0.0508 )
|#7| = #( 0.7671 0.0189 )
|#8| = #( 0.2524 0.2982 ) <-- ... and this one.
|#9| = #( 0.9317 0.5681 )

I'm pretty sure that this isn't working because your operator<() doesn't
obey the following law:

if ( a < b ) and ( b < c ) then it must be that ( a < c )

It is because of that law (I forget the proper name for it) that a sort
algorithm doesn't need to compare all pairs of values. If it has already
determined that (a compare a with c to know that (a


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Thomas Maeder
Guest
PostPosted: Tue Jan 20, 2004 10:32 pm    Post subject: Re: Problem with STL sort() Reply with quote


[email]ho.yin (AT) alumni (DOT) ust.hk[/email] (phgod) writes:

Quote:
Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}

I make several observations:


1) I don't see a reason for this operator to be a member function


2) Is there a reason while you use at() for *this and operator[] for v?
If there is one, I'd write a comment explaining it; if there isn't, I'd
either use at() or operator[] all 4 times


3) Once no_worse is false, the loop can be stopped, because the result then
has to be false:

bool operator<(objectiveClass const &v1, objectiveClass const &v2)
{
objectiveClass::size_type const s(v1.size());
assert(s == v2.size());

bool some_better = false;

for (int i=0; i!=s; ++i)
if (v1[i] > v2[i])
return false;
else if (v1[i] < v2[i])
some_better = true;

return some_better;
}

This has two return statements, which many don't like. I prefer functions
to be so small that it doesn't matter.


4) Unless you have done very careful analysis, comparison of doubles may
lead to surprising results. Floating point calculation is only an
approximation for "real life" real numbers. The same program with the same
input may well behave differently on different platforms even if it's correct
and its behavior is well-defined on each.


5) std::sort requires its funtion object/pointer argument to define a "strict
weak ordering". Your operator< does not satisfy this requirement (nor does
my version given above).

The definition of "strict weak ordering" can be found in §25.3 of the ISO
C++ Standard. Assume that we define an operator== based on the above
operator<:

bool operator==(objectiveClass const &v1, objectiveClass const &v2)
{
return !(v1 }

One of the conditions for operator< to be a strict weak ordering is that
a==b && b==c implies a==c.

Now look at elements #1, #2 and #3 of your set:

Quote:
|#0| = #( 0.0000 0.0010 )
|#1| = #( 0.0416 0.1766 )
|#2| = #( 0.3646 0.0913 )
|#3| = #( 0.0923 0.4872 )
|#4| = #( 0.5268 0.4544 )
|#5| = #( 0.2332 0.8313 )
|#6| = #( 0.5561 0.0508 )
|#7| = #( 0.7671 0.0189 )
|#8| = #( 0.2524 0.2982 )
|#9| = #( 0.9317 0.5681 )


!(#1<#2) evaluates to true
!(#2<#1) evaluates to true
so #1==#2

!(#2<#3) evaluates to true
!(#3<#2) evaluates to true
so #2==#3

This means that #1==#3 should evaluate to true as well, but this isn't the
case since #1<#3 evaluates to true.


Quote:
I'm not familiar with computer algorithms. My question is: Does it
mean that the sort algorithm provided by STL cannot be applied to my
case? Or have I done anything wrong above? Does STL provide other sort
algorithms?

There is no meaningful sort order for your set if the above operator< is to
be used for comparing the elements.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
John Potter
Guest
PostPosted: Tue Jan 20, 2004 10:34 pm    Post subject: Re: Problem with STL sort() Reply with quote
On 20 Jan 2004 06:29:50 -0500, [email]ho.yin (AT) alumni (DOT) ust.hk[/email] (phgod) wrote:

Quote:
Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}

Operator< must provide a strict weak order. This does not.

! ([1,4] < [2,3]) because 4 > 3
! ([2,3] < [1,4]) because 2 > 1
thus [1,4]==[2,3]

Quote:
I use a vector<objectiveClass> A to store the objectiveClass objects.
Then I sort the objectiveClass objects in A using:

sort(A.begin(), A.end());

During the sorting I notice that every comparison between two
objectiveClass objectives gives a correct result, but not every two
objectiveClass objects are compared with each other. This is believed
to have led to an incorrect result:

|#0| = #( 0.0000 0.0010 )
|#1| = #( 0.0416 0.1766 )
|#2| = #( 0.3646 0.0913 )
|#3| = #( 0.0923 0.4872 )
|#4| = #( 0.5268 0.4544 ) <-- look at this one...
|#5| = #( 0.2332 0.8313 )
|#6| = #( 0.5561 0.0508 )
|#7| = #( 0.7671 0.0189 )
|#8| = #( 0.2524 0.2982 ) <-- ... and this one.
|#9| = #( 0.9317 0.5681 )

Let's apply your operator to the 10 objects.

0 1 2 3 4 5 6 7 8 9
0 = < < < < < < < < <
1 > = = < < < = = < <
2 > = = = < = = = = <
3 > > = = = < = = = <
4 > > > = = = = = > <
5 > > = > = = = = = =
6 > = = = = = = = = <
7 > = = = = = = = = <
8 > > = = < = = = = <
9 > > > > > = > > > >

I think the nonsense is obvious. For example, #1==#2 and #2==#3 but
#1<#3. I guess that sort should be allowed to scramble this in just
about any order that puts #0 first. Via transitivity, the rest are
all equal to eachother.

Quote:
In the 10 objectiveClass objects above, |#8| has smaller values (
0.2524 0.2982 ) than |#4| ( 0.5268 0.4544 ), so it is expected to be
in front of |#4|. I have compared |#4| and |#8| explicitly and
objectiveClass::operator< tells me that |#8| < |#4|. I have also
checked that the sort() has not made any attempt to compare between
|#4| and |#8|.

It does not need to because they have been determined to be equal by
transitivity. #4==#5==#6==#7==#8.

Quote:
I'm not familiar with computer algorithms. My question is: Does it
mean that the sort algorithm provided by STL cannot be applied to my
case? Or have I done anything wrong above?

You need to define a strict weak order which produces an implied
equality. What you have is a partial order. You may be looking
for a topological sort. Would 0 7 6 2 1 3 8 4 9 5 be acceptable?

Quote:
Does STL provide other sort algorithms?

Yes, but they all assume a strict weak order imposed by the comparison
operator.

John

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Ulrich Eckhardt
Guest
PostPosted: Tue Jan 20, 2004 10:35 pm    Post subject: Re: Problem with STL sort() Reply with quote
phgod wrote:
Quote:
Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}

|#3| = #( 0.0923 0.4872 )
|#4| = #( 0.5268 0.4544 ) <-- look at this one...

Your problem is that your operator< doesn't result in a strict order (I
think the terminus technicus is 'strict weak ordering'). For the above two
elements, both '#3 < #4' and '#4 < #3' yield false, and you cannot expect
either to come before the other. In the sense of that particular
comparison they are equivalent, one could say.

BTW: publicly deriving from std::vector<> is at least dangerous, because it
was not designed to be inherited from. Inheriting means an ISA
relationship, and that means your class supports the whole interface of
vector<>. However, it seems to have a fixed size of element, it seems
('assert(...)').
This is error-prone and hard to maintain when not documented properly. In
case you really have a fixed amount of elements, std::vector<> might be
the wrong choice for this..

There are more issues like using an int as index, using '<' for that index,
postfix increment, making this a member in the first place, using at for
one but not the other vector, possibility of early aborting the loop and
finally the placement of const to within a reference declaration. ;)

cheers

Uli
--
Questions ?
see C++-FAQ Lite: http://parashift.com/c++-faq-lite/ first !


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Ben Hutchings
Guest
PostPosted: Tue Jan 20, 2004 10:35 pm    Post subject: Re: Problem with STL sort() Reply with quote
phgod wrote:
Quote:
Hello,

Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}
snip


This is not a strict weak ordering, which is required for sorting.
For example, it produces the equivalences
(0 1) == (2 0) == (1 1)
and the inequality
(0 1) < (1 1)

I suggest you give precedence to earlier elements, like this:

bool objectiveClass::operator<(const objectiveClass & v) const
{
assert(size() == v.size());
for (int i = 0; i != size(); ++i)
if (at(i) != v[i])
return at(i) < v[i];
return false; // all elements are equal
}

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Francis Glassborow
Guest
PostPosted: Tue Jan 20, 2004 10:36 pm    Post subject: Re: Problem with STL sort() Reply with quote
In message <a062f4c2.0401200133.763d6145 (AT) posting (DOT) google.com>, phgod
<ho.yin (AT) alumni (DOT) ust.hk> writes
Quote:
Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}

I think that breaks the transitivity requirement. I.e. A < B and B < C
does not imply A < C.

--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Rob Mayoff
Guest
PostPosted: Tue Jan 20, 2004 10:42 pm    Post subject: Re: Problem with STL sort() Reply with quote
[email]ho.yin (AT) alumni (DOT) ust.hk[/email] (phgod) wrote in message news:<a062f4c2.0401200133.763d6145 (AT) posting (DOT) google.com>...
Quote:
My question is: Does it
mean that the sort algorithm provided by STL cannot be applied to my
case? Or have I done anything wrong above? Does STL provide other sort
algorithms?

Your operator< is not a strict weak ordering. Specifically, it does
not provide "transitivity of equivalence". For example, given x=(1,5)
y=(2,2) z=(3,4), your operator< classifies x and y as equivalent, and
classifies x and z as equivalent, but it classifies y < z.

I do not think the standard library provides a sort function suitable
for use with your operator<. All of the standard library sort
functions require a strict weak ordering.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Kevin Saff
Guest
PostPosted: Tue Jan 20, 2004 10:44 pm    Post subject: Re: Problem with STL sort() Reply with quote

"phgod" <ho.yin (AT) alumni (DOT) ust.hk> wrote

Quote:
Hello,

Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}

I use a vector Then I sort the objectiveClass objects in A using:

sort(A.begin(), A.end());

During the sorting I notice that every comparison between two
objectiveClass objectives gives a correct result, but not every two
objectiveClass objects are compared with each other. This is believed
to have led to an incorrect result:

|#0| = #( 0.0000 0.0010 )
|#1| = #( 0.0416 0.1766 )
|#2| = #( 0.3646 0.0913 )
|#3| = #( 0.0923 0.4872 )
|#4| = #( 0.5268 0.4544 ) <-- look at this one...
|#5| = #( 0.2332 0.8313 )
|#6| = #( 0.5561 0.0508 )
|#7| = #( 0.7671 0.0189 )
|#8| = #( 0.2524 0.2982 ) <-- ... and this one.
|#9| = #( 0.9317 0.5681 )

In the 10 objectiveClass objects above, |#8| has smaller values (
0.2524 0.2982 ) than |#4| ( 0.5268 0.4544 ), so it is expected to be
in front of |#4|. I have compared |#4| and |#8| explicitly and
objectiveClass::operator< tells me that |#8| < |#4|. I have also
checked that the sort() has not made any attempt to compare between
|#4| and |#8|.

I'm not familiar with computer algorithms. My question is: Does it
mean that the sort algorithm provided by STL cannot be applied to my
case? Or have I done anything wrong above? Does STL provide other sort
algorithms?

std::sort, like most sorting algorithms, relies on a "strict weak ordering"
of your objects, so that for any two objects A and B:

1) Either A < B, or A == B, or A > B.

(The algorithm only needs <, so == is actually !(A < B || B < A), and > is
just < reversed.)

2) A == B && B == C implies A == C.

Your comparison function fails #2, because by your comparison function
(0.5268 0.4544) == (0.2332 0.8313) &&
(0.2524 0.2982) == (0.2332 0.8313)
however,
(0.5268 0.4544) > (0.2524 0.2982)

You should probably change your comparison function to use either:

A) Lexicographic ordering - like the sorting of books in a library,
first compare the first part; if this is the same, compare the next part;
etc.

B) Absolute value ordering - create a function that translates your
objects into a sortable value; for your class you could use the distance
calculation sqrt (a^2 + b^2).

HTH
--
KCS




[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Bert Klaps
Guest
PostPosted: Wed Jan 21, 2004 9:05 am    Post subject: Re: Problem with STL sort() Reply with quote
"Matthew Watson" <matthew_watson (AT) hotmail (DOT) com> wrote

Quote:

I'm pretty sure that this isn't working because your operator<() doesn't
obey the following law:

if ( a < b ) and ( b < c ) then it must be that ( a < c )

It is because of that law (I forget the proper name for it) that a sort
algorithm doesn't need to compare all pairs of values. If it has already
determined that (a compare a with c to know that (a

This is indeed the reason why not every object is compared to every
other object. However, at first sight the proposed operator< obeys
this law.

The sort algorithm also relies on other properties of the < operator,
like ( a < b ) or ( b < a ) or ( a == b) is true.
The objectiveClass::operator< however does not obey this rule:
it's easy to find examples where none of those three expressions
is true (e.g. #7 and #8 from the original post).

Regards,
Bert Klaps

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Joshua Lehrer
Guest
PostPosted: Wed Jan 21, 2004 9:06 am    Post subject: Re: Problem with STL sort() Reply with quote
"Matthew Watson" <matthew_watson (AT) hotmail (DOT) com> wrote

Quote:
"phgod" <ho.yin (AT) alumni (DOT) ust.hk> wrote in message
news:a062f4c2.0401200133.763d6145 (AT) posting (DOT) google.com...
I use a vector<objectiveClass> A to store the objectiveClass objects.
Then I sort the objectiveClass objects in A using:

sort(A.begin(), A.end());

During the sorting I notice that every comparison between two
objectiveClass objectives gives a correct result, but not every two
objectiveClass objects are compared with each other. This is believed
to have led to an incorrect result:

|#0| = #( 0.0000 0.0010 )
|#1| = #( 0.0416 0.1766 )
|#2| = #( 0.3646 0.0913 )
|#3| = #( 0.0923 0.4872 )
|#4| = #( 0.5268 0.4544 ) <-- look at this one...
|#5| = #( 0.2332 0.8313 )
|#6| = #( 0.5561 0.0508 )
|#7| = #( 0.7671 0.0189 )
|#8| = #( 0.2524 0.2982 ) <-- ... and this one.
|#9| = #( 0.9317 0.5681 )

I'm pretty sure that this isn't working because your operator<() doesn't
obey the following law:

if ( a < b ) and ( b < c ) then it must be that ( a < c )

It is because of that law (I forget the proper name for it) that a sort
algorithm doesn't need to compare all pairs of values. If it has already
determined that (a compare a with c to know that (a


std::sort requires a "strict weak ordering" comparator.

From SGI: "if a is less than b then b is not less than a, if a is less
than b and b is less than c then a is less than c, and so on."

You comparator is not a strict weak ordering.

joshua lehrer
factset research systems
NYSE:FDS

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Bert Klaps
Guest
PostPosted: Wed Jan 21, 2004 9:07 am    Post subject: Re: Problem with STL sort() Reply with quote
[email]ho.yin (AT) alumni (DOT) ust.hk[/email] (phgod) wrote in message news:<a062f4c2.0401200133.763d6145 (AT) posting (DOT) google.com>...
Quote:

Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}

I use a vector Then I sort the objectiveClass objects in A using:

sort(A.begin(), A.end());

The C++ standard actually tells which concepts need to be satisfies
for operator< (see 25.3): for the sort algorithm to work correctly
operator< needs to define a strict weak ordering relation.

Alternatively check the documentation for the Boost Concept Check library
http://www.boost.org/libs/utility/LessThanComparable.html

This strict weak ordering requirement means
that < has to be irreflexive: !(a < a),
transitive: (a < b) && (b < c) implies (a < c)
and < has to define a transitive equivalence:
a and b are equivalent equiv(a,b) if !(a < b) and !(b < a)
equiv(a,b) && equiv(b,c) implies equiv(a,c)

That last requirement is not met, e.g. with a{4,2}, b{2,4}, c{3,1}
a and b are equivalent, b and c are equivalent, but a and c will still
not be equivalent (c < a).

Regards,
Bert Klaps

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Frank Birbacher
Guest
PostPosted: Wed Jan 21, 2004 9:14 am    Post subject: Re: Problem with STL sort() Reply with quote
Hi!

phgod wrote:
Quote:
Hello,

Recently I use the STL's sort(...) to sort a vector of objectiveClass
(a user-defined class) objects. The class objectiveClass is inherited
from vector<double> and has the following operator<:

This operator usually is implemented as a free standing function.

Quote:
bool objectiveClass::operator<(const objectiveClass& v) const {
assert(size() == v.size());
bool no_worse = true, some_better = false;
for(int i=0; i if(at(i) > v[i]) no_worse = false;
if(at(i) < v[i]) some_better = true;
}
return (no_worse && some_better);
}

This does not specify a strict-weak-ordering (required for std::sort). A
strict weak ordering is defined as follows:
Take three objects x and y and z.
Two objects x and y are "equivalent" if both x If x and y are equivalent, and y and z are equivalent, then x and z
must be equivalent (transitivity of equivalence).
x If x If x
Your function does not satisfy the antisymmetry: for the two elements
(1, 2) and (2, 1) there is:
(1, 2) < (2, 1) == false
(2, 1) < (1, 2) == false
Thus the algorithm thinks they are equivalent...

You either write an own sort function, which operates on your sorting
function. Or you change your operator <.

Frank


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.