Generics

Introduction - Generic Collections

Introduction

There were several new C# constructs introduced in .NET 2.0 in order to deal with some type safety and Windows Forms isssues. Apart from partial clases and anonymous delgates, a C# construct called generics was introduced. Generics are conceptually similar to C++ templates in the fact that both deal with parameterized types, but generics are a runtime instantiation as opposed to a C++ compilation instantiation. Stated crudely, rather than passing a parameter to method, you are pasing a data type to an object. Should you have a generalized algorithm, you can use generics to sort through lists or perform binary searches by using this reusable code and passing the parmeterized type correspondant to the type involved in the algorithmic funcationlity-oriented operation. Generics, again, were not introduced until .NET 2.0.

Arrays have some obvious limitations. They are a sequence of homogenous items (homogenous meaning of the same type), but they also stop where collections begin. The collections in the System.Collections.Generic enable you to use generics to constrain what type of item may be stored inside an instance. The primary strength of generics lie in the fact in that they eliminate the need for type conversion by using boxing and unboxing. These types of casts cause “unsafe types” and also reduce the performance. All generic collection classes implement a core-set of base-interfaces that enable common operations independent of the algorithm used by the implementation. This allows generalized algorithms to operate on collections of things. An interface, also known as a contract, differs from a class in that an interface defines a common set of members that all classes which implement the interface must provide. For example, the IComparable interface defines the CompareTo method, which enables two instances of a class to be compared for equality.

Simple Collections (ICollections<t>)

The ICollection<t> interface is used to represent a simple collection of items, each of type T. For example, an ICollection<string> contains a collection of string references. The interface exposes the capability to access and modify the contents of a collection and to determine its length. It also derives from the IEnumerable<t>, meaning that any implementation of ICollection<t> will also supply a GetEnumerator method that returns an enumerator, using which you may walk its contents. This interface and its specific classes can be used for the manipulation of arrays where the size can vary as we add or remove elements. Such arrays are called sequences.

namespace System.Collections.Generic
 {
   public interface ICollection<t> : IEnumerable<t>
  {
   // Properties
      int Count {  get; }
      bool IsReadOnly  { get; }

//Methods

void Add( T item);
void  Clear();
bool Contains(T item);
void CopyTo(T[]  array, int arrayIndex);
IEnumerator<t> GetEnumerator();
IEnumerator   GetEnumerator();
bool Remove(T item);
  }
}

A code example of System Collections (ICollection<t>):

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Text;
public sealed class Program {
        public static void Main()
        {
            ICollection<int> myCollection = new Collection<int>();
// Note that we start by creating a Collection<int> object, 
// in whose parameters are stored by reference to myCollection
            // First, add a few elements to the collection:
            myCollection.Add(105);
            myCollection.Add(232);
            myCollection.Add(350);

            // .And then delete one:
            myCollection.Remove(232);

            // Search for some specific elements:
            Console.WriteLine("Contains {0}? {1}", 105, myCollection.Contains(105));
            Console.WriteLine("Contains {0}? {1}", 232, myCollection.Contains(232));

            // Enumerate the collection's contents:
            foreach (int i in myCollection)
                Console.WriteLine(i);

            // Lastly, copy the contents to an array so that we may iterate that:
            int[] myArray = new int[myCollection.Count];
            myCollection.CopyTo(myArray, 0);
            for (int i = 0; i < myArray.Length; i++)
                Console.WriteLine(myArray[i]);
        }
}

So we declared the interface to expose the functionality from the classes and then use the type to create an object. We used the delimiter in the Console.WriteLine() method to actually search the items of the collection, as the Contains() method returns a Boolean true if an item exists and a false if not. The Add() method adds an item in an unspecified location of the collection.

The IList<t> interface derives from ICollection<t> and adds a few members to support adding, removing, and accessing contents using a 0-based numerical index.

namespace  System.Collections.Generic 
 {
  public  interface IList<t> : ICollection<t>
   {
       // members  inherited from ICollection<t>  have been omitted.
       // Properties
      T this[int index]  {  get;  set: }
     // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);
  }
}

Here is another piece of sample code:

using System;
       using System.Collections.Generic; 
       public sealed class Program {
        public static void Main()
        {
            IList myList = new List();

            // First, we add, insert, and remove some items:
            myList.Add(10.54);
            myList.Add(209.2234);
            myList.Insert(1, 39.999);
            myList.Add(438.2);
            myList.Remove(10.54);

            // Then, we print some specific element indexes:
            Console.WriteLine("IndexOf {0} = {1}", 209.2234, myList.IndexOf(209.2234));
            Console.WriteLine("IndexOf {0} = {1}", 10.54, myList.IndexOf(10.54));

            // Lastly, we enumerate the list using Count and IList<t>'s indexer:
            for (int i = 0; i < myList.Count; i++)
                Console.WriteLine(myList[i]);
        }
}

