Collections and Generics

Lesson 1: Collections

Name	Description
ArrayList	Resizeable index based collection
SortedList	Sorted collection of name / value pairs
Queue	FIFO collection
Stack	LIFO collection
Hashtable	Name / value collection that allows retrieval by name or index
BitArray	Compact collection of boolean values
StringCollection	Resizeable collection of strings
StringDictionary	Name / value pairs of strings, retrieval by name or value
ListDictionary	Stores small lists of objects
HybridDictionary	Uses ListDictionary when number of items in collection is small and migrates to Hashtable for large collections
NamedValueCollection	Name / Value pairs of strings that allow retrieval by name or index

Adding / removing items

Add

and

AddRange

, former for single object latter for collection. Can add objects that exist as variables or are created inline to the

Add

method. Even value types (e.g. Number 50) can be stored in collections, but must be wrapped in object reference (boxing). The

AddRange

method adds range of items, usually from array or another collection, from object that supports

ICollection

interface.

Add

and

AddRange

methods add to end of collection.

Insert

and

InsertRange

place at specific location in collection.

[]

Insert

as it sets the item at the specified location by overwriting the old object at that position.

Remove

,

RemoveAt

and

RemoveRange

. The Remove method deletes a specific object, e.g.

coll.Add(“Hello”);

coll.Remove(“Hello”);

Remove

method does not indicate if removal was successful.

removes item at specified index, whilst

RemoveRange

removes objects as a range of indexes.

will empty a collection of all its items.

will return the index of a specific object

will test if a particular object exists in a collection.

Iteration

Supports numeric indexer allowing items to be accessed in order.

IEnumerable

interface that provides

GetEnumerator

to access the

IEnumerator

interface for the enumerator object of the collection. The IEnumerator interface provides simple mechanism for iterating in forwards direction, supports

Current

property (gets current item in collection being enumerated),

MoveNext

methods which moves to next item in collection (return value indicates if end of collection reached) and

Reset

method that moves enumerator to before the first item in collection (allowing

MoveNext

to get the first item in collection), e.g.

IEnumerator enum = coll.GetEnumerator();

while (enumerator.MoveNext())

{

Console.WriteLine(enumerator.Current);

}

foreach

construct...

foreach(object item in coll)

{

Console.Writeline(item);

}

foreach

construct, e.g.

foreach(string item in coll)

. Note if any non strings encountered then the framework would throw a casting exception.

Consistent interfaces

provides common way to iterate over collection.

ICollection

(which derives from

IEnumerable

) that provides common way to access and copy collection.

Supported properties:

• Count
  –
  number items in collection

• IsSynchronized
  –
  indicates in collection is thread safe

• SyncRoot
  –
  provide object that synchronizes collection

Supported methods:

• CopyTo
  –
  copies contents of collection to array

IList

(that derives from

ICollection

).

Supported properties:

• IsFixedSize – can collection be resized

• IsReadOnly – can collection be changed

• Item – gets / sets item at specific index in collection

Supported methods:

• Add

• Clear

• Contains

• IndexOf

• Insert

• Remove

• RemoveAt

Sorting

ArrayList supports Sort method that works by using Comparer class. The Compare class is a default implementation of IComparer. The Sort method also allows caller to specify their own IComparer object which performs custom comparisons (e.g. Case sensitive compare).

Writing own comparer is straightforward. Only have to implement Compare method of Icomparer, e.g.

public class DescendingComparer : Icomparer

{

CaseInsensitiveComparer _comparer = new CaseInsensitiveComparer();

public int Compare(object x, object y)

{

return _comparer.Compare(y,x);

}

}

Lesson 2: Sequential Lists

ArrayList

, consider

Queue

or

Stack

.

Queues

FIFO handling of objects.

Interface supports putting items into queue and pulling them out.

In ArrayList accessing and removing items from collection were different operations, in queue they are combined into Dequeue method.

Use Enqueue to add items to queue.

Permits addition of duplicate items and null values – can't use result of Dequeue or Peek to determine if queue empty, instead check Count property.

Stacks

LIFO handling of objects.

Interface supports pushing items onto stack and popping them off.

Similar to queue, but instead of enqueueing and dequeuing objects are being pushed and popped.

Use Push to add items.

As with queue can not rely on result of Pop or Peek, instead check Count property.

Lesson 3: Dictionaries

Usage

Store lists of key / value pairs.

Most basic form is Hashtable.

