COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### lexicographical compare in stl_algobase

• Follow

Hi. In a recent review of a C++ book (by a University called IST), I
with respect to Objective-C and JAVA (without generics) in the context
of templates. My reasoning was that cast is performed in these
languages at run time whereas in C++, the template mechanism
instantiates the templates at compile time and no cast is required.

The reviewer actually stated that there is no performance advantage
since (at least) JAVA performs the type casts at "compile-time". This
sounded strange since at least for containers with inheritance the
container does not know what is the actual type of the object stored.

In every test I performed, C++ was always more efficient both from the
run time and memory use, but apparently some "proof" has to be
produced which invalidates general performance comments.

I was actually more puzzled with the comment that the lexicographical
compare "cannot be used to produce a linear ordering since it does not
satisfy the transitivity condition. "

A simplistic code with this comparison operator overload (<) is:

#include <iostream>
#include <set>
using namespace std;
// purposedely easy-to-read ordered pair struct
template<typename T1,typename T2>
struct op {
private:
T1 val1;
T2 val2;
public:
friend ostream & operator<<(ostream &os, const op<T1,T2>& any) {
return(os<<any.val1<<" "<<any.val2<<endl);
}

op():val1(T1()),val2(T2()) {}
void insert(const T1& other1,const T2& other2) {
val1=other1;
val2=other2;
}
T1 get1() {
return(val1);
}
T2 get2() {
return(val2);
}
bool operator=(const op<T1,T2>& other) {
return(other.val1==val1&&other.val2==val2);
}
// does this violate transitivity ?
bool operator<(const op<T1,T2>& other) const {
if (val1<other.val1)return(true);
if (val1>other.val1)return(false);
if (val2<other.val2)return(true);
return(false);
}
};
int main(int argc, char **argv)
{
op<int,double>
opintdouble1,opintdouble2,opintdouble3,opintdouble4,opintdouble5;
opintdouble1.insert(12,33.0);
opintdouble2.insert(44,223.0);
opintdouble3.insert(1002,-312.0);
opintdouble4.insert(93,1222);
opintdouble5.insert(-23,23);
set<op<int,double> > sid;
sid.insert(opintdouble1);
sid.insert(opintdouble2);
sid.insert(opintdouble3);
sid.insert(opintdouble4);
sid.insert(opintdouble5);
unsigned u(0);
for (set<op<int,double> >::const_iterator it(sid.begin());it!
=sid.end();++it) {
cout<<" Sorted list #"<<u<<" "<<*it<<endl;
++u;
}
return(0);
}

Does that < violate transitivity?

I read Kolmogorov and Fomin "Introductory Real Analysis"  (Dover
publications 1975) concerning
this matter and it presents the lexicographical compare as an example
of linear ordering in ordered pairs.

operator < makes use of the lexicographical compare.

It is hard to believe that this implementation fails to satisfy one of
the axioms of the linear ordering, but I would like to know if that is
the case.

Concerning these two matters, what JAVA does and is the implementation
of std::vector theoretically wrong?

(I can provide a google-translated version of part of the review)

P. Areias

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


 0

P. Areias wrote:
> In a recent review of a C++ book (by a University called IST), I
> with respect to Objective-C and JAVA (without generics) in the context
> of templates. My reasoning was that cast is performed in these
> languages at run time whereas in C++, the template mechanism
> instantiates the templates at compile time and no cast is required.
>
> The reviewer actually stated that there is no performance advantage
> since (at least) JAVA performs the type casts at "compile-time". This
> sounded strange since at least for containers with inheritance the
> container does not know what is the actual type of the object stored.
>
> In every test I performed, C++ was always more efficient both from the
> run time and memory use, but apparently some "proof" has to be
> produced which invalidates general performance comments.

Lots of claims and hearsay, without any data this is useless. Also, I don't
get how this relates to the question below.

> I was actually more puzzled with the comment that the lexicographical
> compare "cannot be used to produce a linear ordering since it does not
> satisfy the transitivity condition. "

Well, there is only one way to proof that claim, and that is to give a
counterexample. This example obviously must implement lexicographical
comparisons correctly but still not produce a linear ordering.

