[: GaB :]

There is a huge difference between Arrays and Generics: the former are covariant while the latter are invariant. How and why does they differ?

If a reference has a covariant type then it refers to an object of it's type or a subtype of it's type.
That means if Sub is a subtype of Super, then Sub[] is a subtype of Super[], as arrays are by definition covariant.

One might think this is a feature, but no, it is dangerous to use. Remember: a bag of apples is not a bag of fruits, even when an apple is indeed a fruit. Or else you could put a banana into the bag, that is obviously no an apple. A bag of something is not a bag of anything, even when something is a kind of anything. Exactly this is violated by covariant arrays:

Assume the following Java code:

Object[] objectArray = new Long[1]; // reference to a BagOfAnything = reference to a BagOfSomething
objectArray[0] = "lol"; // Throws ArrayStoreException, you can't put SomethingElse in a bag of Something

The problem is, this should not compile as it is not typesafe. But it does, as arrays are covariant and because on some rare occasions this cast is required (where the logic of the code ensures type safety). Instead it fails at runtime, possibly on a presentation for your Most Important Customer.

This is why C++ prohibits the implicit conversion from Derived** to Base** but permits the conversion from Derived* to Base*.
Otherwise you could park an instance of NuclearSubmarine into an array of Car when the array is first referenced as an array of Vehicle. C++ does no runtime type checking! After storing nuclearSubmarine in cars (through vehicles), you could extract the very same nuclearSubmarine as a Car object from the cars array. There would be no warning, no error, no segfault. And for example if both Car and NuclearSubmarine has a parameterless member function in the first place, I coul invoke it without any problems. I wonder what would happen if Car has openGasCap() and NuclearSubmarine has fireNuclearMissiles().

Stand alone objects are safe covariants, because it is guaranteed that all subtypes of a type have at least the capabilities of the supertype (the interface of a supertype is always a subset of the interface on any subtype). Therefore it is safe to refer to an instance of a subtype as an instance of the supertype.
But arrays aren't classes. Assume array would be a class and operator[] is represented by the member function at().
It couldn't be legal to convert an array or Car objects to an array of Vehicle objects, as the former has a member function at() returning a Car object while the latter has a member function at() returning a Vehicle object. The conversion would broaden the type of the return value, and this is obviously illegal: if you expect something as a return value, it is not OK to return anything.

Generics are typesafe because their type is invariant. A List<Type1> is neither a subtype nor a supertype of List<Type2> for every Type1 and Type2. At compile time the type of List<Type1> equals to List<Type1>, but at runtime this comparison is not possible, as generic type information can (and is) discarded. This is because with generics the compiler is able to ensure type safety so it can discard generic type information and some type checking can be skipped at runtime. So thus for every type Type1, every instance of List<Type1> is an instance of List. Raw types are discouraged, and you can use wildcard types to refer to generics of unknown types. But as generic type information is not available at runtime you can't use the class literal/type token (Type.class).

But it is illegal to create an array of a generic type, a parametrized type, or a type parameter. None of these array creation expressions are legal: new List<E>[], new List<String>[], new E[] (where E is formal generic type). All will result in generic array creation errors at compile time. If allowed, as arrays are not typesafe generics would break the promise of compiler checked type safety.

// Why generic array creation is illegal - won't compile!
List<String>[] stringLists = new List<String>[1]; // compiler error
List<Integer> intList = Arrays.asList(42);   
Object[] objects = stringLists;                    
objects[0] = intList;                              
String s = stringLists[0].get(0); // ClassCastException here at runtime

It is important to note that these restrictions apply to creation expressions (new) only. You can have an array of a formal type parameter (E[]), you just have to create it as an instance of an unparametrized type and cast it like this:

Stack.java:8: warning: [unchecked] unchecked cast
found   : Object[], required: E[]
        elements = (E[]) new Object[size];
                       ^

Do this only if you are 100% sure that it is type safe what you are doing. In this case always document this fact, document it's proof and documents the premises. Then you can use the @SuppressWarnings("unchecked") annotation to hide the warning.

Type parameters (a.k.a. templates in C++) can be used to do crazy things. It is not just a feature improving type safety by making more checks possible at compile time, but it also extends the ways a programmer can express parametrization of classes. In the following example I demonstrate an algorithm that implements a heapsort, but expects three type parameters:

