Generic Key/Value pair collection in that preserves insertion order?

Question

I'm looking for something like a Dictionary<K,V> however with a guarantee that it preserves insertion order. Since Dictionary is a hashtable, I do not think it does.

Is there a generic collection for this, or do I need to use one of the old .NET 1.1 collections?

Solution 1

There is not. However, System.Collections.Specialized.OrderedDictionary should solve most need for it.

EDIT: Another option is to turn this into a Generic. I haven't tested it but it compiles (C# 6) and should work. However, it will still have the same limitations that Ondrej Petrzilka mentions in comments below.

    public class OrderdDictionary<T, K>
    {
        public OrderedDictionary UnderlyingCollection { get; } = new OrderedDictionary();

        public K this[T key]
        {
            get
            {
                return (K)UnderlyingCollection[key];
            }
            set
            {
                UnderlyingCollection[key] = value;
            }
        }

        public K this[int index]
        {
            get
            {
                return (K)UnderlyingCollection[index];
            }
            set
            {
                UnderlyingCollection[index] = value;
            }
        }
        public ICollection<T> Keys => UnderlyingCollection.Keys.OfType<T>().ToList();
        public ICollection<K> Values => UnderlyingCollection.Values.OfType<K>().ToList();
        public bool IsReadOnly => UnderlyingCollection.IsReadOnly;
        public int Count => UnderlyingCollection.Count;
        public IDictionaryEnumerator GetEnumerator() => UnderlyingCollection.GetEnumerator();
        public void Insert(int index, T key, K value) => UnderlyingCollection.Insert(index, key, value);
        public void RemoveAt(int index) => UnderlyingCollection.RemoveAt(index);
        public bool Contains(T key) => UnderlyingCollection.Contains(key);
        public void Add(T key, K value) => UnderlyingCollection.Add(key, value);
        public void Clear() => UnderlyingCollection.Clear();
        public void Remove(T key) => UnderlyingCollection.Remove(key);
        public void CopyTo(Array array, int index) => UnderlyingCollection.CopyTo(array, index);
    }

Solution 2

There actually is one, which is generic and has been around since .net 2.0. It's called KeyedCollection<TKey, TItem>. However, it comes with the restriction that it constructs the keys from the values, so it is not a generic Key/Value pair collection. (Although you can of course use it like KeyedCollection<TKey, Tuple<TKey, TItem>> as a workaround).

If you need it as an IDictionary<TKey, TItem>, it has a .Dictionary property.

A somewhat minor issue that I have with it is that it is an abstract class and you have to subclass it and implement:

protected abstract TKey GetKeyForItem(TItem item)

I'd rather just pass a lambda into the constructor for this purpose, but then again, I guess a virtual method is slightly faster than a lambda (any comments on this appreciated).

Edit As the question came up in the comments: KeyedCollection preserves order, as it inherits from Collection<T>, which does (it derives from IList<T>. See also the documentation of the Add method: Adds an object to the end of the Collection.).

Solution 3

There is an OrderedDictionary class that is a dictionary but can be indexed in insertion order, but it is not generified. There is not a generified one in the .Net framework at present.

I have read a comment somewhere from someone on the .Net team that said that they may implement a generified version in the future, but if so it would most likely be called IndexableDictionary instead of OrderedDictionary to make its behaviour more obvious.

EDIT: found the quote. It was on the MSDN page for OrderedDictionary, attributed to David M. Kean from Microsoft:

This type is actually misnamed; it is not an 'ordered' dictionary as such, but rather an 'indexed' dictionary. Although, today there is no equivalent generic version of this type, if we add one in the future it is likely that we will name such as type 'IndexedDictionary'.

Solution 4

Here is a wrapper for the non-generic Systems.Collections.Specialized.OrderedDictionary type.

This type will return keys/value/pairs sequences in insertion order, much like Ruby 2.0 hashes.

It does not require C#6 magic, conforms to IDictionary<TKey,TValue> (which also means that accessing a non-assigned key throws an exception), and ought to be serializable.

It is given the name 'IndexedDictionary' per note on Adrian's answer.

YMMV.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;

/// <summary>
/// A dictionary that maintains insertion ordering of keys.
/// 
/// This is useful for emitting JSON where it is preferable to keep the key ordering
/// for various human-friendlier reasons.
/// 
/// There is no support to manually re-order keys or to access keys
/// by index without using Keys/Values or the Enumerator (eg).
/// </summary>
[Serializable]
public sealed class IndexedDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    // Non-generic version only in .NET 4.5
    private readonly OrderedDictionary _backing = new OrderedDictionary();

    private IEnumerable<KeyValuePair<TKey, TValue>> KeyValuePairs
    {
        get
        {
            return _backing.OfType<DictionaryEntry>()
                .Select(e => new KeyValuePair<TKey, TValue>((TKey)e.Key, (TValue)e.Value));
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return KeyValuePairs.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        _backing[item.Key] = item.Value;
    }

    public void Clear()
    {
        _backing.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        return _backing.Contains(item.Key);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        KeyValuePairs.ToList().CopyTo(array, arrayIndex);
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        TValue value;
        if (TryGetValue(item.Key, out value)
            && Equals(value, item.Value))
        {
            Remove(item.Key);
            return true;
        }
        return false;
    }

    public int Count
    {
        get { return _backing.Count; }
    }

    public bool IsReadOnly
    {
        get { return _backing.IsReadOnly; }
    }

    public bool ContainsKey(TKey key)
    {
        return _backing.Contains(key);
    }

    public void Add(TKey key, TValue value)
    {
        _backing.Add(key, value);
    }

    public bool Remove(TKey key)
    {
        var result = _backing.Contains(key);
        if (result) {
            _backing.Remove(key);
        }
        return result;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        object foundValue;
        if ((foundValue = _backing[key]) != null
            || _backing.Contains(key))
        {
            // Either found with a non-null value, or contained value is null.
            value = (TValue)foundValue;
            return true;
        }
        value = default(TValue);
        return false;
    }

    public TValue this[TKey key]
    {
        get
        {
            TValue value;
            if (TryGetValue(key, out value))
                return value;
            throw new KeyNotFoundException();
        }
        set { _backing[key] = value; }
    }

    public ICollection<TKey> Keys
    {
        get { return _backing.Keys.OfType<TKey>().ToList(); }
    }

    public ICollection<TValue> Values
    {
        get { return _backing.Values.OfType<TValue>().ToList(); }
    }
}

