Introduction
This article describes the implementation of the framework's OrderedDictionary, its advantages and disadvantages, and shows how to create a generic collection which implements the IOrderedDictionary interface.
Ordered Dictionaries
An ordered dictionary is a collection class in which items can be manipulated by either their index or their key. System.Data.InternalDataCollectionBase, from which data collections such as DataTableCollection and DataColumnCollection are derived, is an example of an ordered dictionary. Items can be accessed either by their name or their index in the collection.
IOrderedDictionary
The .NET Framework 2.0 introduced a new interface for ordered dictionary implementations: System.Collections.IOrderedDictionary. Similar to the IList and IDictionary interfaces, the IOrderedDictionary interface defines a consistent contract for ordered dictionary implementations which ensures that items can be accessed, inserted, and removed by index or key.
OrderedDictionary
System.Collections.OrderedDictionary is the .NET framework's implementation of the IOrderedDictionary interface. It is implemented by storing elements in two separate internal structures: a Hashtable, which stores the key/value pairs like a normal dictionary, and an ArrayList, which stores DictionaryEntry structures containing the key/value pairs.
This implementation of an ordered dictionary is very good at lookup operations: the array allows O(1) lookups by index, and the hashtable allows O(1) lookups by key. However, the necessity of keeping the array synchronized with the hashtable means that insert/delete operations have the performance disadvantage of performing those operations on an array (O(n) at worst). There is also, of course, the extra memory requirement of storing both data structures. Because of these disadvantages, OrderedDictionary should only be used when insert/delete operations will be minimal and there is a need to efficiently access elements by index and/or key.
Oddly, although .NET 2.0 introduced generics and a number of generic collections were included in the framework, there is no generic implementation of the IOrderedDictionary interface. Fortunately, however, creating a generic ordered dictionary is not too difficult.
Implementing A Generic Ordered Dictionary
IOrderedDictionary<TKey,TValue>
IOrderedDictionary<TKey,TValue> is an interface which defines the contract necessary to implement a generic ordered dictionary. It implements the IOrderedDictionary and IDictionary<TKey,TValue> interfaces, and adds a few new members. There are strongly typed Add and Insert methods, and a strongly typed indexer (Item property). Note that the Add method and the indexer hide their base interface counterparts, since they only differ by return types; therefore, classes which implement this interface will have to explicitly implement at least one of each member.
OrderedDictionary<TKey,TValue>
OrderedDictionary<TKey,TValue> is an implementation of IOrderedDictionary<TKey,TValue> that uses the same implementation technique as OrderedDictionary. It stores its elements in a Dictionary<TKey,TValue> and a List<KeyValuePair<TKey,TValue>>. The implementation is fairly simple, and most of it is essentially equivalent to the framework's OrderedDictionary, adjusted to work in a strongly-typed environment. This means that OrderedDictionary<TKey,TValue> has the same memory and performance advantages and disadvantages as OrderedDictionary. The ConvertToKeyType and ConvertToValueType methods are the starting point for implementing the weakly-typed members of the non-generic interfaces which the class implements.
Implementation
Generally, manipulating the OrderedDictionary by index is faster than manipulating it by key; even if the algorithmic complexity is the same, the actual running time will be less when using an index. This is because every modification to an OrderedDictionary requires accessing both the list and the dictionary; and converting an index to its corresponding key is a O(1) operation (it's just a lookup in the list), but converting a key to its corresponding index is a O(n) operation, since it requires a linear search through the list to find the key. Put another way, the list is aware of the dictionary's identifier (the key), but the dictionary is not aware of the list's identifier (the index). Therefore, you should try to manipulate the ordered dictionary by index where possible. Note: in the following discussion, accessing the dictionary by key is assumed to be a O(1) operation, although in reality this is dependent on the implementation of the GetHashCode method of the key type.
Adding/Inserting
Inserting a new item into the OrderedDictionary is a O(n) operation. The key and value are inserted into the dictionary, and a KeyValuePair object which contains the key and value is inserted into the list at the appropriate point.
public int Add(TKey key, TValue value)
{
Dictionary.Add(key, value);
List.Add(new KeyValuePair<TKey,TValue>(key, value));
return Count - 1;
}
public void Insert(int index, TKey key, TValue value)
{
if(index > Count || index < 0)
throw new ArgumentOutOfRangeException("index");
Dictionary.Add(key, value);
List.Insert(index, new KeyValuePair<TKey, TValue>(key, value));
}
Accessing By Index/Key
Accessing a value in the OrderedDictionary is a O(1) operation. The value is retrieved from either the list (by index) or the dictionary (by key).
public TValue this[int index]
{
get
{
return List[index].Value;
}
}
public TValue this[TKey key]
{
get
{
return Dictionary[key];
}
}
Setting By Index
Setting the value of the OrderedDictionary by index replaces the value associated with the key that is currently at that index. This is a O(1) operation: the key at the index is retrieved, and then a new KeyValuePair instance is created and set at the index in the list, and the new value for the key is set in the dictionary.
public TValue this[int index]
{
set
{
if(index >= Count || index < 0)
throw new ArgumentOutOfRangeException("index",
"'index' must be non-negative and less than" +
" the size of the collection");
TKey key = List[index].Key;
List[index] = new KeyValuePair<TKey, TValue>(key, value);
Dictionary[key] = value;
}
}
Setting By Key
Setting the value of the OrderedDictionary by key replaces the value at the current index of the key. This is a O(n) operation: the index of the key is located, and then a new KeyValuePair instance is created and set at the index in the list, and the new value for the key is set in the dictionary.
public TValue this[TKey key]
{
set
{
if(Dictionary.ContainsKey(key))
{
Dictionary[key] = value;
List[IndexOfKey(key)] = new KeyValuePair<TKey, TValue>(key, value);
}
else
{
Add(key, value);
}
}
}
Removing By Index
Removing from the OrderedDictionary by index is a O(n) operation. The key at the index is retrieved, and then the item at the index in the list is removed, and the key is removed from the dictionary.
public void RemoveAt(int index)
{
if(index >= Count || index < 0)
throw new ArgumentOutOfRangeException("index",
"'index' must be non-negative and less than " +
"the size of the collection");
TKey key = List[index].Key;
List.RemoveAt(index);
Dictionary.Remove(key);
}
Removing By Key
Removing from the OrderedDictionary by index is a O(n) operation. The index of the key is located, and then the item at the index in the list is removed, and the key is removed from the dictionary.
public bool Remove(TKey key)
{
if(null == key)
throw new ArgumentNullException("key");
int index = IndexOfKey(key);
if(index >= 0)
{
if(Dictionary.Remove(key))
{
List.RemoveAt(index);
return true;
}
}
return false;
}
Conclusion
Although it does have some drawbacks, an ordered dictionary is a very versatile and user-friendly data structure, allowing operations to be performed either by index or by key. OrderedDictionary<TKey,TValue> provides a type-safe ordered dictionary implementation.
This class uses the same implementation technique employed by the framework's OrderedDictionary class. I have looked around for alternative implementation techniques, in .NET or in other languages, but so far I have not found any. If anyone is aware of any alternative implementation techniques, please let me know.
History
- 5/1/2007: re-published from here.
