Java Generics and Collections

Chapter 4. Declarations

This chapter discusses how to declare a generic class. It describes constructors, static members, and nested classes, and it fills in some details of how erasure works.

Constructors

In a generic class, type parameters appear in the header that declares the class, but not in the constructor:

class Pair<T, U> {
  private final T first;
  private final U second;
  public Pair(T first, U second) { this.first=first; this.second=second; }
  public T getFirst() { return first; }
  public U getSecond() { return second; }
}

The type parameters T and U are declared at the beginning of the class, not in the constructor. However, actual type parameters are passed to the constructor whenever it is invoked:

Pair<String, Integer> pair = new Pair<String, Integer>("one",2);
assert pair.getFirst().equals("one") && pair.getSecond() == 2;

Look Out for This! A common mistake is to forget the type parameters when invoking the constructor:

Pair<String, Integer> pair = new Pair("one",2);

This mistake produces a warning, but not an error. It is taken to be legal, because Pair is treated as a raw type, but conversion from a raw type to the corresponding parameterized type generates an unchecked warning; see Generic Library with Legacy Client, which explains how the -Xlint:unchecked flag can help you spot errors of this kind.

Static Members

Because generics are compiled by erasure, at run time the classes List<Integer>, List<String>, and List<List<String>> are all implemented by a single class, namely List. You can see this using reflection:

List<Integer> ints = Arrays.asList(1,2,3);
List<String> strings = Arrays.asList("one","two");
assert ints.getClass() == strings.getClass();

Here the class associated with a list of integers at run time is the same as the class associated with a list of strings.

One consequence is that static members of a generic class are shared across all instantiations of that class, including instantiations at different types. Static members of a class cannot refer to the type parameter of a generic class, and when accessing a static member the class name should not be parameterized.

For example, here is a class, Cell<T>, in which each cell has an integer identifier and a value of type T:

class Cell<T> {
  private final int id;
  private final T value;
  private static int count = 0;
  private static synchronized int nextId() { return count++; }
  public Cell(T value) { this.value=value; id=nextId(); }
  public T getValue() { return value; }
  public int getId() { return id; }
  public static synchronized int getCount() { return count; }
}

A static field, count, is used to allocate a distinct identifier to each cell. The static nextId method is synchronized to ensure that unique identifiers are generated even in the presence of multiple threads. The static getCount method returns the current count.

Here is code that allocates a cell containing a string and a cell containing an integer, which are allocated the identifiers 0 and 1, respectively:

Cell<String> a = new Cell<String>("one");
Cell<Integer> b = new Cell<Integer>(2);
assert a.getId() == 0 && b.getId() == 1 && Cell.getCount() == 2;

Static members are shared across all instantiations of a class, so the same count is incremented when allocating either a string or an integer cell.

Because static members are independent of any type parameters, we are not permitted to follow the class name with type parameters when accessing a static member:

Cell.getCount();                // ok
Cell<Integer>.getCount(); // compile-time error
Cell<?>.getCount();       // compile-time error

The count is static, so it is a property of the class as a whole, not any particular instance.

For the same reason, you may not refer to a type parameter anywhere within a static member. Here is a second version of Cell, which attempts to use a static variable to keep a list of all values stored in any cell:

class Cell2<T> {
  private final T value;
  private static List<T> values = new ArrayList<T>(); // illegal
  public Cell(T value) { this.value=value; values.add(value); }
  public T getValue() { return value; }
  public static List<T> getValues() { return values; } // illegal
}

Since the class may be used with different type parameters at different places, it makes no sense to refer to T in the declaration of the static field values or the static method getValues(), and these lines are reported as errors at compile time. If we want a list of all values kept in cells, then we need to use a list of objects, as in the following variant:

class Cell2<T> {
  private final T value;
  private static List<Object> values = new ArrayList<Object>(); // ok
  public Cell(T value) { this.value=value; values.add(value); }
  public T getValue() { return value; }
  public static List<Object> getValues() { return values; } // ok
}

This code compiles and runs with no difficulty:

Cell2<String> a = new Cell2<String>("one");
Cell2<Integer> b = new Cell2<Integer>(2);
assert Cell2.getValues().toString().equals("[one, 2]");

Nested Classes

Java permits nesting one class inside another. If the outer class has type parameters and the inner class is not static, then type parameters of the outer class are visible within the inner class.

Example 4-1 shows a class implementing collections as a singly-linked list. The class extends java.util.AbstractCollection, so it only needs to define the methods size, add, and iterator. The class contains an inner class, Node, for the list nodes, and an anonymous inner class implementing Iterator<E>. The type parameter E is in scope within both of these classes.

Example 4-1. Type parameters are in scope for nested, nonstatic classes