Output

IndexOf 209.2234 = 1 

IndexOf 10.54 = -1 
39.999
209.2234
438.2

Reiterate the code, and notice that the object made by calling the new operator has its constructor parameters stored in myList:

IList<double> myList = new List<double>();

// First, we add, insert, and remove some items:
            myList.Add(10.54);
            myList.Add(209.2234);
            myList.Insert(1, 39.999);
            myList.Add(438.2);
            myList.Remove(10.54);

// Then, we print some specific element indexes:
            Console.WriteLine("IndexOf {0} = {1}", 209.2234, myList.IndexOf(209.2234));
            Console.WriteLine("IndexOf {0} = {1}", 10.54, myList.IndexOf(10.54));

// Lastly, we enumerate the list using Count and IList<t>'s indexer:
            for (int i = 0; i < myList.Count; i++)
                Console.WriteLine(myList[i]);
        }
}

We set up our list by adding two numbers, 10.54 and 209.2234, inserting 39.999 between them, and adding 438.2 at the end. Finally, we removed 10.54. We then locate the index of 209.2234, which ends up being, since we removed the previously placed element (10.54). Recall that we are using a 0-based numerical index, which means that 10.54 would have indexed to 0. We also look for 10.54, which results in -1 because we removed it from the collection. Lastly, we loop through the contents of the list, accessing its contents with the indexer.

Dictionaries IDictionary()

A dictionary is a container with a collection of key and value associations. Aside from dictionary, this data structure is often called an associative array, map, or hash table, the latter of which is actually the name of a common implementation technique for creating dictionaries. With IDictionary<tkey>, the type parameters TKey and TValue represent the types of the keys and values it can store. So, for example, an IDictionary<string> is a dictionary that contains string keys that map to integer values.

namespace System.Collection.Generic
   {
       // note members inherited from ICollection<t> have been omitted
            public  interface IDictionary<tkey> :
 ICollection<keyvaluepair<tkey>>
  {
   // Properties
TValue this[TKey key] {  get;  set; }
ICollection<tkey> Keys { get; }
ICollection<tvalue> Values { get; }
// Methods
void  Add(TKey key, TValue value);
bool ContainsKey(TKey key);
bool Remove(TKey key);
bool TryGetValue(TKey key, out TValue value);
  }
[Serializable, StructLayout(LayoutKind.Sequential)]
public  struct KeyValuePair<tkey>
  {
      public  TKey Key;
      public TValue Value;
      public KeyValuePair(TKey key, TValue value);
      public override string ToString();
   }
}

Each key-value association is represented by a KeyValuePair object. Thus, this type is really just a collection of KeyValuePairs. KeyValuePair is a value type that provides two public fields: Key of type TKey and Value of type TValue. Here is the sample code:

       using System;
       using System.Collections.Generic;
       public sealed class Program {
       public static void Main()
           {
            IDictionary<string> salaryMap = new Dictionary<string,>();

            // Add some entries into the dictionary:
            salaryMap.Add("Sean", 62250.5M);
            salaryMap.Add("Wolf", 16000.0M);
            salaryMap.Add("Jamie", 32900.99M);

            // Now, remove one:
            salaryMap.Remove("Wolf");

            // Check whether certain keys exist in the map:
            Console.WriteLine(salaryMap.ContainsKey("Sean")); // Prints `True'
            Console.WriteLine(salaryMap.ContainsKey("Steve")); // Prints `False'

            // Retrieve some values from the map:
            Console.WriteLine("{0:C}", salaryMap["Sean"]); // Prints `$62,250.50'
            Console.WriteLine("{0:C}", salaryMap["Jamie"]); // Prints `$32,900.99'

            // Now just iterate over the map and add up the values:
            decimal total = 0.0M;
            foreach (decimal d in salaryMap.Values)
                total += d;
            Console.WriteLine("{0:C}", total); // Prints `$95,151.49'

            // Iterating over map/value pairs:
            // (The wrong way)
            foreach (string key in salaryMap.Keys)
                Console.WriteLine("{0} == {1}", key, salaryMap[key]);

            // (The right way)
            foreach (KeyValuePair<string> kvp in salaryMap)
                Console.WriteLine("{0} == {1}", kvp.Key, kvp.Value);
        }
}

Output

True
False
$62,250.50
$32,900.99
$95,151.49
Sean == 62250.5
Jamie == 32900.99
Sean == 62250.5
Jamie == 32900.99

Some more basic code to exemplify the concept:

