Java's ordered containers - something strange

While researching the difference between Templates in C++ and Generics in Java I noticed something strange about java.util.TreeSet and java.util.TreeMap. Both of these ordered containers are not type safe - if not used correctly they will throw a Runtime CastClassException. I thought Java generics prevents that situition? Let's take a look.


Background
An ordered container allows elements to be added in any order. When iterating over the elements they come out in in the specified order based on either an operator or a specific operator passed to the container's constructor. Both Java and C++ work in simlilar ways.


C++

In C++ both <map> and <set> are ordered containers and to use them there must exist either the function operator<

class Data {
int _value;
public:
Data(int v) : _value(v) {}
int getValue() const { return _value; }
};

bool operator<(const Data& d1, const Data& d2) {
return d1.getValue() < d2.getValue();
}

int main() {
Data d1(100);
set<Data> data;
data.insert(d1);

}

or a comparison type

class MyOrder { // sorts strings using last character
public:
bool operator()(const std::string& v1, const std::string v2) {
int rv;
char c1= v1[v1.length()-1];
char c2= v2[v2.length()-1];
if(c1 < c2 ) return true;
return false;
}
int main() {
MyOrder myorder;
set<string, MyOrder> data(myorder);
data.insert("hello");

}

In C++ if we forget to implement either of the above constraints the compiler issues an error but only when it encounters code that requires the operation. Let's say we forget to have the operator< for Data :

int main() {
Data d1(100);
std::set<Data> data; // compiles ok
data.insert(d1); // ERROR does not compile
}

C++ does not have a native language construct for Template parameter constraints. There was a proposal in C++0x but it seems that has been rejected.


Java
To maintain either a set or a map in a particular order in Java we use TreeSet and TreeMap. For the Java containers to work either the type must implement java.lang.Comparable<T>

public interface Comparable<T> {
int compareTo(T o);
}

or pass an implementation of the java.util.Comparator<T>

public interface Comparator<T> {
int compare(T o1, T o2)
boolean equals(Object obj)
}

to the container's constructor.


Strangness

The following broken code compiles just fine in Java but throws a Runtime CastClassException which is what Java Generics was to prevent.

class Data {
}

TreeSet<Data> data;
data.add(new Data()); // <--- CastClassException

For TreeSet<T> the API says T must implement the Comparable<T> interface else a runtime ClassCastException will be thrown.

So the ordered containers in Java are not type safe. Now the question is why?

To make TreeSet type safe it should have been declared as
TreeSet<T extends Comparable<? super T>> which would not even allow the code to compile at the declaration stage alone:

class Data {
}

TreeSet<Data> data; // does NOT compile

The reason we have TreeSet<T> is because the Comparable interface has existed since Java 1.2 and the constrained declaration would break the legacy code - a "not within it's bounds" compilation error. A class that implements Comparable is not the same as one that implements Comparable<Data>.


Neither the API nor the "Java Programming Language" book mentions the lack of type safety due to backward compatibility.