> #include <iostream>
> #include <set>
> using namespace std;
> // purposedely easy-to-read ordered pair struct
> template<typename T1,typename T2>
> struct op {
> private:
>   T1 val1;
>   T2 val2;
> public:
>   friend ostream & operator<<(ostream &os, const op<T1,T2>& any)
>   { return(os<<any.val1<<" "<<any.val2<<endl); }
>
> op():val1(T1()),val2(T2()) {}

Huh? Initialise val1 and val2 with their according defaults? This shouldn't
be necessary like this. You would also safe yourself lots of typing
below if
you provided a constructor taking two values. You are aware of std::pair<>
but didn't use it in order to not introduce any side effects, right?

>   void insert(const T1& other1,const T2& other2) {
>     val1=other1;
>     val2=other2;
>   }
>   T1 get1() {
>     return(val1);
>   }
>   T2 get2() {
>     return(val2);
>   }
>   bool operator=(const op<T1,T2>& other) {
>     return(other.val1==val1&&other.val2==val2);
>   }

Stop! You want to overload operator== not operator=. Also, you want to make
this const. BTW: Why do you even think that you need a comparison-operator?
There is nothing in your code that uses it! Also, drop the brackets around
return values, these are useless and return is not a function taking a
parameter list.

>   // does this violate transitivity ?
>   bool operator<(const op<T1,T2>& other) const {
>     if (val1<other.val1)return(true);
>     if (val1>other.val1)return(false);
>     if (val2<other.val2)return(true);
>     return(false);
>   }

No it doesn't generally, provided operator< for T1 and T2 provides this
transitivity. And it doesn't for your instantiation below, since floating-
point numbers know NaNs which are neither less than nor greater than any
real number, but that's not a proof or counterproof of the correctness of
lexical comparisons. BTW: Your code requires a working operator>.
Typically,
the whole STL algorithms are build upon operator< or, rather, std::less<>.
For your code above, it would mean changing the operator and a operand
order
in the second line.

In order to make a proof of that, I'd start off with assuming that for two
unequal values, this doesn't introduce transitivity and show the
contradiction. You start off with the the assumption that neither compares
less than the other, resolve this according to the definition of the
comparison above and you will end up with showing that they are equal,
which
contradicts the assumption that they aren't. This is pretty easy to do and
I'll leave it up to you to do so.

Cheers!

Uli

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


 0

Hi,
On Dec 19, 1:39 am, "P. Areias" <pedromiguelare...@gmail.com> wrote:
> Hi. In a recent review of a C++ book (by a University called IST), I
> with respect to Objective-C and JAVA (without generics) in the context
> of templates. My reasoning was that cast is performed in these
> languages at run time whereas in C++, the template mechanism
> instantiates the templates at compile time and no cast is required.
>

IMO, it is not directly related to casting but to inlining.
Callable objects are passed by value in C++, so the algorithms
know what code will be called when the templates are instanciated.

> The reviewer actually stated that there is no performance advantage
> since (at least) JAVA performs the type casts at "compile-time". This
> sounded strange since at least for containers with inheritance the
> container does not know what is the actual type of the object stored.

Performance is always a tricky subject, all the more in language
wars :).
If the java compilers knows less than the C++ compiler about the
actual
code to be called in templated code, the JVM JIT (if any) knows even
more.
Whether it can (and does) put this knowledge to good use is an other
question, that may lack a definitive answer, imho.

Best regards,

Bernard

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


 0


> Stop! You want to overload operator== not operator=. Also, you want to make
> this const. BTW: Why do you even think that you need a comparison-operator?
> There is nothing in your code that uses it! Also, drop the brackets around
> return values, these are useless and return is not a function taking a
> parameter list.

Yes, there should be a == instead of =, but that is obvious. As for
the return statement, let us see the example in the Microsoft Visual
Studio manual:
// return_statement2.cpp
....
int max ( int a, int b )
{
return ( a > b ? a : b );
}
int main()
{
...
}

It is a matter of style, and hence subject to opinion.

> Your code requires a working operator>.

Why is that? STL requires the operators == and <, I've never found a
need for >.

> For your code above, it would mean changing the operator and a operand
> order
> in the second line.

That is why I used doubles and omitted the existence of std::pair AND
did not STL with exception of std::set.
>
> Cheers!
>

Thank you, the NaN seems an exception, transitivity is satisfied
\forall a,b\in double \\ \{NaN\}

P.

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


 0

P. Areias wrote:
>> Your code requires a working operator>.
>
> Why is that?

Because your lexical comparison uses it.

> STL requires the operators == and <, I've never found a
> need for >.

!(a < b) && !(b < a) is what the STL-descendant parts of the C++ standard
library typically use for equality, so they don't even need an
operator== in
many cases.

:)

Uli

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


 0


> !(a < b) && !(b < a) is what the STL-descendant parts of the C++ standard
> library typically use for equality, so they don't even need an
> operator== in
> many cases.

The word "many" lacks somehow the required rigor for a technical talk.
Let us read once again the manual at Microsoft (http://
msdn.microsoft.com/en-us/library/1fe2x6kt(v=vs.80).aspx)

"Elements inserted into an STL container can be of any object type
that supplies a public copy constructor, a public destructor, and a
public assignment operator. The destructor may not throw an exception.
Furthermore, associative containers such as set and map must have a
public comparison operator defined, which is operator< by default.
Some operations on containers might also require a public default
constructor and a public equivalence operator."

Of course, this can still be debatable from a technical viewpoint.
However, TC++PL 3rd Edition states that:

"By default, containers and algorithms use < when they need to do a
less-than comparison. When the default isn�t right, a programmer can
supply a comparison criterion. However, no mechanism is provided for
also passing an equality test.
Instead, when a programmer supplies a comparison cmp, equality is
tested using two comparisons. For example:
if (x == y) // not done where the user supplied a comparison if (!
cmp(x,y) && !cmp(y,x)) // done where the user supplied a comparison
cmp
"

Which means that IF the cmp comparison is not supplied, the containers
will resort to ==.

Since these two sources, according to some experts, are often wrong, a
simple test for this can be made:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
{
private:
int i;
public:
{
cout<<"Entered <"<<endl;
return(i<other.i);
}
{
cout<<"Entered=="<<endl;
return(i==other.i);
}
};
int main()
{
vrm.push_back(r1);
vrm.push_back(r2);
cout<<"Finished"<<endl;

}

Try to make operator== private and see what happens.

"A little knowledge is a dangerous thing"

P. Areias

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


 0

On 2010-12-22 06:31, P. Areias wrote:
>
> However, TC++PL 3rd Edition states that:
>
> "By default, containers and algorithms use < when they need to do a
> less-than comparison. When the default isn�t right, a programmer can
> supply a comparison criterion. However, no mechanism is provided for
> also passing an equality test.
> Instead, when a programmer supplies a comparison cmp, equality is
> tested using two comparisons. For example:
> if (x == y) // not done where the user supplied a comparison if (!
> cmp(x,y) && !cmp(y,x)) // done where the user supplied a comparison
> cmp
> "
>
> Which means that IF the cmp comparison is not supplied, the containers
> will resort to ==.

I'm not sure which part of TC++PL3e you quoted since I don't have a copy
at hand right now, but if I remember correctly, no algorithm or container
uses a comparison object for < when one is supplied and resorts to ==
otherwise; an algorithm or container always uses either < (or a user-
supplied version thereof), or == (or a user-supplied version thereof).

For example, associative containers use comp(a, b) to determine whether
a is less than b, and !comp(a, b) && !comp(b, a) to determine whether
a is equivalent to b (for the internal ordering). By default, they use
std::less as their comparison operators, so they become (a < b) and
!(a < b) && !(b < a), respectively.

Many algorithms that involve ordering (e.g. std::sort, std::lower_bound)
are similar: they come in pairs where one version uses (a < b) and
the other uses comp(a, b) to determine whether a is less than b.

On the other hand, another set of algorithms do not involve ordering
"comparison objects". One subset (e.g. std::equal) uses pred(a, b) or
(a == b) to determine whether a is equal to b, and the other subset
(e.g. std::find[_if]) uses pred(a) or a == c where c is a specific value
supplied by the user to determine whether a satisfies the given condition.
(The latter subset follows the naming convention of "### or ###_if".)

> #include <iostream>
> #include <vector>
> #include <algorithm>
> using namespace std;
> {
> private:
> int i;
> public:
> bool operator<(const readmanual& other) const
> {
>   cout<<"Entered <"<<endl;
>   return(i<other.i);
> }
> bool operator==(const readmanual& other) const
> {
>   cout<<"Entered=="<<endl;
>   return(i==other.i);
> }
> };
> int main()
> {
> vrm.push_back(r1);
> vrm.push_back(r2);
> cout<<"Finished"<<endl;
>
> }
>
> Try to make operator== private and see what happens.

std::find, being in the second set of algorithms that I mentioned,
uses neither (a < b) nor !comp(a, b) && !comp(b, a), so readmanual::
operator< is not relevant in any way, and you either use std::find to
use readmanual::operator== or std::find_if to use a unary predicate.

I don't see which claim this example is trying to support.

> "A little knowledge is a dangerous thing"

How true... especially in teaching! :)
(Everyone, including me, is imperfect and does possess that danger;
it's just a matter of how much.)

--
Seungbeom Kim

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


 0

OK. Let us summarize:

1) My quote of TC++PL is doubtful (or the book has been adulterated by
a pernicious librarian),
2) Microsoft's C++ manual, subject to much less interpretation than
Stroustrup's work, is wrong.
3) The example I gave works in all compilers I've tested due to a
common bug that plagues all compilers. Or someone has changed the
compilers to make a statement.
4) The Standard (i.e. the 2003 ISO) is also very direct :

20.1.1 Equality comparison

and

25.1.2 Find (T is EqualityComparable)

And even if one of these 3 documents (or the test) is correct, you
don't see the point.

That is revealing. So you are right, regardless of what the documents
state. However, in the improbable event that you are not, there is no
point anyway.

P.

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


 0

> 1) My quote of TC++PL is doubtful (or the book has been adulterated by
> a pernicious librarian),
P. Areias' quote of TC++PL3e was accurate (17.1.4.2, first paragraph).

> 3) The example I gave works in all compilers I've tested due to a
> common bug that plagues all compilers. Or someone has changed the
> compilers to make a statement.
But P. Areias is confusing the use of the comparison cmp in the set,
and the use of the equality operator in the algorithm "find".

His initial example uses a set, and defines operator< for the
elements. His less-than defines an equivalence relationship. He also
(almost) defines an operator==, which luckily agrees with the
equivalence relationship.

But then in his next example, he uses a vector (which does not use a
comparison operator) and the algorithm
find (which does not use a comparison operator) to prove that
operator== is used. Of course it is.

He'd be better to retry his original example where he uses set, and
use the member function find.
Here is his original example, with the comparison and equality
operators marked up with debug output.
Notice that set::find uses the comparison operator to find the
element, whereas the algorithm find uses the equality operator.

Probably the main points of this thread:
operator< and operator== are used in different places in the STL
operator< must be strict weak when used in the STL
if you define operator<, usually it should agree with operator==.
ie.
!(a < b) && !(b < a) => (a == b)

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;
// purposedely easy-to-read ordered pair struct
template<typename T1,typename T2>
struct op {
private:
T1 val1;
T2 val2;

public:
friend ostream & operator<<(ostream &os, const op<T1,T2>& any) {
return(os<<"("<<any.val1<<", "<<any.val2<<")");
}
op():val1(T1()),val2(T2()) {}
void insert(const T1& other1,const T2& other2) {
val1=other1;
val2=other2;
}
T1 get1() {
return(val1);
}
T2 get2() {
return(val2);
}
bool operator==(const op<T1,T2>& other) const {
cout << "?? " << *this << " == " << other << "\n";
return(other.val1==val1&&other.val2==val2);
}
// does this violate transitivity ?
bool operator<(const op<T1,T2>& other) const {
cout << "?? " << *this << " < " << other << "\n";
if (val1<other.val1)return(true);
if (other.val1<val1)return(false);
if (val2<other.val2)return(true);
return(false);
}
};

int main(int argc, char **argv)
{
op<int,double>

opintdouble1,opintdouble2,opintdouble3,opintdouble4,opintdouble5;
opintdouble1.insert(12,33.0);
opintdouble2.insert(44,223.0);
opintdouble3.insert(1002,-312.0);
opintdouble4.insert(93,1222);
opintdouble5.insert(-23,23);
set<op<int,double> > sid;
sid.insert(opintdouble1);
sid.insert(opintdouble2);
sid.insert(opintdouble3);
sid.insert(opintdouble4);
sid.insert(opintdouble5);
unsigned u(0);
for (set<op<int,double> >::const_iterator it(sid.begin());
it!=sid.end();++it) {
cout<<" Sorted list #"<<u<<" "<<*it<<endl;
++u;
}

cout << "** Finding (via set::find)\n";
set<op<int,double> >::iterator pos_member;
pos_member = sid.find(opintdouble2);
cout << "   Found: " << *pos_member << "\n";

cout << "** Finding (via algorithm find)\n";
set<op<int,double> >::iterator pos_algo;
pos_algo = find(sid.begin(), sid.end(), opintdouble2);
cout << "   Found: " << *pos_algo << "\n";

return(0);
}

Output from g++

?? (44, 223) < (12, 33)
?? (12, 33) < (44, 223)
?? (44, 223) < (12, 33)
?? (1002, -312) < (12, 33)
?? (1002, -312) < (44, 223)
?? (44, 223) < (1002, -312)
?? (1002, -312) < (44, 223)
?? (93, 1222) < (44, 223)
?? (93, 1222) < (1002, -312)
?? (44, 223) < (93, 1222)
?? (93, 1222) < (1002, -312)
?? (-23, 23) < (44, 223)
?? (-23, 23) < (12, 33)
?? (-23, 23) < (12, 33)
Sorted list #0 (-23, 23)
Sorted list #1 (12, 33)
Sorted list #2 (44, 223)
Sorted list #3 (93, 1222)
Sorted list #4 (1002, -312)
** Finding (via set::find)
?? (44, 223) < (44, 223)
?? (12, 33) < (44, 223)
?? (44, 223) < (44, 223)
Found: (44, 223)
** Finding (via algorithm find)
?? (-23, 23) == (44, 223)
?? (12, 33) == (44, 223)
?? (44, 223) == (44, 223)
Found: (44, 223)

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


 0

8 Replies
123 Views

Similiar Articles:

7/21/2012 9:01:06 PM