lexicographical compare in stl_algobase

Hi. 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.

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.

An inspection of the header of std::vector shows that the overloaded
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! ]