¿No hay una implementación genérica de OrderedDictionary?

No parece haber una implementación genérica de OrderedDictionary (que se encuentra en el espacio de nombres System.Collections.Specialized ) en .NET 3.5. ¿Hay alguno que me estoy perdiendo?

He encontrado implementaciones para proporcionar la funcionalidad, pero me pregunto si / por qué no hay una implementación genérica lista para usar y si alguien sabe si es algo en .NET 4.0.

    Tienes razón. No existe un equivalente genérico de OrderedDictionary en el marco mismo.

    (Ese sigue siendo el caso de .NET4 también, hasta donde yo sé).

    EDITAR : ¡Pero puedes votar por él en UserVoice de Visual Studio!

    La implementación de un OrderedDictionary genérico no es terriblemente difícil, pero lleva mucho tiempo y, francamente, esta clase es un gran descuido por parte de Microsoft. Hay varias formas de implementar esto, pero elegí usar KeyedCollection para mi almacenamiento interno. También opté por implementar varios métodos para clasificar la forma en que List hace, ya que este es esencialmente un híbrido IList e IDictionary. He incluido mi implementación aquí para la posteridad.

    Aquí está la interfaz. Observe que incluye System.Collections.Specialized.IOrderedDictionary , que es la versión no genérica de esta interfaz proporcionada por Microsoft.

     // http://unlicense.org using System; using System.Collections.Generic; using System.Collections.Specialized; namespace mattmc3.Common.Collections.Generic { public interface IOrderedDictionary : IDictionary, IOrderedDictionary { new TValue this[int index] { get; set; } new TValue this[TKey key] { get; set; } new int Count { get; } new ICollection Keys { get; } new ICollection Values { get; } new void Add(TKey key, TValue value); new void Clear(); void Insert(int index, TKey key, TValue value); int IndexOf(TKey key); bool ContainsValue(TValue value); bool ContainsValue(TValue value, IEqualityComparer comparer); new bool ContainsKey(TKey key); new IEnumerator> GetEnumerator(); new bool Remove(TKey key); new void RemoveAt(int index); new bool TryGetValue(TKey key, out TValue value); TValue GetValue(TKey key); void SetValue(TKey key, TValue value); KeyValuePair GetItem(int index); void SetItem(int index, TValue value); } } 

    Aquí está la implementación junto con las clases de ayuda:

     // http://unlicense.org using System; using System.Collections.ObjectModel; using System.Diagnostics; using System.Collections; using System.Collections.Specialized; using System.Collections.Generic; using System.Linq; namespace mattmc3.Common.Collections.Generic { ///  /// A dictionary object that allows rapid hash lookups using keys, but also /// maintains the key insertion order so that values can be retrieved by /// key index. ///  public class OrderedDictionary : IOrderedDictionary { #region Fields/Properties private KeyedCollection2> _keyedCollection; ///  /// Gets or sets the value associated with the specified key. ///  /// The key associated with the value to get or set. public TValue this[TKey key] { get { return GetValue(key); } set { SetValue(key, value); } } ///  /// Gets or sets the value at the specified index. ///  /// The index of the value to get or set. public TValue this[int index] { get { return GetItem(index).Value; } set { SetItem(index, value); } } public int Count { get { return _keyedCollection.Count; } } public ICollection Keys { get { return _keyedCollection.Select(x => x.Key).ToList(); } } public ICollection Values { get { return _keyedCollection.Select(x => x.Value).ToList(); } } public IEqualityComparer Comparer { get; private set; } #endregion #region Constructors public OrderedDictionary() { Initialize(); } public OrderedDictionary(IEqualityComparer comparer) { Initialize(comparer); } public OrderedDictionary(IOrderedDictionary dictionary) { Initialize(); foreach (KeyValuePair pair in dictionary) { _keyedCollection.Add(pair); } } public OrderedDictionary(IOrderedDictionary dictionary, IEqualityComparer comparer) { Initialize(comparer); foreach (KeyValuePair pair in dictionary) { _keyedCollection.Add(pair); } } #endregion #region Methods private void Initialize(IEqualityComparer comparer = null) { this.Comparer = comparer; if (comparer != null) { _keyedCollection = new KeyedCollection2>(x => x.Key, comparer); } else { _keyedCollection = new KeyedCollection2>(x => x.Key); } } public void Add(TKey key, TValue value) { _keyedCollection.Add(new KeyValuePair(key, value)); } public void Clear() { _keyedCollection.Clear(); } public void Insert(int index, TKey key, TValue value) { _keyedCollection.Insert(index, new KeyValuePair(key, value)); } public int IndexOf(TKey key) { if (_keyedCollection.Contains(key)) { return _keyedCollection.IndexOf(_keyedCollection[key]); } else { return -1; } } public bool ContainsValue(TValue value) { return this.Values.Contains(value); } public bool ContainsValue(TValue value, IEqualityComparer comparer) { return this.Values.Contains(value, comparer); } public bool ContainsKey(TKey key) { return _keyedCollection.Contains(key); } public KeyValuePair GetItem(int index) { if (index < 0 || index >= _keyedCollection.Count) { throw new ArgumentException(String.Format("The index was outside the bounds of the dictionary: {0}", index)); } return _keyedCollection[index]; } ///  /// Sets the value at the index specified. ///  /// The index of the value desired /// The value to set ///  /// Thrown when the index specified does not refer to a KeyValuePair in this object ///  public void SetItem(int index, TValue value) { if (index < 0 || index >= _keyedCollection.Count) { throw new ArgumentException("The index is outside the bounds of the dictionary: {0}".FormatWith(index)); } var kvp = new KeyValuePair(_keyedCollection[index].Key, value); _keyedCollection[index] = kvp; } public IEnumerator> GetEnumerator() { return _keyedCollection.GetEnumerator(); } public bool Remove(TKey key) { return _keyedCollection.Remove(key); } public void RemoveAt(int index) { if (index < 0 || index >= _keyedCollection.Count) { throw new ArgumentException(String.Format("The index was outside the bounds of the dictionary: {0}", index)); } _keyedCollection.RemoveAt(index); } ///  /// Gets the value associated with the specified key. ///  /// The key associated with the value to get. public TValue GetValue(TKey key) { if (_keyedCollection.Contains(key) == false) { throw new ArgumentException("The given key is not present in the dictionary: {0}".FormatWith(key)); } var kvp = _keyedCollection[key]; return kvp.Value; } ///  /// Sets the value associated with the specified key. ///  /// The key associated with the value to set. /// The the value to set. public void SetValue(TKey key, TValue value) { var kvp = new KeyValuePair(key, value); var idx = IndexOf(key); if (idx > -1) { _keyedCollection[idx] = kvp; } else { _keyedCollection.Add(kvp); } } public bool TryGetValue(TKey key, out TValue value) { if (_keyedCollection.Contains(key)) { value = _keyedCollection[key].Value; return true; } else { value = default(TValue); return false; } } #endregion #region sorting public void SortKeys() { _keyedCollection.SortByKeys(); } public void SortKeys(IComparer comparer) { _keyedCollection.SortByKeys(comparer); } public void SortKeys(Comparison comparison) { _keyedCollection.SortByKeys(comparison); } public void SortValues() { var comparer = Comparer.Default; SortValues(comparer); } public void SortValues(IComparer comparer) { _keyedCollection.Sort((x, y) => comparer.Compare(x.Value, y.Value)); } public void SortValues(Comparison comparison) { _keyedCollection.Sort((x, y) => comparison(x.Value, y.Value)); } #endregion #region IDictionary void IDictionary.Add(TKey key, TValue value) { Add(key, value); } bool IDictionary.ContainsKey(TKey key) { return ContainsKey(key); } ICollection IDictionary.Keys { get { return Keys; } } bool IDictionary.Remove(TKey key) { return Remove(key); } bool IDictionary.TryGetValue(TKey key, out TValue value) { return TryGetValue(key, out value); } ICollection IDictionary.Values { get { return Values; } } TValue IDictionary.this[TKey key] { get { return this[key]; } set { this[key] = value; } } #endregion #region ICollection> void ICollection>.Add(KeyValuePair item) { _keyedCollection.Add(item); } void ICollection>.Clear() { _keyedCollection.Clear(); } bool ICollection>.Contains(KeyValuePair item) { return _keyedCollection.Contains(item); } void ICollection>.CopyTo(KeyValuePair[] array, int arrayIndex) { _keyedCollection.CopyTo(array, arrayIndex); } int ICollection>.Count { get { return _keyedCollection.Count; } } bool ICollection>.IsReadOnly { get { return false; } } bool ICollection>.Remove(KeyValuePair item) { return _keyedCollection.Remove(item); } #endregion #region IEnumerable> IEnumerator> IEnumerable>.GetEnumerator() { return GetEnumerator(); } #endregion #region IEnumerable IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } #endregion #region IOrderedDictionary IDictionaryEnumerator IOrderedDictionary.GetEnumerator() { return new DictionaryEnumerator(this); } void IOrderedDictionary.Insert(int index, object key, object value) { Insert(index, (TKey)key, (TValue)value); } void IOrderedDictionary.RemoveAt(int index) { RemoveAt(index); } object IOrderedDictionary.this[int index] { get { return this[index]; } set { this[index] = (TValue)value; } } #endregion #region IDictionary void IDictionary.Add(object key, object value) { Add((TKey)key, (TValue)value); } void IDictionary.Clear() { Clear(); } bool IDictionary.Contains(object key) { return _keyedCollection.Contains((TKey)key); } IDictionaryEnumerator IDictionary.GetEnumerator() { return new DictionaryEnumerator(this); } bool IDictionary.IsFixedSize { get { return false; } } bool IDictionary.IsReadOnly { get { return false; } } ICollection IDictionary.Keys { get { return (ICollection)this.Keys; } } void IDictionary.Remove(object key) { Remove((TKey)key); } ICollection IDictionary.Values { get { return (ICollection)this.Values; } } object IDictionary.this[object key] { get { return this[(TKey)key]; } set { this[(TKey)key] = (TValue)value; } } #endregion #region ICollection void ICollection.CopyTo(Array array, int index) { ((ICollection)_keyedCollection).CopyTo(array, index); } int ICollection.Count { get { return ((ICollection)_keyedCollection).Count; } } bool ICollection.IsSynchronized { get { return ((ICollection)_keyedCollection).IsSynchronized; } } object ICollection.SyncRoot { get { return ((ICollection)_keyedCollection).SyncRoot; } } #endregion } public class KeyedCollection2 : KeyedCollection { private const string DelegateNullExceptionMessage = "Delegate passed cannot be null"; private Func _getKeyForItemDelegate; public KeyedCollection2(Func getKeyForItemDelegate) : base() { if (getKeyForItemDelegate == null) throw new ArgumentNullException(DelegateNullExceptionMessage); _getKeyForItemDelegate = getKeyForItemDelegate; } public KeyedCollection2(Func getKeyForItemDelegate, IEqualityComparer comparer) : base(comparer) { if (getKeyForItemDelegate == null) throw new ArgumentNullException(DelegateNullExceptionMessage); _getKeyForItemDelegate = getKeyForItemDelegate; } protected override TKey GetKeyForItem(TItem item) { return _getKeyForItemDelegate(item); } public void SortByKeys() { var comparer = Comparer.Default; SortByKeys(comparer); } public void SortByKeys(IComparer keyComparer) { var comparer = new Comparer2((x, y) => keyComparer.Compare(GetKeyForItem(x), GetKeyForItem(y))); Sort(comparer); } public void SortByKeys(Comparison keyComparison) { var comparer = new Comparer2((x, y) => keyComparison(GetKeyForItem(x), GetKeyForItem(y))); Sort(comparer); } public void Sort() { var comparer = Comparer.Default; Sort(comparer); } public void Sort(Comparison comparison) { var newComparer = new Comparer2((x, y) => comparison(x, y)); Sort(newComparer); } public void Sort(IComparer comparer) { List list = base.Items as List; if (list != null) { list.Sort(comparer); } } } public class Comparer2 : Comparer { //private readonly Func _compareFunction; private readonly Comparison _compareFunction; #region Constructors public Comparer2(Comparison comparison) { if (comparison == null) throw new ArgumentNullException("comparison"); _compareFunction = comparison; } #endregion public override int Compare(T arg1, T arg2) { return _compareFunction(arg1, arg2); } } public class DictionaryEnumerator : IDictionaryEnumerator, IDisposable { readonly IEnumerator> impl; public void Dispose() { impl.Dispose(); } public DictionaryEnumerator(IDictionary value) { this.impl = value.GetEnumerator(); } public void Reset() { impl.Reset(); } public bool MoveNext() { return impl.MoveNext(); } public DictionaryEntry Entry { get { var pair = impl.Current; return new DictionaryEntry(pair.Key, pair.Value); } } public object Key { get { return impl.Current.Key; } } public object Value { get { return impl.Current.Value; } } public object Current { get { return Entry; } } } } 

    Y ninguna implementación estaría completa sin algunas pruebas (pero trágicamente, SO no me deja publicar ese código en una publicación), así que tendré que dejarlo para escribir sus pruebas. Pero, dejé algunos de ellos para que pueda hacerse una idea de cómo funciona:

     // http://unlicense.org using System; using System.Collections.Generic; using System.Linq; using Microsoft.VisualStudio.TestTools.UnitTesting; using mattmc3.Common.Collections.Generic; namespace mattmc3.Tests.Common.Collections.Generic { [TestClass] public class OrderedDictionaryTests { private OrderedDictionary GetAlphabetDictionary(IEqualityComparer comparer = null) { OrderedDictionary alphabet = (comparer == null ? new OrderedDictionary() : new OrderedDictionary(comparer)); for (var a = Convert.ToInt32('a'); a < = Convert.ToInt32('z'); a++) { var c = Convert.ToChar(a); alphabet.Add(c.ToString(), c.ToString().ToUpper()); } Assert.AreEqual(26, alphabet.Count); return alphabet; } private List> GetAlphabetList() { var alphabet = new List>(); for (var a = Convert.ToInt32('a'); a < = Convert.ToInt32('z'); a++) { var c = Convert.ToChar(a); alphabet.Add(new KeyValuePair(c.ToString(), c.ToString().ToUpper())); } Assert.AreEqual(26, alphabet.Count); return alphabet; } [TestMethod] public void TestAdd() { var od = new OrderedDictionary(); Assert.AreEqual(0, od.Count); Assert.AreEqual(-1, od.IndexOf("foo")); od.Add("foo", "bar"); Assert.AreEqual(1, od.Count); Assert.AreEqual(0, od.IndexOf("foo")); Assert.AreEqual(od[0], "bar"); Assert.AreEqual(od["foo"], "bar"); Assert.AreEqual(od.GetItem(0).Key, "foo"); Assert.AreEqual(od.GetItem(0).Value, "bar"); } [TestMethod] public void TestRemove() { var od = new OrderedDictionary(); od.Add("foo", "bar"); Assert.AreEqual(1, od.Count); od.Remove("foo"); Assert.AreEqual(0, od.Count); } [TestMethod] public void TestRemoveAt() { var od = new OrderedDictionary(); od.Add("foo", "bar"); Assert.AreEqual(1, od.Count); od.RemoveAt(0); Assert.AreEqual(0, od.Count); } [TestMethod] public void TestClear() { var od = GetAlphabetDictionary(); Assert.AreEqual(26, od.Count); od.Clear(); Assert.AreEqual(0, od.Count); } [TestMethod] public void TestOrderIsPreserved() { var alphabetDict = GetAlphabetDictionary(); var alphabetList = GetAlphabetList(); Assert.AreEqual(26, alphabetDict.Count); Assert.AreEqual(26, alphabetList.Count); var keys = alphabetDict.Keys.ToList(); var values = alphabetDict.Values.ToList(); for (var i = 0; i < 26; i++) { var dictItem = alphabetDict.GetItem(i); var listItem = alphabetList[i]; var key = keys[i]; var value = values[i]; Assert.AreEqual(dictItem, listItem); Assert.AreEqual(key, listItem.Key); Assert.AreEqual(value, listItem.Value); } } [TestMethod] public void TestTryGetValue() { var alphabetDict = GetAlphabetDictionary(); string result = null; Assert.IsFalse(alphabetDict.TryGetValue("abc", out result)); Assert.IsNull(result); Assert.IsTrue(alphabetDict.TryGetValue("z", out result)); Assert.AreEqual("Z", result); } [TestMethod] public void TestEnumerator() { var alphabetDict = GetAlphabetDictionary(); var keys = alphabetDict.Keys.ToList(); Assert.AreEqual(26, keys.Count); var i = 0; foreach (var kvp in alphabetDict) { var value = alphabetDict[kvp.Key]; Assert.AreEqual(kvp.Value, value); i++; } } [TestMethod] public void TestInvalidIndex() { var alphabetDict = GetAlphabetDictionary(); try { var notGonnaWork = alphabetDict[100]; Assert.IsTrue(false, "Exception should have thrown"); } catch (Exception ex) { Assert.IsTrue(ex.Message.Contains("index is outside the bounds")); } } [TestMethod] public void TestMissingKey() { var alphabetDict = GetAlphabetDictionary(); try { var notGonnaWork = alphabetDict["abc"]; Assert.IsTrue(false, "Exception should have thrown"); } catch (Exception ex) { Assert.IsTrue(ex.Message.Contains("key is not present")); } } [TestMethod] public void TestUpdateExistingValue() { var alphabetDict = GetAlphabetDictionary(); Assert.IsTrue(alphabetDict.ContainsKey("c")); Assert.AreEqual(2, alphabetDict.IndexOf("c")); Assert.AreEqual(alphabetDict[2], "C"); alphabetDict[2] = "CCC"; Assert.IsTrue(alphabetDict.ContainsKey("c")); Assert.AreEqual(2, alphabetDict.IndexOf("c")); Assert.AreEqual(alphabetDict[2], "CCC"); } [TestMethod] public void TestInsertValue() { var alphabetDict = GetAlphabetDictionary(); Assert.IsTrue(alphabetDict.ContainsKey("c")); Assert.AreEqual(2, alphabetDict.IndexOf("c")); Assert.AreEqual(alphabetDict[2], "C"); Assert.AreEqual(26, alphabetDict.Count); Assert.IsFalse(alphabetDict.ContainsValue("ABC")); alphabetDict.Insert(2, "abc", "ABC"); Assert.IsTrue(alphabetDict.ContainsKey("c")); Assert.AreEqual(2, alphabetDict.IndexOf("abc")); Assert.AreEqual(alphabetDict[2], "ABC"); Assert.AreEqual(27, alphabetDict.Count); Assert.IsTrue(alphabetDict.ContainsValue("ABC")); } [TestMethod] public void TestValueComparer() { var alphabetDict = GetAlphabetDictionary(); Assert.IsFalse(alphabetDict.ContainsValue("a")); Assert.IsTrue(alphabetDict.ContainsValue("a", StringComparer.OrdinalIgnoreCase)); } [TestMethod] public void TestSortByKeys() { var alphabetDict = GetAlphabetDictionary(); var reverseAlphabetDict = GetAlphabetDictionary(); Comparison stringReverse = ((x, y) => (String.Equals(x, y) ? 0 : String.Compare(x, y) >= 1 ? -1 : 1)); reverseAlphabetDict.SortKeys(stringReverse); for (int j = 0, k = 25; j < alphabetDict.Count; j++, k--) { var ascValue = alphabetDict.GetItem(j); var dscValue = reverseAlphabetDict.GetItem(k); Assert.AreEqual(ascValue.Key, dscValue.Key); Assert.AreEqual(ascValue.Value, dscValue.Value); } } 

    - ACTUALIZACIÓN -

    Fuente para esta y otras librerías .NET que faltan realmente útiles aquí: https://github.com/mattmc3/dotmore/blob/master/dotmore/Collections/Generic/OrderedDictionary.cs

    Para el registro, hay un KeyedCollection genérico que permite que los objetos sean indexados por un int y una clave. La clave debe estar embebida en el valor.

    Aquí hay un hallazgo extraño: el espacio de nombres System.Web.Util en System.Web.Extensions.dll contiene un OrderedDictionary genérico

     // Type: System.Web.Util.OrderedDictionary`2 // Assembly: System.Web.Extensions, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35 // Assembly location: C:\Windows\Microsoft.NET\Framework\v4.0.30319\System.Web.Extensions.dll namespace System.Web.Util { internal class OrderedDictionary : IDictionary, ICollection>, IEnumerable>, IEnumerable 

    No estoy seguro de por qué MS lo colocó allí en lugar del paquete System.Collections.Generic, pero supongo que puede copiar y pegar el código y usarlo (es interno, por lo que no puede usarlo directamente). Parece que la implementación usa un diccionario estándar y listas de clave / valor separadas. Muy claro…

    Por lo que vale, así es como lo resolví (editado para mejorar mi primer bash):

      public class PairList : List> { Dictionary itsIndex = new Dictionary(); public void Add(TKey key, TValue value) { Add(new KeyValuePair(key, value)); itsIndex.Add(key, Count-1); } public TValue Get(TKey key) { var idx = itsIndex[key]; return this[idx].Value; } } 

    Se puede inicializar así:

     var pairList = new PairList { { "pitcher", "Ken" }, { "catcher", "Brad"}, { "left fielder", "Stan"}, }; 

    y accedido así:

     foreach (var pair in pairList) { Console.WriteLine("position: {0}, player: {1}", pair.Key, pair.Value); } // guaranteed to print in the order of initialization 

    Un problema conceptual importante con una versión genérica de OrderedDictionary es que los usuarios de un OrderedDictionary esperarían poder indexarlo numéricamente utilizando un int , o mediante una búsqueda usando un TKey . Cuando el único tipo de clave era Object , como en el caso de OrderedDictionary no genérico, el tipo de argumento pasado al indexador sería suficiente para distinguir si se debe realizar el tipo de operación de indexación. Sin embargo, como está, no está claro cómo debería comportarse el indexador de un OrderedDictionary .

    Si las clases como Drawing.Point hubieran recomendado y seguido una regla de que las estructuras mutables por partes debieran exponer sus elementos mutables como campos en lugar de propiedades, y se abstengan de utilizar establecedores de propiedades que modifiquen this , un OrderedDictionary podría exponer eficientemente un Propiedad ByIndex que devolvió una estructura Indexer que contenía una referencia al diccionario, y tenía una propiedad indexada cuyo getter y setter llamarían GetByIndex y SetByIndex sobre ella. Por lo tanto, uno podría decir algo como MyDict.ByIndex[5] += 3; para agregar 3 al 6 ° elemento del diccionario. Desafortunadamente, para que el comstackdor acepte tal cosa, sería necesario hacer que la propiedad ByIndex devuelva una nueva instancia de clase en lugar de una estructura cada vez que se invoca, eliminando las ventajas que se obtendrían al evitar el boxeo. En vb.net, uno podría sortear ese problema usando una propiedad indexada (así MyDict.ByIndex[int] sería un miembro de MyDict , en lugar de requerir que MyDict.ByIndex sea ​​un miembro de MyDict que incluye un indexador), pero C # no permite tales cosas.

    Todavía podría haber valido la pena ofrecer un OrderedDictionary where TKey:class , pero gran parte de la razón para proporcionar generics en primer lugar era permitir su uso con tipos de valor.

    Para muchos propósitos, he encontrado que uno puede salir List> con una List> . (No si lo necesita para ampliar Dictionary , obviamente, y no si necesita una búsqueda de valor-clave superior a O (n)).

    Hay SortedDictionary . Aunque semánticamente cerca, no estoy afirmando que es lo mismo que OrderedDictionary simplemente porque no lo son. Incluso a partir de las características de rendimiento. Sin embargo, la diferencia muy interesante y bastante importante entre Dictionary (y, en esa medida, OrderedDictionary y las implementaciones proporcionadas en las respuestas) y SortedDictionary es que este último está utilizando un árbol binario debajo. Esta es una distinción fundamental porque hace que la clase sea inmune a las restricciones de memoria aplicadas a la clase genérica. Vea este hilo acerca de OutOfMemoryExceptions lanzado cuando la clase genérica se utiliza para manejar grandes conjuntos de pares clave-valor.

    ¿Cómo averiguar el valor máximo para el parámetro de capacidad pasado al constructor del diccionario para evitar OutOfMemoryException?

    Correcto, es una omisión desafortunada. Extraño el OrderedDict de Python

    Un diccionario que recuerda el orden en que se insertaron las claves por primera vez. Si una nueva entrada sobrescribe una entrada existente, la posición de inserción original no se modifica. Eliminar una entrada y reinsertarla lo moverá hasta el final.

    Así que escribí mi propia OrderedDictionary en C #. ¿Como funciona? Mantiene dos colecciones: un diccionario desordenado de vainilla y una lista ordenada de claves. With this solution, the standard dictionary operations keep their fast complexities, and look up by index is fast too.

    https://gist.github.com/hickford/5137384

    Here’s the interface

     ///  /// A dictionary that remembers the order that keys were first inserted. If a new entry overwrites an existing entry, the original insertion position is left unchanged. Deleting an entry and reinserting it will move it to the end. ///  /// The type of keys /// The type of values public interface IOrderedDictionary : IDictionary { ///  /// The value of the element at the given index. ///  TValue this[int index] { get; set; } ///  /// Find the position of an element by key. Returns -1 if the dictionary does not contain an element with the given key. ///  int IndexOf(TKey key); ///  /// Insert an element at the given index. ///  void Insert(int index, TKey key, TValue value); ///  /// Remove the element at the given index. ///  void RemoveAt(int index); } 

    As a follow up to the comment from @VB here’s an accessible implementation of the System.Runtime.Collections.OrderedDictionary< ,> . I was originally going to access it by reflection and provide it via a factory but the dll this is in does not seem to be very accessible at all so I just pulled the source itself.

    One thing to note is the indexer here will not throw KeyNotFoundException . I absolutely hate that convention and that was the 1 liberty i took in this implementation. If that’s important to you, just replace the line for return default(TValue); . Uses C# 6 ( compatible with Visual Studio 2013 )

     ///  /// System.Collections.Specialized.OrderedDictionary is NOT generic. /// This class is essentially a generic wrapper for OrderedDictionary. ///  ///  /// Indexer here will NOT throw KeyNotFoundException ///  public class OrderedDictionary : IDictionary, IDictionary { private readonly OrderedDictionary _privateDictionary; public OrderedDictionary() { _privateDictionary = new OrderedDictionary(); } public OrderedDictionary(IDictionary dictionary) { if (dictionary == null) return; _privateDictionary = new OrderedDictionary(); foreach (var pair in dictionary) { _privateDictionary.Add(pair.Key, pair.Value); } } public bool IsReadOnly => false; public int Count => _privateDictionary.Count; int ICollection.Count => _privateDictionary.Count; object ICollection.SyncRoot => ((ICollection)_privateDictionary).SyncRoot; bool ICollection.IsSynchronized => ((ICollection)_privateDictionary).IsSynchronized; bool IDictionary.IsFixedSize => ((IDictionary)_privateDictionary).IsFixedSize; bool IDictionary.IsReadOnly => _privateDictionary.IsReadOnly; ICollection IDictionary.Keys => _privateDictionary.Keys; ICollection IDictionary.Values => _privateDictionary.Values; void IDictionary.Add(object key, object value) { _privateDictionary.Add(key, value); } void IDictionary.Clear() { _privateDictionary.Clear(); } bool IDictionary.Contains(object key) { return _privateDictionary.Contains(key); } IDictionaryEnumerator IDictionary.GetEnumerator() { return _privateDictionary.GetEnumerator(); } void IDictionary.Remove(object key) { _privateDictionary.Remove(key); } object IDictionary.this[object key] { get { return _privateDictionary[key]; } set { _privateDictionary[key] = value; } } void ICollection.CopyTo(Array array, int index) { _privateDictionary.CopyTo(array, index); } public TValue this[TKey key] { get { if (key == null) throw new ArgumentNullException(nameof(key)); if (_privateDictionary.Contains(key)) { return (TValue) _privateDictionary[key]; } return default(TValue); } set { if (key == null) throw new ArgumentNullException(nameof(key)); _privateDictionary[key] = value; } } public ICollection Keys { get { var keys = new List(_privateDictionary.Count); keys.AddRange(_privateDictionary.Keys.Cast()); return keys.AsReadOnly(); } } public ICollection Values { get { var values = new List(_privateDictionary.Count); values.AddRange(_privateDictionary.Values.Cast()); return values.AsReadOnly(); } } public void Add(KeyValuePair item) { Add(item.Key, item.Value); } public void Add(TKey key, TValue value) { if (key == null) throw new ArgumentNullException(nameof(key)); _privateDictionary.Add(key, value); } public void Clear() { _privateDictionary.Clear(); } public bool Contains(KeyValuePair item) { if (item.Key == null || !_privateDictionary.Contains(item.Key)) { return false; } return _privateDictionary[item.Key].Equals(item.Value); } public bool ContainsKey(TKey key) { if (key == null) throw new ArgumentNullException(nameof(key)); return _privateDictionary.Contains(key); } public void CopyTo(KeyValuePair[] array, int arrayIndex) { if (array == null) throw new ArgumentNullException(nameof(array)); if (arrayIndex < 0) throw new ArgumentOutOfRangeException(nameof(arrayIndex)); if (array.Rank > 1 || arrayIndex >= array.Length || array.Length - arrayIndex < _privateDictionary.Count) throw new ArgumentException("Bad Copy ToArray", nameof(array)); var index = arrayIndex; foreach (DictionaryEntry entry in _privateDictionary) { array[index] = new KeyValuePair((TKey) entry.Key, (TValue) entry.Value); index++; } } public IEnumerator> GetEnumerator() { foreach (DictionaryEntry entry in _privateDictionary) { yield return new KeyValuePair((TKey) entry.Key, (TValue) entry.Value); } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } public bool Remove(KeyValuePair item) { if (false == Contains(item)) return false; _privateDictionary.Remove(item.Key); return true; } public bool Remove(TKey key) { if (key == null) throw new ArgumentNullException(nameof(key)); if (false == _privateDictionary.Contains(key)) return false; _privateDictionary.Remove(key); return true; } public bool TryGetValue(TKey key, out TValue value) { if (key == null) throw new ArgumentNullException(nameof(key)); var keyExists = _privateDictionary.Contains(key); value = keyExists ? (TValue) _privateDictionary[key] : default(TValue); return keyExists; } } 

    Pull requests/discussion accepted on GitHub

    I implemented generic OrderedDictionary by wraping around SortedList and adding private Dictionary _order . Then I created internal implementation of Comparer passing reference to the _order dictionary. Then I use this comparer for internal SortedList. This class keeps order of elements passed to constructor and order of additions.

    This implementation has almost the same BigO characteristics as SortedList since Adding and Removing to _order is O(1). Each element will take (according to the book ‘C# 4 in a Nutshell’, p. 292, table 7-1) additional memory space of 22 (overhead) + 4 (int order) + TKey size (let assume 8) = 34. Together with SortedList overhead of 2 bytes the total overhead is 36 bytes, while the same book says that non-generic OrderedDictionary has overhead of 59 bytes.

    If I pass sorted=true to constructor, then _order is not used at all, the OrderedDictionary is exactly SortedList with minor overhead for wrapping, if at all meaningful.

    I am going to store not-so-many large reference objects in the OrderedDictionary , so for me this c.36 bytes overhead is tolerable.

    The main code is below. The complete updated code is on this gist .

     public class OrderedList : IDictionary, IDictionary { private readonly Dictionary _order; private readonly SortedList _internalList; private readonly bool _sorted; private readonly OrderComparer _comparer; public OrderedList(IDictionary dictionary, bool sorted = false) { _sorted = sorted; if (dictionary == null) dictionary = new Dictionary(); if (_sorted) { _internalList = new SortedList(dictionary); } else { _order = new Dictionary(); _comparer = new OrderComparer(ref _order); _internalList = new SortedList(_comparer); // keep prder of the IDictionary foreach (var kvp in dictionary) { Add(kvp); } } } public OrderedList(bool sorted = false) : this(null, sorted) { } private class OrderComparer : Comparer { public Dictionary Order { get; set; } public OrderComparer(ref Dictionary order) { Order = order; } public override int Compare(TKey x, TKey y) { var xo = Order[x]; var yo = Order[y]; return xo.CompareTo(yo); } } private void ReOrder() { var i = 0; _order = _order.OrderBy(kvp => kvp.Value).ToDictionary(kvp => kvp.Key, kvp => i++); _comparer.Order = _order; _lastOrder = _order.Values.Max() + 1; } public void Add(TKey key, TValue value) { if (!_sorted) { _order.Add(key, _lastOrder); _lastOrder++; //very rare event if (_lastOrder == int.MaxValue) ReOrder(); } _internalList.Add(key, value); } public bool Remove(TKey key) { var result = _internalList.Remove(key); if (!_sorted) _order.Remove(key); return result; } // Other IDictionary<> + IDictionary members implementation wrapping around _internalList // ... }