Click here to Skip to main content
Click here to Skip to main content

Generic Keyed List

, 27 Jan 2006
Rate this:
Please Sign up or sign in to vote.
A KeyedList using C# 2.0 Generics.

Introduction

A while ago, I wrote a KeyedList for C# 1.0 (or is it 1.1?). Recently I needed the KeyedList for a C# 2.0 project, and so it occurred to me to rewrite it, but this time using generics.

In brief, a keyed list is an ordered dictionary. Unlike the Dictionary<TKey, TValue> provided by .NET 2.0, which does not guarantee order, the KeyedList<TKey, TValue> is a dictionary that also implements ordinal indexing in addition to keyed indexing. This is useful when you are interested in indexing by ordinal value rather than key.

Implemented Interfaces

The KeyedList implements the IDictionary<TKey, TValue> interface and its properties and methods:

  • Item
  • Keys
  • Values
  • ContainsKey
  • Add
  • Remove
  • TryGetValue

and the IList<TKey> interface with its properties and methods:

  • Item
  • IndexOf
  • Insert
  • RemoveAt

Implementation

Internally, the KeyedList class maintains both a dictionary and a list:

private Dictionary<K, V> objectTable = new Dictionary<K, V>();
private List<KeyValuePair<K, V>> objectList = new List<KeyValuePair<K, V>>();

As per the MSDN documentation for Dictionary<TKey, TValue>: "The order of the keys in the Dictionary.KeyCollection is unspecified". A second collection, a List<KeyValuePair<T, V>>, is used to maintain the ordering of the key-value pairs. An important distinction is therefore made between:

/// <summary>
/// Get an unordered list of keys.
/// This collection refers back to the keys in the original Dictionary.
/// </summary>
public ICollection<K> Keys
{
  get { return objectTable.Keys; }
}

/// <summary>
/// Get an unordered list of values.
/// This collection refers back to the values in the original Dictionary.
/// </summary>
public ICollection<V> Values
{
  get { return objectTable.Values; }
}

and:

/// <summary>
/// Get the ordered list of keys.
/// This is a copy of the keys in the original Dictionary.
/// </summary>
public List<K> OrderedKeys
{
  get
  {
    List<K> retList = new List<K>();

    foreach (KeyValuePair<K, V> kvp in objectList)
    {
      retList.Add(kvp.Key);
    }

    return retList;
  }
}

/// <summary>
/// Get the ordered list of values.
/// This is a copy of the values in the original Dictionary.
/// </summary>
public List<V> OrderedValues
{
  get
  {
    List<V> retList = new List<V>();

    foreach (KeyValuePair<K, V> kvp in objectList)
    {
      retList.Add(kvp.Value);
    }

    return retList;
  }
}

The Values and Keys properties return a collection that is not a copy, so changes to the dictionary continue to be reflected in the key collection. However, this is not true for OrderedValues and OrderedKeys properties, as this is a local copy.

Indexers

Two indexers are implemented--ordinal and key:

/// <summary>
/// Get/Set the value at the specified index.
/// </summary>
/// <param name="idx">The index.</param>
/// <returns>The value.</returns>
public KeyValuePair<K, V> this[int idx]
{
  get
  {
    if (idx < 0 || idx >= Count)
    {
      throw new ArgumentOutOfRangeException("index");
    }

    return objectList[idx]; 
  }
  set
  {
    if (idx < 0 || idx >= Count)
    {
      throw new ArgumentOutOfRangeException("index");
    }

    objectList[idx] = value;
    objectTable[value.Key] = value.Value;
  }
}

/// <summary>
/// Get/Set the value associated with the specified key.
/// </summary>
/// <param name="key">The key.</param>
/// <returns>The associated value.</returns>
public virtual V this[K key]
{
  get { return objectTable[key]; }
  set
  {
    if (objectTable.ContainsKey(key))
    {
      objectTable[key] = value;
      objectList[IndexOf(key)] = new KeyValuePair<K, V>(key, value);
    }
    else
    {
      Add(key, value);
    }
  }
}

The index by key setter introduces a complexity--what if the key doesn't exist? In the dictionary, a key-value pair is created, but in the KeyedList, where does this entry get created in the ordered list? The behavior that I've chosen is to simply append the new key-value pair to the end of the list, however you may prefer a different implementation, perhaps even throwing an exception, so this method has been marked virtual.

