Transcript generics_collections

Generics
Collections
Why do we need Generics?
 Another method of software re-use.
 When we implement an algorithm, we want to re-use it for
different types.
 Example: We write a generic method for sorting an array of
objects, then call the generic method with an array of any type.
 The compiler performs type checking to ensure that the array
passed to the sorting method contains only elements of the
same type.
 Generics provide compile-time type safety.
Generic Methods
 Generic methods enable you to specify, with a single method
declaration, a set of related methods.
 Example: OverloadedMethods.cs
• Note that the array element type (int, double or char)
appears only once in each method—in the method header.
• If we replace the element types in each method with a
generic name then all three methods would look like follows:
private static void DisplayArray( T[] inputArray )
{
foreach ( T element in inputArray )
Console.Write( element + " " );
Console.WriteLine( "\n" );
}
 However, it will not compile, because its syntax is not correct.
 GenericMethods.cs
Generic Methods
 All generic method declarations have a type-parameter list delimited by








angle brackets that follows the method’s name.
Each type-parameter list contains one or more type parameters.
A type parameter is an identifier that is 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.
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.
The type-parameter names throughout the method declaration must
match those declared in the type-parameter list.
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.
You can also use explicit type arguments to indicate the
exact type that should be used to call a generic function, as in
DisplayArray< int >( intArray );
Generic Classes
 A generic class describes a class in a type-independent
manner.
 We can then instantiate type-specific objects of the generic
class.
 Let’s look at example: Stack.sln
 StackTest.cs: repeats code in
TestPopInt/TestPopDouble and
TestPushInt/TestPushDouble
 How to fix this? Let’s code this together first.
 NewStackTest.cs
Generic Interfaces
 In NewStackTest.cs, we used a generic interface:
IEnumerable < T >
 Similar to generic classes, generic interfaces enable you to
specify, with a single interface declaration, a set of related
interfaces.
Type Constraints
 Suppose we want to implement a generic Maximum method that
determines and returns the largest of its three arguments
(all of the same type)  Let’s code this together first.
 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 possible type.
 Generic code is restricted to performing operations that are guaranteed
to work for every possible type.
 Similarly, you cannot call a method on a generic-type variable unless the
compiler can ensure that all possible types support that method.
• 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.
Type Constraints
IComparable< T > Interface
 It is possible to compare two objects of the same type if that
type implements the generic interface
IComparable< T >.
 The structures in the Framework Class Library that
correspond to the simple types all implement this interface.
 Types that implement IComparable< T > must declare a
CompareTo method for comparing objects.
 Method CompareTo must return:
 0 if the objects are equal.
 A negative integer if the caller is less than the argument.
 A positive integer if the caller is greater than the argument.
 Example: MaximumTest.cs
Type Constraints
private static T Maximum< T >( T x, T y, T z )
where T : IComparable< T >
 The where clause specifies the type constraint.
 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.
You can specify that a type argument must be a reference or a value type by
using the reference-type (class) or the value-type (struct) constraints.
You can specify a constructor constraint—new()—to indicate that the
generic code can create objects of the type of the type parameter.
If a type parameter is specified with a constructor constraint, the type
argument’s class must provide a public parameterless/default constructor.
It is possible to apply multiple constraints to a type parameter. To do so,
simply provide a comma-separated list of constraints in the where clause.
Common Data Structures - summary
 We’ve seen Array only so far  fixed-size (can grow with





Resize)
Dynamic data structures can automatically grow and shrink
at execution time.
Linked lists are collections of data items that are “chained
together”.
Stacks have insertions and deletions made at only
one end: the top.
Queues represent waiting lines; insertions are made
at the back and deletions are made from the front.
Binary trees facilitate high-speed searching and sorting of
data.
Collections
 For the vast majority of applications, there is no need to




build custom data structures.
Instead, you can use the prepackaged data-structure
classes provided by the .NET Framework.
These classes are known as collection classes—they store
collections of data. Each instance of one of these classes is
a collection of items.
Collection classes enable programmers to store sets of
items by using existing data structures, without concern for
how they are implemented.
System.Collections contains collections that store
references to objects.
Collection Interfaces
 All collection classes in the .NET Framework implement
some combination of the collection interfaces.
Interface
Description
ICollection
The root interface from which interfaces IList and IDictionary inherit.
Contains a Count property to determine the size of a collection and a
CopyTo method for copying a collection’s contents into a traditional array.
IList
An ordered collection that can be manipulated like an array. Provides an
indexer for accessing elements with an int index. Also has methods for
searching and modifying a collection, including Add, Remove, Contains
and IndexOf.
IEnumerable
An object that can be enumerated. This interface contains exactly one
method, GetEnumerator, which returns an IEnumerator object. ICollection
implements IEnumerable, so all collection classes implement IEnumerable
directly or indirectly.
IDictionary
A collection of values, indexed by an arbitrary “key” object. Provides an
indexer for accessing elements with an object index and methods for
modifying the collection (e.g., Add, Remove). IDictionary property Keys
contains the objects used as indices, and property Values contains all the
stored objects.
ArrayList
 The ArrayList collection class is a conventional arrays and
