C# Generics: Collection Interfaces

Collection Interfaces

The .NET Framework provides two sets of standard interfaces for enumerating and comparing collections: the traditional (nontype-safe) and the new generic type-safe collections. This book focuses only on the new, type-safe collection interfaces as these are far preferable.

You can declare an ICollection of any specific type by substituting the actual type (for example, int or string) for the generic type in the interface declaration (<T>).

TIP: C++ programmers note: C# generics are similar in syntax and usage to C++ templates. However, because the generic types are expanded to their specific type at runtime, the JIT compiler is able to share code among different instances, dramatically reducing the code bloat that you may see when using templates in C++.

The key generic collection interfaces are listed in Table 9-2. [3]

Table 9-2. Collection interfaces

ICollection<T>

IEnumerator<T>
IEnumerable<T>

ICollection<T>

IComparer<T>
IComparable<T>

IList<T>

IDictionary<K,V>

The IEnumerable<T> Interface

You can support the foreachstatement in ListBoxTest by implementing the IEnumerable<T> interface (see Example 9-11). IEnumerable has only one method, GetEnumerator( ), whose job is to return an implementation of IEnumerator<T>. The C# language provides special help in creating the enumerator, using the new keyword yield.

Example 9-11. Making a ListBox an enumerable class

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace Enumerable
{
   public class ListBoxTest : IEnumerable<String>
   {
      private string[] strings;
      private int ctr = 0;
      // Enumerable classes can return an enumerator
      public IEnumerator<string> GetEnumerator( )
      {
         foreach ( string s in strings )
         {
            yield return s;
         }
      }

      // initialize the list box with strings
      public ListBoxTest( params string[] initialStrings )
      {
         // allocate space for the strings
         strings = new String[8];

         // copy the strings passed in to the constructor
         foreach ( string s in initialStrings )
         {
            strings[ctr++] = s;
         }
      }

      // add a single string to the end of the list box
      public void Add( string theString )
      {
         strings[ctr] = theString;
         ctr++;
      }

      // allow array-like access
      public string this[int index]
      {
         get
         {
            if ( index < 0 || index >= strings.Length )
            {
               // handle bad index
            }
            return strings[index];
         }
         set
         {
            strings[index] = value;
         }
      }

      // publish how many strings you hold
      public int GetNumEntries( )
      {
         return ctr;
      }
   }

   public class Tester

   {
      static void Main( )
      {
         // create a new list box and initialize
         ListBoxTest lbt =
            new ListBoxTest( "Hello", "World" );

         // add a few strings
         lbt.Add( "Who" );
         lbt.Add( "Is" );
         lbt.Add( "John" );
         lbt.Add( "Galt" );

         // test the access
         string subst = "Universe";
         lbt[1] = subst;

         // access all the strings
         foreach ( string s in lbt )
         {
            Console.WriteLine( "Value: {0}", s );
         }
      }
   }
}

Output:
Value: Hello
Value: Universe
Value: Who
Value: Is
Value: John
Value: Galt
Value:
Value:

The program begins in Main( ), creating a new ListBoxTest object and passing two strings to the constructor. When the object is created, an array of Strings is created with enough room for eight strings. Four more strings are added using the Add method, and the second string is updated, just as in the previous example.

The big change in this version of the program is that a foreach loop is called, retrieving each string in the listbox. The foreach loop automatically uses the IEnumerable<T> interface, invoking GetEnumerator( ).

The GetEnumerator method is declared to return an IEnumerator of string:

public IEnumerator<string> GetEnumerator( )

The implementation iterates through the array of strings, yielding each in turn:

foreach ( string s in strings )
{
   yield return s;
}

All the bookkeeping for keeping track of which element is next, resetting the iterator, and so forth, is provided for you by the framework.

Related Reading Programming C# Building .NET Applications with C# By Jesse Liberty

Constraints

There are times when you must ensure that the elements you add to a generic list meet certain constraints (e.g., they derive from a given base class, or they implement a specific interface). In the next example, we implement a simplified singly linked, sortable list. The list consists of Nodes, and each Node must be guaranteed that the types added to it implement IComparer. You do so with the following statement:

 public class Node<T> : 
    IComparable<Node<T>> where T : IComparable<T>

This defines a generic Node that holds a type, T. Node of T implements the IComparable<T> interface, which means that two Nodes of T can be compared. The Node class is constrained (whereT:IComparable<T>) to hold only types that implement the IComparable interface. Thus, you may substitute any type for T so long as that type implements IComparable.

Example 9-12 illustrates the complete implementation, with analysis to follow.

Example 9-12. Using constraints

using System;
using System.Collections.Generic;

namespace UsingConstraints
{
    public class Employee : IComparable<Employee>
    {
        private string name;
        public Employee(string name)
        {
            this.name = name;
        }
        public override string ToString( )
        {
            return this.name;
        }

        // implement the interface
        public int CompareTo(Employee rhs)
        {
            return this.name.CompareTo(rhs.name);
        }
        public bool Equals(Employee rhs)
        {
            return this.name == rhs.name;
        }
    }

    // node must implement IComparable of Node of T.
    // constrain Nodes to only take items that implement Icomparable
    // by using the where keyword.
    public class Node<T> : 
        IComparable<Node<T>> where T : IComparable<T>

    {
        // member fields
        private T data;
        private Node<T> next = null;
        private Node<T> prev = null;

        // constructor
        public Node(T data)
        {
            this.data = data;
        }

        // properties
        public T Data { get { return this.data; } }

        public Node<T> Next
        {
            get { return this.next; }
        }

        public int CompareTo(Node<T> rhs)
        {
            // this works because of the constraint
            return data.CompareTo(rhs.data);
        }

        public bool Equals(Node<T> rhs)
        {
            return this.data.Equals(rhs.data);
        }

        // methods
        public Node<T> Add(Node<T> newNode)
        {
            if (this.CompareTo(newNode) > 0) // goes before me
            {
                newNode.next = this;  // new node points to me

                // if I have a previous, set it to point to
                // the new node as its next
                if (this.prev != null)
                {
                    this.prev.next = newNode;
                    newNode.prev = this.prev;
                }

                // set prev in current node to point to new node
                this.prev = newNode;

                // return the newNode in case it is the new head
                return newNode;
            }
            else            // goes after me
            {
                // if I have a next, pass the new node along for 
                   // comparison
                if (this.next != null)
                {
                    this.next.Add(newNode);
                }

                // I don't have a next so set the new node
                    // to be my next and set its prev to point to me.
                else
                {
                    this.next = newNode;
                    newNode.prev = this;
                }

                return this;
            }
        }

        public override string ToString( )
        {
            string output = data.ToString( );

            if (next != null)
            {
                output += ", " + next.ToString( );
            }

            return output;
        }
    }        // end class

    public class LinkedList<T> where T : IComparable<T>

    {
        // member fields
        private Node<T> headNode = null;

        // properties

        // indexer
        public T this[int index]
        {
            get
            {
                int ctr = 0;
                Node<T> node = headNode;

                while (node != null && ctr <= index)
                {
                    if (ctr == index)
                    {
                        return node.Data;
                    }
                    else
                    {
                        node = node.Next;
                    }

                    ++ctr;
                } // end while
                throw new ArgumentOutOfRangeException( );
            }      // end get
        }          // end indexer

        // constructor
        public LinkedList( )
        {
        }

        // methods
        public void Add(T data)
        {
            if (headNode == null)
            {
                headNode = new Node<T>(data);
            }
            else
            {
                headNode = headNode.Add(new Node<T>(data));
            }
        }
        public override string ToString( )
        {
            if (this.headNode != null)
            {
                return this.headNode.ToString( );
            }
            else
            {
                return string.Empty;
            }
        }
    }

    // Test engine
    class Test

    {
        // entry point
        static void Main(string[] args)
        {
            // make an instance, run the method
            Test t = new Test( );
            t.Run( );
        }

        public void Run( )
        {
            LinkedList<int> myLinkedList = new LinkedList<int>( );
            Random rand = new Random( );
            Console.Write("Adding: ");

            for (int i = 0; i < 10; i++)
            {
                int nextInt = rand.Next(10);
                Console.Write("{0}  ", nextInt);
                myLinkedList.Add(nextInt);
            }

            LinkedList<Employee> employees = new LinkedList<Employee>( );
            employees.Add(new Employee("John"));
            employees.Add(new Employee("Paul"));
            employees.Add(new Employee("George"));
            employees.Add(new Employee("Ringo"));

            Console.WriteLine("\nRetrieving collections...");

            Console.WriteLine("Integers: " + myLinkedList);
            Console.WriteLine("Employees: " + employees);
        }
    }
}

In this example, you begin by declaring a class that can be placed into the linked list:

public class Employee : IComparable<Employee>

This declaration indicates that Employee objects are comparable, and we see that the Employee class implements the required methods (CompareTo and Equals). Note that these methods are type-safe (they know that the parameter passed to them will be of type Employee). The LinkedList itself is declared to hold only types that implement IComparable:

public class LinkedList<T> where T : IComparable<T>

so you are guaranteed to be able to sort the list. The LinkedList holds an object of type Node. Node also implements IComparable and requires that the objects it holds as data themselves implement IComparable:

public class Node<T> : 
    IComparable<Node<T>> where T : IComparable<T>

These constraints make it safe and simple to implement the CompareTo method of Node because the Node knows it will be comparing other Nodes whose data is comparable:

public int CompareTo(Node<T> rhs)
{
    // this works because of the constraint
    return data.CompareTo(rhs.data);
}

Notice that we don't have to test rhs to see if it implements IComparable; we've already constrained Node to hold only data that implements IComparable.

List<T>

The classic problem with the Array type is its fixed size. If you don't know in advance how many objects an array will hold, you run the risk of declaring either too small an array (and running out of room) or too large an array (and wasting memory).

Your program might be asking the user for input, or gathering input from a web site. As it finds objects (strings, books, values, etc.), you will add them to the array, but you have no idea how many objects you'll collect in any given session. The classic fixed-size array is not a good choice, as you can't predict how large an array you'll need.

The List class is an array whose size is dynamically increased as required. Lists provide a number of useful methods and properties for their manipulation. Some of the most important are shown in Table 9-3.

Table 9-3. List methods and properties

When you create a List, you don't define how many objects it will contain. Add to the List using the Add() method, and the list takes care of its own internal bookkeeping, as illustrated in Example 9-13.

Example 9-13. Working with List

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace ListCollection
{
   // a simple class to store in the List
   public class Employee
   {
      private int empID;

      public Employee( int empID )
      {
         this.empID = empID;
      }
      public override string ToString( )
      {
         return empID.ToString( );
      }
      public int EmpID
      {
         get
         {
            return empID;
         }
         set
         {
            empID = value;
         }
      }
   }
   public class Tester
   {
      static void Main( )
      {

         List<Employee> empList = new List<Employee>( );
         List<int> intList = new List<int>( );

         // populate the List
         for ( int i = 0; i < 5; i++ )
         {
            empList.Add( new Employee( i + 100 ) );
            intList.Add( i * 5 );
         }

         // print all the contents
         for ( int i = 0; i < intList.Count; i++ )
         {
            Console.Write( "{0} ", intList[i].ToString( ) );
         }

         Console.WriteLine( "\n" );

         // print all the contents of the Employee List
         for ( int i = 0; i < empList.Count; i++ )
         {
            Console.Write( "{0} ", empList[i].ToString( ) );
         }

         Console.WriteLine( "\n" );
         Console.WriteLine( "empList.Capacity: {0}",
            empList.Capacity );
      }
   }
}

Output:
0 5 10 15 20
100 101 102 103 104
empArray.Capacity: 16

With an Array class, you define how many objects the array will hold. If you try to add more than that, the Array class will throw an exception. With a List, you don't declare how many objects the List will hold. The List has a property, Capacity, which is the number of elements the List is capable of storing:

public int Capacity { get; set; }

The default capacity is 16. When you add the 17th element, the capacity is automatically doubled to 32. If you change the for loop to:

for (int i = 0;i<17;i++)

the output looks like this:

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
empArray.Capacity: 32

You can manually set the capacity to any number equal to or greater than the count. If you set it to a number less than the count, the program will throw an exception of type ArgumentOutOfRangeException.

Implementing IComparable

Like all collections, the List implements the Sort( ) method, which allows you to sort any objects that implement IComparable. In the next example, you'll modify the Employee object to implement IComparable:

public class Employee : IComparable<Employee>

To implement the IComparable<Employee> interface, the Employee object must provide a CompareTo() method:

public int CompareTo(Employee rhs)
{
   return this.empID.CompareTo(r.empID);
}

The CompareTo( ) method takes an Employee as a parameter. We know this is an Employee because this is a type-safe collection. The current Employee object must compare itself to the Employee passed in as a parameter and return -1 if it is smaller than the parameter, 1 if it is greater than the parameter, and 0 if it is equal to the parameter. It is up to Employee to determine what smallerthan, greaterthan, and equalto mean. In this example, you delegate the comparison to the empId member. The empId member is an int and uses the default CompareTo( ) method for integer types, which will do an integer comparison of the two values.

TIP: The System.Int32 class implements IComparable<Int32>, so you may delegate the comparison responsibility to integers.

You are now ready to sort the array list of employees, empList. To see if the sort is working, you'll need to add integers and Employee instances to their respective arrays with random values. To create the random values, you'll instantiate an object of class Random; to generate the random values, you'll call the Next( ) method on the Random object, which returns a pseudorandom number. The Next( ) method is overloaded; one version allows you to pass in an integer that represents the largest random number you want. In this case, you'll pass in the value 10 to generate a random number between 0 and 10:

Random r = new Random();
r.Next(10);

Example 9-14 creates an integer array and an Employee array, populates them both with random numbers, and prints their values. It then sorts both arrays and prints the new values.

Example 9-14. Sorting an integer and an employee array

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace IComparable
{
   // a simple class to store in the array
   public class Employee : IComparable<Employee>

   {
      private int empID;

      public Employee( int empID )
      {
         this.empID = empID;
      }

      public override string ToString( )
      {
         return empID.ToString( );
      }

      public bool Equals( Employee other )
      {
         if ( this.empID == other.empID )
         {
            return true;
         }
         else
         {
            return false;
         }
      }

      // Comparer delegates back to Employee
      // Employee uses the integer's default
      // CompareTo method

      public int CompareTo( Employee rhs )
      {
         return this.empID.CompareTo( rhs.empID );
      }
   }
   public class Tester
   {
      static void Main( )
      {
         List<Employee> empArray = new List<Employee>( );
         List<Int32> intArray = new List<Int32>( );

         // generate random numbers for 
         // both the integers and the
         // employee id's

         Random r = new Random( );

         // populate the array
         for ( int i = 0; i < 5; i++ )
         {
            // add a random employee id
            empArray.Add( new Employee( r.Next( 10 ) + 100 ) );

            // add a random integer
            intArray.Add( r.Next( 10 ) );
         }

         // display all the contents of the int array
         for ( int i = 0; i < intArray.Count; i++ )
         {
            Console.Write( "{0} ", intArray[i].ToString( ) );
         }
         Console.WriteLine( "\n" );

         // display all the contents of the Employee array
         for ( int i = 0; i < empArray.Count; i++ )
         {
            Console.Write( "{0} ", empArray[i].ToString( ) );
         }
         Console.WriteLine( "\n" );

         // sort and display the int array
         intArray.Sort( );
         for ( int i = 0; i < intArray.Count; i++ )
         {
            Console.Write( "{0} ", intArray[i].ToString( ) );
         }
         Console.WriteLine( "\n" );

         // sort and display the employee array
         Employee.EmployeeComparer c = Employee.GetComparer( );
         empArray.Sort(c);

         empArray.Sort( );

         // display all the contents of the Employee array
         for ( int i = 0; i < empArray.Count; i++ )
         {
            Console.Write( "{0} ", empArray[i].ToString( ) );
         }
         Console.WriteLine( "\n" );
      }
   }
}

Output:
4 5 6 5 7 
108 100 101 103 103 
4 5 5 6 7 
100 101 103 103 108

The output shows that the integer array and Employee array were generated with random numbers. When sorted, the display shows the values have been ordered properly.

Implementing IComparer

When you call Sort( ) on the List, the default implementation of IComparer is called, which uses QuickSort to call the IComparable implementation of CompareTo() on each element in the List.

You are free to create your own implementation of IComparer, which you might want to do if you need control over how the sort ordering is defined. In the next example, you will add a second field to Employee, yearsOfSvc. You want to be able to sort the Employee objects in the List on either field, empID or yearsOfSvc.

To accomplish this, create a custom implementation of IComparer, which you pass to the Sort() method of the List. This IComparer class, EmployeeComparer, knows about Employee objects and knows how to sort them.

EmployeeComparer has the WhichComparison property, of type Employee. EmployeeComparer.ComparisonType:

public Employee.EmployeeComparer.ComparisonType
   WhichComparison 
{
   get{return whichComparison;}
   set{whichComparison = value;}
}

ComparisonType is an enumeration with two values, empID or yearsOfSvc (indicating that you want to sort by employee ID or years of service, respectively):

public enum ComparisonType
{
   EmpID,
   YearsOfService
};

Before invoking Sort( ), create an instance of EmployeeComparer and set its ComparisionType property:

Employee.EmployeeComparer c = Employee.GetComparer(); 
c.WhichComparison=Employee.EmployeeComparer.ComparisonType.EmpID;
empArray.Sort(c);

When you invoke Sort( ), the List calls the Compare method on the EmployeeComparer, which in turn delegates the comparison to the Employee.CompareTo() method, passing in its WhichComparison property:

public int Compare( Employee lhs, Employee rhs )
{
    return lhs.CompareTo( rhs, WhichComparison );
}

The Employee object must implement a custom version of CompareTo( ), which takes the comparison and compares the objects accordingly:

public int CompareTo(
    Employee rhs, 
    Employee.EmployeeComparer.ComparisonType which)
{
   switch (which)
   {
      case Employee.EmployeeComparer.ComparisonType.EmpID:
         return this.empID.CompareTo(rhs.empID);
      case Employee.EmployeeComparer.ComparisonType.Yrs:
         return this.yearsOfSvc.CompareTo(rhs.yearsOfSvc);
   }
   return 0;
}

The complete source for this example is shown in Example 9-15. The integer array has been removed to simplify the example, and the output of the employee's ToString( ) method has been enhanced to enable you to see the effects of the sort.

Example 9-15. Sorting an array by employees' IDs and years of service

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace IComparer
{
   public class Employee : IComparable<Employee>

   {
      private int empID;

      private int yearsOfSvc = 1;

      public Employee( int empID )
      {
         this.empID = empID;
      }

      public Employee( int empID, int yearsOfSvc )
      {
         this.empID = empID;
         this.yearsOfSvc = yearsOfSvc;
      }

      public override string ToString( )
      {
         return "ID: " + empID.ToString( ) +
         ". Years of Svc: " + yearsOfSvc.ToString( );
      }

      public bool Equals( Employee other )
      {
         if ( this.empID == other.empID )
         {
            return true;
         }
         else
         {
            return false;
         }
      }

      // static method to get a Comparer object
      public static EmployeeComparer GetComparer( )
      {
         return new Employee.EmployeeComparer( );
      }

      // Comparer delegates back to Employee
      // Employee uses the integer's default
      // CompareTo method
      public int CompareTo( Employee rhs )
      {
         return this.empID.CompareTo( rhs.empID );
      }

      // Special implementation to be called by custom comparer
      public int CompareTo(
         Employee rhs,
         Employee.EmployeeComparer.ComparisonType which )
      {
         switch ( which )
         {
            case Employee.EmployeeComparer.ComparisonType.EmpID:
               return this.empID.CompareTo( rhs.empID );
            case Employee.EmployeeComparer.ComparisonType.Yrs:
               return this.yearsOfSvc.CompareTo( rhs.yearsOfSvc );
         }
         return 0;

      }

      // nested class which implements IComparer
      public class EmployeeComparer : IComparer<Employee>

      {
         
         // private state variable
         private Employee.EmployeeComparer.ComparisonType
            whichComparison;

         // enumeration of comparison types
         public enum ComparisonType
         {
            EmpID,
            Yrs
         };

         public  bool Equals( Employee lhs, Employee rhs )
         {
            return this.Compare( lhs, rhs ) == 0;
         }

         public  int GetHashCode(Employee e)
         {
            return e.GetHashCode( );
         }

         // Tell the Employee objects to compare themselves
         public int Compare( Employee lhs, Employee rhs )
         {
             return lhs.CompareTo( rhs, WhichComparison );
         }

         public Employee.EmployeeComparer.ComparisonType

            WhichComparison 
         {
            get{return whichComparison;}
            set{whichComparison = value;}
         }
      }
   }
   public class Tester
   {
      static void Main( )
      {
         List<Employee> empArray = new List<Employee>( );

         // generate random numbers for 
         // both the integers and the
         // employee id's
         Random r = new Random( );

         // populate the array
         for ( int i = 0; i < 5; i++ )
         {
            // add a random employee id

            empArray.Add(
               new Employee(
                  r.Next( 10 ) + 100, r.Next( 20 )
               )
            );
         }

         // display all the contents of the Employee array
         for ( int i = 0; i < empArray.Count; i++ )
         {
            Console.Write( "\n{0} ", empArray[i].ToString( ) );
         }
         Console.WriteLine( "\n" );

         // sort and display the employee array
         Employee.EmployeeComparer c = Employee.GetComparer( );
         c.WhichComparison = 
            Employee.EmployeeComparer.ComparisonType.EmpID;
         empArray.Sort( c );

         // display all the contents of the Employee array
         for ( int i = 0; i < empArray.Count; i++ )
         {
            Console.Write( "\n{0} ", empArray[i].ToString( ) );
         }
         Console.WriteLine( "\n" );

         c.WhichComparison = Employee.EmployeeComparer.ComparisonType.Yrs;
         empArray.Sort( c );

         for ( int i = 0; i < empArray.Count; i++ )
         {
            Console.Write( "\n{0} ", empArray[i].ToString( ) );
         }
         Console.WriteLine( "\n" );
      }
   }
}

Output:
ID: 103. Years of Svc: 11
ID: 108. Years of Svc: 15
ID: 107. Years of Svc: 14
ID: 108. Years of Svc: 5
ID: 102. Years of Svc: 0

ID: 102. Years of Svc: 0
ID: 103. Years of Svc: 11
ID: 107. Years of Svc: 14
ID: 108. Years of Svc: 15
ID: 108. Years of Svc: 5

ID: 102. Years of Svc: 0
ID: 108. Years of Svc: 5
ID: 103. Years of Svc: 11
ID: 107. Years of Svc: 14
ID: 108. Years of Svc: 15

The first block of output shows the Employee objects as they are added to the List. The employee ID values and the years of service are in random order. The second block shows the results of sorting by the employee ID, and the third block shows the results of sorting by years of service.

TIP: If you are creating your own collection, as in Example 9-11, and wish to implement IComparer, you may need to ensure that all the types placed in the list implement IComparer (so that they may be sorted), by using constraints as described earlier.

Queues

A queue represents a first-in, first-out (FIFO) collection. The classic analogy is to a line (or queue if you are British) at a ticket window. The first person in line ought to be the first person to come off the line to buy a ticket.

A queue is a good collection to use when you are managing a limited resource. For example, you might want to send messages to a resource that can handle only one message at a time. You would then create a message queue so that you can say to your clients: "Your message is important to us. Messages are handled in the order in which they are received."

The Queue class has a number of member methods and properties, as shown in Table 9-4.

Table 9-4. Queue methods and properties

Add elements to your queue with the Enqueue command and take them off the queue with Dequeue or by using an enumerator. Example 9-16 illustrates.

Example 9-16. Working with a queue

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace Queue
{
   public class Tester
   {

      static void Main( )
      {

         Queue<Int32> intQueue = new Queue<Int32>( );

         // populate the array
         for ( int i = 0; i < 5; i++ )
         {

            intQueue.Enqueue( i * 5 );

         }

         // Display the Queue.
         Console.Write( "intQueue values:\t" );
         PrintValues( intQueue );

         // Remove an element from the queue.
         Console.WriteLine(
            "\n(Dequeue)\t{0}", intQueuee.Dequeue( ) );

         // Display the Queue.
         Console.Write( "intQueue values:\t" );
         PrintValues( intQueue );

         // Remove another element from the queue.
         Console.WriteLine(
            "\n(Dequeue)\t{0}", intQueuee.Dequeue( ) );

         // Display the Queue.
         Console.Write( "intQueue values:\t" );
         PrintValues( intQueue );

         // View the first element in the 
         // Queue but do not remove.
         Console.WriteLine(
            "\n(Peek)   \t{0}", intQueuee.Peek( ) );

         // Display the Queue.
         Console.Write( "intQueue values:\t" );
         PrintValues( intQueue );

      }

      public static void PrintValues(IEnumerable<Int32> myCollection)
      {
         IEnumerator<Int32> myEnumerator =
            myCollection.GetEnumerator( );
         while ( myEnumerator.MoveNext( ) )
            Console.Write( "{0} ", myEnumerator.Current );
         Console.WriteLine( );
      }
   }
}

Output:
intQueue values:       0 5 10 15 20

(Dequeue)       0
intQueuee values:       5 10 15 20

(Dequeue)       5
intQueue values:       10 15 20

(Peek)          10

intQueue values:       10 15 20

In this example the List is replaced by a Queue. I've dispensed with the Employee class to save room, but of course you can Enqueue user-defined objects as well.

The output shows that queuing objects adds them to the Queue, and calls to Dequeue return the object and also remove them from the Queue. The Queue class also provides a Peek() method that allows you to see, but not remove, the first element.

Because the Queue class is enumerable, you can pass it to the PrintValues method, which is provided as an IEnumerable interface. The conversion is implicit. In the PrintValues method you call GetEnumerator, which you will remember is the single method of all IEnumerable classes. This returns an IEnumerator, which you then use to enumerate all the objects in the collection.

Stacks

A stack is a last-in, first-out (LIFO) collection, like a stack of dishes at a buffet table, or a stack of coins on your desk. A dish added on top is the first dish you take off the stack.

The principal methods for adding to and removing from a stack are Push() and Pop(); Stack also offers a Peek() method, very much like Queue. The significant methods and properties for Stack are shown in Table 9-5.

Table 9-5. Stack methods and properties

The List, Queue, and Stack types contain overloaded CopyTo( ) and ToArray( ) methods for copying their elements to an array. In the case of a Stack, the CopyTo( ) method will copy its elements to an existing one-dimensional array, overwriting the contents of the array beginning at the index you specify. The ToArray( ) method returns a new array with the contents of the stack's elements. Example 9-17 illustrates.

Example 9-17. Working with a stack

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace Stack
{
   public class Tester
   {
      static void Main( )
      {
         Stack<Int32> intStack = new Stack<Int32>( );

         // populate the array

         for ( int i = 0; i < 8; i++ )
         {
            intStack.Push( i * 5 );
         }

         // Display the Stack.
         Console.Write( "intStack values:\t" );
         PrintValues( intStack );

         // Remove an element from the stack.
         Console.WriteLine( "\n(Pop)\t{0}",
         intStack.Pop( ) );

         // Display the Stack.
         Console.Write( "intStack values:\t" );
         PrintValues( intStack );

         // Remove another element from the stack.
         Console.WriteLine( "\n(Pop)\t{0}",
            intStack.Pop( ) );

         // Display the Stack.
         Console.Write( "intStack values:\t" );
         PrintValues( intStack );

         // View the first element in the 
         // Stack but do not remove.
         Console.WriteLine( "\n(Peek)   \t{0}",
            intStack.Peek( ) );

         // Display the Stack.
         Console.Write( "intStack values:\t" );
         PrintValues( intStack );

         // declare an array object which will 
         // hold 12 integers
         int[] targetArray = new int[12];

         for (int i = 0; i < targetArray.Length; i++)
         {
             targetArray[i] = i * 100 + 100;
         }
        // Display the values of the target Array instance.
        Console.WriteLine( "\nTarget array:  " );
        PrintValues( targetArray );

         // Copy the entire source Stack to the  
         // target Array instance, starting at index 6.
         intStack.CopyTo( targetArray, 6 );

         // Display the values of the target Array instance.
         Console.WriteLine( "\nTarget array after copy:  " );
         PrintValues( targetArray );
      }

      public static void PrintValues(
         IEnumerable<Int32> myCollection )
      {
         IEnumerator<Int32> enumerator =
             myCollection.GetEnumerator( );
         while ( enumerator.MoveNext( ) )
            Console.Write( "{0}  ", enumerator.Current );
         Console.WriteLine( );
      }
   }
}

Output:
intStack values:        35  30  25  20  15  10  5  0

(Pop)   35
intStack values:        30  25  20  15  10  5  0

(Pop)   30
intStack values:        25  20  15  10  5  0

(Peek)          25
intStack values:        25  20  15  10  5  0

Target array:
100  200  300  400  500  600  700  800  900  0  0  0

Target array after copy:
100  200  300  400  500  600  25  20  15  10  5  0

The new  array:
25  20  15  10  5  0

The output reflects that the items pushed onto the stack were popped in reverse order.

The effect of CopyTo() can be seen by examining the target array before and after calling CopyTo( ). The array elements are overwritten beginning with the index specified (6).

Dictionaries

A dictionary is a collection that associates a key to a value. A language dictionary, such as Webster's, associates a word (the key) with its definition (the value).

To see the value of dictionaries, start by imagining that you want to keep a list of the state capitals. One approach might be to put them in an array:

string[] stateCapitals = new string[50];

The stateCapitals array will hold 50 state capitals. Each capital is accessed as an offset into the array. For example, to access the capital for Arkansas, you need to know that Arkansas is the fourth state in alphabetical order:

string capitalOfArkansas = stateCapitals[3];

It is inconvenient, however, to access state capitals using array notation. After all, if I need the capital for Massachusetts, there is no easy way for me to determine that Massachusetts is the 21st state alphabetically.

It would be far more convenient to store the capital with the state name. A dictionary allows you to store a value (in this case, the capital) with a key (in this case, the name of the state).

A .NET Framework dictionary can associate any kind of key (string, integer, object, etc.) with any kind of value (string, integer, object, etc.). Typically, of course, the key is fairly short, the value fairly complex.

The most important attributes of a good dictionary are that it is easy to add and quick to retrieve values (see Table 9-6).

Table 9-6. Dictionary methods and properties

Count

Item( )

Keys

Values

Add( )

Clear( )

ContainsKey()

ContainsValue( )

GetEnumerator( )

GetObjectData()

Remove( )

The key in a Dictionary can be a primitive type, or it can be an instance of a user-defined type (an object). Objects used as keys for a Dictionary must implement GetHashCode() as well as Equals. In most cases, you can simply use the inherited implementation from Object.

IDictionary<K,V>

Dictionaries implement the IDictionary<K,V> interface (where K is the key type and V is the value type). IDictionary provides a public property Item. The Item property retrieves a value with the specified key. In C#, the declaration for the Item property is:

V[K key]
{get; set;}

The Item property is implemented in C# with the index operator ([]). Thus, you access items in any Dictionary object using the offset syntax, as you would with an array.

Example 9-18 demonstrates adding items to a Dictionary and then retrieving them with the Item property.

Example 9-18. The Item property as offset operators

namespace Dictionary
{
   public class Tester
   {
      static void Main( )
      {
         // Create and initialize a new Dictionary.
         Dictionary<string,string> Dictionary = 
           new Dictionary<string,string>( );
         Dictionary.Add("000440312", "Jesse Liberty");
         Dictionary.Add("000123933", "Stacey Liberty");
         Dictionary.Add("000145938", "John Galt");
         Dictionary.Add("000773394", "Ayn Rand");

         // access a particular item
         Console.WriteLine("myDictionary[\"000145938\"]: {0}",
            Dictionary["000145938"]);
      }
   }
}

Output:
Dictionary["000145938"]: John Galt

Example 9-18 begins by instantiating a new Dictionary. The type of the key and of the value is declared to be string.

Add four key/value pairs. In this example, the Social Security number is tied to the person's full name. (Note that the Social Security numbers here are intentionally bogus.)

Once the items are added, you access a specific entry in the dictionary using the Social Security number as key.

WARNING If you use a reference type as a key, and the type is mutable (strings are immutable), you must not change the value of the key object once you are using it in a dictionary.

If, for example, you use the Employee object as a key, changing the employee ID creates problems if that property is used by the Equals or GetHashCode methods because the dictionary consults these methods.

Footnotes

[3] For backward compatibility, C# also provides nongeneric interfaces (e.g., ICollection, IEnumerator), but they aren't considered here because they are obsolescent.

[4] The idiom in the FCL is to provide an Item element for collection classes which is implemented as an indexer in C#.

Jesse Liberty is a senior program manager for Microsoft Silverlight where he is responsible for the creation of tutorials, videos and other content to facilitate the learning and use of Silverlight. Jesse is well known in the industry in part because of his many bestselling books, including O'Reilly Media's Programming .NET 3.5, Programming C# 3.0, Learning ASP.NET with AJAX and the soon to be published Programming Silverlight.

View catalog information for Programming C#, 4th Edition

Return to ONDotnet.com.

Copyright © 2009 O'Reilly Media, Inc.