The Generic Collections
C# 2.0 greatly expanded the Collections API by adding generic collections. The generic collections are declared in the System.Collections.Generic namespace. In many cases, the generic collection classes are simply generic equivalents of the non-generic classes discussed earlier. However, the correspondence is not one-to-one. For example, there is a generic collection called LinkedList that implements a doubly linked list, but there is no non-generic equivalent. In some cases, parallel functionality exists between the generic and non-generic classes, but the names differ. For example, the generic version of ArrayList is called List, and the generic version of Hashtable is called Dictionary. Also, the specific contents of the various interfaces and classes have gone through a minor reorganization, with some functionality shifting from one interface to another, for example. However, overall, if you understand the non-generic collections, then you can easily use the generic collections.
In general, the generic collections work in the same way as the non-generic collections, with the exception that a generic collection is type-safe. Thus, a generic collection can store only items that are compatible with its type argument. Therefore, if you want a collection that is capable of storing unrelated, mixed types, you should use one of the non-generic collections. However, for all cases in which a collection is storing only one type of object, then a generic collection is now your best choice.
The generic collections are defined by a set of interfaces and the classes that implement those interfaces. Each is described by the following sections.
The Generic Interfaces
System.Collections.Generic defines a number of generic interfaces, all of which parallel their corresponding, non-generic counterparts. The generic interfaces are summarized in Table 23-10.
| Interface | Description |
|---|---|
| ICollection<T> | Defines the foundational features for the generic collections. |
| IComparer<T> | Defines the generic Compare( ) method that performs a comparison on objects stored in a collection. |
| IDictionary<TK, TV> | Defines a generic collection that consists of key/value pairs. |
| IEnumerable<T> | Defines the generic GetEnumerator( ) method, which supplies the enumerator for a collection class. |
| IEnumerator<T> | Provides members that enable the contents of a collection to be obtained one at a time. |
| IEqualityComparer<T> | Compares two objects for equality. |
| IList<T> | Defines a generic collection that can be accessed via an indexer. |
The ICollection<T> Interface
The ICollection<T> interface defines those features that all generic collections have in common. It inherits the IEnumerable and IEnumerable<T> interfaces. ICollection<T> is the generic version of the non-generic ICollection interface. However, there are some differences between the two.
ICollection<T> defines the following properties:
int Count { get; } bool IsReadOnly { get; } Count contains the number of items currently held in the collection. IsReadOnly is true if the collection is read-only. It is false if the collection is read/write.
ICollection<T> defines the following methods. Notice that it defines a few more methods than does its non-generic counterpart.
| Method | Description |
|---|---|
| void Add(T obj) | Adds obj to the invoking collection. Throws a NotSupportedException if the collection is read-only. |
| void Clear( ) | Deletes all elements from the invoking collection. |
| bool Contains(T obj) | Returns true if the invoking collection contains the object passed in obj and false otherwise. |
| void CopyTo(T[ ] target, int startIdx) | Copies the contents of the invoking collection to the array specified by target, beginning at the index specified by startIdx. |
| bool Remove(T obj) | Removes the first occurrence of obj from the invoking collection. Returns true if obj was removed and false if it was not found in the invoking collection. |
Several of these methods will throw NotSupportedException if the collection is read-only. Because ICollection<T> inherits IEnumerable, it also includes the method GetEnumerator( ).
The IList<T> Interface
The IList<T> interface inherits IEnumerable, ICollection<T>, and IEnumerable<T> and defines the behavior of a generic collection that allows elements to be accessed via a zero-based index. It is the generic version of the non-generic IList interface. IList<T> defines the methods shown in Table 23-11. Two of these methods imply the modification of a collection. If the collection is read-only or of fixed size, then the Insert( ) and RemoveAt( ) methods will throw a NotSupportedException.
| Method | Description |
|---|---|
| int IndexOf(T obj) | Returns the index of obj if obj is contained within the invoking collection. If obj is not found, −1 is returned. |
| void Insert(int idx, T obj) | Inserts obj at the index specified by idx. |
| void RemoveAt(int idx) | Removes the object at the index specified by idx from the invoking collection. |
IList<T> defines the following indexer:
T this[int idx] { get; set; } This indexer sets or gets the value of the element at the index specified by idx.
The IDictionary<TK, TV> Interface
The IDictionary<TK, TV> interface defines the behavior of a generic collection that maps unique keys to values. That is, it defines a collection that stores key/value pairs. IDictionary<TK, TV> inherits ICollection<KeyValuePair<TK, TV>>, IEnumerable <KeyValuePair<TK, TV>>, and IEnumerable, and is the generic version of the non-generic IDictionary. The methods declared by IDictionary<TK, TV> are summarized in Table 23-12. All throw an ArgumentNullException if an attempt is made to specify a null key.
| Method | Description |
|---|---|
| void Add(TK k, TV v) | Adds the key/value pair specified by k and v to the invoking collection. k must not be null. An ArgumentException is thrown if k is already stored in the collection. |
| bool ContainsKey(TK k) | Returns true if the invoking collection contains k as a key. Otherwise, returns false. |
| bool Remove(TK k) | Removes the entry whose key equals k. |
| bool TryGetValue(TK k, out TV v) | Attempts to retrieve the value associated with k, putting it into v. Returns true if successful and false otherwise. |
IDictionary<TK, TV> defines the following properties:
| Property | Description |
|---|---|
| ICollection Keys<TK> { get; } | Obtains a collection of the keys. |
| ICollection Values<TV> { get; } | Obtains a collection of the values. |
Notice that the keys and values contained within the collection are available as separate lists through the Keys and Values properties.
IDictionary<TK, TV> defines the following indexer:
TV this[TK key] { get; set; } You can use this indexer to get or set the value of an element. You can also use it to add a new element to the collection. Notice that the “index” is not actually an index, but rather the key of the item.
IEnumerable<T> and IEnumerator<T>
IEnumerable<T> and IEnumerator<T> are the generic equivalents of the non-generic IEnumerable and IEnumerator interfaces described earlier. Each inherits its non-generic equivalent. They have the same methods and properties, and work in the same way. Of course, the generic versions operate on data of the type specified by the type argument.
IEnumerable<T> declares the GetEnumerator( ) method as shown here:
IEnumerator<T> GetEnumerator( )
It returns an enumerator of type T for the collection. Thus, it returns a type-safe enumerator.
IEnumerator<T> inherits the two methods defined by the non-generic IEnumerator: MoveNext( ) and Reset( ). It also declares the Current property, as shown here:
T Current { get; } It returns a T reference to the next object. Thus, the generic version of Current is type-safe.
There is one other difference between IEnumerator and IEnumerator<T>: IEnumerator<T> inherits the IDisposable interface, but IEnumerator does not.
IComparer<T>
The IComparer<T> interface is the generic version of IComparer described earlier. The main difference between the two is that IComparer<T> is type-safe. It declares the Compare( ) method as shown here:
int Compare(T obj1, T obj2)
This method compares obj1 with obj2 and returns greater than zero if obj1 is greater than obj2, zero if the two objects are the same, and less than zero if obj1 is less that obj2.
IEqualityComparer<T>
The IEqualityComparer<T> interface is the equivalent of its non-generic relative IEqualityComparer. It defines these two methods:
bool Equals(T obj1, T obj2) int GetHashCode(T obj)
Equals( ) must return true if obj1 and obj2 are equal. GetHashCode( ) must return the hash code for obj.
The KeyValuePair <TK, TV> Structure
System.Collections.Generic defines a structure called KeyValuePair<TK, TV>, which is used to store a key and its value. It is used by the generic collection classes that store key/ value pairs, such as Dictionary<TK, TV>. This structure defines the following two properties:
public TK Key {get;} public TV Value {get;} These fields hold the key or value associated with an entry. You can construct a KeyValuePair<TK, TV> object by using the following constructor:
public KeyValuePair(TK k, TV v)
Here, k is the key and v is the value.
The Generic Collection Classes
As mentioned at the start of this section, the generic collection classes largely parallel their non-generic relatives, although in some cases the names have been changed. Also, some differences in organization and functionality exist. Table 23-13 shows the generic collection classes, which are all defined in System.Collections.Generic. Each is examined in turn by the following sections.
| Class | Description |
|---|---|
| Dictionary<TK, TV> | Stores key/value pairs. Provides functionality similar to that found in the non-generic Hashtable class. |
| LinkedList<T> | Stores elements in a doubly linked list. |
| List<T> | A dynamic array. Provides functionality similar to that found in the non-generic ArrayList class. |
| Queue<T> | A first-in, first-out list. Provides functionality similar to that found in the non-generic Queue class. |
| SortedDictionary<TK, TV> | A sorted list of key/value pairs. |
| SortedList<TK, TV> | A sorted list of key/value pairs. Provides functionality similar to that found in the non-generic SortedList class. |
| Stack<T> | A first-in, last-out list. Provides functionality similar to that found in the non-generic Stack class. |
The List<T> Collection
The List<T> class implements a generic, dynamic array and is conceptually similar to the non-generic ArrayList class. List<T> implements both the generic and non-generic forms of the ICollection, IList, and IEnumerable interfaces. List<T> has the constructors shown here:
public List( ) public List(IEnumerable<T> c) public List(int capacity)
The first constructor builds an empty List with a default initial capacity. The second constructor builds a List that is initialized with the elements of the collection specified by c and with an initial capacity equal to the number of elements. The third constructor builds an array list that has the specified initial capacity. The capacity is the size of the underlying array that is used to store the elements. The capacity grows automatically as elements are added. Each time the list must be enlarged, its capacity is increased.
In addition to the methods defined by the interfaces that it implements, List<T> defines several methods of its own. A sampling is shown in Table 23-14.
| Method | Description |
|---|---|
| public void AddRange(IEnumerable<T> c) | Adds the elements in c to the end of the invoking list. |
| public virtual int BinarySearch(T v) | Searches the invoking collection for the value passed in v. The index of the matching element is returned. If the value is not found, a negative value is returned. The invoking list must be sorted. |
| public int BinarySearch(T v, IComparer<T> comp) | Searches the invoking collection for the value passed in v using the comparison object specified by comp. The index of the matching element is returned. If the value is not found, a negative value is returned. The invoking list must be sorted. |
| public int BinarySearch(int startIdx, int count, T v, IComparer<T> comp) | Searches the invoking collection for the value passed in v using the comparison object specified by comp. The search begins at startIdx and runs for count elements. The index of the matching element is returned. If the value is not found, a negative value is returned. The invoking list must be sorted. |
| public List<T> GetRange(int idx, int count) | Returns a portion of the invoking list. The range returned begins at idx and runs for count elements. The returned object refers to the same elements as the invoking object. |
| public int IndexOf(T v) | Returns the index of the first occurrence of v in the invoking collection. Returns −1 if v is not found. |
| public void InsertRange(int startIdx, IEnumerable<T> c) | Inserts the elements of c into the invoking collection, starting at the index specified by startIdx. |
| public int LastIndexOf(T v) | Returns the index of the last occurrence of v in the invoking collection. Returns −1 if v is not found. |
| public void RemoveRange(int idx, int count) | Removes count elements from the invoking collection, beginning at idx. |
| public void Reverse( ) | Reverses the contents of the invoking collection. |
| public void Reverse(int startIdx, int count) | Reverses count elements of the invoking collection, beginning at startIdx. |
| public void Sort( ) | Sorts the collection into ascending order. |
| public void Sort(IComparer<T> comp) | Sorts the collection using the specified comparison object. If comp is null, the default comparison for each object is used. |
| public void Sort(Comparison<T> comp) | Sorts the collection using the specified comparison delegate. |
| public void Sort(int startIdx, int count, IComparer<T> comp) | Sorts a portion of the collection using the specified comparison object. The sort begins at startIdx and runs for count elements. If comp is null, the default comparison for each object is used. |
| public T[ ] ToArray( ) | Returns an array that contains copies of the elements of the invoking object. |
| public void TrimExcess( ) | Reduces the capacity of the invoking list so that it is no more than 10% greater than the number of elements that it currently holds. |
Two properties are defined by List<T>: Capacity and Count. They are shown here:
public int Capacity { get; set; } public int Count { get; } Capacity gets or sets the capacity of the invoking list. The capacity is the number of elements that can be held before the list must be enlarged. Because a list grows automatically, it is not necessary to set the capacity manually. However, for efficiency reasons, you might want to set the capacity when you know in advance how many elements the list will contain. This prevents the overhead associated with the allocation of more memory. Count contains the number of elements in the list.
The following indexer is defined by List<T>:
public T this[int idx] { get; set; } It sets or gets the value of the element at the index specified by idx.
Here is a program that demonstrates List<T>. It reworks the first ArrayList program shown earlier in this chapter. The only changes necessary are to substitute the name List for ArrayList and to use the generic type parameters.
// Demonstrate List<T>. using System; using System.Collections.Generic; class GenListDemo { public static void Main() { // Create a list. List<char> lst = new List<char>(); Console.WriteLine("Initial number of elements: " + lst.Count); Console.WriteLine(); Console.WriteLine("Adding 6 elements"); // Add elements to the array list lst.Add('C'); lst.Add('A'); lst.Add('E'); lst.Add('B'); lst.Add('D'); lst.Add('F'); Console.WriteLine("Number of elements: " + lst.Count); // Display the array list using array indexing. Console.Write("Current contents: "); for(int i=0; i < lst.Count; i++) Console.Write(lst[i] + " "); Console.WriteLine("\n"); Console.WriteLine("Removing 2 elements"); // Remove elements from the array list. lst.Remove('F'); lst.Remove('A'); Console.WriteLine("Number of elements: " + lst.Count); // Use foreach loop to display the list. Console.Write("Contents: "); foreach(char c in lst) Console.Write(c + " "); Console.WriteLine("\n"); Console.WriteLine("Adding 20 more elements"); // Add enough elements to force lst to grow. for(int i=0; i < 20; i++) lst.Add((char)('a' + i)); Console.WriteLine("Current capacity: " + lst.Capacity); Console.WriteLine("Number of elements after adding 20: " + lst.Count); Console.Write("Contents: "); foreach(char c in lst) Console.Write(c + " "); Console.WriteLine("\n"); // Change contents using array indexing. Console.WriteLine("Change first three elements"); lst[0] = 'X'; lst[1] = 'Y'; lst[2] = 'Z'; Console.Write("Contents: "); foreach(char c in lst) Console.Write(c + " "); Console.WriteLine(); // Because of generic type-safety, // the following line is illegal. // lst.Add(99); // Error, not a char! } } The output, shown here, is the same as that produced by the non-generic version of the program:
Initial number of elements: 0 Adding 6 elements Number of elements: 6 Current contents: C A E B D F Removing 2 elements Number of elements: 4 Contents: C E B D Adding 20 more elements Current capacity: 32 Number of elements after adding 20: 24 Contents: C E B D a b c d e f g h i j k l m n o p q r s t Change first three elements Contents: X Y Z D a b c d e f g h i j k l m n o p q r s t
LinkedList<T>
The LinkedList<T> class implements a generic doubly linked list. It implements ICollection, ICollection<T>, IEnumerable, IEnumerableI<T>, Serializable, and IDeserializationCallback. (The last two interfaces support the serialization of the list.) LinkedList<T> defines two public constructors, shown here:
public LinkedList( ) public LinkedList(IEnumerable<T> c)
The first creates an empty linked list. The second creates a list initialized with the elements in c.
Like most linked list implementations, LinkedList<T> encapsulates the values stored in the list in nodes that contain links to the previous and next element in the list. These nodes are objects of type LinkedListNode<T>. LinkedListNode<T> provides the four properties shown here:
public LinkedListNode<T> Next { get; } public LinkedListNode<T> Previous { get; } public LinkedList<T> List { get; } public T Value { get; set; } Next and Previous obtain a reference to the next or previous node in the list, respectively. You can use these properties to traverse the list in either direction. A null reference is returned if no next or previous node exists. You can obtain a reference to the list, itself, via List. You can get or set the value within a node by using Value.
LinkedList<T> defines many methods. A sampling is shown in Table 23-15. LinkedList<T> defines these properties:
public int Count { get; } public LinkedListNode<T> First { get; } public LinkedListNode<T> Last { get; } | Method | Description |
|---|---|
| public LinkedListNode<T> AddAfter(LinkedListNode<T> n, T v) | Adds a node with the value v to the list immediately after the node specified by n. The node passed in n must not be null. Returns a reference to the node containing the value v. |
| public void AddAfter(LinkedListNode<T> n, LinkedListNode<T> new) | Adds the node passed in new to the list immediately after the node specified by n. The node passed in n must not be null. Throws an InvalidOperationException if n is not in the list. |
| public LinkedListNode<T> AddBefore(LinkedListNode<T> n, T v) | Adds a node with the value v to the list immediately before the node specified by n. The node passed in n must not be null. Returns a reference to the node containing the value v. |
| public void AddBefore(LinkedListNode<T> n, LinkedListNode<T> new) | Adds the node passed in new to the list immediately before the node specified by n. The node passed in n must not be null. Throws an InvalidOperationException if n is not in the list. |
| public LinkedListNode<T> AddFirst( T v) | Adds a node with the value v to the start of the list. Returns a reference to the node containing the value v. |
| public void AddFirst(LinkedListNode<T> new) | Adds new to the start of the list. Throws an InvalidOperationException if new is part of another list. |
| public LinkedListNode<T> AddLast(T v) | Adds a node with the value v to the end of the list. Returns a reference to the node containing the value v. |
| public void AddLast(LinkedListNode<T> new) | Adds new to the end of the list. Throws an InvalidOperationException if new is part of another list. |
| public LinkedListNode<T> Find(T v) | Returns a reference to the first node in the list that has the value v. null is returned if v is not in the list. |
| public LinkedListNode<T> FindLast(T v) | Returns a reference to the last node in the list that has the value v. null is returned if v is not in the list. |
| public bool Remove(T v) | Removes the first node in the list that has the value v. Returns true if the node was removed. (That is, if a node with the value v was in the list and it was removed.) Returns false otherwise. |
| public void Remove(LinkedListNode<T> n) | Removes the node that matches n. Throws an InvalidOperationException if n is not in the list. |
| public void RemoveFirst( ) | Removes the first node in the list. |
| public void RemoveLast( ) | Removes the last node in the list. |
Count obtains the number of nodes in the list. First obtains the first node in the list. Last obtains the last node in the list.
Here is an example that demonstrates the LinkedList<T> class:
// Demonstrate LinkedList<T>. using System; using System.Collections.Generic; class GenLinkedListDemo { public static void Main() { // Create a linked list. LinkedList<char> ll = new LinkedList<char>(); Console.WriteLine("Initial number of elements: " + ll.Count); Console.WriteLine(); Console.WriteLine("Adding 5 elements."); // Add elements to the linked list ll.AddFirst('A'); ll.AddFirst('B'); ll.AddFirst('C'); ll.AddFirst('D'); ll.AddFirst('E'); Console.WriteLine("Number of elements: " + ll.Count); // Display the linked list by manually walking // through the list. LinkedListNode<char> node; Console.Write("Display contents by following links: "); for(node = ll.First; node != null; node = node.Next) Console.Write(node.Value + " "); Console.WriteLine("\n"); //Display the linked list by use of a foreach loop. Console.Write("Display contents with foreach loop: "); foreach(char ch in ll) Console.Write(ch + " "); Console.WriteLine("\n"); // Display the list backwards by manually walking // from last to first. Console.Write("Follow links backwards: "); for(node = ll.Last; node != null; node = node.Previous) Console.Write(node.Value + " "); Console.WriteLine("\n"); // Remove two elements. Console.WriteLine("Removing 2 elements."); // Remove elements from the linked list. ll.Remove('C'); ll.Remove('A'); Console.WriteLine("Number of elements: " + ll.Count); // Use foreach loop to display the modified list. Console.Write("Contents after deletion: "); foreach(char ch in ll) Console.Write(ch + " "); Console.WriteLine("\n"); // Add three elements to the end of the list. ll.AddLast('X'); ll.AddLast('Y'); ll.AddLast('Z'); Console.Write("Contents after addition to end: "); foreach(char ch in ll) Console.Write(ch + " "); Console.WriteLine("\n"); } } Here is the output:
Initial number of elements: 0 Adding 5 elements. Number of elements: 5 Display contents by following links: E D C B A Display contents with foreach loop: E D C B A Follow links backwards: A B C D E Removing 2 elements. Number of elements: 3 Contents after deletion: E D B Contents after addition to end: E D B X Y Z
Perhaps the most important thing to notice in this program is that the list is traversed in both the forward and backwards direction by following the links provided by the Next and Previous properties. The bidirectional property of doubly linked lists is especially important in applications such as databases in which the ability to efficiently move through the list in both directions is often necessary.
The Dictionary<TK, TV> Class
The Dictionary<TK, TV> class stores key/value pairs. In a dictionary, values are accessed through their keys. In this regard it is similar to the non-generic Hashtable class. Dictionary<TK, TV> implements both the generic and non-generic forms of IDictionary, ICollection, and IEnumerable. It also implements ISerializable and IDeserializationCallback. (The last two interfaces support the serialization of the list.) Dictionaries are dynamic, growing as needed.
Dictionary<TK, TV> provides many constructors. Here is a sampling:
public Dictionary( ) public Dictionary(IDictionary<TK, TV> dict) public Dictionary(int capacity)
The first constructor creates an empty dictionary with a default capacity. The second creates a dictionary that contains the same elements as those in dict. The third lets you specify an initial capacity. If you know in advance that you will need a dictionary of a certain size, then specifying that capacity will prevent the resizing of the dictionary at runtime, which is a costly process.
Dictionary<TK, TV> defines several methods. Some commonly used ones are shown in Table 23-16.
| Method | Description |
|---|---|
| public void Add(TK k, TV v) | Adds the key/value pair specified by k and v to the dictionary. If the k is already in the dictionary, then its value is unchanged and an ArgumentException is thrown. |
| public bool ContainsKey(TK k) | Returns true if k is a key in the invoking dictionary. Returns false otherwise. |
| public bool ContainsValue(TV v) | Returns true if v is a value in the invoking dictionary. Returns false otherwise. |
| public IDictionary.Enumerator<TK, TV> GetEnumerator( ) | Returns an enumerator for the invoking dictionary. |
| public bool Remove(TK k) | Removes k from the dictionary. Returns true if successful. Returns false if k was not in the dictionary. |
Dictionary<TK, TV> defines the following properties:
| Property | Description |
|---|---|
| public IEqualityComparer<TK> Comparer { get; } | Obtains the comparer for the invoking dictionary. |
| public int Count { get; } | Obtains the number of elements currently held by the invoking dictionary. |
| public Dictionary.KeyCollection<TK, TV> Keys { get; } | Obtains a collection of the keys. |
| public Dictionary.ValueCollection<TK, TV> Values { get; } | Obtains a collection of the values. |
Notice that the keys and values contained within the collection are available as separate lists through the Keys and Values properties. The types Dictionary.KeyCollection and Dictionary.ValueCollection are collections that implement ICollection and IEnumerable in both their generic and non-generic forms.
Dictionary<TK, TV> defines the following indexer:
public TV this[TK key] { get; set; } You can use this indexer to get or set the value of an element. You can also use it to add a new element to the collection. Notice that the “index” is not actually an index, but rather the key of the item.
Dictionary<TK, TV> stores key/value pairs in the form of a KeyValuePair<TK, TV> structure. Recall that this structure defines the following two fields:
public TK Key; public TV Value;
These fields hold the key or value associated with an entry. Most of the time, you won’t need to use KeyValuePair<TK, TV> directly because Dictionary allows you to work the keys and values individually. However, when enumerating a Dictionary, such as in a foreach loop, the objects being enumerated are KeyValuePairs.
In a Dictionary<TK, TV>, all keys must be unique, and a key must not change while it is in use as a key. Values need not be unique. The objects in a Dictionary<TK, TV> are not stored in sorted order.
Here is an example that demonstrates Dictionary<TK, TV>:
// Demonstrate the generic Dictionary<TK, TV> class. using System.Collections.Generic; using System; class GenDictionaryDemo { public static void Main() { // Create a Dictionary that holds employee // names and their corresponding salaries. Dictionary<string, double> dict = new Dictionary<string, double>(); // Add elements to the collection. dict.Add("Butler, John", 73000); dict.Add("Swartz, Sarah", 59000); dict.Add("Pyke, Thomas", 45000); dict.Add("Frank, Ed", 99000); // Get a collection of the keys (names). ICollection<string> c = dict.Keys; // Use the keys to obtain the values (salaries). foreach(string str in c) Console.WriteLine("{0}, Salary: {1:C}", str, dict[str]); } } Here is the output:
Butler, John, Salary: $73,000.00 Swartz, Sarah, Salary: $59,000.00 Pyke, Thomas, Salary: $45,000.00 Frank, Ed, Salary: $99,000.00
The SortedDictionary<TK, TV> Class
The SortedDictionary<TV, TK> class stores key/value pairs and is similar to Dictionary<TK, TV> except that it is sorted by key. SortedDictionary<TK, TV> implements both the generic and non-generic forms of IDictionary, ICollection, and IEnumerable. SortedDictionary<TK, TV> provides the following constructors:
public SortedDictionary( ) public SortedDictionary(IDictionary<TK, TV> dict) public SortedDictionary(IComparer<TK> comp) public SortedDictionary(IDictionary<TK, TV> dict, IComparer<TK> comp)
The first constructor creates an empty dictionary with a default capacity. The second creates a dictionary that contains the same elements as those in dict. The third lets you specify the IComparer that the dictionary will use for sorting, and the fourth lets you initialize the dictionary and specify the IComparer.
SortedDictionary<TK, TV> defines several methods. A sampling is shown in Table 23-17.
| Method | Description |
|---|---|
| public void Add(TK k, TV v) | Adds the key/value pair specified by k and v to the dictionary. If the k is already in the dictionary, then its value is unchanged and an ArgumentException is thrown. |
| public bool ContainsKey(TK k) | Returns true if k is a key in the invoking dictionary. Returns false otherwise. |
| public bool ContainsValue(TV v) | Returns true if v is a value in the invoking dictionary. Returns false otherwise. |
| public SortedDictionary.Enumerator<TK, TV> GetEnumerator( ) | Returns an enumerator for the invoking dictionary. |
| public bool Remove(TK k) | Removes k from the dictionary. Returns true ifsuccessful. Returns false if k was not in the dictionary. |
SortedDictionary<TK, TV> defines the following properties:
| Property | Description |
|---|---|
| public IComparer<TK> Comparer { get; } | Obtains the comparer for the invoking dictionary. |
| public int Count { get; } | Obtains the number of elements currently held by the invoking dictionary. |
| public SortedDictionary.KeyCollection<TK, TV> Keys { get; } | Obtains a collection of the keys. |
| public SortedDictionary.ValueCollection<TK, TV> Values { get; } | Obtains a collection of the values. |
Notice that the keys and values contained within the collection are available as separate lists through the Keys and Values properties. The types SortedDictionary.KeyCollection and SortedDictionary.ValueCollection are collections that implement ICollection and IEnumerable in both their generic and non-generic forms.
SortedDictionary<TK, TV> defines the following indexer:
public TV this[TK key] { get; set; } You can use this indexer to get or set the value of an element. You can also use it to add a new element to the collection. Notice that the “index” is not actually an index, but rather the key of the item.
SortedDictionary stores key/value pairs in the form of a KeyValuePair<TK, TV> structure. Recall that this structure defines the following two fields:
public TK Key; public TV Value;
These fields hold the key or value associated with an entry. However, most of the time, you won’t need to use KeyValuePair<TK, TV> directly because SortedDictionary allows you to work the keys and values individually. However, when enumerating a SortedDictionary, such as in a foreach loop, the objects being enumerated are KeyValuePairs.
In a SortedDictionary, all keys must be unique, and a key must not change while it is in use as a key. Values need not be unique.
Here is an example that demonstrates SortedDictionary<TK, TV). It reworks the Dictionary example shown in the preceding section. In this version the database of employees and salaries is sorted based on name (which is the key).
// Demonstrate the generic SortedDictionary<TK, TV> class. using System; using System.Collections.Generic; class GenSortedDictionaryDemo { public static void Main() { // Create a Dictionary that holds employee // names and their corresponding salaries. SortedDictionary<string, double> dict = new SortedDictionary<string, double>(); // Add elements to the collection. dict.Add("Butler, John", 73000); dict.Add("Swartz, Sarah", 59000); dict.Add("Pyke, Thomas", 45000); dict.Add("Frank, Ed", 99000); // Get a collection of the keys (names). ICollection<string> c = dict.Keys; // Use the keys to obtain the values (salaries). foreach(string str in c) Console.WriteLine("{0}, Salary: {1:C}", str, dict[str]); } } The output is shown here:
Butler, John, Salary: $73,000.00 Frank, Ed, Salary: $99,000.00 Pyke, Thomas, Salary: $45,000.00 Swartz, Sarah, Salary: $59,000.00
As you can see, the list is now sorted based on the key, which is the employee’s name.
The SortedList<TK, TV> Class
The SortedList<TK, TV> class stores a sorted list of key/value pairs. It is the generic equivalent of the non-generic SortedList class. SortedList<TK, TV> implements both the generic and non-generic forms of IDictionary, ICollection, and IEnumerable. The size of a SortedList<TK, TV> is dynamic and will automatically grow as needed. SortedList<TV, TK> is similar to SortedDictionary<TK, TV> but has different runtime characteristics.
SortedList<TK, TV> provides many constructors. Here is a sampling:
public SortedList( ) public SortedList(IDictionary<TK, TV> dict) public SortedList(int capacity) public SortedList(IComparer<TK> comp)
The first constructor creates an empty list with a default capacity. The second creates a list that contains the same elements as those in dict. The third lets you specify an initial capacity. If you know in advance that you will need a list of a certain size, then specifying that capacity will prevent the resizing of the list at runtime, which is a costly process. The fourth form lets you specify a comparison method that will be used to compare the object contained in the list.
The capacity of a SortedList<TK, TV> grows automatically as needed when elements are added to the list. When the current capacity is exceeded, the capacity is increased. The advantage of specifying a capacity is that you can prevent or minimize the overhead associated with resizing the collection. Of course, it makes sense to specify an initial capacity only if you have some idea of how many elements will be stored.
In addition to the methods defined by the interfaces that it implements, SortedList<TK, TV> also defines several methods of its own. A sampling is shown in Table 23-18. Notice that the enumerator returned by GetEnumerator( ) enumerates the key/value pairs stored in the list as objects of type KeyValuePair.
| Method | Description |
|---|---|
| public void Add(TK k, TV v) | Adds the key/value pair specified by k and v to the list. If the k is already in the list, then its value is unchanged and an ArgumentException is thrown. |
| public bool ContainsKey(TK k) | Returns true if k is a key in the invoking list. Returns false otherwise. |
| public bool ContainsValue(TV v) | Returns true if v is a value in the invoking list. Returns false otherwise. |
| public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator( ) | Returns an enumerator for the invoking list. |
| public int IndexOfKey(TK k) | Returns the index of the key specified by k. Returns −1 if the key is not in the list. |
| public int IndexOfValue(TV v) | Returns the index of the first occurrence of the value specified by v. Returns −1 if the value is not in the list. |
| public bool Remove(TK k) | Removes the key/value pair associated with k from the list. Returns true if successful. Returns false if k is not in the list. |
| public void RemoveAt(int idx) | Removes the key/value pair at the index specified by idx. |
| public void TrimExcess( ) | Removes the excess capacity of the invoking list. |
SortedList<TK, TV> defines the following properties:
| Property | Description |
|---|---|
| public int Capacity { get; set; } | Obtains or sets the capacity of the invoking list. |
| public IComparer<TK> Comparer { get; } | Obtains the comparer for the invoking list. |
| public int Count { get; } | Obtains the number of elements currently held by the invoking list. |
| public IList<TK> Keys { get; } | Obtains a collection of the keys. |
| public IList<TV> Values { get; } | Obtains a collection of the values. |
SortedList<TK, TV> defines the following indexer:
public TV this[TK key] { get; set; } You can use this indexer to get or set the value of an element. You can also use it to add a new element to the collection. Notice that the “index” is not actually an index, but rather the key of the item.
Here is an example that demonstrates SortedList<TK, TV). It reworks the employee database example one more time. In this version, the database is stored in a SortedList.
// Demonstrate a SortedList<TK, TV>. using System; using System.Collections.Generic; class GenSLDemo { public static void Main() { // Create a sorted SortedList<T> for // employee names and salaries. SortedList<string, double> sl = new SortedList<string, double>(); // Add elements to the collection. sl.Add("Butler, John", 73000); sl.Add("Swartz, Sarah", 59000); sl.Add("Pyke, Thomas", 45000); sl.Add("Frank, Ed", 99000); // Get a collection of the keys. ICollection<string> c = sl.Keys; // Use the keys to obtain the values. foreach(string str in c) Console.WriteLine("{0}, Salary: {1:C}", str, sl[str]); Console.WriteLine(); } } The output is shown here:
Butler, John, Salary: $73,000.00 Frank, Ed, Salary: $99,000.00 Pyke, Thomas, Salary: $45,000.00 Swartz, Sarah, Salary: $59,000.00
As the output shows, the list is sorted based on employee name, which is the key.
The Stack<T> Class
Stack<T> is the generic equivalent of the non-generic Stack class. Stack<T> supports a first-in, last-out stack. It implements the ICollection, IEnumerable<T>, and IEnumerable interfaces. Stack<T> is a dynamic collection that grows as needed to accommodate the elements it must store. Stack<T> defines the following constructors:
public Stack( ) public Stack(int capacity) public Stack(IEnumerable<T> c)
The first form creates an empty stack with a default initial capacity. The second form creates an empty stack with the initial capacity specified by capacity. The third form creates a stack that contains the elements of the collection specified by c.
In addition to the methods defined by the interfaces that it implements, Stack<T> defines the methods shown in Table 23-19. Stack<T> works just like its non-generic counterpart. To put an object on the top of the stack, call Push( ). To remove and return the top element, call Pop( ). An InvalidOperationException is thrown if you call Pop( ) when the invoking stack is empty. You can use Peek( ) to return, but not remove, the top object.
| Method | Description |
|---|---|
| public T Peek( ) | Returns the element on the top of the stack, but does not remove it. |
| public T Pop( ) | Returns the element on the top of the stack, removing it in the process. |
| public void Push(T v) | Pushes v onto the stack. |
| public T[ ] ToArray( ) | Returns an array that contains copies of the elements of the invoking stack. |
| public void TrimExcess( ) | Removes the excess capacity of the invoking stack. |
The following program demonstrates Stack<T>:
// Demonstrate the Stack<T> class. using System; using System.Collections.Generic; class GenStackDemo { public static void Main() { Stack<string> st = new Stack<string>(); st.Push("One"); st.Push("Two"); st.Push("Three"); st.Push("Four"); st.Push("Five"); while(st.Count > 0) { string str = st.Pop(); Console.Write(str + " "); } Console.WriteLine(); } } The output is shown here:
Five Four Three Two One
The Queue<T> Class
Queue<T> is the generic equivalent of the non-generic Queue class. It supports a first-in, first-out list. Queue<T> implements the ICollection, IEnumerable<T>, and IEnumerable interfaces. Queue<T> is a dynamic collection that grows as needed to accommodate the elements it must store. Queue<T> defines the following constructors:
public Queue( ) public Queue (int capacity) public Queue (IEnumerable c)
The first form creates an empty queue with an initial default capacity. The second form creates an empty queue with the initial capacity specified by capacity. The third form creates a queue that contains the elements of the collection specified by c.
In addition to the methods defined by the interfaces that it implements, Queue<T> defines the methods shown in Table 23-20. Queue<T> works just like its non-generic counterpart. To put an object in the queue, call Enqueue( ). To remove and return the object at the front of the queue, call Dequeue( ). An InvalidOperationException is thrown if you call Dequeue( ) when the invoking queue is empty. You can use Peek( ) to return, but not remove, the next object.
| Method | Description |
|---|---|
| public T Dequeue( ) | Returns the object at the front of the invoking queue. The object is removed in the process. |
| public void Enqueue(T v) | Adds v to the end of the queue. |
| public T Peek( ) | Returns the object at the front of the invoking queue, but does not remove it. |
| public T[ ] ToArray( ) | Returns an array that contains copies of the elements of the invoking queue. |
| public void TrimExcess( ) | Removes the excess capacity of the invoking stack. |
Here is an example that demonstrates Queue<T>:
// Demonstrate the Queue<T> class. using System; using System.Collections.Generic; class GenQueueDemo { public static void Main() { Queue<double> q = new Queue<double>(); q.Enqueue(98.6); q.Enqueue(212.0); q.Enqueue(32.0); q.Enqueue(3.1416); double sum = 0.0; Console.Write("Queue contents: "); while(q.Count > 0) { double val = q.Dequeue(); Console.Write(val + " "); sum += val; } Console.WriteLine("\nTotal is " + sum); } } The output is shown here:
Queue contents: 98.6 212 32 3.1416 Total is 345.7416
EAN: 2147483647
Pages: 300