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

OrderedDictionary<T>: A generic implementation of IOrderedDictionary

, 1 May 2007
Rate this:
Please Sign up or sign in to vote.
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.

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.

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

Share

About the Author

Overboard Software
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

 
Bugbug in List property getter? Pinmemberbertyhell28-Nov-13 1:28 
SuggestionNo Need to Store the Value Twice PinmemberJehu Galeahsa17-Dec-12 6:39 
GeneralThanks + some limitations PinmemberStefan Holtmeier1-Jul-10 2:47 
GeneralThanks and some comments on your works PinmemberCrescentMoon10-Mar-10 20:03 
Thanks for your work! Such nice class.
 
mrbest666 has corrected, your class throws StackOverFlowExc. Correct it easily by replacing List by _list in List method of OrderedDictionary class. CommonGenius should update for other developers.
 
And the other problem, I have developed in NETCF3.5 and IOrderdDictionary is not supported. Any suggestion?
 
Thanks in advanced.
GeneralKeyedCollection alternative PinmemberCésar Roberto de Souza6-Aug-09 3:16 
GeneralStack overflow bug Pinmembermrbest66610-Aug-07 5:11 
GeneralRe: Stack overflow bug Pinmemberpaparascal6-Oct-08 14:00 
GeneralRe: Stack overflow bug Pinmemberswoop3511-Feb-12 19:02 
GeneralKeys and Values PinmemberAndreas Hardt31-Jul-07 20:15 
GeneralRe: Keys and Values PinmemberCommonGenius1-Aug-07 3:49 
GeneralGreat but PinmemberStefan Prodan4-May-07 2:34 
GeneralRe: Great but PinmemberCommonGenius4-May-07 7:23 
Generalaka a KeyedList PinprotectorMarc Clifton2-May-07 2:34 
Generalsuggestions PinmemberBillWoodruff1-May-07 23:14 
GeneralRe: suggestions PinmemberCommonGenius2-May-07 7:32 
GeneralGood work! PinmemberTeyko1-May-07 20:16 

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
Web02 | 2.8.140821.2 | Last Updated 2 May 2007
Article Copyright 2007 by Overboard Software
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid