22. Generics

...our special individuality, as distinguished from our generic humanity.

—Oliver Wendell Holmes, Sr.

Every man of genius sees the world at a different angle from his fellows.

—Havelock Ellis

Born under one law, to another bound.

—Lord Brooke

22.1 Introduction

In Chapter 21, we presented data structures that stored and manipulated object references. This chapter continues our multi-chapter discussion on data structures. You could store any object in our data structures. One inconvenient aspect of storing object references occurs when retrieving them from a collection. An application normally needs to process specific types of objects. As a result, the object references obtained from a collection typically need to be downcast to an appropriate type to allow the application to process the objects correctly. In addition, data of value types (e.g., int and double) must be boxed to be manipulated with object references, which increases the overhead of processing such data. Most importantly, processing all data as type object limits the C# compiler’s ability to perform type checking.

Though we can easily create data structures that manipulate any type of data as objects (as we did in Chapter 21), it would be nice if we could detect type mismatches at compile time—this is known as compile-time type safety. For example, if a Stack should store only int values, attempting to push a string onto that Stack should cause a compile-time error. Similarly, a Sort method should be able to compare elements that are all guaranteed to have the same type. If we create type-specific versions of class Stack class and method Sort, the C# compiler would certainly be able to ensure compile-time type safety. However, this would require that we create many copies of the same basic code.

This chapter discusses generics, which provide the means to create the general models mentioned above. Generic methods enable you to specify, with a single method declaration, a set of related methods. Generic classes enable you to specify, with a single class declaration, a set of related classes. Similarly, generic interfaces enable you to specify, with a single interface declaration, a set of related interfaces. Generics provide compile-time type safety. [Note: You can also implement generic structs and delegates.] So far in this book, we’ve used the generic types List (Chapter 9) and Dictionary (Chapter 17).

We can write a generic method for sorting an array of objects, then invoke the generic method separately with an int array, a double array, a string array and so on, to sort each different type of array. The compiler performs type checking to ensure that the array passed to the sorting method contains only elements of the correct type. We can write a single generic Stack class that manipulates a stack of objects, then instantiate Stack objects for a stack of ints, a stack of doubles, a stack of strings and so on. The compiler performs type checking to ensure that the Stack stores only elements of the correct type.

This chapter presents examples of generic methods and generic classes. It also considers the relationships between generics and other C# features, such as overloading. Chapter 23, Collections, discusses the .NET Framework’s generic and nongeneric collections classes. A collection is a data structure that maintains a group of related objects or values. The .NET Framework collection classes use generics to allow you to specify the exact types of object that a particular collection will store.

22.2 Motivation for Generic Methods

Overloaded methods are often used to perform similar operations on different types of data. To understand the motivation for generic methods, let’s begin with an example (Fig. 22.1) that contains three overloaded DisplayArray methods (lines 23–29, lines 32–38 and lines 41–47). These methods display the elements of an int array, a double array and a char array, respectively. Soon, we’ll reimplement this program more concisely and elegantly using a single generic method.

Fig. 22.1. Using overloaded methods to display arrays of different types.

The program begins by declaring and initializing three arrays—six-element int array intArray (line 10), seven-element double array doubleArray (line 11) and five-element char array charArray (line 12). Then, lines 14–19 output the arrays.

When the compiler encounters a method call, it attempts to locate a method declaration that has the same method name and parameters that match the argument types in the method call. In this example, each DisplayArray call exactly matches one of the Display-Array method declarations. For example, line 15 calls DisplayArray with intArray as its argument. At compile time, the compiler determines argument intArray’s type (i.e., int[]), attempts to locate a method named DisplayArray that specifies a single int[] parameter (which it finds at lines 23–29) and sets up a call to that method. Similarly, when the compiler encounters the DisplayArray call at line 17, it determines argument double-Array’s type (i.e., double[]), then attempts to locate a method named DisplayArray that specifies a single double[] parameter (which it finds at lines 32–38) and sets up a call to that method. Finally, when the compiler encounters the DisplayArray call at line 19, it determines argument charArray’s type (i.e., char[]), then attempts to locate a method named DisplayArray that specifies a single char[] parameter (which it finds at lines 41–47) and sets up a call to that method.

Study each DisplayArray method. Note that the array element type (int, double or char) appears in two locations in each method—the method header (lines 23, 32 and 41) and the foreach statement header (lines 25, 34 and 43). If we replace the element types in each method with a generic name (such as T for “type”) then all three methods would look like the one in Fig. 22.2. It appears that if we can replace the array element type in each of the three methods with a single “generic type parameter,” then we should be able to declare one DisplayArray method that can display the elements of any array. The method in Fig. 22.2 will not compile, because its syntax is not correct. We declare a generic Display-Array method with the proper syntax in Fig. 22.3.

