11. Generics
Begin 2.0
As your projects become more sophisticated, you will need a better way to reuse and customize existing software. To facilitate code reuse, especially the reuse of algorithms, C# includes a feature called generics. Just as methods are powerful because they can take arguments, so types and methods that take type arguments have significantly more functionality.
Generics are lexically similar to generic types in Java and templates in C++. In all three languages, these features enable the implementation of algorithms and patterns once, rather than requiring separate implementations for each type the algorithm or pattern operates upon. However, C# generics are very different from both Java generics and C++ templates in the details of their implementation and impact upon the type system of their respective languages. Generics were added to the runtime and C# in version 2.0.
C# without Generics
We begin the discussion of generics by examining a class that does not use generics. This class, System.Collections.Stack, represents a collection of objects such that the last item to be added to the collection is the first item retrieved from the collection (last in, first out [LIFO]). Push() and Pop(), the two main methods of the Stack class, add items to the stack and remove them from the stack, respectively. The declarations for the methods on the stack class appear in Listing 11.1.
LISTING 11.1: The System.Collections.Stack Method Signatures
public class Stack
{
public virtual object Pop() { ... }
public virtual void Push(object obj) { ... }
// ...
}
Programs frequently use stack type collections to facilitate multiple undo operations. For example, Listing 11.2 uses the System.Collections.Stack class for undo operations within a program that simulates the Etch A Sketch game.
LISTING 11.2: Supporting Undo in a Program Similar to the Etch A Sketch Game
using System;
using System.Collections;
class Program
{
// ...
public void Sketch()
{
Stack path = new Stack();
Cell currentPosition;
ConsoleKeyInfo key; // Added in C# 2.0
do
{
// Etch in the direction indicated by the
// arrow keys that the user enters
key = Move();
switch (key.Key)
{
case ConsoleKey.Z:
// Undo the previous Move
if (path.Count >= 1)
{
currentPosition = (Cell)path.Pop();
Console.SetCursorPosition(
currentPosition.X, currentPosition.Y);
Undo();
}
break;
case ConsoleKey.DownArrow:
case ConsoleKey.UpArrow:
case ConsoleKey.LeftArrow:
case ConsoleKey.RightArrow:
// SaveState()
currentPosition = new Cell(
Console.CursorLeft, Console.CursorTop);
path.Push(currentPosition);
break;
default:
Console.Beep(); // Added in C# 2.0
break;
}
}
while (key.Key != ConsoleKey.X); // Use X to quit
}
}
public struct Cell
{
// Use read-only field prior to C# 6.0
public int X { get; }
public int Y { get; }
public Cell(int x, int y)
{
X = x;
Y = y;
}
}
The results of Listing 11.2 appear in Output 11.1 on the next page.
Using the variable path, which is declared as a System.Collections.Stack, you save the previous move by passing a custom type, Cell, into the Stack.Push() method using path.Push(currentPosition). If the user enters a Z (or presses Ctrl+Z), you undo the previous move by retrieving it from the stack using a Pop() method, setting the cursor position to be the previous position, and calling Undo().
Although this code is functional, there is a fundamental shortcoming in the System.Collections.Stack class. As shown in Listing 11.1, the Stack class collects values of type object. Because every object in the CLR derives from object, Stack provides no validation that the elements you place into it are homogenous or are of the intended type. For example, instead of passing currentPosition, you can pass a string in which X and Y are concatenated with a decimal point between them. However, the compiler must allow the inconsistent data types because the stack class is written to take any object, regardless of its more specific type.
Furthermore, when retrieving the data from the stack using the Pop() method, you must cast the return value to a Cell. But if the type of the value returned from the Pop() method is not Cell, an exception is thrown. By deferring type checking until runtime by using a cast, you make the program more brittle. The fundamental problem with creating classes that can work with multiple data types without generics is that they must work with a common base class (or interface), usually object.
Using value types, such as a struct or an integer, with classes that use object exacerbates the problem. If you pass a value type to the Stack.Push() method, for example, the runtime automatically boxes it. Similarly, when you retrieve a value type, you need to explicitly unbox the data and cast the object reference you obtain from the Pop() method into a value type. Casting a reference type to a base class or interface has a negligible performance impact, but the box operation for a value type introduces more overhead, because it must allocate memory, copy the value, and then later garbage-collect that memory.
C# is a language that encourages “type safety”: The language is designed so that many type errors, such as assigning an integer to a variable of type string, can be caught at compile time. The fundamental problem is that the stack class is not as type-safe as one expects a C# program to be. To change the stack class to enforce type safety to restrict the contents of the stack to be a particular data type (without using generic types), you must create a specialized stack class, as in Listing 11.3.
LISTING 11.3: Defining a Specialized Stack Class
public class CellStack
{
public virtual Cell Pop();
public virtual void Push(Cell cell);
// ...
}
Because CellStack can store only objects of type Cell, this solution requires a custom implementation of the stack methods, which is less than ideal. Implementing a type-safe stack of integers would require yet another custom implementation; each implementation would look remarkably like every other one. There would be lots of duplicated, redundant code.
Introducing Generic Types
Generics provide a facility for creating data structures that can be specialized to handle specific types. Programmers define these parameterized types so that each variable of a particular generic type has the same internal algorithm, but the types of data and method signatures can vary based on the type arguments provided for the type parameters.
To minimize the learning curve for developers, C# designers chose syntax that superficially resembles C++ templates. In C#, the syntax for generic classes and structures uses angle brackets to both declare the generic type parameters in the type declaration and specify the generic type arguments when the type is used.
Using a Generic Class
Listing 11.6 shows how you can specify the actual type argument used by the generic class. You instruct the path variable to be the “Stack of Cell” type by specifying Cell within angle bracket notation in both the object creation expression and the declaration statement. In other words, when declaring a variable (path in this case) using a generic data type, C# requires the developer to identify the actual type arguments used by the generic type. Listing 11.6 illustrates this process with the new generic Stack class.
LISTING 11.6: Implementing Undo with a Generic Stack Class
using System;
using System.Collections.Generic;
class Program
{
// ...
public void Sketch()
{
Stack<Cell> path; // Generic variable declaration
path = new Stack<Cell>(); // Generic object instantiation
Cell currentPosition;
ConsoleKeyInfo key;
do
{
// Etch in the direction indicated by the
// arrow keys entered by the user.
key = Move();
switch (key.Key)
{
case ConsoleKey.Z:
// Undo the previous Move.
if (path.Count >= 1)
{
// No cast required.
currentPosition = path.Pop();
Console.SetCursorPosition(
currentPosition.X, currentPosition.Y);
Undo();
}
break;
case ConsoleKey.DownArrow:
case ConsoleKey.UpArrow:
case ConsoleKey.LeftArrow:
case ConsoleKey.RightArrow:
// SaveState()
currentPosition = new Cell(
Console.CursorLeft, Console.CursorTop);
// Only type Cell allowed in call to Push().
path.Push(currentPosition);
break;
default:
Console.Beep(); // Added in C# 2.0
break;
}
} while (key.Key != ConsoleKey.X); // Use X to quit.
}
}
The results of Listing 11.6 appear in Output 11.2.
In the path declaration shown in Listing 11.6, you declare a variable and initialize it with a new instance of the System.Collections.Generic.Stack<Cell> class. You specify in angle brackets that the data type of the stack’s elements is Cell. As a result, every object added to and retrieved from path is of type Cell. In turn, you no longer need to cast the return of path.Pop() or ensure that only Cell type objects are added to path in the Push() method.
Defining a Simple Generic Class
Generics allow you to author algorithms and patterns, and reuse the code for different data types. Listing 11.7 creates a generic Stack<T> class similar to the System.Collections.Generic.Stack<T> class used in the code in Listing 11.6. You specify a type parameter (in this case, T) within angle brackets after the class name. The generic Stack<T> can then be supplied with a single type argument that is “substituted” everywhere T appears in the class. Thus the stack can store items of any stated type, without duplicating code or converting the item to type object. The type parameter T is a placeholder that must be supplied with a type argument. In Listing 11.7, you can see that the type parameter will be used for the internal Items array, the type for the parameter to the Push() method, and the return type for the Pop() method.
LISTING 11.7: Declaring a Generic Class, Stack<T>
public class Stack<T>
{
// Use read-only field prior to C# 6.0
private T[] InternalItems { get; }
public void Push(T data)
{
...
}
public T Pop()
{
...
}
}
Benefits of Generics
There are several advantages to using a generic class over a nongeneric version (such as the System.Collections.Generic.Stack<T> class used earlier instead of the original System.Collections.Stack type).
1. Generics facilitate increased type safety, preventing data types other than those explicitly intended by the members within the parameterized class. In Listing 11.7, the parameterized stack class restricts you to the Cell data type when using Stack<Cell>. (For example, the statement path.Push("garbage") produces a compile-time error indicating that there is no overloaded method for System.Collections.Generic.Stack<T>.Push(T) that can work with the string, because it cannot be converted to a Cell.)
2. Compile-time type checking reduces the likelihood of InvalidCastException type errors at runtime.
3. Using value types with generic class members no longer causes a boxing conversion to object. (For example, path.Pop() and path.Push() do not require an item to be boxed when added or unboxed when removed.)
4. Generics in C# reduce code bloat. Generic types retain the benefits of specific class versions, without the overhead. (For example, it is no longer necessary to define a class such as CellStack.)
5. Performance improves because casting from an object is no longer required, thereby eliminating a type check operation. Also, performance improves because boxing is no longer necessary for value types.
6. Generics reduce memory consumption by avoiding boxing and, therefore, consuming less memory on the heap.
7. Code becomes more readable because of fewer casting checks and because of the need for fewer type-specific implementations.
8. Editors that assist coding via some type of IntelliSense work directly with return parameters from generic classes. There is no need to cast the return data for IntelliSense to work.
At their core, generics offer the ability to code pattern implementations and then reuse those implementations wherever the patterns appear. Patterns describe problems that occur repeatedly within code, and templates provide a single implementation for these repeating patterns.
Type Parameter Naming Guidelines
Just as when you name a method’s formal parameter, so you should be as descriptive as possible when naming a type parameter. Furthermore, to distinguish the parameter as being a type parameter, its name should include a T prefix. For example, in defining a class such as EntityCollection<TEntity>, you use the type parameter name “TEntity.”
The only time you would not use a descriptive type parameter name is when such a description would not add any value. For example, using “T” in the Stack<T> class is appropriate, since the indication that “T” is a type parameter is sufficiently descriptive; the stack works for any type.
In the next section, you will learn about constraints. It is a good practice to use constraint-descriptive type names. For example, if a type parameter must implement IComponent, consider a type name of “TComponent.”
Guidelines
DO choose meaningful names for type parameters and prefix the name with T.
CONSIDER indicating a constraint in the name of a type parameter.
Generic Interfaces and Structs
C# supports the use of generics throughout the language, including interfaces and structs. The syntax is identical to that used by classes. To declare an interface with a type parameter, place the type parameter in angle brackets immediately after the interface name, as shown in the example of IPair<T> in Listing 11.8.
LISTING 11.8: Declaring a Generic Interface
interface IPair<T>
{
T First { get; set; }
T Second { get; set; }
}
This interface represents pairs of like objects, such as the coordinates of a point, a person’s genetic parents, or nodes of a binary tree. The type contained in the pair is the same for both items.
To implement the interface, you use the same syntax as you would for a nongeneric class. Note that it is legal, and indeed common, for the type argument for one generic type to be a type parameter of another, as shown in Listing 11.9. The type argument of the interface is the type parameter declared by the class. In addition, this example uses a struct rather than a class, demonstrating that C# supports custom generic value types.
LISTING 11.9: Implementing a Generic Interface
public struct Pair<T>: IPair<T>
{
public T First { get; set; }
public T Second { get; set; }
}
Support for generic interfaces is especially important for collection classes, where generics are most prevalent. Before generics, developers relied on a series of interfaces within the System.Collections namespace. Like their implementing classes, these interfaces worked only with type object, and as a result, the interface forced all access to and from these collection classes to require a cast. By using type-safe generic interfaces, you can avoid cast operations.
Defining a Constructor and a Finalizer
Perhaps surprisingly, the constructors (and finalizer) of a generic class or struct do not require type parameters; in other words, they do not require Pair<T>(){...}. In the pair example in Listing 11.11, the constructor is declared using public Pair(T first, T second).
LISTING 11.11: Declaring a Generic Type’s Constructor
public struct Pair<T>: IPair<T>
{
public Pair(T first, T second)
{
First = first;
Second = second;
}
public T First { get; set; }
public T Second { get; set; }
}
Specifying a Default Value
Listing 11.11 included a constructor that takes the initial values for both First and Second, and assigns them to _First and _Second. Since Pair<T> is a struct, any constructor you provide must initialize all fields. This presents a problem, however. Consider a constructor for Pair<T> that initializes only half of the pair at instantiation time.
Defining such a constructor, as shown in Listing 11.12, causes a compile-time error because the field _Second is still uninitialized at the end of the constructor. Providing initialization for _Second presents a problem because you don’t know the data type of T. If it is a reference type, null would work, but this approach would not work if T were a non-nullable value type.
LISTING 11.12: Not Initializing All Fields, Causing a Compile-Time Error
public struct Pair<T>: IPair<T>
{
// ERROR: Field 'Pair<T>._second' must be fully assigned
// before control leaves the constructor
// public Pair(T first)
// {
// First = first;
// }
// ...
}
To deal with this scenario, C# provides the default operator, first discussed in Chapter 8. In Chapter 8, we showed how the default value of int could be specified with default(int). In the case of T, which _Second requires, you can use default(T) as shown in Listing 11.13.
LISTING 11.13: Initializing a Field with the default Operator
public struct Pair<T>: IPair<T>
{
public Pair(T first)
{
First = first;
Second = default(T);
}
// ...
}
The default operator can provide the default value for any type, including type parameters.
Multiple Type Parameters
Generic types may declare any number of type parameters. The initial Pair<T> example contains only one type parameter. To enable support for storing a dichotomous pair of objects, such as a name/value pair, you could create a new version of the type that declares two type parameters, as shown in Listing 11.14.
LISTING 11.14: Declaring a Generic with Multiple Type Parameters
interface IPair<TFirst, TSecond>
{
TFirst First { get; set; }
TSecond Second { get; set; }
}
public struct Pair<TFirst, TSecond>: IPair<TFirst, TSecond>
{
public Pair(TFirst first, TSecond second)
{
First = first;
Second = second;
}
public TFirst First { get; set; }
public TSecond Second { get; set; }
}
When you use the Pair<TFirst, TSecond> class, you supply multiple type parameters within the angle brackets of the declaration and instantiation statements; you then supply matching types to the parameters of the methods when you call them. Listing 11.15 illustrates this approach.
LISTING 11.15: Using a Type with Multiple Type Parameters
Pair<int, string> historicalEvent =
new Pair<int, string>(1914,
"Shackleton leaves for South Pole on ship Endurance");
Console.WriteLine("{0}: {1}",
historicalEvent.First, historicalEvent.Second);
The number of type parameters—that is, the arity—uniquely distinguishes the class from others of the same name. Therefore, it is possible to define both Pair<T> and Pair<TFirst, TSecond> within the same namespace because of the arity variation. Furthermore, because of their close semantic relationship, generics that differ only by arity should be placed into the same C# file.
Guidelines
DO place multiple generic classes into a single file if they differ only by the number of generic parameters.
Begin 4.0
Arity in Abundance
In C# 4.0, the CLR team defined nine new generic types, all called Tuple. As with Pair<...>, it was possible to reuse the same name because of the variation in arity (each class had a different number of type parameters), as shown in Listing 11.16.
LISTING 11.16: Using Arity to Overload a Type Definition
public class Tuple { ... }
public class Tuple<T1>:
IStructuralEquatable, IStructuralComparable, IComparable {...}
public class Tuple<T1, T2>: ... {...}
public class Tuple<T1, T2, T3>: ... {...}
public class Tuple<T1, T2, T3, T4>: ... {...}
public class Tuple<T1, T2, T3, T4, T5>: ... {...}
public class Tuple<T1, T2, T3, T4, T5, T6>: ... {...}
public class Tuple<T1, T2, T3, T4, T5, T6, T7>: ... {...}
public class Tuple<T1, T2, T3, T4, T5, T6, T7, TRest>: ... {...}
The Tuple<...> set of classes was designed for the same purpose as the Pair<T> and Pair<TFirst, TSecond> classes, except together they can handle seven type arguments. In fact, using the last Tuple shown in Listing 11.16, TRest can be used to store another Tuple, making the number of elements of the tuple practically unlimited.
Another interesting member of the tuple family of classes is the nongeneric Tuple class. This class has eight static “factory” methods for instantiating the various generic tuple types. Although each generic type could be instantiated directly using its constructor, the Tuple type’s factory methods allow for inference of the type arguments. Listing 11.17 shows the difference.
LISTING 11.17: Using a Tuple’s Create() Factory Methods
Tuple<string, Contact> keyValuePair;
keyValuePair =
Tuple.Create(
"555-55-5555", new Contact("Inigo Montoya"));
keyValuePair =
new Tuple<string, Contact>(
"555-55-5555", new Contact("Inigo Montoya"));
Obviously, when the Tuple gets large, the number of type parameters to specify could be cumbersome without the Create() factory methods.
As you might have deduced from the fact that the framework libraries declare eight different generic tuple types, there is no support in the CLR type system for “variadic” generic types. Methods can take an arbitrary number of arguments by using “parameter arrays,” but there is no corresponding technique for generic types; every generic type must be of a specific arity.
End 4.0
Nested Generic Types
Type parameters on a containing generic type will “cascade” down to any nested types automatically. If the containing type declares a type parameter T, for example, all nested types will also be generic and type parameter T will be available on the nested type as well. If the nested type includes its own type parameter named T, this will hide the type parameter within the containing type and any reference to T in the nested type will refer to the nested T type parameter. Fortunately, reuse of the same type parameter name within the nested type will cause a compiler warning to prevent accidental overlap (see Listing 11.18).
LISTING 11.18: Nested Generic Types
class Container<T, U>
{
// Nested classes inherit type parameters.
// Reusing a type parameter name will cause
// a warning.
class Nested<U>
{
void Method(T param0, U param1)
{
}
}
}
The containing type’s type parameters are accessible in the nested type the same way that members of the containing type are also accessible from the nested type. The rule is simply that a type parameter is available anywhere within the body of the type that declares it.
Guidelines
AVOID shadowing a type parameter of an outer type with an identically named type parameter of a nested type.
Constraints
Generics support the ability to define constraints on type parameters. These constraints ensure that the types provided as type arguments conform to various rules. Take, for example, the BinaryTree<T> class shown in Listing 11.19.
LISTING 11.19: Declaring a BinaryTree<T> Class with No Constraints
public class BinaryTree<T>
{
public BinaryTree ( T item)
{
Item = item;
}
public T Item { get; set; }
public Pair<BinaryTree<T>> SubItems { get; set; }
}
(An interesting side note is that BinaryTree<T> uses Pair<T> internally, which is possible because Pair<T> is simply another type.)
Suppose you want the tree to sort the values within the Pair<T> value as it is assigned to the SubItems property. To achieve the sorting, the SubItems set accessor uses the CompareTo() method of the supplied key, as shown in Listing 11.20.
LISTING 11.20: Needing the Type Parameter to Support an Interface
public class BinaryTree<T>
{
public T Item { get; set; }
public Pair<BinaryTree<T>> SubItems
{
get{ return _SubItems; }
set
{
IComparable<T> first;
// ERROR: Cannot implicitly convert type...
first = value.First; // Explicit cast required
if (first.CompareTo(value.Second) < 0)
{
// first is less than second.
// ...
}
else
{
// first and second are the same or
// second is less than first.
// ...
}
_SubItems = value;
}
}
private Pair<BinaryTree<T>> _SubItems;
}
At compile time, the type parameter T is an unconstrained generic. When the code is written as shown in Listing 11.20, the compiler assumes that the only members available on T are those inherited from the base type object, since every type has object as a base class. Only methods such as ToString(), therefore, are available to call on an instance of the type parameter T. As a result, the compiler displays a compilation error because the CompareTo() method is not defined on type object.
You can cast the T parameter to the IComparable<T> interface to access the CompareTo() method, as shown in Listing 11.21.
LISTING 11.21: Needing the Type Parameter to Support an Interface or Exception Thrown
public class BinaryTree<T>
{
public T Item { get; set; }
public Pair<BinaryTree<T>> SubItems
{
get{ return _SubItems; }
set
{
IComparable<T> first;
first = (IComparable<T>)value.First.Item;
if (first.CompareTo(value.Second.Item) < 0)
{
// first is less than second.
...
}
else
{
// second is less than or equal to first.
...
}
_SubItems = value;
}
}
private Pair<BinaryTree<T>> _SubItems;
}
Unfortunately, if you now declare a BinaryTree<SomeType> class variable but the type argument does not implement the IComparable<SomeType> interface, you will encounter an execution-time error—specifically, an InvalidCastException. This eliminates a key reason for having generics in the first place: to improve type safety.
To avoid this exception and instead generate a compile-time error if the type argument does not implement the interface, C# allows you to supply an optional list of constraints for each type parameter declared in the generic type. A constraint declares the characteristics that the generic type requires of the type argument supplied for each type parameter. You declare a constraint using the where keyword, followed by a “parameter–requirements” pair, where the parameter must be one of those declared in the generic type and the requirements describe the class or interfaces to which the type argument must be convertible, the presence of a default constructor, or a reference/value type restriction.
Interface Constraints
To ensure that a binary tree has its nodes correctly ordered, you can use the CompareTo() method in the BinaryTree class. To do this most effectively, you should impose a constraint on the T type parameter. That is, you need the T type parameter to implement the IComparable<T> interface. The syntax for declaring this constraint appears in Listing 11.22.
LISTING 11.22: Declaring an Interface Constraint
public class BinaryTree<T>
where T: System.IComparable<T>
{
public T Item { get; set; }
public Pair<BinaryTree<T>> SubItems
{
get{ return _SubItems; }
set
{
IComparable<T> first;
// Notice that the cast can now be eliminated.
first = value.First.Item;
if (first.CompareTo(value.Second.Item) < 0)
{
// first is less than second.
...
}
else
{
// second is less than or equal to first.
...
}
_SubItems = value;
}
}
private Pair<BinaryTree<T>> _SubItems;
}
When given the interface constraint addition in Listing 11.22, the compiler ensures that each time you use the BinaryTree<T> class, you specify a type parameter that implements the corresponding construction of the IComparable<T> interface. Furthermore, you no longer need to explicitly cast the variable to an IComparable<T> interface before calling the CompareTo() method. Casting is not even required to access members that use explicit interface implementation, which in other contexts would hide the member without a cast. When calling a method on a value typed as a generic type parameter, the compiler checks whether the method matches any method on any of the interfaces declared as constraints.
If you tried to create a BinaryTree<T> variable using System.Text.StringBuilder as the type parameter, you would receive a compiler error because StringBuilder does not implement IComparable<StringBuilder>. The error is similar to the one shown in Output 11.3.
error CS0311: The type 'System.Text.StringBuilder' cannot be used as type
parameter 'T' in the generic type or method 'BinaryTree<T>'. There is no
implicit reference conversion from 'System.Text.StringBuilder' to
'System.IComparable<System.Text.StringBuilder>'.
To specify an interface for the constraint, you declare an interface type constraint. This constraint even circumvents the need to cast so as to call an explicit interface member implementation.
Class Type Constraints
Sometimes you might want to constrain a type argument to be convertible to a particular class type. You do this using a class type constraint, as shown in Listing 11.23.
LISTING 11.23: Declaring a Class Type Constraint
public class EntityDictionary<TKey, TValue>
: System.Collections.Generic.Dictionary<TKey, TValue>
where TValue : EntityBase
{
...
}
In Listing 11.23, EntityDictionary<TKey, TValue> requires that all type arguments provided for the type parameter TValue be implicitly convertible to the EntityBase class. By requiring the conversion, it becomes possible to use the members of EntityBase on values of type TValue within the generic implementation, because the constraint will ensure that all type arguments can be implicitly converted to the EntityBase class.
The syntax for the class type constraint is the same as that for the interface type constraint, except that class type constraints must appear before any interface type constraints (just as the base class must appear before implemented interfaces in a class declaration). However, unlike interface constraints, multiple base class constraints are not allowed since it is not possible to derive from multiple unrelated classes. Similarly, base class constraints cannot specify sealed classes or nonclass types. For example, C# does not allow a type parameter to be constrained to string or System.Nullable<T> because there would then be only one possible type argument for that type parameter—that’s hardly “generic.” If the type parameter is constrained to a single type, there is no need for the type parameter in the first place; just use that type directly.
Certain “special” types are not legal as class type constraints. See the Advanced Topic “Constraint Limitations,” later in this chapter, for details.
struct/class Constraints
Another valuable generic constraint is the ability to restrict type arguments to be any non-nullable value type or any reference type. Instead, C# provides special syntax that works for reference types as well. Rather than specifying a class from which T must derive, you simply use the keyword struct or class, as shown in Listing 11.24.
LISTING 11.24: Specifying the Type Parameter As a Value Type
public struct Nullable<T> :
IFormattable, IComparable,
IComparable<Nullable<T>>, INullable
where T : struct
{
// ...
}
Note that the class constraint—somewhat confusingly—does not restrict the type argument to class types; rather, it restricts it to reference types. A type argument supplied for a type parameter constrained with the class constraint may be any class, interface, delegate, or array type.
Because a class type constraint requires a particular class, using a struct constraint with a class type constraint would be contradictory. Therefore, you cannot combine struct and class constraints.
The struct constraint has one special characteristic: Nullable value types do not satisfy the constraint. Why? Nullable value types are implemented as the generic type Nullable<T>, which itself applies the struct constraint to T. If nullable value types satisfied that constraint, it would be possible to define the nonsense type Nullable<Nullable<int>>. A doubly nullable integer is confusing to the point of being meaningless. (As expected, the shorthand syntax int?? is also disallowed.)
Multiple Constraints
For any given type parameter, you may specify any number of interface type constraints, but no more than one class type constraint (just as a class may implement any number of interfaces but inherit from only one other class). Each new constraint is declared in a comma-delimited list following the generic type parameter and a colon. If there is more than one type parameter, each must be preceded by the where keyword. In Listing 11.25, the generic EntityDictionary class declares two type parameters: TKey and TValue. The TKey type parameter has two interface type constraints, and the TValue type parameter has one class type constraint.
LISTING 11.25: Specifying Multiple Constraints
public class EntityDictionary<TKey, TValue>
: Dictionary<TKey, TValue>
where TKey : IComparable<TKey>, IFormattable
where TValue : EntityBase
{
...
}
In this case, there are multiple constraints on TKey itself and an additional constraint on TValue. When specifying multiple constraints on one type parameter, an AND relationship is assumed. If a type C is supplied as the type argument for TKey, C must implement IComparable<C> and IFormattable, for example.
Notice there is no comma between each where clause.
Constructor Constraints
In some cases, it is desirable to create an instance of the type argument’s type inside the generic class. In Listing 11.26, for example, the MakeValue() method for the EntityDictionary<TKey, TValue> class must create an instance of the type argument corresponding to type parameter TValue.
LISTING 11.26: Requiring a Default Constructor Constraint
public class EntityBase<TKey>
{
public TKey Key { get; set; }
}
public class EntityDictionary<TKey, TValue> :
Dictionary<TKey, TValue>
where TKey: IComparable<TKey>, IFormattable
where TValue : EntityBase<TKey>, new()
{
// ...
public TValue MakeValue(TKey key)
{
TValue newEntity = new TValue();
newEntity.Key = key;
Add(newEntity.Key, newEntity);
return newEntity;
}
// ...
}
Because not all objects are guaranteed to have public default constructors, the compiler does not allow you to call the default constructor on an unconstrained type parameter. To override this compiler restriction, you can add the text new() after all other constraints are specified. This text is a constructor constraint, and it requires the type argument corresponding to the constrained type parameter to have a public default constructor. Only the default constructor constraint is available. You cannot specify a constraint that ensures that the type argument supplied provides a constructor that takes formal parameters.
Constraint Inheritance
Neither generic type parameters nor their constraints are inherited by a derived class, because generic type parameters are not members. (Remember, class inheritance is the property that the derived class has all of the members of the base class.) It is a common practice to make new generic types that inherit from other generic types. In such a case, because the type parameters of the derived generic type become the type arguments of the generic base class, the type parameters must have equal (or stronger) constraints as those on the base class. Confused? Consider Listing 11.27.
LISTING 11.27: Inherited Constraints Specified Explicitly
class EntityBase<T> where T : IComparable<T>
{
// ...
}
// ERROR:
// The type 'U' must be convertible to
// 'System.IComparable<U>' to use it as parameter
// 'T' in the generic type or method.
// class Entity<U> : EntityBase<U>
// {
// ...
// }
In Listing 11.27, EntityBase<T> requires that the type argument U supplied for T by the base class specifier EntityBase<U> implement IComparable<U>. Therefore, the Entity<U> class needs to require the same constraint on U. Failure to do so will result in a compile-time error. This pattern increases a programmer’s awareness of the base class’s type constraint in the derived class, avoiding the confusion that might otherwise occur when the programmer uses the derived class and discovers the constraint but does not understand where it comes from.
We have not covered generic methods yet; we’ll get to them later in this chapter. For now, simply recognize that methods may also be generic and may also place constraints on the type arguments supplied for their type parameters. How, then, are constraints handled when a virtual generic method is inherited and overridden? In contrast to the situation with type parameters declared on a generic class, constraints on overriding virtual generic methods (or explicit interface) methods are inherited implicitly and may not be restated (see Listing 11.28).
LISTING 11.28: Repeating Inherited Constraints on Virtual Members Is Prohibited
class EntityBase
{
public virtual void Method<T>(T t)
where T : IComparable<T>
{
// ...
}
}
class Order : EntityBase
{
public override void Method<T>(T t)
// Constraints may not be repeated on overriding
// members
// where T : IComparable<T>
{
// ...
}
}
In the generic class inheritance case, the type parameter on the derived class can be further constrained by adding not only the constraints on the base class (required), but also other constraints. However, overriding virtual generic methods need to conform exactly to the constraints defined by the base class method. Additional constraints could break polymorphism, so they are not allowed and the type parameter constraints on the overriding method are implied.
Generic Methods
Earlier, you saw that it is a relatively simple matter to add a method to a type when the type is generic; such a method can use the generic type parameters declared by the type. You did this, for example, in the generic class examples we have seen so far.
Generic methods use generic type parameters, much as generic types do. They can be declared in generic or nongeneric types. If declared in a generic type, their type parameters are distinct from those of their containing generic type. To declare a generic method, you specify the generic type parameters the same way you do for generic types: Add the type parameter declaration syntax immediately following the method name, as shown in the MathEx.Max<T> and MathEx.Min<T> examples in Listing 11.35.
LISTING 11.35: Defining Generic Methods
public static class MathEx
{
public static T Max<T>(T first, params T[] values)
where T : IComparable<T>
{
T maximum = first;
foreach (T item in values)
{
if (item.CompareTo(maximum) > 0)
{
maximum = item;
}
}
return maximum;
}
public static T Min<T>(T first, params T[] values)
where T : IComparable<T>
{
T minimum = first;
foreach (T item in values)
{
if (item.CompareTo(minimum) < 0)
{
minimum = item;
}
}
return minimum;
}
}
In this example, the method is static, although C# does not require this.
Generic methods, like generic types, can include more than one type parameter. The arity (the number of type parameters) is an additional distinguishing characteristic of a method signature. That is, it is legal to have two methods that are identical in their names and formal parameter types, as long as they differ in method type parameter arity.
Generic Method Type Inference
Just as type arguments are provided after the type name when using a generic type, so the method type arguments are provided after the method type name. The code used to call the Min<T> and Max<T> methods looks like that shown in Listing 11.36.
LISTING 11.36: Specifying the Type Parameter Explicitly
Console.WriteLine(
MathEx.Max<int>(7, 490));
Console.WriteLine(
MathEx.Min<string>("R.O.U.S.", "Fireswamp"));
The output to Listing 11.36 appears in Output 11.4.
490
Fireswamp
Not surprisingly, the type arguments, int and string, correspond to the actual types used in the generic method calls. However, specifying the type arguments is redundant because the compiler can infer the type parameters from the formal parameters passed to the method. Clearly, the caller of Max in Listing 11.36 intends the type argument to be int because both of the method arguments are of type int. To avoid redundancy, you can exclude the type parameters from the call in all cases when the compiler is able to logically infer which type arguments you must have intended. An example of this practice, which is known as method type inference, appears in Listing 11.37. The output appears in Output 11.5.
LISTING 11.37: Inferring the Type Argument from the Arguments
Console.WriteLine(
MathEx.Max(7, 490)); // No type arguments!
Console.WriteLine(
MathEx.Min("R.O.U.S'", "Fireswamp"));
490
Fireswamp
For method type inference to succeed, the types of the arguments must be “matched” with the formal parameters of the generic method in such a way that the desired type arguments can be inferred. An interesting question to consider is what happens when contradictory inferences are made. For example, when you call the Max<T> method using MathEx.Max(7.0, 490), the compiler could deduce from the first argument that the type argument should be double, and it could deduce from the second argument that the type argument is int, a contradiction. In C# 2.0, this would have produced an error. A more sophisticated analysis would notice that the contradiction can be resolved because every int can be converted to double, so double is the best choice for the type argument. C# 3.0 and C# 4.0 both included improvements to the method type inferencing algorithm that permit the compiler to make these more sophisticated analyses.
In cases where method type inference is still not sophisticated enough to deduce the type arguments, you can resolve the error either by inserting casts on the arguments that clarify to the compiler the argument types that should be used in the inferences, or by giving up on type inferencing and including the type arguments explicitly.
Notice that the method type inference algorithm, when making its inferences, considers only the arguments, the arguments’ types, and the formal parameter types of the generic method. Other factors that could, in practice, be used in the analysis—such as the return type of the generic method, the type of the variable that the method’s returned value is being assigned to, or the constraints on the method’s generic type parameters—are not considered at all by the method type inference algorithm.
Specifying Constraints
Type parameters of generic methods may be constrained in exactly the same way that type parameters of generic types are constrained. For example, you can restrict a method’s type parameter to implement an interface or to be convertible to a class type. The constraints are specified between the argument list and the method body, as shown in Listing 11.38.
LISTING 11.38: Specifying Constraints on Generic Methods
public class ConsoleTreeControl
{
// Generic method Show<T>
public static void Show<T>(BinaryTree<T> tree, int indent)
where T : IComparable<T>
{
Console.WriteLine("
{0}{1}",
"+ --".PadLeft(5*indent, ' '),
tree.Item.ToString());
if (tree.SubItems.First != null)
Show(tree.SubItems.First, indent+1);
if (tree.SubItems.Second != null)
Show(tree.SubItems.Second, indent+1);
}
}
Here, the Show<T> implementation itself does not directly use any member of the IComparable<T> interface, so you might wonder why the constraint is required. Recall, however, that the BinaryTree<T> class did require this constraint (see Listing 11.39).
LISTING 11.39: BinaryTree<T> Requiring IComparable<T> Type Parameters
public class BinaryTree<T>
where T: System.IComparable<T>
{
...
}
Because the BinaryTree<T> class requires this constraint on its T, and because Show<T> uses its T as a type argument corresponding to a constrained type parameter, Show<T> needs to ensure that the constraint on the class’s type parameter is met on its method type argument.
Covariance and Contravariance
A question often asked by new users of generic types is why an expression of type List<string> may not be assigned to a variable of type List<object>—if a string may be converted to type object, surely a list of strings is similarly compatible with a list of objects. But this is not, generally speaking, either type-safe or legal. If you declare two variables with different type parameters using the same generic class, the variables are not type-compatible even if they are assigning from a more specific type to a more generic type—in other words, they are not covariant.
Covariant is a technical term from category theory, but its underlying idea is straightforward: Suppose two types X and Y have a special relationship—namely, that every value of the type X may be converted to the type Y. If the types I<X> and I<Y> always also have that same special relationship, we say, “I<T> is covariant in T.” When dealing with simple generic types with only one type parameter, the type parameter can be understood and we simply say, “I<T> is covariant.” The conversion from I<X> to I<Y> is called a covariant conversion.
For example, instances of a generic class, Pair<Contact> and Pair<PdaItem>, are not type-compatible even when the type arguments are themselves compatible. In other words, the compiler prevents the conversion (implicit or explicit) of Pair<Contact> to Pair<PdaItem>, even though Contact derives from PdaItem. Similarly, converting Pair<Contact> to the interface type IPair<PdaItem> will also fail. See Listing 11.40 for an example.
LISTING 11.40: Conversion between Generics with Different Type Parameters
// ...
// Error: Cannot convert type ...
Pair<PdaItem> pair = (Pair<PdaItem>) new Pair<Contact>();
IPair<PdaItem> duple = (IPair<PdaItem>) new Pair<Contact>();
But why is this not legal? Why are List<T> and Pair<T> not covariant? Listing 11.41 shows what would happen if the C# language allowed unrestricted generic covariance.
LISTING 11.41: Preventing Covariance Maintains Homogeneity
//...
Contact contact1 = new Contact("Princess Buttercup"),
Contact contact2 = new Contact("Inigo Montoya");
Pair<Contact> contacts = new Pair<Contact>(contact1, contact2);
// This gives an error: Cannot convert type ...
// But suppose it did not.
// IPair<PdaItem> pdaPair = (IPair<PdaItem>) contacts;
// This is perfectly legal, but not type-safe.
// pdaPair.First = new Address("123 Sesame Street");
...
An IPair<PdaItem> can contain an address, but the object is really a Pair<Contact> that can contain only contacts, not addresses. Type safety is completely violated if unrestricted generic covariance is allowed.
Now it should also be clear why a list of strings may not be used as a list of objects. You cannot insert an integer into a list of strings, but you can insert an integer into a list of objects; thus it must be illegal to cast a list of strings to a list of objects, an error the compiler can enforce.
Begin 4.0
Enabling Covariance with the out Type Parameter Modifier in C# 4.0
You might have noticed that both of the problems described earlier as consequences of unrestricted covariance arise because the generic pair and the generic list allow their contents to be written. Suppose we eliminated this possibility by making a read-only IReadOnlyPair<T> interface that exposes T only as coming “out” of the interface (that is, used as the return type of a method or read-only property) and never going “into” it (that is, used as a formal parameter or writeable property type). If we restricted ourselves to an “out only” interface with respect to T, the covariance problem just described would not occur (see Listing 11.42).
LISTING 11.42: Potentially Possible Covariance
interface IReadOnlyPair<T>
{
T First { get; }
T Second { get; }
}
interface IPair<T>
{
T First { get; set; }
T Second { get; set; }
}
public struct Pair<T> : IPair<T>, IReadOnlyPair<T>
{
// ...
}
class Program
{
static void Main()
{
// Error: Only theoretically possible without
// the out type parameter modifier
Pair<Contact> contacts =
new Pair<Contact>(
new Contact("Princess Buttercupt"),
new Contact("Inigo Montoya") );
IReadOnlyPair<PdaItem> pair = contacts;
PdaItem pdaItem1 = pair.First;
PdaItem pdaItem2 = pair.Second;
}
}
When we restrict the generic type declaration to expose data only as it comes out of the interface, there is no reason for the compiler to prevent covariance. All operations on an IReadOnlyPair<PdaItem> instance would convert Contacts (from the original Pair<Contact> object) up to the base class PdaItem—a perfectly valid conversion. There is no way to “write” an address into the object that is really a pair of contacts, because the interface does not expose any writeable properties.
The code in Listing 11.42 still does not compile. However, support for safe covariance was added to C# 4. To indicate that a generic interface is intended to be covariant in one of its type parameters, you can declare the type parameter with the out type parameter modifier. Listing 11.43 shows how to modify the interface declaration to indicate that it should be allowed to be covariant.
LISTING 11.43: Covariance Using the out Type Parameter Modifier
...
interface IReadOnlyPair<out T>
{
T First { get; }
T Second { get; }
}
Modifying the type parameter on the IReadOnlyPair<out T> interface with out will cause the compiler to verify that T is, indeed, used only for “outputs”—method return types and read-only property return types—and never for formal parameters or property setters. From then on, the compiler will allow any covariant conversions involving the interface to succeed. When this modification is made to the code in Listing 11.42, it will compile and execute successfully.
A number of important restrictions are placed on covariant conversions:
• Only generic interfaces and generic delegates (described in Chapter 12) may be covariant. Generic classes and structs are never covariant.
• The varying type arguments of both the “source” and “target” generic types must be reference types, not value types. That is, an IReadOnlyPair<string> may be converted covariantly to IReadOnlyPair<object> because both string and IReadOnlyPair<object> are reference types. An IReadOnlyPair<int> may not be converted to IReadOnlyPair<object> because int is not a reference type.
• The interface or delegate must be declared as supporting covariance, and the compiler must be able to verify that the annotated type parameters are, in fact, used in only “output” positions.
Enabling Contravariance with the in Type Parameter Modifier in C# 4.0
Covariance that “goes backward” is called contravariance. Again, suppose two types X and Y are related such that every value of the type X may be converted to the type Y. If the types I<X> and I<Y> always have that same special relationship “backward”—that is, every value of the type I<Y> can be converted to the type I<X>—we say, “I<T> is contravariant in T.”
Most people find that contravariance is much harder to comprehend than covariance is. The canonical example of contravariance is a comparer. Suppose you have a derived type, Apple, and a base type, Fruit. Clearly, they have the special relationship: Every value of type Apple may be converted to Fruit.
Now suppose you have an interface ICompareThings<T> that has a method bool FirstIsBetter(T t1, T t2) that takes two Ts, and returns a bool saying whether the first one is better than the second one.
What happens when we provide type arguments? An ICompareThings<Apple> has a method that takes two Apples and compares them. An ICompareThings<Fruit> has a method that takes two Fruits and compares them. But since every Apple is a Fruit, clearly a value of type ICompareThings<Fruit> can be safely used anywhere that an ICompareThings<Apple> is needed. The “direction” of the convertibility has been “reversed”; hence the term “contra-variance.”
Perhaps unsurprisingly, the opposite of the restrictions on a covariant interface are necessary to ensure safe contravariance. An interface that is contravariant in one of its type parameters must use that type parameter only in “input” positions such as formal parameters (or in the types of write-only properties, which are extremely rare). You can mark an interface as being contravariant by declaring the type parameter with the in modifier, as shown in Listing 11.44.
LISTING 11.44: Contravariance Using the in Type Parameter Modifier
class Fruit {}
class Apple : Fruit {}
class Orange : Fruit {}
interface ICompareThings<in T>
{
bool FirstIsBetter(T t1, T t2);
}
class Program
{
class FruitComparer : ICompareThings<Fruit>
{ ... }
static void Main()
{
// Allowed in C# 4.0
ICompareThings<Fruit> fc = new FruitComparer();
Apple apple1 = new Apple();
Apple apple2 = new Apple();
Orange orange = new Orange();
// A fruit comparer can compare apples and oranges:
bool b1 = fc.FirstIsBetter(apple1, orange);
// or apples and apples:
bool b2 = fc.FirstIsBetter(apple1, apple2);
// This is legal because the interface is
// contravariant.
ICompareThings<Apple> ac = fc;
// This is really a fruit comparer, so it can
// still compare two apples.
bool b3 = ac.FirstIsBetter(apple1, apple2);
}
}
Similar to covariance support, contravariance uses a type parameter modifier: in, which appears in the interface’s type parameter declaration. This instructs the compiler to check that T never appears on a property getter or as the return type of a method, thereby enabling contravariant conversions for this interface.
Contravariant conversions have all the analogous restrictions as described earlier for covariant conversions: They are valid only for generic interface and delegate types, the varying type arguments must be reference types, and the compiler must be able to verify that the interface is safe for the contravariant conversions.
An interface can be covariant in one type parameter and contravariant in another, but this seldom arises in practice except with delegates. The Func<A1, A2, ..., R> family of delegates, for example, are covariant in the return type, R, and contravariant in all of the argument types.
Lastly, note that the compiler will check the validity of the covariance and contravariance type parameter modifiers throughout the source. Consider the PairInitializer<in T> interface in Listing 11.45.
LISTING 11.45: Compiler Validation of Variance
// ERROR: Invalid variance; the type parameter 'T' is not
// invariantly valid
interface IPairInitializer<in T>
{
void Initialize(IPair<T> pair);
}
// Suppose the code above were legal, and see what goes
// wrong:
class FruitPairInitializer : IPairInitializer<Fruit>
{
// Let's initiaize our pair of fruit with an
// apple and an orange:
public void Initialize(IPair<Fruit> pair)
{
pair.First = new Orange();
pair.Second = new Apple();
}
}
// ... later ...
var f = new FruitPairInitializer();
// This would be legal if contravariance were legal:
IPairInitializer<Apple> a = f;
// And now we write an orange into a pair of apples:
a.Initialize(new Pair<Apple>());
A casual observer might be tempted to think that since IPair<T> is used only as an “input” formal parameter, the contravariant in modifier on IPairInitializer is valid. However, the IPair<T> interface cannot safely vary, so it cannot be constructed with a type argument that can vary. As you can see, this would not be type-safe and, in turn, the compiler disallows the IPairInitializer<T> interface from being declared as contravariant in the first place.
Support for Unsafe Covariance in Arrays
So far we have described covariance and contravariance as being properties of generic types. Of all the nongeneric types, arrays are most like generics; that is, just as we think of a generic “list of T” or a generic “pair of T,” so we can think of an “array of T” as being the same sort of pattern. Since arrays clearly support both reading and writing, given what you know about covariance and contravariance, you probably would suppose that arrays may be neither safely contravariant nor covariant. That is, you might imagine that an array can be safely covariant only if it is never written to, and safely contravariant only if it is never read from—though neither seems like a realistic restriction.
Unfortunately, C# does support array covariance, even though doing so is not type-safe. For example, Fruit[] fruits = new Apple[10]; is perfectly legal in C#. If you then include the expression fruits[0] = new Orange();, the runtime will issue a type safety violation in the form of an exception. It is deeply disturbing that it is not always legal to assign an Orange into an array of Fruit because it might really be an array of Apples, but that is the situation in not just C#, but all CLR languages that use the runtime’s implementation of arrays.
Try to avoid using unsafe array covariance. Every array is convertible to the read-only (and therefore safely covariant) interface IEnumerable<T>; that is, IEnumerable<Fruit> fruits = new Apple[10] is both safe and legal because there is no way to insert an Orange into the array if all you have is the read-only interface.
Guidelines
AVOID unsafe array covariance. Instead, CONSIDER converting the array to the read-only interface IEnumerable<T>, which can be safely converted via covariant conversions.
End 4.0
Generic Internals
Given the discussions in earlier chapters about the prevalence of objects within the CLI type system, it should come as no surprise to learn that generics are also objects. In fact, the type parameter on a generic class becomes metadata that the runtime uses to build appropriate classes when needed. Generics, therefore, support inheritance, polymorphism, and encapsulation. With generics, you can define methods, properties, fields, classes, interfaces, and delegates.
To achieve this, generics require support from the underlying runtime. In turn, the addition of generics to the C# language is a feature of both the compiler and the platform. To avoid boxing, for example, the implementation of generics is different for value-based type parameters than for generics with reference type parameters.
Summary
The addition of generic types and methods to C# 2.0 fundamentally transformed the coding style of C# developers. In almost all cases in which programmers used object within C# 1.0 code, generics became a better choice in C# 2.0. In modern C# programs, using object (particularly in the context of any collection type) should make you consider whether the problem would be better solved with generics. The increased type safety enabled by elimination of casts, the elimination of the boxing performance penalty, and reduction of repeated code are all significant improvements.
Chapter 16 looks at one of the most pervasive generic namespaces, System.Collections.Generic. As its name implies, this namespace is composed almost exclusively of generic types. It provides clear examples of how some types that originally used objects were then converted to use generics. However, before we tackle these topics, we will investigate expressions, which provide a significant C# 3.0 (and later) improvement for working with collections.