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
and the IList<TKey> interface with its properties and methods:
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:
public ICollection<K> Keys
{
get { return objectTable.Keys; }
}
public ICollection<V> Values
{
get { return objectTable.Values; }
}
and:
public List<K> OrderedKeys
{
get
{
List<K> retList = new List<K>();
foreach (KeyValuePair<K, V> kvp in objectList)
{
retList.Add(kvp.Key);
}
return retList;
}
}
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:
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;
}
}
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:
public K GetKey(int idx)
{
if (idx < 0 || idx >= Count)
{
throw new ArgumentOutOfRangeException("index");
}
return objectList[idx].Key;
}
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:
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;
}
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:
public bool ContainsKey(K key)
{
return objectTable.ContainsKey(key);
}
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:
public void Add(K key, V value)
{
objectTable.Add(key, value);
objectList.Add(new KeyValuePair<K, V>(key, value));
}
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:
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));
}
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:
public bool Remove(K key)
{
bool found=objectTable.Remove(key);
if (found)
{
objectList.RemoveAt(IndexOf(key));
}
return found;
}
public bool Remove(KeyValuePair<K, V> kvp)
{
return Remove(kvp.Key);
}
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:
IEnumerator IEnumerable.GetEnumerator()
{
return objectList.GetEnumerator();
}
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:
public bool IsReadOnly
{
get { return false; }
}
public int Count
{
get { return objectList.Count; }
}
public bool TryGetValue(K key, out V val)
{
return objectTable.TryGetValue(key, out val);
}
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.
