Click here to Skip to main content
15,868,087 members
Articles / DevOps
Tip/Trick

A Generic OrderedDictionary in C#

Rate me:
Please Sign up or sign in to vote.
4.96/5 (9 votes)
20 Nov 2019CPOL2 min read 26.8K   173   10   33
A fully generic ordered dictionary class in C#

Ordered Dictionary Demo Screenshot

Introduction

This article presents an OrderedDictionary<TKey,TValue> you can use in your projects since the Microsoft's OrderedDictionary class doesn't have a generic counterpart. This is a rewrite of the ordered dictionary rather than a wrapper to avoid boxing and unboxing.

Background

Standard IDictionary<TKey,TValue> containers aren't guaranteed to preserve the order of items. Sometimes however, you need a container that allows you to address by key or by index. That is what this class is for.

Using the Code

The code is partitioned into sections via partial classes in order to make it easier to read and navigate. The following is the core of the ordered dictionary, in OrderedDictionary.cs:

C#
/// <summary>
/// Represents a dictionary where the items are in an explicit and indexable order
/// </summary>
/// <typeparam name="TKey">The type of the keys in this dictionary</typeparam>
/// <typeparam name="TValue">The type of the values in this dictionary</typeparam>
public partial class OrderedDictionary<TKey,TValue>
{
    // we keep these synced
    List<KeyValuePair<TKey,TValue>> _innerList;
    Dictionary<TKey, TValue> _innerDictionary;
    IEqualityComparer<TKey> _comparer = null;
    /// <summary>
    /// Creates an ordered dictionary with the specified capacity and comparer
    /// </summary>
    /// <param name="capacity">The initial capacity</param>
    /// <param name="comparer">The comparer</param>
    public OrderedDictionary(int capacity,IEqualityComparer<TKey> comparer)
    {
        _innerDictionary = new Dictionary<TKey, TValue>(capacity, comparer);
        _innerList = new List<KeyValuePair<TKey,TValue>>(capacity);
        _comparer = comparer;
    }
    /// <summary>
    /// Creates an ordered dictionary with the specified items and the specified comparer
    /// </summary>
    /// <param name="collection">The collection or dictionary to copy from</param>
    /// <param name="comparer">The comparer to use</param>
    public OrderedDictionary(IEnumerable<KeyValuePair<TKey,TValue>> collection, 
                             IEqualityComparer<TKey> comparer)
    {
        _innerDictionary = new Dictionary<TKey, TValue>(comparer);
        _innerList = new List<KeyValuePair<TKey, TValue>>();
        _AddValues(collection);
        _comparer = comparer;
    }
    /// <summary>
    /// Creates an ordered dictionary with the specified capacity
    /// </summary>
    /// <param name="capacity">The initial capacity</param>
    public OrderedDictionary(int capacity)
    {
        _innerDictionary = new Dictionary<TKey, TValue>(capacity);
        _innerList = new List<KeyValuePair<TKey, TValue>>(capacity);
    }
    /// <summary>
    /// Creates an ordered dictionary filled with the specified collection or dictionary
    /// </summary>
    /// <param name="collection">The collection or dictionary to copy</param>
    public OrderedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection)
    {
        _innerDictionary = new Dictionary<TKey, TValue>();
        _innerList = new List<KeyValuePair<TKey, TValue>>();
        _AddValues(collection);
    }
    /// <summary>
    /// Creates an ordered dictionary with the specified comparer
    /// </summary>
    /// <param name="comparer">The equality comparer to use for the keys</param>
    public OrderedDictionary(IEqualityComparer<TKey> comparer)
    {
        _innerDictionary = new Dictionary<TKey, TValue>(comparer);
        _innerList = new List<KeyValuePair<TKey, TValue>>();
        _comparer = comparer;
    }
    /// <summary>
    /// Creates a default instance of the ordered dictionary
    /// </summary>
    public OrderedDictionary()
    {
        _innerDictionary = new Dictionary<TKey, TValue>();
        _innerList = new List<KeyValuePair<TKey, TValue>>();
    }
    /// <summary>
    /// Gets the value at the specified index
    /// </summary>
    /// <param name="index">The index of the value to retrieve</param>
    /// <returns>The value of the item at the specified index</returns>
    public TValue GetAt(int index)
    {
        return _innerList[index].Value;
    }
    /// <summary>
    /// Sets the value at the specified index
    /// </summary>
    /// <param name="index">The index of the value to set</param>
    /// <param name="value">The new value to assign</param>
    public void SetAt(int index,TValue value)
    {
        var key = _innerList[index].Key;
        _innerList[index] = new KeyValuePair<TKey, TValue>(key, value);
        _innerDictionary[key] = value;
    }
    /// <summary>
    /// Inserts an item into the ordered dictionary at the specified position
    /// </summary>
    /// <param name="index">The index to insert the item before</param>
    /// <param name="key">The key of the new item</param>
    /// <param name="value">The value of the new item</param>
    public void Insert(int index, TKey key, TValue value)
        => (this as IList<KeyValuePair<TKey, TValue>>).Insert
           (index, new KeyValuePair<TKey, TValue>(key, value));
    
    void _AddValues(IEnumerable<KeyValuePair<TKey,TValue>> collection)
    {
        foreach (var kvp in collection)
        {
            _innerDictionary.Add(kvp.Key, kvp.Value);
            _innerList.Add(kvp);
        }
    }
}