• The type of some kind of random access iterator. The elements accessible through this are going to be sorted. This parameter is required, but can be guessed by the compiler.
• The type of some kind of strict weak ordering. If this parameter is not present, the compiler will try to use the default operator< for the iterated elements ( std::less() ).
• The type of some kind of index function used by heapsort. Here comes the funny part: it is possible to reuse this heapsort algorithm. For example you want order elements like the pipes of a lilac/orgel (the highest value is in the middle, others surround them in a descending order), you can simply specify an indexing here, so that the highest element is placed by this function in the middle instead of the head or tail the as heapsort does. In other words when heapsort refers to the n-th element, this is filtered through this index function. This way you can achieve sort patterns that you couldn't apply by using a different ordering function. The default is such one, the supplied lilacsorter. You would get the same result by applying heapsort and reordering the result afterwards using this index function, but this would take additionally up to O(n) time.

The type parameters are required to instantiate them (as a class or function) at runtime. Of course I could use some generic interface (a class with virtual functions). Using templates instead is more advanced because the compiler can check at compile time, whether the supplied arguments are of the correct type or not. It makes also possible for supplying the most general default values: the compiler can automatically guess the operator< for a type having one.

Here is the header heapsortplus.h:

1
2
3
4
56
7
8
9
1011
12
13
14
1516
17
18
19
2021
22
23
24
2526
27
28
29
3031
32
33
34
3536
37
38
39
4041
42
43
44
4546
47
48
49
5051
52
53
54
5556
57
58
59
6061
62
63
64
6566
67
68
69
7071
72
73
74
7576
77
78
79
8081
82
83
84
8586
87
88
89
9091
92
93
94
9596
97
98
99
100101
102
103
104
105106
107
108
109
110111
112
113
114
115116
117
118
119
120121
122
123
124
125126
127
128
129

/** @file heapsortplus.h                Templateable sorting functions for C++.
 *
 * With the heapsortplus function you can sort an arbitrary (random access) iterable 
 * set of elements. It uses the well known (and fast) heapsort algorithm for sorting.
 * You can specify the ordering operator.  * You can also specify a permutation (bijective relation) of the elements the iterator 
 * iterates on, so even with a standard ordering operator you can achieve special 
 * sorting results. In other ways this is an index function used by the sorter. For example
 * you can order the elements in a way, that the biggest elements are sorted to the 
 * centre, and the smaller ones to the left and right in descending order. There is no * ordering relation that would result in this ordering.
 */
 
#ifndef heapsortplus_h
#define heapsortplus_h 
/** heapsort's shiftdown function
 */
template <class RandomAccessIterator, class StrictWeakOrdering, class Indexer>
void shiftdown(RandomAccessIterator i,unsigned long int from, unsigned long int end,                                const StrictWeakOrdering& less,const Indexer& idx) {
        unsigned long int child, root = from;
        while ( root * 2 + 1 <= end ) {
                child = root * 2 + 1;
                if (child < end && less(i[idx(child+1)],i[idx(child)])) ++child;                if (less(i[idx(child)],i[idx(root)])) 
                        { std::swap(i[idx(child)],i[idx(root)]); root=child; } else return;
        }
}
 /** initializes the heap
 */
template <class RandomAccessIterator, class StrictWeakOrdering, class Indexer>
void heapify(RandomAccessIterator first,unsigned long int count,
                        const StrictWeakOrdering& less,const Indexer& idx) {        unsigned long int from = count / 2 - 1 + count % 2;
        shiftdown(first, from, count - 1,less,idx);
        while (from>0) {
                --from;
                shiftdown(first, from, count - 1,less,idx);        }
}
 
/** the sorter
 */template <class RandomAccessIterator,class StrictWeakOrdering,class Indexer>
void heapsortplus(RandomAccessIterator first,RandomAccessIterator end,
                                const StrictWeakOrdering& less,const Indexer& idx) {
        if (end-first<2) return;
        unsigned long int count=end-first;        unsigned long int last=count-1;
        heapify(first,count,less,idx);
        while (last > 0) {
                        std::swap(first[idx(0)],first[idx(last)]);
                        --last;                        shiftdown(first,0,last,less,idx);
        }
}
 
