Introduction

This sample demonstrates how to derive a generic class called KeyedList<TKey, TValue> from the List<T> generic collection class and add new functionality to the derived class. 

Building the Sample 

This code sample uses a subset of the "Northwind Traders" mdb for test data located in the KeyedList\App_Data folder. Relative paths are set up in the source code.

Description

The main goal for this sample is to demonstrate how to create and use a custom generic class that is similar in concept to a JavaScript object literal collection. This type of collection is very useful for working with SQL query results. This is demonstrated with the provided test code that uses a Microsoft Access database for source data.

Besides being derived from the List<T> class, the KeyedList class also implements the IXmlSerializable interface.

The code snippet below shows the class declaration with constructor calls to the base class constructors.

C#
Edit|Remove
  /// <summary> 
  /// Holds a List(T) of KeValuePair objects. 
  /// Overrides Sort() to Sort with a Compare function that sorts on either 
  /// TKey of Int32, Int64, or String type. 
  /// Implements IXmlSerializable for customized serialization 
  /// </summary> 
  /// <typeparam name="TKey"></typeparam> 
  /// <typeparam name="TValue"></typeparam> 
  [XmlRoot("KeyedList")] 
  public class KeyedList<TKey, TValue> : List<KeyValuePair<TKey, TValue>>, IXmlSerializable 
  { 
    /// <summary> 
    /// Default Custructor with initial capacity of 100 
    /// </summary> 
    public KeyedList() : base() { } 
 
    /// <summary> 
    /// Cunstuctor to receive initial size as parameter 
    /// </summary> 
    /// <param name="size"></param> 
    public KeyedList(int size) : base(size) { } 
 
...

This class contains a few boolean properties to control optional features. These are:

The Add method is overloaded with an additional method to allow for adding TKey and TValues objects directly so there is no need to create a new KeyValuePair first. There are also TryAdd and AddSorted methods that work in a similar pattern. Note that AddSorted uses the List<T> Insert method to insert the new KVP at the sorted position returned by the private iKeyIndex method. AddSorted also sorts the list if it is not already sorted. Otherwise it would make no sense to add an item to a "sorted" position. Here is the code that implements the Add Method.

C#
Edit|Remove
    /// <summary> 
    /// Add a KeyValuePair object to the end of the list 
    /// </summary> 
    /// <param name="key"></param> 
    /// <param name="value"></param> 
    public void Add(TKey key, TValue value) 
    { 
      if (_AllowDuplicateKeys) 
      { 
        this.Add(new KeyValuePair<TKey, TValue>(key, value)); 
        _IsSorted = false; 
      } 
      else 
      { 
        if (iKeyIndex(key) > -1) 
        { 
          throw new Exception("Duplicate key is not allowed."); 
        } 
        else 
        { 
          this.Add(new KeyValuePair<TKey, TValue>(key, value)); 
          _IsSorted = false; 
        } 
      } 
    }

I replace the Sort() for List<T> with a method that runs the Sort(Comparison(Of T)) method overload. This way the most useful key types (String, Int32, and Int64) can be sorted with the default comparer delegate.

Update: I have added a specialized string key sort that sorts on string keys much quicker than with the built-in quick sort. The faster method operates on an array of KeyValuePairs and gains speed by optimizing how strings are partitioned for sorting.

C#
Edit|Remove
    /// <summary> 
    /// Use for default sorting on int or string keys 
    /// </summary> 
    public new void Sort() 
    { 
      if (typeof(TKey) == typeof(String)) 
      { 
        KeyValuePair<TKey, TValue>[] kvpArray = this.ToArray(); 
        this.Clear(); 
        this.Sort(kvpArray); //sort String key type 
        this.AddRange(kvpArray); 
        if (!this.SortAscd) 
        { 
          this.Reverse(); 
        } 
      } 
      else 
      { 
        this.Sort(CompareKey); 
      } 
      //this.Sort(CompareKey); 
      _IsSorted = true; 
    } 
 
//... overloaded Sort method ... 
    /// <summary> 
    /// Sort an array of KeyValuePair structs 
    /// </summary> 
    /// <param name="sList"></param> 
    public void Sort(KeyValuePair<TKey, TValue>[] sList) 
    { 
      InPlaceSort(sList, 00, sList.Length); 
    } 
 

Here is my generic CompareKey implementation. Note that generic types have to be assigned to object type variables before they can be cast into fixed types. I use "is <type>" to determine the type of the generic parameter.

C#
Edit|Remove
    /// <summary> 
    /// Compare two KeyValuePair objects by TKey. 
    /// Supports Int32, Int64 or String types of TKey 
    /// </summary> 
    /// <param name="kv1"></param> 
    /// <param name="kv2"></param> 
    /// <returns></returns> 
    public int CompareKey(KeyValuePair<TKey, TValue> kv1, KeyValuePair<TKey, TValue> kv2) 
    { 
      object o1 = kv1.Key; 
      object o2 = kv2.Key; 
      int iCompareResult = 0; 
      if (kv1.Key is String) 
      { 
        iCompareResult = String.Compare(o1 as string, o2 as stringfalse); 
      } 
      else if (kv1.Key is Int32) 
      { 
        if ((Int32)o1 == (Int32)o2) 
          iCompareResult = 0; 
        else if ((Int32)o1 > (Int32)o2) 
          iCompareResult = 1; 
        else 
          iCompareResult = -1; 
      } 
      else if (kv1.Key is Int64) 
      { 
        if ((Int64)o1 == (Int64)o2) 
          iCompareResult = 0; 
        else if ((Int64)o1 > (Int64)o2) 
          iCompareResult = 1; 
        else 
          iCompareResult = -1; 
      } 
      else 
      { 
        throw new Exception("Sort key type is not supported"); 
      } 
      if (!this.SortAscd) { iCompareResult = -iCompareResult; } 
      return iCompareResult; 
    }

I implemented my own BinarySearch method overload to return the index position of a given key in the KeyedList object. It uses  a private CompareKey method that is implemented in a similar pattern as the public CompareKey method delegate that is used for sorting.

C#
Edit|Remove
    /// <summary> 
    /// Recursive method to find position of TKey object within list of KeyValuePairs 
    /// </summary> 
    /// <param name="key"></param> 
    /// <param name="iMin"></param> 
    /// <param name="iMax"></param> 
    /// <returns>index if found, else -1</returns> 
    public int BinarySearch(TKey key, int iMin, int iMax) 
    { 
      if (iMax < iMin) { return -1; } //no items found 
 
      int iMid = (iMin+iMax)/2; 
      TKey LKey = this[iMid].Key; 
      if (CompareKey(LKey, key) > 0) 
      { //key is in lower subset 
        return BinarySearch(key, iMin, iMid - 1); 
      } 
      else if (CompareKey(LKey, key) < 0) 
      { //key is in upper subset 
        return BinarySearch(key, iMid + 1, iMax); 
      } 
      return iMid; //match found at iMid index 
    } 

I implemented a GetValuesForKey method to return a possible array of values for a given key when duplicate keys are allowed. Here is the snippet for this case. Note how easy it is to return a TValue type array from a generic List<TValue> type.

C#
Edit|Remove
        List<TValue> Lv = new List<TValue>(); 
        int len = this.Count; 
        for (int i = 0; i < len; ++i) 
        { 
          if (key.Equals(this[i].Key)) { 
            Lv.Add(this[i].Value); 
          } 
        } 
        return Lv.ToArray(); 

I also implement an indexer that both sets and returns value(s) by index. Only a single value can be returned by the indexer so AllowDuplicateKeys must be false for the get operation. Note that default(TValue) is used to return null or 0 if key is not found. Of note in the setter is that KeyValuePair is immutable, so I just assign a new KVP to the list index of the matched key.

C#
Edit|Remove
    /// <summary> 
    /// Key based indexer that implements a getter and a setter  
    /// for accessing or modifying values based on key. 
    /// set modifies value(s) when match or adds new kvp when no match is found. 
    /// </summary> 
    /// <param name="key"></param> 
    /// <returns>TValue result</returns> 
    public TValue this[TKey key] 
    { 
      get 
      { 
        if (!_AllowDuplicateKeys) 
        { 
          TValue[] tva = GetValuesForKey(key); 
          if (tva.Length == 1) { return tva[0]; } 
          return default(TValue); //return a legal "uninitialized" value for TValue type 
        } 
        throw new Exception("Cannot use get indexer for lists that allow Duplicate Keys"); 
      } 
      set 
      { 
        if (!_AllowDuplicateKeys) 
        { 
          int i = iKeyIndex(key); 
          if (i > -1) 
          { 
            this[i] = new KeyValuePair<TKey, TValue>(key, value); 
          } 
          else 
          { //add new key-value pair to list 
            this.Add(key, value); 
            _IsSorted = false; 
          } 
        } 
        else 
        { //change all values matching key 
          int len = this.Count; 
          int i = 0; 
          for (; i < len; ++i) 
          { 
            if (key.Equals(this[i].Key)) 
            { 
              this[i] = new KeyValuePair<TKey, TValue>(key, value); 
            } 
          } 
          if (i == len) 
          { //add new key-value pair to list 
            this.Add(key, value); 
            _IsSorted = false; 
          } 
        } 
      } 
    } 

The last public methods I implement are the ReadXML and WriteXML methods for the IXmlSerializable interface. Note how valueSerializer uses the Serialize method overload to eliminate the default namespace stuff when you serialize the value class. Here is the code snippet for WriteXML.

C#
Edit|Remove
    public void WriteXml(System.Xml.XmlWriter writer) 
    { 
      XmlSerializerNamespaces xmlnsOverride = new XmlSerializerNamespaces(); 
      xmlnsOverride.Add(""""); //save time by eliminating  default class namespace 
      XmlSerializer keySerializer = new XmlSerializer(typeof(TKey)); 
      XmlSerializer valueSerializer = new XmlSerializer(typeof(TValue)); 
      foreach (KeyValuePair<TKey, TValue> kvp in this) 
      { 
        writer.WriteStartElement("item"); 
        writer.WriteStartElement("key"); 
        keySerializer.Serialize(writer, kvp.Key); 
        writer.WriteEndElement(); 
        writer.WriteStartElement("value"); 
        valueSerializer.Serialize(writer, kvp.Value, xmlnsOverride); 
        writer.WriteEndElement(); 
        writer.WriteEndElement(); 
      } 
    } 

See DeserializeTest\Products.xml in the downloaded sample for an example of a serialized xml file.

Source Code Files

More Information

For more information on Generic Collections in .NET, see http://msdn.microsoft.com/en-us/library/bb762916(v=vs.90).aspx

Reference to fast StringSort (multikey quicksort) methods:

http://www.codeproject.com/Articles/146086/Fast-String-Sort-in-C-and-F