Also note that, the ordinal indexer returns a KeyValuePair, whereas the key indexer returns the value. So it would be useful to also have methods that, given the ordinal index, simply returns the key or the value:

/// <summary>
/// Returns the key at the specified index.
/// </summary>
/// <param name="idx">The index.</param>
/// <returns>The key at the index.</returns>
public K GetKey(int idx)
{
  if (idx < 0 || idx >= Count)
  {
    throw new ArgumentOutOfRangeException("index");
  }

  return objectList[idx].Key;
}

/// <summary>
/// Returns the value at the specified index.
/// </summary>
/// <param name="idx">The index.</param>
/// <returns>The value at the index.</returns>
public V GetValue(int idx)
{
  if (idx < 0 || idx >= Count)
  {
    throw new ArgumentOutOfRangeException("index");
  }

  return objectList[idx].Value;
}

IndexOf

We also may want to acquire the index, given the key, but IList<KeyValuePair<K, V>> requires that IndexOf(KeyValuePair<K, V>>) be implemented. This results in a slightly odd method because, after all, the key is unique, so there can't be different values for the same key. This method simply calls the IndexOf(K key) method. For large collections, it probably would be a considerable performance improvement if the dictionary wrapped the index value in an internal "Value" class, so you could use the dictionary's hash lookup to acquire the index value. However, that's beyond the scope of this implementation, which is simply:

/// <summary>
/// Get the index of a particular key.
/// </summary>
/// <param name="key">The key to find the index of.</param>
/// <returns>The index of the key, or -1 if not found.</returns>
public int IndexOf(K key)
{
  int ret = -1;

  for (int i = 0; i < objectList.Count; i++)
  {
    if (objectList[i].Key.Equals(key))
    {
      ret = i;
      break;
    }
  }

  return ret;
}

/// <summary>
/// Given the key-value pair, find the index.
/// </summary>
/// <param name="kvp">The key-value pair.</param>
/// <returns>The index, or -1 if not found.</returns>
public int IndexOf(KeyValuePair<K, V> kvp)
{
  return IndexOf(kvp.Key);
}

Contains

We need to implement a Contains method for both the IDictionary and the IList interfaces (this theme is repeated for Add and Remove as well). Again, only the key is tested when the KeyValuePair<K, V> is passed:

/// <summary>
/// Test if the KeyedList contains the key.
/// </summary>
/// <param name="key">The key.</param>
/// <returns>True if the key is found.</returns>
public bool ContainsKey(K key)
{
  return objectTable.ContainsKey(key);
}

/// <summary>
/// Test if the KeyedList contains the key in the key-value pair.
/// </summary>
/// <param name="kvp">The key-value pair.</param>
/// <returns>True if the key is found.</returns>
public bool Contains(KeyValuePair<K, V> kvp)
{
  return objectTable.ContainsKey(kvp.Key);
}

Add

The Add methods add an entry to the dictionary and a key-value pair to the list:

/// <summary>
/// Adds a key-value pair to the KeyedList.
/// </summary>
/// <param name="key">The key.</param>
/// <param name="value">The associated value.</param>
public void Add(K key, V value)
{
  objectTable.Add(key, value);
  objectList.Add(new KeyValuePair<K, V>(key, value));
}

/// <summary>
/// Adds a key-value pair to the KeyedList.
/// </summary>
/// <param name="kvp">The KeyValuePair instance.</param>
public void Add(KeyValuePair<K, V> kvp)
{
  Add(kvp.Key, kvp.Value);
}

Insert

Insert is similar to add, except that it inserts the key and value at the specified location in the list:

/// <summary>
/// Insert the key-value at the specified index.
/// </summary>
/// <param name="idx">The zero-based insert point.</param>
/// <param name="key">The key.</param>
/// <param name="value">The value.</param>
public void Insert(int idx, K key, V value)
{
  if ( (idx < 0) || (idx > Count) )
  {
    throw new ArgumentOutOfRangeException("index");
  }

  objectTable.Add(key, value);
  objectList.Insert(idx, new KeyValuePair<K, V>(key, value));
}