provides dynamic resizing of the collection.
Method / Property
Add
Capacity
Clear
Contains
Count
IndexOf
Description
Adds an object to the end of the ArrayList.
Property that gets and sets the number of elements for which space
is currently reserved in the ArrayList.
Removes all elements from the ArrayList.
Determines whether an element is in the ArrayList.
Read-only property that gets the number of elements stored in the
ArrayList.
Returns the zero-based index of the first occurrence of a value in the
ArrayList
Insert
Inserts an element into the ArrayList at the specified index.
Remove
Removes the first occurrence of a specific object from the ArrayList.
RemoveAt
TrimToSize
Removes the element at the specified index of the ArrayList.
Sets the capacity to the actual number of elements in the ArrayList.
ArrayList
 Let’s write code to use ArrayList.
 Suppose we have two color string arrays as follows:
private static readonly string[] colors =
{ "MAGENTA", "RED", "WHITE", "BLUE", "CYAN" };
private static readonly string[] removeColors =
{ "RED", "WHITE", "BLUE" };
1.
2.
3.
4.
5.
Let’s create an arrayList and add items in colors into it.
Let’s display the size and capacity of arrayList.
Let’s find the index of the item “BLUE”.
Let’s write a method that removes the items in one
ArrayList from another. And then call that method to
remove removeColors array from our first arrayList.
ArrayListTest.cs
HashTable
 Arrays uses nonnegative integer indexes as keys. Sometimes
associating these integer keys with objects to store them is
impractical, so we develop a scheme for using arbitrary keys.
 When an application needs to store something, the scheme
could convert the application key rapidly to an index.
 Once the application has a key for which it wants to retrieve
the data, simply apply the conversion to the key to find the
array index where the data resides.
 The scheme we describe here is the basis of a technique
called hashing, in which we store data in a data structure
called a hash table.
HashTable
 A hash function performs a calculation that determines




where to place data in the hash table.
The hash function is applied to the key in a key/value pair
of objects.
Class Hashtable can accept any object as a key. For this
reason, class object defines method GetHashCode,
which all objects inherit.
Example: Let’s write a program that counts the number of
occurrences of each word in a string read from console.
To split the sentence into words, we will use this:
// split input text into tokens
string[] words = Regex.Split( input, @"\s+" );
 HashTable solution.
HashTable
 Hashtable method ContainsKey determines whether a key is in the
hash table.
 Read-only property Keys returns an ICollection that contains all
the keys.
 Hashtable property Count returns the number of key/value pairs in the
Hashtable.
 If you use a foreach statement with a Hashtable object, the iteration
variable will be of type DictionaryEntry.
 The enumerator of a Hashtable (or any other class that implements
IDictionary) uses the DictionaryEntry structure to store key/value pairs.
 This structure provides properties Key and Value for retrieving the key
and value of the current element.
 If you do not need the key, class Hashtable also provides a read-only
Values property that gets an ICollection of all the values stored in
the Hashtable.
Stack & Queue
 Stack:
 Push
 Pop
 Peek
 Example:
 StackTest.cs
 Queue:
 Enqueue
 Dequeue
 Peek
 Exercise: re-write the
StackTest.cs example at
home using a Queue this
time.
 QueueTest.cs
BitArray
 Manages a compact array of bit values, which are
represented as Booleans, where true indicates that the bit
is on (1) and false indicates the bit is off (0).
 http://msdn.microsoft.com/enus/library/system.collections.bitarray.aspx
Generic Collections
Problems with Nongeneric Collections
 Having to store data as object references causes less efficient
code due to unboxing.
 The .NET Framework also includes the
System.Collections.Generic namespace, which
uses C#’s generics capabilities.
 Many of these new classes are simply generic counterparts
of the classes in namespace System.Collections.
 Generic collections eliminate the need for explicit type casts
that decrease type safety and efficiency.
 Generic collections are especially useful for storing structs,
since they eliminate the overhead of boxing and unboxing.
Generic Collection Interfaces
Interface
ICollection(T)
Description
Defines methods to manipulate generic collections.
IList(T)
Represents a collection of objects that can be individually
accessed by index.
IEnumerable(T)
Exposes the enumerator, which supports a simple iteration
over a collection of a specified type.
IEnumerator(T)
Supports a simple iteration over a generic collection.
IDictionary(TKey,TValue)
IComparer(T)
Represents a generic collection of key/value pairs.
Defines a method that a type implements to compare two
objects.
http://msdn.microsoft.com/en-us/library/system.collections.generic.aspx
SortedDictionary<TKey, TValue>
 A dictionary is the general term for a collection of key/value
pairs.
 A hash table is one way to implement a dictionary.
 Let’s re-write the word counting example using
SortedDictionary this time.
 SortedDictionaryTest.cs
Other Generic Collection Classes
 List(T)
 Let’s re-write the ArrayListTest.cs using List<T> this time.
 ListTest.cs
 Stack(T)
 Queue(T)
 LinkedList(T)
 SortedList(TKey, TValue)