Click here to Skip to main content
14,391,240 members

A Generic OrderedDictionary in C#

Rate this:
5.00 (6 votes)
Please Sign up or sign in to vote.
5.00 (6 votes)
20 Nov 2019CPOL
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:

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

Share

About the Author

honey the codewitch
United States United States
Just a shiny lil monster. Casts spells in C++. Mostly harmless.

Comments and Discussions

 
QuestionMaybe InsertionOrderPreservingDictionary is a better name? Pin
Qwertie2-Dec-19 11:45
MemberQwertie2-Dec-19 11:45 
AnswerRe: Maybe InsertionOrderPreservingDictionary is a better name? Pin
honey the codewitch2-Dec-19 14:14
Memberhoney the codewitch2-Dec-19 14:14 
GeneralRe: Maybe InsertionOrderPreservingDictionary is a better name? Pin
rhyous2hrs 6mins ago
Memberrhyous2hrs 6mins ago 
GeneralRe: Maybe InsertionOrderPreservingDictionary is a better name? Pin
honey the codewitch2hrs 1 min ago
Memberhoney the codewitch2hrs 1 min ago 
AnswerRe: Maybe InsertionOrderPreservingDictionary is a better name? Pin
honey the codewitch2-Dec-19 15:14
Memberhoney the codewitch2-Dec-19 15:14 
QuestionYes there is a SortedDictionary<Tkey, TValue> Pin
Matthew Dennis21-Nov-19 9:15
sysadminMatthew Dennis21-Nov-19 9:15 
AnswerRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch21-Nov-19 12:44
Memberhoney the codewitch21-Nov-19 12:44 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 12:36
professionalJörgen Andersson23-Nov-19 12:36 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 12:39
Memberhoney the codewitch23-Nov-19 12:39 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 13:16
professionalJörgen Andersson23-Nov-19 13:16 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 13:18
Memberhoney the codewitch23-Nov-19 13:18 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 13:19
Memberhoney the codewitch23-Nov-19 13:19 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 13:30
professionalJörgen Andersson23-Nov-19 13:30 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 13:33
Memberhoney the codewitch23-Nov-19 13:33 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 13:37
professionalJörgen Andersson23-Nov-19 13:37 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 13:39
Memberhoney the codewitch23-Nov-19 13:39 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 13:45
professionalJörgen Andersson23-Nov-19 13:45 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 13:59
professionalJörgen Andersson23-Nov-19 13:59 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch23-Nov-19 14:13
Memberhoney the codewitch23-Nov-19 14:13 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jörgen Andersson23-Nov-19 14:17
professionalJörgen Andersson23-Nov-19 14:17 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jeff Bowman25-Nov-19 13:22
professionalJeff Bowman25-Nov-19 13:22 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch25-Nov-19 15:58
Memberhoney the codewitch25-Nov-19 15:58 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jeff Bowman25-Nov-19 17:24
professionalJeff Bowman25-Nov-19 17:24 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
honey the codewitch25-Nov-19 17:28
Memberhoney the codewitch25-Nov-19 17:28 
GeneralRe: Yes there is a SortedDictionary<Tkey, TValue> Pin
Jeff Bowman28-Nov-19 15:34
professionalJeff Bowman28-Nov-19 15:34 

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.

Tip/Trick
Posted 20 Nov 2019

Stats

4.7K views
85 downloads
7 bookmarked