As you can see, this class implements the standard Dictionary<TKey,TValue> constructors. Using them is exactly the same. It also has several extra methods like GetAt() and SetAt(). These and the rest allow for indexing into the dictionary. The dictionary also implements a list interface - IList<KeyValuePair<TKey,TValue>> which allows you to treat the entire container like an indexed list of key/value pairs. Of course, it also implements the standard dictionary interfaces.

All lookups are hashtable lookups or indexed lookups. This means they are fast. The add, insert, set, and removal methods are slightly slower than a standard dictionary as a result of having to keep both containers in sync.

Using it is demonstrated in the demo program. Enjoy!

Points of Interest

In order to fulfill all of the operations, we require two copies of every TKey and TValue entry - one set in the list, and the other in the dictionary. This is required. There is no other way to efficiently provide all of the operations without mirroring all of the data between both containers. The trade off is more speed at the cost of more memory.

History

  • 20th November, 2019 - Initial submission

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
Just a shiny lil monster. Casts spells in C++. Mostly harmless.

Comments and Discussions

 
QuestionIndex of Key Pin
Brad Oestreicher28-Feb-22 5:57
Brad Oestreicher28-Feb-22 5:57 
AnswerRe: Index of Key Pin
honey the codewitch28-Feb-22 6:24
mvahoney the codewitch28-Feb-22 6:24 
QuestionNice work Pin
SteveTheThread22-Jan-20 2:42
SteveTheThread22-Jan-20 2:42 
AnswerRe: Nice work Pin
honey the codewitch22-Jan-20 3:56
mvahoney the codewitch22-Jan-20 3:56 
QuestionMaybe InsertionOrderPreservingDictionary is a better name? Pin
Qwertie2-Dec-19 10:45
Qwertie2-Dec-19 10:45 
AnswerRe: Maybe InsertionOrderPreservingDictionary is a better name? Pin
honey the codewitch2-Dec-19 13:14
mvahoney the codewitch2-Dec-19 13:14 
GeneralRe: Maybe InsertionOrderPreservingDictionary is a better name? Pin
rhyous13-Dec-19 13:11
rhyous13-Dec-19 13:11 
GeneralRe: Maybe InsertionOrderPreservingDictionary is a better name? Pin
honey the codewitch13-Dec-19 13:16
mvahoney the codewitch13-Dec-19 13:16 
AnswerRe: Maybe InsertionOrderPreservingDictionary is a better name? Pin
honey the codewitch2-Dec-19 14:14
mvahoney the codewitch2-Dec-19 14:14 
QuestionYes there is a SortedDictionary<Tkey, TValue> Pin
Matthew Dennis21-Nov-19 8:15
sysadminMatthew Dennis21-Nov-19 8:15 
AnswerRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch21-Nov-19 11:44
mvahoney the codewitch21-Nov-19 11:44 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 11:36
professionalJörgen Andersson23-Nov-19 11:36 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 11:39
mvahoney the codewitch23-Nov-19 11:39 
SortedDictionary and SortedList are similar in functionality in that they both store items in sort order.

OrderedDictionary, like the standard List, stores items in whatever order they were inserted in.

For example, OrderedDictionary has Insert(int index,TKey key, TValue value)

and honestly, SortedList should have been called SortedDictionary, while SortedDictionary could have been RedBlackTreeDictionary
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.

GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 12:16
professionalJörgen Andersson23-Nov-19 12:16 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 12:18
mvahoney the codewitch23-Nov-19 12:18 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 12:19
mvahoney the codewitch23-Nov-19 12:19 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 12:30
professionalJörgen Andersson23-Nov-19 12:30 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 12:33
mvahoney the codewitch23-Nov-19 12:33 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 12:37
professionalJörgen Andersson23-Nov-19 12:37 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 12:39
mvahoney the codewitch23-Nov-19 12:39 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 12:45
professionalJörgen Andersson23-Nov-19 12:45 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 12:59
professionalJörgen Andersson23-Nov-19 12:59 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 13:13
mvahoney the codewitch23-Nov-19 13:13 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 13:17
professionalJörgen Andersson23-Nov-19 13:17 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jeff Bowman25-Nov-19 12:22
professionalJeff Bowman25-Nov-19 12:22 

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.