public class LinkedCollection<E> extends AbstractCollection<E> {
  private class Node {
    private E element;
    private Node next = null;
    private Node(E elt) { element = elt; }
  }
  private Node first = new Node(null);
  private Node last = first;
  private int size = 0;
  public LinkedCollection() {}
  public LinkedCollection(Collection<? extends E> c) { addAll(c); }
  public int size() { return size; }
  public boolean add(E elt) {
    last.next = new Node(elt); last = last.next; size++;
    return true;
  }
  public Iterator<E> iterator() {
    return new Iterator<E>() {
      private Node current = first;
      public boolean hasNext() {
        return current.next != null;
      }
      public E next() {
        if (current.next != null) {
          current = current.next;
          return current.element;
        } else throw new NoSuchElementException();
      }
      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }
}

For contrast, Example 4-2 shows a similar implementation, but this time the nested Node class is static, and so the type parameter E is not in scope for this class. Instead, the nested class is declared with its own type parameter, T. Where the previous version referred to Node, the new version refers to Node<E>. The anonymous iterator class in the preceding example has also been replaced by a nested static class, again with its own type parameter.

If the node classes had been made public rather than private, you would refer to the node class in the first example as LinkedCollection<E>.Node, whereas you would refer to the node class in the second example as LinkedCollection.Node<E>.

Example 4-2. Type parameters are not in scope for nested, static classes

class LinkedCollection<E> extends AbstractCollection<E> {
  private static class Node<T> {
    private T element;
    private Node<T> next = null;
    private Node(T elt) { element = elt; }
  }
  private Node<E> first = new Node<E>(null);
  private Node<E> last = first;
  private int size = 0;
  public LinkedCollection() {}
  public LinkedCollection(Collection<? extends E> c) { addAll(c); }
  public int size() { return size; }
  public boolean add(E elt) {
    last.next = new Node<E>(elt); last = last.next; size++;
    return true;
  }
  private static class LinkedIterator<T> implements Iterator<T> {
    private Node<T> current;
    public LinkedIterator(Node<T> first) { current = first; }
    public boolean hasNext() {
      return current.next != null;
    }
    public T next() {
      if (current.next != null) {
        current = current.next;
        return current.element;
      } else throw new NoSuchElementException();
    }
    public void remove() {
      throw new UnsupportedOperationException();
    }
  }
  public Iterator<E> iterator() {
    return new LinkedIterator<E>(first);
  }
}

Of the two alternatives described here, the second is preferable. Nested classes that are not static are implemented by including a reference to the enclosing instance, since they may, in general, access components of that instance. Static nested classes are usually both simpler and more efficient.

How Erasure Works

The erasure of a type is defined as follows: drop all type parameters from parameterized types, and replace any type variable with the erasure of its bound, or with Object if it has no bound, or with the erasure of the leftmost bound if it has multiple bounds. Here are some examples:

• The erasure of List<Integer>, List<String>, and List<List<String>> is List.

• The erasure of List<Integer>[] is List[].

• The erasure of List is itself, similarly for any raw type (see Generic Library with Legacy Client for an explanation of raw types).

• The erasure of int is itself, similarly for any primitive type.

• The erasure of Integer is itself, similarly for any type without type parameters.

• The erasure of T in the definition of asList (see Generic Methods and Varargs) is Object, because T has no bound.

• The erasure of T in the definition of max (see Maximum of a Collection) is Comparable, because T has bound Comparable<? super T>.

• The erasure of T in the final definition of max (see Multiple Bounds) is Object, because T has bound Object & Comparable<T> and we take the erasure of the leftmost bound.

• The erasures of S and T in the definition of copy (see Multiple Bounds) are Readable and Appendable, because S has bound Readable & Closeable and T has bound Appendable & Closeable.

• The erasure of LinkedCollection<E>.Node or LinkedCollection.Node<E> (see Nested Classes) is LinkedCollection.Node.

In Java, two distinct methods cannot have the same signature. Since generics are implemented by erasure, it also follows that two distinct methods cannot have signatures with the same erasure. A class cannot overload two methods whose signatures have the same erasure, and a class cannot implement two interfaces that have the same erasure.

For example, here is a class with two convenience methods. One adds together every integer in a list of integers, and the other concatenates together every string in a list of strings:

class Overloaded {
  public static int sum(List<Integer> ints) {
    int sum = 0;
    for (int i : ints) sum += i;
    return sum;
  }
  public static String sum(List<String> strings) {
    StringBuffer sum = new StringBuffer();
    for (String s : strings) sum.append(s);
    return sum.toString();
  }
}

This works as intended:

assert sum(Arrays.asList(1,2,3)) == 6;
assert sum(Arrays.asList("a","b")).equals("ab");

Here are the erasures of the signatures of the two methods:

int sum(List)
String sum(List)

The two methods have different return types, which is sufficient for Java to distinguish them.

However, say we change the methods so that each appends its result to the end of the argument list rather than returning a value:

class Overloaded2 {
  // compile-time error, cannot overload two methods with same erasure
  public static boolean allZero(List<Integer> ints) {
    for (int i : ints) if (i != 0) return false;
    return true;
  }
  public static boolean allZero(List<String> strings) {
    for (String s : strings) if (s.length() != 0) return false;
    return true;
  }
}

We intend this code to work as follows:

assert allZero(Arrays.asList(0,0,0));
assert allZero(Arrays.asList("","",""));

However, in this case the erasures of the signatures of both methods are identical:

boolean allZero(List)

Therefore, a name clash is reported at compile time. It is not possible to give both methods the same name and try to distinguish between them by overloading, because after erasure it is impossible to distinguish one method call from the other.

For another example, here is a bad version of the integer class, that tries to make it possible to compare an integer with either an integer or a long:

class Integer implements Comparable<Integer>, Comparable<Long> {
    // compile-time error, cannot implement two interfaces with same erasure
    private final int value;
    public Integer(int value) { this.value = value; }
    public int compareTo(Integer i) {
        return (value < i.value) ? -1 : (value == i.value) ? 0 : 1;
    }
    public int compareTo(Long l) {
        return (value < l.value) ? -1 : (value == l.value) ? 0 : 1;
    }
}

If this were supported, it would, in general, require a complex and confusing definition of bridge methods (see Bridges). By far, the simplest and most understandable option is to ban this case.