using System;
using System.Collections.Generic;
class Program 
 {
  static void Main(string[]  args)
    {
      Dictionary<int,> cl = new Dictionary<int,>();
       cl[44] = "UnitedKingdom";
       cl[33] = "France";
       cl[31] = "Netherlands";
       cl[55] = "Brazil";    
       Console.WriteLine("The 33 code is for: {0}", cl[33]);    

       foreach (KeyValuePair<int,> item in cl)
        {
            int code = item.Key;
            string country = item.Value;        
            Console.WriteLine("Code {0} = {1}", code, country);
         }   
      Console.Read();
     }
}

Output

The 33 code is for: France
Code 44 = UnitedKingdom
Code 33 = France
Code 31 = Netherlands
Code 55 = Brazil

Enumerators IEnumerable<t> and IEnumerator<t>

The general concept of an enumerator is that of a type whose sole purpose is to advance through and read anther collection’s contents. Enumerators do not provide write capabilities. IEnumerable<t> represents a type whose contents can be enumerated, while IEnumerator<t> is the type for performing the actual enumeration:

namespace System.Collections.Generic
 {
  public interface IEnumerable<t> : IEnumerable
   {
     // Methods
           IEnumerator<t> GetEnumerator();
           IEnumerator GetEnumerator(); // inherited from IEnumerable
      }
    public interface IEnumerator<t> : IDisposable, IEnumerator
    {
       // Properties
        
        T Current { get; }
        object Current {  get; }   // inherited from IEnumerator
        // Methods
       void Dispose();
        bool MoveNext();
        void Reset();
    }
 } 

Upon instantiation, an enumeration becomes dependent on a collection. Walking an enumeration’s contents involve the foreach construct, which rely on enumerators to access the contents of any enumerable collection. So when you write the following code:

IEnumerable enumerable = new string[] { "A", "B", "C" };
foreach (string s in enumerable)
Console.WriteLine(s);
. . . .

The C# compiler will actually emit a call to enumerable’s GetEnumerator() method for you and will use the resulting enumerator to walk through its contents. Here is a sample code:

         using System;
         using System.Collections.Generic;
         public sealed class Program {
         public static void Main()
        {
            IEnumerable<string> enumerable = new string[] { "A", "B", "C" };

            // Short-hand form:
            foreach (string s in enumerable)
                Console.WriteLine(s);

            // Long-hand form:
            IEnumerator<string> enumerator = enumerable.GetEnumerator();
            while (enumerator.MoveNext())
            {
                string s = enumerator.Current;
                Console.WriteLine(s);
            }
        }
}

Output

A
B
C
A
B
C

C# Iterators

To create an iterator, you must create a (static) method that returns either IEnumerable<t> or IEnumerator<t>, and generates a sequence of values using the yield statement. The C# compiler will create the underlying IEnumerator<t> type for you:

       class DoublerContainer : IEnumerable<int>
        {
            private List<int> myList = new List<int>();

            public DoublerContainer(List<int> myList)
            {
                this.myList = myList;
            }

            public IEnumerator<int> GetEnumerator()
            {
                foreach (int i in myList)
                    yield return i * 2;
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return ((IEnumerable<int>)this).GetEnumerator();
            }
  }

Now we create a static method that returns either IEnumerable<t> or IEnumerator<t>, and generates a sequence of values using the yield statement.

using System;
using System.Collections.Generic;
static IEnumerable<int> Fibonacci(int max);
        {
            int i1 = 1;
            int i2 = 1;

            while (i1 <= max)
            {
                yield return i1;
                int t = i1;
                i1 = i2;
                i2 = t + i2;
            }
        }
        public class Program {
        public static void Main()
        {
            // First, walk a doubler-container:
            Console.WriteLine("Doubler:");
            DoublerContainer dc = new DoublerContainer(
                new List<int>(new int[] { 10, 20, 30, 40, 50 }));
            foreach (int x in dc)
                Console.WriteLine(x);

            // Next, walk the fibonacci generator:
            Console.WriteLine("Fibonacci:");
            foreach (int i in Fibonacci(21))
                Console.WriteLine(i);
        }
     }
   }

Output

Doubler:
20
40
60
80
100
Fibonacci:
1
1
2
3
5
8
13
21

Collections Implementations

Standard List (List<t>)

The List<t> class is the most commonly used implementation of IList<t>, providing an order, indexable collection of objects. When you construct a new list, you can optionally pass in its initial capacity as an argument using the List<t>(int capacity) constructor. List<t> also has methods like Reverse and sort that actually modify the order in which a list's items are stored.

