A Generic OrderedDictionary in C#

Updated on 2019-11-20

A fully generic ordered dictionary class in C#

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:

/// <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