/// <summary>
/// Insert the key-value pair at the specified index location.
/// </summary>
/// <param name="idx">The key.</param>
/// <param name="kvp">The value.</param>
public void Insert(int idx, KeyValuePair<K, V> kvp)
{
  if ( (idx < 0) || (idx > Count) )
  {
    throw new ArgumentOutOfRangeException("index");
  }

  objectTable.Add(kvp.Key, kvp.Value);
  objectList.Insert(idx, kvp);
}

Remove

Remove lets you remove an entry either by key, key-value pair, or index:

/// <summary>
/// Remove the entry.
/// </summary>
/// <param name="key">The key identifying the key-value pair.</param>
/// <returns>True if removed.</returns>
public bool Remove(K key)
{
  bool found=objectTable.Remove(key);

  if (found)
  {
    objectList.RemoveAt(IndexOf(key));
  }

  return found;
}

/// <summary>
/// Remove the key in the specified KeyValuePair instance. The Value
/// property is ignored.
/// </summary>
/// <param name="kvp">The key-value identifying the entry.</param>
/// <returns>True if removed.</returns>
public bool Remove(KeyValuePair<K, V> kvp)
{
  return Remove(kvp.Key);
}

/// <summary>
/// Remove the entry at the specified index.
/// </summary>
/// <param name="idx">The index to the entry to be removed.</param>
public void RemoveAt(int idx)
{
  if ( (idx < 0) || (idx >= Count) )
  {
    throw new ArgumentOutOfRangeException("index");
  }

  objectTable.Remove(objectList[idx].Key);
  objectList.RemoveAt(idx);
}

GetEnumerator

The interfaces require two GetEnumerator methods:

/// <summary>
/// Returns an ordered System.Collections KeyValuePair objects.
/// </summary>
IEnumerator IEnumerable.GetEnumerator()
{
  return objectList.GetEnumerator();
}

/// <summary>
/// Returns an ordered KeyValuePair enumerator.
/// </summary>
IEnumerator<KeyValuePair<K, V>> 
    IEnumerable<KeyValuePair<K, V>>.GetEnumerator()
{
  return objectList.GetEnumerator();
}

Note that this test calls the IDictionary<TKey, TValue> enumerator.

[Test]
public void EnumerationTest()
{
  int n = 0;

  foreach (KeyValuePair<string, int> kvp in k)
  {
    Assertion.Assert(kvp.Value == n, "Expected ordered list of values.");
    ++n;
  }
}

In fact, you have to specifically cast to get the non-generic enumerator.

Miscellaneous

A few other methods are implemented as well:

/// <summary>
/// Returns false.
/// </summary>
public bool IsReadOnly
{
  get { return false; }
}

/// <summary>
/// Returns the number of entries in the KeyedList.
/// </summary>
public int Count
{
  get { return objectList.Count; }
}

/// <summary>
/// Attempt to get the value, given the key, without throwing an exception 
/// if not found.
/// </summary>
/// <param name="key">The key indentifying the entry.</param>
/// <param name="val">The value, if found.</param>
/// <returns>True if found.</returns>
public bool TryGetValue(K key, out V val)
{
  return objectTable.TryGetValue(key, out val);
}

/// <summary>
/// Copy the entire key-value pairs to the KeyValuePair array, starting
/// at the specified index of the target array. The array is populated 
/// as an ordered list.
/// </summary>
/// <param name="kvpa">The KeyValuePair array.</param>
/// <param name="idx">The position to start the copy.</param>
public void CopyTo(KeyValuePair<K, V>[] kvpa, int idx)
{
  objectList.CopyTo(kvpa, idx);
}

Unit Tests

The download includes unit tests for each of the properties/methods in this class. Hopefully it has been tested sufficiently!

Conclusion

It's not often that one needs a KeyedList, but it is unfortunate that .NET 2.0 doesn't provide one. So hopefully this implementation will meet your needs.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Marc Clifton

United States United States
Marc is the creator of two open source projets, MyXaml, a declarative (XML) instantiation engine and the Advanced Unit Testing framework, and Interacx, a commercial n-tier RAD application suite.  Visit his website, www.marcclifton.com, where you will find many of his articles and his blog.
 