Solution 5

There is a generic implementation on code project which comes with a reasonable amount of test cases.

The author chose a rather funny name (KeyedList) which makes it pretty hard to find.

View more solutions

Comments

[Peter Ramos]

Not generic, but looks close enough. Thanks.

[Michael]

-1, OP asked for a dictionary preserving insertion order and not preserving a sorting by key

[nawfal]

Are your sure KeyedCollection preserves order?

[Evgeniy Berezovsky]

It preserves order, as it inherits from Collection<T>, which does. See also the documentation of the Add method: Adds an object to the end of the Collection<T>. (Inherited from Collection<T>.).

[Ondrej Petrzilka]

OrderedDictionary is fine unless you need O(1) removals. It has O(n) removals by key (it searches for index and then moves items in array). Only fast removals are from end and by index.

[John Stock]

This should not be marked as the answer as it does not support generics which is what was asked by the OP. "Close enough" still does not make this the answer for others looking at this.

[McAden]

@JohnStock how's that?

[Nyerguds]

Could just as well use List<> then though. Big disadvantage of this approach is that looking up by key gets more complex.

[Nyerguds]

If there's a GetKeyForItem, doesn't that imply the list can't contain duplicate values?

[Evgeniy Berezovsky]

@ToolmakerSteve You are wrong for two reasons. Firstly, the specification guarantees insertion order (just read my first comment to this answer). So if it was indeed "simply a Dictionary" internally, it would be a severe bug. Secondly, check the current source code again and you will find the dictionary to be optional, created only when a configurable threshold is reached. KeyedCollection instead uses a List to store its items, which it inherits from Collection.

[ToolmakerSteve]

@EugeneBeresovsky - thanks, I see my mistake. I missed that KeyedCollection inherits from Collection, and calls base.InsertItem when adding an item. Unfortunately, StackOverflow (rather oddly) lacks a way to remove a downvote unless an answer is edited. :( Anyway, I've removed my incorrect comment.

[Evgeniy Berezovsky]

@ToolmakerSteve I edited my answer to describe the insertion order guarantee.

[Evgeniy Berezovsky]

@Nyerguds GetKeyForItem you have to implement to extract a key from a value. However, as KeyedCollection cannot hold duplicate keys, duplicate values aren't possible, as they would lead to the same key. But to make things more interesting: You can implement this method to return null for a collection that contains items without keys, in which case the items can be accessed only by their index. So multiple "null key" values are possible, duplicate or not.

[ToolmakerSteve]

Thanks. BTW, I see nothing in Collection<T>, ICollection<T>, or IList<T> docs that guarantees order of remaining elements is preserved after Remove or RemoveAt. Are we to infer that from the concept of a "list"?

[JJS]

shame that this uses OrderedDictionary and incurs boxing.

[Sinjai]

How would you make this implement IEnumerable<KeyValuePair<T, K>>?

[McAden]

@Sinjai I'd create an IEnumerator<KeyValuePair<T, K>> which does the actual enumeration in a typed manner. From there simply pass that to the IEnumerable<KeyValuePair<T, K>> implementation. See docs.microsoft.com/en-us/dotnet/api/…

[Sinjai]

@McAden I suppose my question is "how do I do the enumeration in a typed manner?" But it's looking more like I should just be using this.

[McAden]

It's been a long time since I've looked at this code and I've never actually needed it in practice - just helping the OP. However, you can get a count of the object, and it's got an index accessor. So you should be able to get the "next" value but I'm not sure about key. It'd look and see what type the built-in IDictionaryEnumerator there actually returns and if that can be cast. Otherwise I'm not sure.

[Sinjai]

@McAden That was my thought, too. It returns an inner class of OrderedDictionary, OrderedDictionaryEnumerator : IDictionaryEnumerator, IEnumerator. This works, but with unknown levels of jank.

[Sinjai]

How does this differ from McAden's answer?

[user2864740]

"It does not require C#6 magic, conforms to IDictionary<TKey,TValue> (which also means that accessing a non-assigned key throws an exception), and ought to be serializable."

[Sinjai]

And what are the benefits of not requiring C# 6 and conforming to IDictionary<TKey, TValue>?

[user2864740]

Those should be explanatory.. 1) not using/requiring C#6 (for whatever reason - and yes, I do deal with such code); 2) being able to use the resulting object where a IDictionary<TKey, TValue> is expected/required (consider that even ConcurrentDictionary<..> implements IDictionary<..>)