Fig. 22.2. DisplayArray method in which actual type names are replaced by convention with the generic name T.

22.3 Generic-Method Implementation

If the operations performed by several overloaded methods are identical for each argument type, the overloaded methods can be more compactly and conveniently coded using a generic method. You can write a single generic-method declaration that can be called at different times with arguments of different types. Based on the types of the arguments passed to the generic method, the compiler handles each method call appropriately.

Figure 22.3 reimplements the application of Fig. 22.1 using a generic DisplayArray method (lines 24–30). Note that the DisplayArray method calls in lines 16, 18 and 20 are identical to those of Fig. 22.1, the outputs of the two applications are identical and the code in Fig. 22.3 is 17 lines shorter than that in Fig. 22.1. As illustrated in Fig. 22.3, generics enable us to create and test our code once, then reuse it for many different types of data. This demonstrates the expressive power of generics.

Fig. 22.3. Using a generic method to display arrays of different types.

Line 24 begins method DisplayArray’s declaration. All generic method declarations have a type-parameter list delimited by angle brackets (<T> in this example) that follows the method’s name. Each type-parameter list contains one or more type parameters, separated by commas. A type parameter is an identifier that’s used in place of actual type names. The type parameters can be used to declare the return type, the parameter types and the local variable types in a generic method declaration; the type parameters act as placeholders for type arguments that represent the types of data that will be passed to the generic method. A generic method’s body is declared like that of any other method. Note that the type-parameter names throughout the method declaration must match those declared in the type-parameter list. For example, line 26 declares element in the foreach statement as type T, which matches the type parameter (T) declared in line 24. Also, a type parameter can be declared only once in the type-parameter list but can appear more than once in the method’s parameter list. Type-parameter names need not be unique among different generic methods.

Method DisplayArray’s type-parameter list (line 24) declares type parameter T as the placeholder for the array-element type that DisplayArray will output. Note that T appears in the parameter list as the array-element type (line 24). The foreach statement header (line 26) also uses T as the element type. These are the same two locations where the overloaded DisplayArray methods of Fig. 22.1 specified int, double or char as the element type. The remainder of DisplayArray is identical to the version presented in Fig. 22.1.

As in Fig. 22.1, the program of Fig. 22.3 begins by declaring and initializing six-element int array intArray (line 11), seven-element double array doubleArray (line 12) and five-element char array charArray (line 13). Then each array is output by calling DisplayArray (lines 16, 18 and 20)—once with argument intArray, once with argument doubleArray and once with argument charArray.

When the compiler encounters a method call such as line 16, it analyzes the set of methods (both nongeneric and generic) that might match the method call, looking for a method that best matches the call. If there are no matching methods, or if there’s more than one best match, the compiler generates an error. If you have any uncertainty on which of your methods will be called, the complete details of method-call resolution can be found in Section 14.5.5.1 of the Ecma C# Language Specification

www.ecma-international.org/publications/standards/Ecma-334.htm

or Section 7.5.3 of the Microsoft C# Language Specification 4

bit.ly/CSharp4Spec

In the case of line 16, the compiler determines that the best match occurs if the type parameter T in lines 24 and 26 of method DisplayArray’s declaration is replaced with the type of the elements in the method call’s argument intArray (i.e., int). Then, the compiler sets up a call to DisplayArray with the int as the type argument for the type parameter T. This is known as the type-inferencing process. The same process is repeated for the calls to method DisplayArray in lines 18 and 20.

You can also use explicit type arguments to indicate the exact type that should be used to call a generic function. For example, line 16 could be written as

DisplayArray< int >( intArray ); // pass an int array argument

The preceding method call explicitly provides the type argument (int) that should be used to replace type parameter T in lines 24 and 26 of the DisplayArray method’s declaration.

For each variable declared with a type parameter, the compiler also determines whether the operations performed on such a variable are allowed for all types that the type parameter can assume. The only operation performed on the array elements in this example is to output the string representation of the elements. Line 27 performs an implicit boxing conversion for every value-type array element and an implicit ToString call on every array element. Since all objects have a ToString method, the compiler is satisfied that line 27 performs a valid operation for any array element.

By declaring DisplayArray as a generic method in Fig. 22.3, we eliminated the need for the overloaded methods of Fig. 22.1, saving 17 lines of code and creating a reusable method that can output the string representations of the elements in any one-dimensional array, not just arrays of int, double or char elements.

22.4 Type Constraints

In this section, we present a generic Maximum method that determines and returns the largest of its three arguments (all of the same type). The generic method in this example uses the type parameter to declare both the method’s return type and its parameters. Normally, when comparing values to determine which one is greater, you would use the > operator. However, this operator is not overloaded for use with every type that’s built into the Framework Class Library or that might be defined by extending those types. Generic code is restricted to performing operations that are guaranteed to work for every possible type. Thus, an expression like variable1 < variable2 is not allowed unless the compiler can ensure that the operator < is provided for every type that will ever be used in the generic code. Similarly, you cannot call a method on a generic-type variable unless the compiler can ensure that all types that will ever be used in the generic code support that method.

IComparable<T> Interface

It’s possible to compare two objects of the same type if that type implements the generic interface IComparable<T> (of namespace System). A benefit of implementing interface IComparable<T> is that IComparable<T> objects can be used with the sorting and searching methods of classes in the System.Collections.Generic namespace—we discuss those methods in Chapter 23. The structures in the Framework Class Library that correspond to the simple types all implement this interface. For example, the structure for simple type double is Double and the structure for simple type int is Int32—both Double and Int32 implement the IComparable<T> interface. Types that implement IComparable<T> must declare a CompareTo method for comparing objects. For example, if we have two ints, int1 and int2, they can be compared with the expression:

int1.CompareTo( int2 )

Method CompareTo must return 0 if the objects are equal, a negative integer if int1 is less than int2 or a positive integer if int1 is greater than int2. It’s the responsibility of the programmer who declares a type that implements IComparable<T> to define method CompareTo such that it compares the contents of two objects of that type and returns the appropriate result.

Specifying Type Constraints

Even though IComparable objects can be compared, they cannot be used with generic code by default, because not all types implement interface IComparable<T>. However, we can restrict the types that can be used with a generic method or class to ensure that they meet certain requirements. This feature—known as a type constraint—restricts the type of the argument supplied to a particular type parameter. Figure 22.4 declares method Maximum (lines 20–34) with a type constraint that requires each of the method’s arguments to be of type IComparable<T>. This restriction is important, because not all objects can be compared. However, all IComparable<T> objects are guaranteed to have a CompareTo method that can be used in method Maximum to determine the largest of its three arguments.

Fig. 22.4. Generic method Maximum returns the largest of three objects.

Generic method Maximum uses type parameter T as the return type of the method (line 20), as the type of method parameters x, y and z (line 20), and as the type of local variable max (line 23). Generic method Maximum’s where clause (after the parameter list in line 21) specifies the type constraint for type parameter T. In this case, the clause where T : IComparable<T> indicates that this method requires the type argument to implement interface IComparable<T>. If no type constraint is specified, the default type constraint is object.

C# provides several kinds of type constraints. A class constraint indicates that the type argument must be an object of a specific base class or one of its subclasses. An interface constraint indicates that the type argument’s class must implement a specific interface. The type constraint in line 20 is an interface constraint, because IComparable<T> is an interface. You can specify that the type argument must be a reference type or a value type by using the reference-type constraint (class) or the value-type constraint (struct), respectively. Finally, you can specify a constructor constraint—new()—to indicate that the generic code can use operator new to create new objects of the type represented by the type parameter. If a type parameter is specified with a constructor constraint, the type argument’s class must provide a public parameterless or default constructor to ensure that objects of the class can be created without passing constructor arguments; otherwise, a compilation error occurs.

It’s possible to apply multiple constraints to a type parameter. To do so, simply provide a comma-separated list of constraints in the where clause. If you have a class constraint, reference-type constraint or value-type constraint, it must be listed first—only one of these types of constraints can be used for each type parameter. Interface constraints (if any) are listed next. The constructor constraint is listed last (if there is one).

Analyzing the Code

Method Maximum assumes that its first argument (x) is the largest and assigns it to local variable max (line 23). Next, the if statement at lines 26–27 determines whether y is greater than max. The condition invokes y’s CompareTo method with the expression y.CompareTo(max). If y is greater than max, then y is assigned to variable max (line 27). Similarly, the statement at lines 30–31 determines whether z is greater than max. If so, line 31 assigns z to max. Then, line 33 returns max to the caller.

In Main (lines 7–16), line 10 calls Maximum with the integers 3, 4 and 5. Generic method Maximum is a match for this call, but its arguments must implement interface IComparable<T> to ensure that they can be compared. Type int is a synonym for struct Int32, which implements interface IComparable<int>. Thus, ints (and other simple types) are valid arguments to method Maximum.