Marc lives in Philmont, NY.

Comments and Discussions

 
Question.NET 4.5 PinmemberGediminas Bukauskas2-Apr-13 7:08 
AnswerRe: .NET 4.5 PinprotectorMarc Clifton2-Apr-13 12:17 
QuestionMuch appreciated PinmemberAllan Gaunt4-Sep-12 1:04 
GeneralThanks - this has saved me hours PinmemberMember 395465026-Jan-09 1:35 
GeneralThanks Pinmemberfelipesabino18-Oct-07 3:56 
QuestionIs this serializable? Pinmembertwesterd3-Sep-07 13:44 
AnswerRe: Is this serializable? PinprotectorMarc Clifton3-Sep-07 14:58 
Generalim looking for a List accessing by key ... PinmemberE.T.3-Mar-07 6:46 
GeneralRe: im looking for a List accessing by key ... PinmemberE.T.3-Mar-07 7:33 
GeneralRe: im looking for a List accessing by key ... PinmemberCommonGenius2-May-07 7:49 
Questionisn't it what sortedList does ? PinmemberE.T.3-Mar-07 6:40 
AnswerRe: isn't it what sortedList does ? PinmemberCommonGenius2-May-07 7:43 
QuestionKeyedCollection PinmemberAndre Azevedo11-May-06 13:13 
AnswerRe: KeyedCollection PinmemberAlexander Turlov24-May-06 8:32 
GeneralRe: KeyedCollection PinprotectorMarc Clifton24-May-06 8:37 
As I replied to Andre:
 
Andre Azevedo wrote:
Can you use KeyedCollection instead?

 
In MSDN, regarding KeyedCollection:
 
Unlike dictionaries, an element of KeyedCollection is not a key/value pair; instead, the entire element is the value and the key is embedded within the value.
 
which, if that's the way you're working with the data, that's fine. But my KeyedList is generic but implements a key/value pair. A subtle but important difference depending on your needs.
 
Marc
 
Pensieve
Some people believe what the bible says. Literally. At least [with Wikipedia] you have the chance to correct the wiki -- Jörgen Sigvardsson
AnswerRe: KeyedCollection PinprotectorMarc Clifton24-May-06 8:37 
GeneralRe: KeyedCollection PinmemberAlexander Turlov24-May-06 16:41 
GeneralBug!?! Pinmemberhahnl5-May-06 22:10 
GeneralRe: Bug!?! PinmemberPaul P 2223-May-06 21:49 
GeneralRe: Bug!?! PinprotectorMarc Clifton24-May-06 8:42 
GeneralRe: Bug!?! PinprotectorMarc Clifton24-May-06 8:40 
GeneralVts.UnitTest PinmemberDoncp1-Apr-06 6:06 
QuestionWhat about KeyedCollection? Pinmemberekriel1-Feb-06 6:18 
GeneralSuggestion Pinmemberjmw28-Jan-06 5:27 
QuestionIndexer PinmemberXIUnin28-Jan-06 3:11 
AnswerRe: Indexer PinprotectorMarc Clifton28-Jan-06 11:56 
QuestionRe: Indexer PinmemberHarkos30-Jan-06 0:00 
AnswerRe: Indexer PinmemberRichard Deeming30-Jan-06 7:57 
GeneralRe: Indexer PinmemberHarkos31-Jan-06 1:18 
AnswerRe: Indexer PinmemberDrew Noakes5-Jun-07 3:52 
QuestionMemory? PinmemberMatthew Hazlett27-Jan-06 14:20 
AnswerRe: Memory? PinprotectorMarc Clifton27-Jan-06 15:44 
GeneralRe: Memory? PinmemberS. Senthil Kumar28-Jan-06 20:08 
GeneralRe: Memory? PinmemberHarkos29-Jan-06 23:58 
GeneralRe: Memory? PinmemberS. Senthil Kumar30-Jan-06 6:15 
GeneralRe: Memory? PinmemberHarkos31-Jan-06 1:29 
GeneralRe: Memory? PinmemberS. Senthil Kumar31-Jan-06 5:57 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140721.1 | Last Updated 27 Jan 2006
Article Copyright 2006 by Marc Clifton
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid