Re: lexicographical compare in stl_algobase
P. Areias wrote:
In a recent review of a C++ book (by a University called IST), I
was faced with comments concerning the performance advantage of C++
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! ]