Is it bad practice to make generic arrays, and what would be the alternative?

Question

I've been coding with C++ in school for 3 years now. I've started coding in Java just 2 days ago; my question is:

Is it bad practice to make generic arrays? What would be the alternative?

I am stumped and I can't seem to make a generic array besides doing something weird such as this example:

//Class implementing the MergeSort algorithm with generic types
// Revised by Doina January 2014

package Sorting;

import java.lang.*;

public class MergeSort {

    // Wrapper method for the real algorithm
    // T is the generic type which will be instantiated at runtime
    //  elementas are required to be comparable
    public static <T extends Comparable<T>> void sort(T[] a) {
        mergesort(a, 0, a.length - 1);
    }

    // Recursive mergesort method, following the pseudocode
    private static <T extends Comparable<T>> void mergesort(T[] a, int i, int j) {
        if (j - i < 1) return;
        int mid = (i + j) / 2;
        mergesort(a, i, mid);
        mergesort(a, mid + 1, j);
        merge(a, i, mid, j);
    }

    // Merge method
    // Here we need to allocate a new array, but Java does not allow allocating arrays of a generic type
    // As a work-around we allocate an array of type Object[] the use type casting
    // This would usually generate a warning, which is suppressed
    @SuppressWarnings("unchecked")
    private static <T extends Comparable<T>> void merge(T[] a, int p, int mid, int q) {

        Object[] tmp = new Object[q - p + 1];
        int i = p;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= q) {
            if (a[i].compareTo(a[j]) <= 0)
                tmp[k] = a[i++];
            else
                tmp[k] = a[j++];
            k++;
        }
        if (i <= mid && j > q) {
            while (i <= mid)
                tmp[k++] = a[i++];
        } else {
            while (j <= q)
                tmp[k++] = a[j++];
        }
        for (k = 0; k < tmp.length; k++) {
            a[k + p] = (T) (tmp[k]); // this is the line that woudl generate the warning
        }
    }

    // Main methos to test the code, using Integer Objects
    public static void main(String[] args) {
        Integer[] a = new Integer[5];
        a[0] = new Integer(2);
        a[1] = new Integer(1);
        a[2] = new Integer(4);
        a[3] = new Integer(3);
        a[4] = new Integer(-1);

        // T will be instantiated to Integer as a resutl of this call
        MergeSort.sort(a);

        // Print the result after the sorting
        for (int i = 0; i < a.length; i++)
            System.out.println(a[i].toString());
    }
}

Answer 1

It's not that it's a bad idea per se; it's just that generics and arrays don't mix very well.

The reason is due to covariance and invariance. Arrays are covariant (Integer[] is an Object[] because Integer is an Object, but generic classes are invariant (List<Integer> is not a List<Object> even though an Integer is an Object).

You also have to deal with unchecked casts, which defeat the entire purpose of generics. The most common way to create a generic array - E[] foo = (E[]) new Object[10]; - is not type-safe and can't be enforced at compile time. It's possible to reason about it at runtime, but the compile-time checks which generics bring to the table are lost at that point.

To answer the question directly, where and when possible, you want to use Java Collections instead, as they play very nicely with generics.

Just glancing at your supplied code, I imagine that using List<T> instead of T[] would get you by most of your problems (and I would hope that you're passing an ArrayList in since those operations can become expensive with a linked list).

Answer 2

It's not bad practice to create a generic array, but doing so correctly is so cumbersome people usually avoid it.

The reason it is cumbersome is that generics are erased, while arrays are reified. That is, type parameters are erased during compilation, while the component type of arrays is retained. Therefore, the runtime knows the component type of every array, but has forgotten the type arguments of all objects, i.e. the line

E[] array = new E[10];

does not compile because the runtime needs to know the component type for the new array, but has forgotten was E is.

The workaround in Makoto's answer:

E[] array = (E[]) new Object[10];

is not a good idea, as it actually creates an Object[], but then pretends to the compiler that is an E[]. As the the runtime has forgotten was E is, this cast also succeeds at runtime, even though it is not type correct. However, the runtime still enforces memory safety, by performing an additional check as soon as it is able, i.e. when the object is stored in a variable whose type is not generic. For instance:

static <E> E[] createArray(int size) {
    return (E[]) new Object[size];
}

public static void main(String[] args) {
    String[] array = createArray(size); // throws ClassCastException
    for (String s : array) {
        // whatever
    }
}

That is, this workaround is hack that only works under certain circumstances, and will cause highly puzzling behaviour otherwise (a ClassCastException in a line of code that does not contain a cast ...).

The only way to create an E[] is through reflection, by providing the class object of our desired component type:

Class<E> eClass = ...;
E[] array = Arrays.newInstance(eClass, 10);

but how can we get this class object? If our caller knows, they can pass us a class literal (like Integer.class), or we can use reflection on some other object. In your case, you have another E[] at hand, so you can ask that array what E is:

E[] originalArray = ...;
Class<E> eClass = (Class<E>) originalArray.getClass().getComponentType();
E[] newArray = (E[]) Array.newInstance(eClass, size);

This will ensure the new array is of the same type as the old one, which is E[], unless somebody lied to us about the type of that array using Makoto's workaround.

As you can see, it is possible to create a generic array, but it is so cumbersome that people usually go the great lengths to avoid it. The usual alternative are using an array of some super type (in your merge sort, Comparable[] might work even better than Object[], because you would not have to cast), or using an ArrayList instead.

Answer 3

Adding to Makoto's answer,I would say that Arrays are covariant due to the fact that their type information is available at runtime whereas generic classes are invariant as type information is not available due to type erasure at compile time.

Covariant Arrays :-

Object[] covariantArrays = new String[5];
covariantArrays[0] = new Dog(); // will give java.lang.ArrayStoreException

Invariant Arrays :-

List invariantArrays   = new List<String>();
invariantArrays.add(new Dog());   // Works fine as type information is not available

For this reason Generic arrays don't go well as Generics are limited to compile type safety and Arrays have real type information available even at Runtime