/** index relation to retain the ordering of the sort*/
template <class T, class D>
class minsorter {
        protected:
                T first,length;        public:
        minsorter(D f, D l) 
        {       
                first=f;
                length=l;        }
        inline T operator()(T x) const {
                return x;
        }
}; 
/** index relation to reverse the ordering of the sort
*/
template <class T, class D>
class maxsorter {        protected:
                D first,length;
        public:
        maxsorter(D f, D l) 
        {                       first=f;
                length=l;
        }
        inline T operator()(T x) const {
                return length-x-1;        }
};
 
/** index relation impossible to substitute with an ordering
*/template <class T, class D>
class lilacsorter {
        protected:
                D first,length;
        public:        lilacsorter(D f, D l) 
        {       
                first=f;
                length=l;
        }        inline T operator()(T x) const {
                return (length/2)-((x-first)%2==0?-1:1)*(x/2)-((x-first)%2==0?0:1);
        }
};
 /** use the default lilacsorter
*/
template <class RandomAccessIterator, class StrictWeakOrdering>
void heapsortplus(RandomAccessIterator first,RandomAccessIterator end, const StrictWeakOrdering& less) {
        heapsortplus(first,end,less,        lilacsorter<
                typename std::iterator_traits<RandomAccessIterator>::value_type,
                typename std::iterator_traits<RandomAccessIterator>::difference_type
        >(0,end-first));
} 
/** let the compiler guess the default ordering
*/
template <class RandomAccessIterator>
void heapsortplus(RandomAccessIterator first,RandomAccessIterator end) {        heapsortplus(first,end,std::less<typename RandomAccessIterator::value_type>());
}
 
#endif //heapsortplus_h

Here are some use cases:

1
2
3
4
56
7
8
9
1011
12
13
14
1516
17
18
19
2021
22
23
24
2526
27
28
29
3031
32
33
34
3536
37
38
39
4041
42
43
44
4546
47
48
49
5051
52
53
54
5556
57
58

#include <iostream>
#include "heapsortplus.h"
#include <vector>
 
using namespace std; 
// inverse sorting function
template<class T>
bool inverseless(T a,T b) {
        return !less<T>()(a,b);}
 
// special sorting fuction
bool myless(const int& a,const int& b) {
        return (a%2==0^b%2==0?b%2==0:a<b);}
 
int main() {
        srand(time(NULL));
        vector<int> v(23); 
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) *i=random()%100;
        cout <<         "Original         : ";
        // 93 50 50 36 59 68 77 20 80 36 24 29 75 16 21 34 8 1 48 72 88 33 89
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";        cout << endl;
 
        heapsortplus(v.begin(),v.end());
        cout << endl << "Lilacsort        : ";
        // 8 20 24 33 36 48 50 68 75 80 89 93 88 77 72 59 50 36 34 29 21 16 1           for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";
        cout << endl;
 
        heapsortplus(v.begin(),v.end(),inverseless<int>);
        cout << endl << "InverseLilacsort : ";        // 89 80 75 68 50 48 36 33 24 20 8 1 16 21 29 34 36 50 59 72 77 88 93
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";
        cout << endl;
 
        heapsortplus(v.begin(),v.end(),std::less<int>(),minsorter<int,int>(0,v.size()));        cout << endl << "Minsort          : ";
        // 93 89 88 80 77 75 72 68 59 50 50 48 36 36 34 33 29 24 21 20 16 8 1
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";
        cout << endl;
         heapsortplus(v.begin(),v.end(),std::less<int>(),maxsorter<int,int>(0,v.size()));
        cout << endl << "Maxsort          : ";
        // 1 8 16 20 21 24 29 33 34 36 36 48 50 50 59 68 72 75 77 80 88 89 93
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";
        cout << endl; 
        heapsortplus(v.begin(),v.end(),myless,maxsorter<int,int>(0,v.size()));
        cout << endl << "My less's maxsort: ";
        // 1 21 29 33 59 75 77 89 93 8 16 20 24 34 36 36 48 50 50 68 72 80 88
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";        cout << endl;
        return 0;
}

Although overloading an inherited function implies that the (now) overloaded function of the base class will not be visible anymore in the subclass, by using the using keyword, you can make it accessible again:

#include <iostream>
#include <string>

using namespace std;

class A {
    public:
        void x() { cerr <<"x"; }
};

class B : public A {
    public:
        void x(string s) { cerr <<s; }
        using A::x;
};

int main() {
    B b;
    b.x();  // without using A::x in B's declaration, this line would fail to compile
}