Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C#
Article

OrderedDictionary<T>: A generic implementation of IOrderedDictionary

Rate me:
Please Sign up or sign in to vote.
4.96/5 (24 votes)
1 May 20075 min read 138.2K   2.5K   45   20
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.

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.

C#
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).

C#
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.

C#
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.

C#
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.

C#
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.

C#
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.

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


Written By
Software Developer (Senior)
United States United States
David Nelson has been programming in various languages for 17 years, and has been programming in .NET (C# and VB.NET) since 2003.
He is a MCTS in .NET 2.0 Web Applications, and is a moderator on the MSDN Forums (http://forums.microsoft.com/msdn).

Comments and Discussions

 
QuestionIf you need sorting, but don't need to access by index, SortedDictionary TKey, TValue is an alternative Pin
ToolmakerSteve29-Jan-18 9:11
ToolmakerSteve29-Jan-18 9:11 
QuestionLicense terms? Pin
Adam Myers1-Apr-15 10:37
Adam Myers1-Apr-15 10:37 
Bugbug in List property getter? Pin
bertyhell28-Nov-13 1:28
bertyhell28-Nov-13 1:28 
GeneralRe: bug in List property getter? Pin
Member 1134115729-Dec-14 21:30
Member 1134115729-Dec-14 21:30 
PraiseRe: bug in List property getter? Pin
stixoffire17-Oct-18 0:31
stixoffire17-Oct-18 0:31 
SuggestionNo Need to Store the Value Twice Pin
Travis W Parks17-Dec-12 6:39
Travis W Parks17-Dec-12 6:39 
GeneralThanks + some limitations Pin
Stefan Holtmeier1-Jul-10 2:47
Stefan Holtmeier1-Jul-10 2:47 
GeneralThanks and some comments on your works Pin
CrescentMoon10-Mar-10 20:03
CrescentMoon10-Mar-10 20:03 
GeneralKeyedCollection alternative Pin
César de Souza6-Aug-09 3:16
professionalCésar de Souza6-Aug-09 3:16 
GeneralStack overflow bug Pin
mrbest66610-Aug-07 5:11
mrbest66610-Aug-07 5:11 
GeneralRe: Stack overflow bug Pin
paparascal6-Oct-08 14:00
paparascal6-Oct-08 14:00 
GeneralRe: Stack overflow bug Pin
swoop3511-Feb-12 19:02
swoop3511-Feb-12 19:02 
GeneralKeys and Values Pin
Andreas Hardt31-Jul-07 20:15
Andreas Hardt31-Jul-07 20:15 
GeneralRe: Keys and Values Pin
Overboard Software1-Aug-07 3:49
Overboard Software1-Aug-07 3:49 
GeneralGreat but Pin
Stefan Prodan4-May-07 2:34
Stefan Prodan4-May-07 2:34 
GeneralRe: Great but Pin
Overboard Software4-May-07 7:23
Overboard Software4-May-07 7:23 
Generalaka a KeyedList Pin
Marc Clifton2-May-07 2:34
mvaMarc Clifton2-May-07 2:34 
Generalsuggestions Pin
BillWoodruff1-May-07 23:14
professionalBillWoodruff1-May-07 23:14 
GeneralRe: suggestions Pin
Overboard Software2-May-07 7:32
Overboard Software2-May-07 7:32 
GeneralGood work! Pin
Teyko1-May-07 20:16
Teyko1-May-07 20:16 

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

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