Generics, templates and collections

In CMP-200 Jonah built stacks, queues, hash tables and heaps by hand, each one for a particular kind of element: detections in one, timers in another. Object-oriented languages let you write a data structure once and use it for any element type, safely, through generics in Java, templates in C++ and type parameters in Python's type hints. They also ship large libraries of ready-made, well-tested collections built this way. This lesson explains how generic types work, the surprising rules that govern them in Java, how C++ templates differ, and how to choose among the Java collections, connecting each to the data structure behind it.

The problem generics solve

Before Java 5, the standard collections stored elements as Object, the root of every class hierarchy. A list could hold anything, so every read needed a cast: Detection d = (Detection) list.get(i). If someone had put a String into the list by mistake, the cast failed at run time with a ClassCastException, possibly far from where the wrong object was added. The compiler could not help, because to it the list was just a list of Objects. Tally.java still contains raw lists of this kind, and one of them once mixed Integer node identifiers with Long ones, causing lookups to fail silently because Integer.valueOf(17) does not equal Long.valueOf(17).

Generic classes and methods

A generic class declares one or more type parameters in angle brackets, conventionally single capital letters such as T for type, E for element, K and V for key and value. Code that uses the class supplies type arguments: List<Detection> is a list whose elements are Detection objects, and the compiler checks every add and inserts every cast automatically. Errors that used to appear at run time, if at all, now stop compilation at the line that is wrong. A generic method declares its own type parameters before its return type, so one method can work on many types while keeping their relationships, such as returning the same type it received.

/** A fixed-capacity buffer that keeps the most recent items, for any element type. */
public final class RecentBuffer<T> implements Iterable<T> {
    private final Object[] items;        // generic arrays cannot be created directly (erasure)
    private int next = 0, size = 0;

    public RecentBuffer(int capacity) { items = new Object[capacity]; }

    public void add(T item) {
        items[next] = item;
        next = (next + 1) % items.length;
        size = Math.min(size + 1, items.length);
    }

    public T newest() {                  // unchecked cast: safe, add() stores only T
        if (size == 0) throw new IllegalStateException("empty");
        return (T) items[(next - 1 + items.length) % items.length];
    }

    @Override public Iterator<T> iterator() { /* oldest to newest */ ... }
}

RecentBuffer<Alert> recentAlerts = new RecentBuffer<>(50);   // diamond: type inferred
recentAlerts.add(new Alert(4417, "silent 30 min"));
Alert a = recentAlerts.newest();                             // no cast needed
// recentAlerts.add("text");                                 // compile error: String is not an Alert

public static <T extends Comparable<T>> T maxOf(List<T> xs) {  // a bounded generic method
    T best = xs.get(0);
    for (T x : xs) if (x.compareTo(best) > 0) best = x;
    return best;
}

The method maxOf shows a bounded type parameter. Writing <T extends Comparable<T>> says that T may be any type whose objects can be compared with each other, so the method body may call compareTo. Without the bound, the compiler would know nothing about T and would reject the call. Bounds let generic code use the operations it needs while still accepting every suitable type.

Type erasure and its consequences

Java implements generics by type erasure: the compiler checks the type arguments, inserts the necessary casts, and then erases the type parameters, so at run time a List<Detection> and a List<String> are both just List. Erasure kept new generic code compatible with older libraries, but it has consequences you will meet. You cannot write new T() or new T[10], because the type is not known at run time, which is why RecentBuffer stores an Object array and casts. You cannot test x instanceof List<Detection>. Primitive types cannot be type arguments, so you write List<Integer>, and each int is boxed into an Integer object, costing memory and time; for large numeric arrays, plain int[] remains far more efficient. The cast to T in newest() is unchecked: the compiler cannot verify it and flags it at compile time, so the programmer must ensure, as add() does here, that only T values are ever stored, and can then silence the message with an annotation on the method.

Wildcards and variance

A puzzle confuses almost everyone at first. A LoopNode is a CounterNode, so is a List<LoopNode> a List<CounterNode>? In Java, no. If it were, code could take the List<LoopNode>, view it as a List<CounterNode>, and add a RadarNode to it, corrupting a list that is supposed to hold only loop nodes. Generic types are therefore invariant. When a method only reads from a collection, declare the parameter as List<? extends CounterNode>, which accepts a list of CounterNode or of any subclass, but forbids adding. When a method only writes into a collection, declare it as List<? super LoopNode>, which accepts lists of LoopNode or any supertype. Joshua Bloch summarized the rule as PECS: producer extends, consumer super.

// Reads only: accepts List<CounterNode>, List<LoopNode>, List<RadarNode>...
static long countSilent(List<? extends CounterNode> nodes, Instant now) {
    return nodes.stream().filter(n -> n.isSilent(now, Duration.ofMinutes(30))).count();
}

// Writes only: accepts List<LoopNode>, List<CounterNode>, List<Object>
static void loadLoopNodes(List<? super LoopNode> out, Config cfg) {
    for (LoopConfig lc : cfg.loops()) out.add(new LoopNode(lc.id(), lc.lanes(), lc.spacingCm()));
}

C++ templates