Line 12 passes three double arguments to Maximum. Again, this is allowed because double is a synonym for the Double struct, which implements IComparable<double>. Line 15 passes Maximum three strings, which are also IComparable<string> objects. Note that we intentionally placed the largest value in a different position in each method call (lines 10, 12 and 15) to show that the generic method always finds the maximum value, regardless of its position in the argument list and regardless of the inferred type argument.

22.5 Overloading Generic Methods

A generic method may be overloaded. Each overloaded method must have a unique signature (as discussed in Chapter 7). A class can provide two or more generic methods with the same name but different method parameters. For example, we could provide a second version of generic method DisplayArray (Fig. 22.3) with the additional parameters low-Index and highIndex that specify the portion of the array to output.

A generic method can be overloaded by nongeneric methods with the same method name. When the compiler encounters a method call, it searches for the method declaration that best matches the method name and the argument types specified in the call. For example, generic method DisplayArray of Fig. 22.3 could be overloaded with a version specific to strings that outputs the strings in neat, tabular format. If the compiler cannot match a method call to either a nongeneric method or a generic method, or if there’s ambiguity due to multiple possible matches, the compiler generates an error.

22.6 Generic Classes

The concept of a data structure (e.g., a stack) that contains data elements can be understood independently of the element type it manipulates. A generic class provides a means for describing a class in a type-independent manner. We can then instantiate type-specific versions of the generic class. This capability is an opportunity for software reusability.

With a generic class, you can use a simple, concise notation to indicate the actual type(s) that should be used in place of the class’s type parameter(s). At compilation time, the compiler ensures your code’s type safety, and the runtime system replaces type parameters with type arguments to enable your client code to interact with the generic class.

One generic Stack class, for example, could be the basis for creating many Stack classes (e.g., “Stack of double,” “Stack of int,” “Stack of char,” “Stack of Employee”). Figure 22.5 presents a generic Stack class declaration. This class should not be confused with the class Stack from namespace System.Collections.Generics. A generic class declaration is similar to a nongeneric class declaration, except that the class name is followed by a type-parameter list (line 5) and, optionally, one or more constraints on its type parameter. Type parameter T represents the element type the Stack will manipulate. As with generic methods, the type-parameter list of a generic class can have one or more type parameters separated by commas. Type parameter T is used throughout the Stack class declaration (Fig. 22.5) to represent the element type. Class Stack declares variable elements as an array of type T (line 8). This array (created at line 21) will store the Stack’s elements. [Note: This example implements a Stack as an array. As you’ve seen in Chapter 21, Stacks also are commonly implemented as linked lists.]

Fig. 22.5. Generic class Stack.

Class Stack has two constructors. The parameterless constructor (lines 11–15) passes the default stack size (10) to the one-argument constructor, using the syntax this (line 12) to invoke another constructor in the same class. The one-argument constructor (lines 18–26) validates the stackSize argument and creates an array of the specified stackSize (if it’s greater than 0) or throws an exception, otherwise.

Method Push (lines 30–38) first determines whether an attempt is being made to push an element onto a full Stack. If so, lines 33–34 throw a FullStackException (declared in Fig. 22.6). If the Stack is not full, line 36 increments the top counter to indicate the new top position, and line 37 places the argument in that location of array elements.

Fig. 22.6. FullStackException indicates a stack is full.

Method Pop (lines 42–49) first determines whether an attempt is being made to pop an element from an empty Stack. If so, line 45 throws an EmptyStackException (declared in Fig. 22.7). Otherwise, line 47 decrements the top counter to indicate the new top position, and line 48 returns the original top element of the Stack.

Fig. 22.7. EmptyStackException indicates a stack is empty.

Classes FullStackException (Fig. 22.6) and EmptyStackException (Fig. 22.7) each provide a parameterless constructor, a one-argument constructor of exception classes (as discussed in Section 13.8) and a two-argument constructor for creating a new exception using an existing one. The parameterless constructor sets the default error message while the other two constructors set custom error messages.

As with generic methods, when a generic class is compiled, the compiler performs type checking on the class’s type parameters to ensure that they can be used with the code in the generic class. The constraints determine the operations that can be performed on the type parameters. The runtime system replaces the type parameters with the actual types at runtime. For class Stack (Fig. 22.5), no type constraint is specified, so the default type constraint, object, is used. The scope of a generic class’s type parameter is the entire class.

Now, let’s consider an application (Fig. 22.8) that uses the Stack generic class. Lines 13–14 declare variables of type Stack<double> (pronounced “Stack of double”) and Stack<int> (pronounced “Stack of int”). The types double and int are the Stack’s type arguments. The compiler replaces the type parameters in the generic class so that the compiler can perform type checking. Method Main instantiates objects doubleStack of size 5 (line 18) and intStack of size 10 (line 19), then calls methods TestPushDouble (lines 28–48), TestPopDouble (lines 51–73), TestPushInt (lines 76–96) and TestPopInt (lines 99–121) to manipulate the two Stacks in this example.

Fig. 22.8. Testing generic class Stack.

Method TestPushDouble (lines 28–48) invokes method Push to place the double values 1.1, 2.2, 3.3, 4.4 and 5.5 stored in array doubleElements onto doubleStack. The foreach statement terminates when the test program attempts to Push a sixth value onto doubleStack (which is full, because doubleStack can store only five elements). In this case, the method throws a FullStackException (Fig. 22.6) to indicate that the Stack is full. Lines 42–47 catch this exception and display the message and stack-trace information. The stack trace indicates the exception that occurred and shows that Stack method Push generated the exception at line 36 of the file Stack.cs (Fig. 22.5). The trace also shows that method Push was called by StackTest method TestPushDouble at line 39 of StackTest.cs. This information enables you to determine the methods that were on the method-call stack at the time that the exception occurred. Because the program catches the exception, the C# runtime environment considers the exception to have been handled, and the program can continue executing.

Method TestPopDouble (lines 51–73) invokes Stack method Pop in an infinite while loop to remove all the values from the stack. Note in the output that the values are popped off in last-in, first-out order—this, of course, is the defining characteristic of stacks. The while loop (lines 61–65) continues until the stack is empty. An EmptyStackException occurs when an attempt is made to pop from the empty stack. This causes the program to proceed to the catch block (lines 67–72) and handle the exception, so the program can continue executing. When the test program attempts to Pop a sixth value, the doubleStack is empty, so method Pop throws an EmptyStackException.

Method TestPushInt (lines 76–96) invokes Stack method Push to place values onto intStack until it’s full. Method TestPopInt (lines 99–121) invokes Stack method Pop to remove values from intStack until it’s empty. Once again, note that the values pop off in last-in, first-out order.

Creating Generic Methods to Test Class Stack< T >

Note that the code in methods TestPushDouble and TestPushInt is almost identical for pushing values onto a Stack<double> or a Stack<int>, respectively. Similarly the code in methods TestPopDouble and TestPopInt is almost identical for popping values from a Stack<double> or a Stack<int>, respectively. This presents another opportunity to use generic methods. Figure 22.9 declares generic method TestPush (lines 33–54) to perform the same tasks as TestPushDouble and TestPushInt in Fig. 22.8—that is, Push values onto a Stack<T>. Similarly, generic method TestPop (lines 57–79) performs the same tasks as TestPopDouble and TestPopInt in Fig. 22.8—that is, Pop values off a Stack<T>. Note that the output of Fig. 22.9 precisely matches the output of Fig. 22.8.

Fig. 22.9. Testing generic class Stack.

Method Main (lines 17–30) creates the Stack<double> (line 19) and Stack<int> (line 20) objects. Lines 23–29 invoke generic methods TestPush and TestPop to test the Stack objects.

Generic method TestPush (lines 33–54) uses type parameter T (specified at line 33) to represent the data type stored in the Stack. The generic method takes three arguments—a string that represents the name of the Stack object for output purposes, an object of type Stack<T> and an IEnumerable<T> that contains the elements that will be Pushed onto Stack<T>. Note that the compiler enforces consistency between the type of the Stack and the elements that will be pushed onto the Stack when Push is invoked, which is the type argument of the generic method call. Generic method TestPop (lines 57–79) takes two arguments—a string that represents the name of the Stack object for output purposes and an object of type Stack<T>.

22.7 Wrap-Up

This chapter introduced generics. We discussed how generics ensure compile-time type safety by checking for type mismatches at compile time. You learned that the compiler will allow generic code to compile only if all operations performed on the type parameters in the generic code are supported for all types that could be used with the generic code. You also learned how to declare generic methods and classes using type parameters. We demonstrated how to use a type constraint to specify the requirements for a type parameter—a key component of compile-time type safety. We discussed several kinds of type constraints, including reference-type constraints, value-type constraints, class constraints, interface constraints and constructor constraints. We also discussed how to implement multiple type constraints for a type parameter. Finally, we showed how generics improve code reuse. In the next chapter, we demonstrate the .NET Framework Class Library’s collection classes, interfaces and algorithms. Collection classes are pre-built data structures that you can reuse in your applications, saving you time.