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

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?

Answers


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);
    }

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


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'.


Well, you could use a List<KeyValuePair<K,V>>, which would preserve the order... however you would lose the lookup functionality of the dictionary. Why do you need the order to be preserved ?


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.


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(); }
    }
}

I know you're writing C#, but Java has a class called LinkedHashMap that uses a private LinkedList to maintain the order of insertion of keys. If you can't find a suitable generic solution, perhaps that would be a start on implementing your own.


Another option for a Generic Key/Value pair that preserves insertion is to use something like:

Queue<KeyValuePair<string, string>>

This would be a guaranteed ordered list. You can en-queue and dequeue in an ordered faction similar to Add/Remove of dictionary as opposed to resizing an Array. It can often serve as a middle ground between a non-resizing ordered (by insertion) array and an autoresizing unordered (by insertion) list.


If you need constant complexity of Add, Remove, ContainsKey and order preservation, then there's no such generic in .NET Framework 4.5.

If you're okay with 3rd party code, take a look at my repository (permissive MIT license): https://github.com/OndrejPetrzilka/Rock.Collections

There's OrderedDictionary<K,V> collection:

  • source code based on classic Dictionary<K,V> (from .NET Core)
  • preserves order of insertions and allows manual reordering
  • features reversed enumeration
  • has same operation complexities as Dictionary<K,V>
  • Add and Remove operations are ~20% slower compared to Dictionary<K,V>
  • consumes 8 more bytes of memory per item

Code:

//A SortedDictionary is sorted on the key (not value)
System.Collections.Generic.SortedDictionary<string, string> testSortDic = new SortedDictionary<string, string>();

//Add some values with the keys out of order
testSortDic.Add("key5", "value 1");
testSortDic.Add("key3", "value 2");
testSortDic.Add("key2", "value 3");
testSortDic.Add("key4", "value 4");
testSortDic.Add("key1", "value 5"); 

//Display the elements.  
foreach (KeyValuePair<string, string> kvp in testSortDic)
{
    Console.WriteLine("Key = {0}, value = {1}", kvp.Key, kvp.Value);
}

Output:

Key = key1, value = value 5
Key = key2, value = value 3
Key = key3, value = value 2
Key = key4, value = value 4
Key = key5, value = value 1     

Need Your Help

VHDL/Verilog related programming forums?

vhdl verilog system-verilog systemc

Hardware design with VHDL or Verilog is more like programming nowadays. However, I see SO members are not so actively talking about VHDL/Verilog programming.

Does the order of LINQ functions matter?

c# performance linq

Basically, as the question states... does the order of LINQ functions matter in terms of performance? Obviously the results would have to be identical still...