Dictionaries always require tow pieces of information for an add operation – a key and a value, e.g.

sbishop@contoso.com

”

, “Bishop, Scott”);

or

sbishop@contoso.com

”

] = “Bishop, Scott”;

To retrieve item call indexer with key required, e.g.

sbishop@contoso.com

”

]);

Dictionaries designed for looking up key / value pairs – thus iterating is more complicated. Each element in dictionary is a DictionaryEntry object which is a container for a Key and Value pair. This to iterate over values in a dictionary perform the following:

foreach(DictionaryEntry entry in emailLookup)

{

Console.WriteLine(entry.Value);

}

IDictionary

interface (derived form

ICollection

) that provides, amongst others, the

Keys

property that gets an

ICollection

of the keys in the collection and

Values

that provides an

ICollection

of the values in the collection.

somewhat like

IList

, but does not provide access by index, only key. Supports two methods to test for existence of key (

ContainsKey

) or value (

ContainsValue

).

Equality

Hashtable uses integer value (a hash) to aid in key storage. Every object in framework derives from Object and so supports GetHashCode method. To test for equality the Hashtable checks that hash value of the objects presented. Hashtable only supports unique hashes of values- not unique values. Consequently the following code will only store one item (i.e. the second entry overwrites the first as the hash of “First” is the same.

duplicates[“First”] = “1st”;

duplicates[“First”] = “the first”;

The Hashtable does not rely on the hash value alone for equality tests. If it finds two objects with the same hash it will go on to test that the two objects are equal (by calling the Equals method implemented by Object). If these two tests pass then the keys are identical.

May need to override the implementations of GetHashCode and Equals to get desired behaviour – e.g. Basing generation of hash on a user defined name, etc.

IEqualityComparer interface

Provides equality test outside of class, e.g. Want to store string keys in Hashtable, but ignore case. Changing string class to be case insensitive would be painful, therefore use external class to calculate equality. Hashtable class can accept instance of IEqualityComparer as argument.

Supports two methods: GetHashCode and Equals.

public class InsensitiveComparer : IEqualityComparer

{

CaseInsensitiveComparer _comparer = new CaseInsensitiveComparer();

public int GetHashCode(object obj)

{

return obj.ToString.ToLowerInvariant().GetHashCode();

}

public new bool Equals(object x, object y)

{

if (_comparer.Compare(x,y) == 0) return true;

return false;

}

}

SortedList

A dictionary class that shares some behaviour with list. Can access items within SortedList in order, e.g.

sort[“first”] = “1st”;

sort[“second”] = “2nd”;

sort[“third”] = “3rd”;

sort[“fourth”] = “4th”;

foreach(DictionaryEntry entry in sort)

{

Console.WriteLine(“{0} {1}”, entry.Key, entry.Value);

}

generates...

st

th

nd

third 3rd

i.e. the list is sorted by the key

SortedList supports additional methods that allow key and value access by index number, e.g. GetByIndex, IndexOfKey and IndexOfValue.

Specialised Dictionaries

ListDictionary

Hashtable is efficient, but requires overhead and so is not good for small collections (less than 10 items). ListDictionary has same interface as Hashtable, but is implemented internally as an array.

HybridDictionary

Using ListDictionary for larger collections is not good. The HybridDictionary is implemented as a ListDictionary until the list becomes too large in which case it converts itself to a Hashtable.

OrderedDictionary

Item

property that supports access by index and

Insert

and

RemoveAt

methods that allow key / value pairs at specified indexes to be added / removed.

Lesson 4: Specialized Collections

Working With Bits

Two classes simplify bit operations – BitArray and BitVector32.

BitArray

Resizeable collection. When create must specify it size. This can be changed later via the Length property. Does not support Add or Remove methods – missing because each entry can only be true or false, so idea of adding / removing does not really apply. Once initialised collection of boolean values all set to false. Power of BitArray resides in ability to perform boolean operations on two BitArrays of same size, e.g.

BitArray bits = new BitArray(3);

bits[1] = true;

BitArray moreBits = new BitArray(3);

moreBits[0] = true;

BitArray xorBits = bits.Xor(moreBits);

BitVector32

Data

property.

CreateMask

method. Calling without any parameters creates mask for first bit in structure, calling again with integer value (representing previous mask created) will provide a mask for the next bit, e.g.

int firstBit = BitVectore32.CreateMask();

int secondBit = BitVector32.CreateMask(firstBit);

int thirdBit = BitVector32.CreateMask(thirdBit);

BitVector32 vector = new BitVector32(0); // Init to all false

vector[firstBit] = true;

vector[thirdBit] = true;

BitVector32

allows sections to be created within structure to store numbers up to certain values, e.g. To store maximum value of 10, maximum value of 50 and maximum value of 500 use the following:

BitVector32.Section firstSection = BitVector32.CreateSection(10);

BitVector32.Section secondSection = BitVector32.CreateSection(50, firstSection);

BitVector32.Section thirdSection = BitVector32.CreateSection(500, secondSection);

CreeateMask

the

CreateSection

uses the last section to determine where to pack the new number. Can gain access using indexer as follows:

packedBits[firstSection] = 10;

packedBits[thirdtSection] = 192;

Data

property to gain access to underlying number that contains the three packed numbers.

Collecting Strings

StringCollection

Dynamically sized collection that only stores strings. Working with it is virtually identical to ArrayList. Adding a non-string generates a compilation error. When retrieving a value the code is working with strings (not objects) – reduces the number of casts required.

StringDictionary

Strongly typed dictionary. Use like Hashtable, except both key and value must be string. Keys are case-insensitive, i.e. “Four” and “four” are the same.

Case-insensitive Collections

Previously case insensitive collections were produced by using the IComparer and IEqualityComparer interfaces. This is a common requirement and so the CollectionsUtil class provides static methods to create case insensitive Hashtables and SortedLists.

Culture-Invariant Collections

Default collection behaviour is to use current threads culture. Sometimes need to do comparisons without regard to current culture, e.g. Web applications or applications that store information across cultures. Cannot be created via CollectionsUtil class, instead specify collection with a StringComparer using the comparison rules of the invariant culture, e.g.

Hashtable hash = new Hashtable(StringComparer.InvariantCulture);

NameValueCollection

Similar to StringDictionary, but allows multiple values per key and retrieval by index as well as key. To retrieve all values for a key use the GetValues method, e.g.

NamsValueCollection nv = new NameValueCollection();

nv.Add(“key”, “value 1”);

nv.Add(“key”, “value 2”);

foreach (string s in nv.GetValues(“key”))

Console.WriteLine(s);

Note, adding values via the indexer will cause them to be overwritten, i.e. The following code will only have 1 value (“first”) in nv:

nv[“First”] = “1st”;

nv[“First”] = “first”;

Can access values by index, if more than one value is associated with an index then they are retuned as a comma-delimited list, e,.g.

nv.Add(“First”, “1st”);

nv.Add(“Second”, “2nd”);

nv.Add(“Second, “not first”);

for(int x=0; x < nv.Count; x++) Console.WriteLine(nv[x]);

generates...

Lesson 5: Generic Collections

Programming is about solving problems – often the same solution is common to lots of situations, e.g. The need to collect ordered list of items. .NET offers ArrayList to solve this problem as it stores lists of objects, but this introduces problems. For example can store list of integers in ArrayList. Consumer of ArrayList assumes only integers are present in the list – but there is nothing to stop non-integers being placed into the ArrayList. When the consumer code casts the object from the ArrayList to an integer a run-time error will occur. Could write wrapper class around ArrayList that only accepts integer values, but this is a lot of work – especially when need to implement similar class for other data types.

Generic types are types that take other type names to define them. For example instead of creating collection strongly typed to a specific type (as in the example before), can write a collection that can use any type, e.g.

public class MyList<T> : ICollection, IEnumerable

{

private ArrayList _innerList = new ArrayList();

public void Add(T val)

{

_innerList.Add(val);

}

public T this[int index]

{

get { return (T)_innerList[index];}

}

T

. Every place that would refer to an integer now refers to

T

. Instantiate as follows...

MyList<int> myIntList = new MyList<int>;

MyList<string> myStringList = new MyList<string>;

Generics used in many places within framework, but most frequently see in collection classes.

Generic classes exist for most of the non-generic collections present in .NET 1.0

Type	Generic Type
ArrayList	List<>
Queue	Queue<>
Stack	Stack<>
Hashtable	Dictionary<>
SortedList	SortedList<>
ListDictionary	Dictionary<>
HybridDictionary<>	Dictionary<>
OrderedDictionary	Dictionary<>
SortedDictionary	SortedDictionary<>
NameValueCollection	Dictionary<>
DictionaryEntry	KeyValuePair<>
StringCollection	List<String>
StringDictionary	Dictionary<String>
N/A	LinkedList<>

Generic List

Simple, type safe ordered list of objects

Use Add to add items to list, items must be same type as that specified in the generic type parameter of the list.

Can use indexer to access list items

Can use foreach syntax to iterate over list contents.

The Sort method supports a generic delegate. A generic delegate uses generic parameters to define the calling convention of the delegate. For example the generic Comparison delegate for the Sort method is defined as:

public delegate int Comparison<T>(T x, T y);

To sort list in reverse order could write entire Comparer class, or just a method that matches the generic delegate...

static int ReverseIntComparison(int x, int y){ return y – x;}

Note the method is not generic, but it matches the generic Comparison delegate – the List in this example is composed of integers so the Comparison must use integers. To invoke the sort issue the following command...

intList.Sort(ReverseIntComparison);

Generic Queue and Stack

When adding items (via Enqueue or Push) the type of the item must match the type specified in the generic type parameter.

Items retrieved (via Dequeue or Pop) will be of the type specified in the generic type parameter.

Generic Dictionary

Closely resembles Hashtable, ListDictionary and HybridDictionary.

Stores key / value pair in a collection – need to specify two generic type parameters when creating an instance of the Dictionary class – one for the key, the other the value.

Can use indexer syntax to access the entries, but types used must match the generic type parameters passed to the constructor of the dictionary.

When retrieving entries they are presented as a KeyValuePair, not a DictionaryEntry as in the non-generic Dictionary.

The KeyValuePair class takes two types (like the Dictionary) – one for the key and the other the value. Ordinarily instances of this type are not created directly, instead they are returned from the generic dictionary class, e.g. when iterating

foreach(KeyValuePair<int, string> entry in dict)

{

Console.WriteLine(“{0} = {1}”, entry.Key, entry.Value);

}

Generic SortedList and SortedDictioanry

Similar to generic dictionary except items sorted by the key of the collection.

Generic LinkedList

A LinkedList is a set of items that are linked to each other. From each item can navigate to the next or previous item without having to access the collection itself. Very useful when passing objects around that must known about their siblings. Important properties include:

• Count
  –
  number of nodes in LinkedList

• First
  –
  first node in LinkedList

• Last
  –
  last node in LinkedList

Important methods include:

• AddAfter
  –
  add node after existing node in list

• AddBefore
  –
  add node before existing node in list

• AddFirst
  –
  add node at beginning of list

• AddLast
  –
  add node at end of list

• Find
  –
  find first node containing specified value

• FindLast
  –
  find last node containing specified value

• Remove
  –
  remove first node containing specified value from list

• RemoveFirst
  –
  remove first node from list

• RemoveLast
  –
  remove last node from list

LinkedList contains collection of LinkedListNode objects. When working with list primarily getting and walking down the LinkedListNodes. Important properties include:

• List
  –
  get the LinkedList the node belongs to

• Next
  –
  the next node in the LinkedList

• Previous
  –
  the previous node in the LinkedList

• Value
  –
  the value of the node

The LinkedList enumerator does not use LinkedListNode objects – unlike the behaviour of the generic Dictionary class (which returns a KeyValuePair object). The difference is because the LinkedListNode object can be used to walk the list of items, but onlu one piece of data is held in each node. Therefore there is no need to return the nodes during enumeration - only their values.

Generic Collection Class Structure

The generic collections work in similar ways in many areas. These common areas include the use of generic collection interfaces, enumerators and comparisons.

Interfaces

Besides implementing the standard IEnumerable, ICollection, IList, interafces etc., the generic classes implement generic variations that provide type safe interface methods, e.g.

IList theList = (IList)) stringList;

object firstItem = theList[0];

Ilist<string> typeSafeList = (Ilist<string> stringList;

String firstString = typeSafeList[0];

Enumerators

To facilitate iteration each collection supports generic nested Enumerator structure, e.g.

List<string>.Enumerator e = stringList.GetEnumerator();

while (e.MoveNext()) { string s = e.Current; }

Comparisons

In cases where need to write own implementations of the IComparer and IEqulaityComparer there are generic base classes that do much of the required work. Implement any abstract methods and override default behaviour as appropriate, e.g.:

class MyComparer<T> : Comparere<T>

{

public override int Compare(T x, T y)

{

return x.GetHashCode() - y.GetHashCode();

}

}