using System;
using System.Collections.Generic;
public sealed class Program {
public static void Main() {
// create an initialize byte array
Byte[] byteArray = new Byte[] { 5, 1, 2, 4, 3 };
// call byte sort algorithm
Array.Sort(byteArray);
// call binary search algorithm
Int32 i = Array.BinarySearch(byteArray, 3);
 Console.WriteLine(i);
  }
}

The output is 2.

Lastly, an example of welding .NET language constructs together to develop a practical application.

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

        struct Employee
        {
            public string FirstName;
            public string LastName;
            public int Extension;
            public string SocialSecurityNumber;
            public bool Salaried;

            public Employee(string firstName, string lastName, 
			int extension, string ssn, bool salaried)
            {
                this.FirstName = firstName;
                this.LastName = lastName;
                this.Extension = extension;
                this.SocialSecurityNumber = ssn;
                this.Salaried = salaried;
            }

            public override string ToString()
            {
                return string.Format("{0}, {1}; {2}; {3}; {4}", 
		LastName, FirstName, Extension, SocialSecurityNumber, Salaried);
            }        

        private static List<employee> CreateEmployees()
        {
            List<employee> emps = new List<employee>();
            emps.Add(new Employee("Joe", "Duffy", 32500, "000-11-2222", true));
            emps.Add(new Employee("George", "Bush", 50123, "001-01-0001", true));
            emps.Add(new Employee("Jess", "Robinson", 99332, "321-21-4321", false));
            emps.Add(new Employee("Billy", "Bob", 32332, "333-22-1111", true));
            emps.Add(new Employee("Homer", "Simpson", 93812, "999-88-7777", false));
            return emps;
        }

        private static List<employee> DeserializeEmployees(Stream s)
        {
            List<employee> employees = new List<employee>();
            BinaryReader reader = new BinaryReader(s);

            try
            {
                while (true)
                {
                    Employee e = new Employee();
                    e.FirstName = reader.ReadString();
                    e.LastName = reader.ReadString();
                    e.Extension = reader.ReadInt32();
                    e.SocialSecurityNumber = reader.ReadString();
                    e.Salaried = reader.ReadBoolean();
                    employees.Add(e);
                    Console.WriteLine("Read: {0}", e.ToString());
                }
            }
            catch (EndOfStreamException)
            {
                // ok, expected end of stream
            }

            return employees;
        }

        private static void SerializeEmployees(Stream s, IEnumerable<employee> employees)
        {
            BinaryWriter writer = new BinaryWriter(s);
            foreach (Employee e in employees)
            {
                writer.Write(e.FirstName);
                writer.Write(e.LastName);
                writer.Write(e.Extension);
                writer.Write(e.SocialSecurityNumber);
                writer.Write(e.Salaried);
                Console.WriteLine("Wrote: {0}", e.ToString());
            }
        }
        public sealed class Program {
        public static void Main()
        {
            Stream s = new MemoryStream();
            IEnumerable<employee> employees = CreateEmployees();

            SerializeEmployees(s, employees);

            // Deserialize:
            s.Seek(0, SeekOrigin.Begin);
            DeserializeEmployees(s);

            // Print out raw bytes:
            s.Seek(0, SeekOrigin.Begin);
            int read;
            while ((read = s.ReadByte()) != -1)
                Console.Write("{0:X} ", read);
        }
     }
}

Output

Wrote: Duffy, Joe; 32500; 000-11-2222; True
Wrote: Bush, George; 50123; 001-01-0001; True
Wrote: Robinson, Jess; 99332; 321-21-4321; False
Wrote: Bob, Billy; 32332; 333-22-1111; True
Wrote: Simpson, Homer; 93812; 999-88-7777; False
Read: Duffy, Joe; 32500; 000-11-2222; True
Read: Bush, George; 50123; 001-01-0001; True
Read: Robinson, Jess; 99332; 321-21-4321; False
Read: Bob, Billy; 32332; 333-22-1111; True
Read: Simpson, Homer; 93812; 999-88-7777; False
3 4A 6F 65 5 44 75 66 66 79 F4 7E 0 0 B 30 30 30 2D 31 31 2D 32 32 32 32 1 6 47
65 6F 72 67 65 4 42 75 73 68 CB C3 0 0 B 30 30 31 2D 30 31 2D 30 30 30 31 1 4 4A
 65 73 73 8 52 6F 62 69 6E 73 6F 6E 4 84 1 0 B 33 32 31 2D 32 31 2D 34 33 32 31
0 5 42 69 6C 6C 79 3 42 6F 62 4C 7E 0 0 B 33 33 33 2D 32 32 2D 31 31 31 31 1 5 4
8 6F 6D 65 72 7 53 69 6D 70 73 6F 6E 74 6E 1 0 B 39 39 39 2D 38 38 2D 37 37 37 3
7 0

History

• 8^th May, 2009: Initial post