C++ templates look similar but work differently. A template is a pattern from which the compiler generates a separate, fully typed copy of the code for each set of template arguments it is used with, a process called instantiation. std::vector<Detection> and std::vector<int> become two different classes in the compiled program. Nothing is erased, so templates work with primitive types without boxing, can create objects of type T, and are fully optimized for each type, which is why C++ containers are as fast as hand-written code. The costs are longer compile times, larger executables when many instantiations are generated, and, historically, notoriously long error messages. C++20 concepts let a template state its requirements, such as std::totally_ordered<T>, much as Java's bounds do, which makes error messages far clearer. Templates are also Turing-complete at compile time, which enables template metaprogramming, a powerful technique best used sparingly.

// C++20: one template, separate optimized code for each element type
template <std::totally_ordered T>
const T& max_of(const std::vector<T>& xs) {
    const T* best = &xs.front();
    for (const T& x : xs) if (*best < x) best = &x;
    return *best;
}

std::vector<int> speeds{62, 88, 54};
std::vector<std::string> names{"Princess", "Bath", "Division"};
int top = max_of(speeds);                 // instantiates max_of<int>
const std::string& last = max_of(names);  // instantiates max_of<std::string>

The Java collections framework

Java's standard library organizes its collections around a small set of interfaces, each with several implementations whose performance follows directly from the data structures in CMP-200. Collection is the root interface for groups of elements. List keeps elements in order with positional access. Set holds no duplicates. Queue and Deque support adding and removing at the ends. Map, which is not a Collection, associates keys with values. Following lesson 7, declare variables with these interface types and choose the implementation once, when you construct the object.

Two families of interfaces control ordering. A class that has one natural order implements Comparable<T> and its compareTo method, as String, Integer and Instant do. When you need a different order, or the class has none, pass a Comparator<T>, a separate object, often a lambda, that compares two elements: Comparator.comparing(Detection::time).thenComparing(Detection::lane). TreeMap, TreeSet, PriorityQueue and the sort methods all accept a comparator. For TreeSet and TreeMap the comparator must be consistent with equals, or elements that compare as equal will silently replace each other.

Collections are traversed with iterators, objects that implement Iterator<T> with hasNext and next, and the for-each loop uses them behind the scenes for anything Iterable. Modifying most collections while iterating over them with for-each makes the iterator throw ConcurrentModificationException at the next step, a deliberate fail-fast check; remove elements with the iterator's own remove method or with removeIf. Finally, List.of, Set.of and Map.of create unmodifiable collections, ideal for constants and for the defensive copies of lesson 2.

Generics in Python

Python's built-in list, dict and set hold any objects, and type annotations such as list[Detection] or dict[int, Node] have no effect at run time; they exist for readers and for static checkers such as mypy. Generic classes of your own use TypeVar or, since Python 3.12, the syntax class RecentBuffer[T]. Python's standard library provides the same structures as Java's: collections.deque, heapq for binary heaps, collections.Counter for counting and sorted with a key function in place of a Comparator.

from collections import Counter, deque
from typing import Generic, TypeVar, Iterator
import heapq

T = TypeVar("T")

class RecentBuffer(Generic[T]):
    def __init__(self, capacity: int):
        self._items: deque[T] = deque(maxlen=capacity)   # a ring buffer from the library
    def add(self, item: T) -> None:
        self._items.append(item)
    def newest(self) -> T:
        return self._items[-1]
    def __iter__(self) -> Iterator[T]:
        return iter(self._items)

alerts: RecentBuffer[str] = RecentBuffer(3)
for a in ["n4417 silent", "n311 low battery", "n17 lane 9", "n902 glare"]:
    alerts.add(a)
print("recent:", list(alerts), "| newest:", alerts.newest())

dets = [("07:42:13", 2, "car"), ("07:42:09", 1, "bus"), ("07:42:13", 1, "car"),
        ("07:41:58", 2, "heavy truck"), ("07:42:01", 1, "car")]
by_time_then_lane = sorted(dets, key=lambda d: (d[0], d[1]))   # like a Comparator chain
print("first:", by_time_then_lane[0], "| last:", by_time_then_lane[-1])
print("per class:", dict(Counter(cls for _, _, cls in dets)))
print("two longest gaps (s):", heapq.nlargest(2, [4, 11, 3, 15, 8]))

lanes = [1, 2, 9, 3, 9, 4]
try:
    for x in lanes:                    # modifying while iterating is a classic bug
        if x == 9:
            lanes.remove(x)
except RuntimeError:
    pass
print("after naive removal:", lanes, "(one 9 survived)")
lanes = [x for x in [1, 2, 9, 3, 9, 4] if x != 9]
print("after filtering into a new list:", lanes)

recent: ['n311 low battery', 'n17 lane 9', 'n902 glare'] | newest: n902 glare
first: ('07:41:58', 2, 'heavy truck') | last: ('07:42:13', 2, 'car')
per class: {'car': 3, 'bus': 1, 'heavy truck': 1}
two longest gaps (s): [15, 11]
after naive removal: [1, 2, 3, 4] (one 9 survived)
after filtering into a new list: [1, 2, 3, 4]

The last part of the example shows why Java's fail-fast iterators exist. Python lists do not detect modification during iteration, so removing an element shifts the rest left and the loop skips the element that moved into the removed one's place; one 9 survives without any error. Building a new list, or iterating over a copy, avoids the problem in both languages.