¿La colección genérica de pares clave/valor preserva la orden de inserción?

Question

Estoy buscando algo así como un Diccionario < K, V > sin embargo, con la garantía de que conserva el orden de inserción. Dado que Dictionary es una tabla hash, no creo que lo haga.

¿Existe una colección genérica para esto o debo usar una de las antiguas colecciones de .NET 1.1?

Answer 1

No hay. Sin embargo, System.Collections.Specialized.OrderedDictionary debería resolver la mayoría de las necesidades.

EDITAR: Otra opción es convertir esto en un genérico. No lo he probado pero compila (C# 6) y debería funcionar. Sin embargo, seguirá teniendo las mismas limitaciones que Ondrej Petrzilka menciona en los comentarios a continuación.

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

Answer 2

Bueno, podría usar un List<KeyValuePair<K,V>>, que preservaría el orden ... sin embargo, perdería la funcionalidad de búsqueda del diccionario. ¿Por qué necesitas que se guarde la orden?

Answer 3

No es una clase OrderedDictionary que es un diccionario, pero puede ser indexada en orden de inserción, pero no es generified. No existe uno genérico en el marco de .Net actualmente.

He leído un comentario en alguna parte de alguien en el equipo de Net que dijeron que pueden poner en práctica una versión generified en el futuro, pero si es así, lo más probable sería llamado en lugar de OrderedDictionary para hacer su comportamiento más obvio.

EDIT: encontró la cita. Fue en la página de MSDN para OrderedDictionary, atribuido a David M. Kean de Microsoft:

Este tipo es realmente mal llamado; no es un diccionario 'ordenado' como tal, sino más bien un diccionario 'indexado'. Aunque hoy no existe una versión genérica equivalente de este tipo, si añadimos una en el futuro, es probable que la nombremos como tipo 'IndexedDictionary'.

Answer 4

Hay una implementación genérica en code project que viene con una cantidad razonable de casos de prueba.

El autor eligió un nombre bastante divertido (KeyedList) que hace que sea bastante difícil de encontrar.

Answer 5

Sé que está escribiendo C#, pero Java tiene una clase llamada LinkedHashMap que usa una LinkedList privada para mantener el orden de inserción de las claves. Si no puede encontrar una solución genérica adecuada, quizás sería un comienzo para implementar la suya propia.

Answer 6

Realmente hay uno, que es genérico y ha estado presente desde .net 2.0. Se llama KeyedCollection<TKey, TItem>. Sin embargo, tiene la restricción de que quiere construir las claves a partir de los valores, por lo que no es una colección genérica de pares clave/valor.

Si lo necesita como IDictionary<TKey, TItem>, tiene una propiedad .Dictionary.

Un aspecto un tanto menor que la que tengo con él es que es una clase abstracta y hay que hacerla una subclase e implementar:

protected abstract TKey GetKeyForItem(TItem item) 

Yo prefiero pasar una lambda en el constructor para este fin , pero de nuevo, supongo que un método virtual es un poco más rápido que un lambda (cualquier comentario sobre esto se agradece).

Answer 7

Código:

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

Salida:

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  

Answer 8

Otra opción para un/Valor par clave genérica que conserva la inserción es usar algo como:

Queue<KeyValuePair<string, string>> 

Esto sería una lista ordenada garantizada Puede encola y dequeue en una facción ordenada similar a Agregar/Eliminar de diccionario en lugar de cambiar el tamaño de una Matriz. A menudo puede servir como un término medio entre una matriz ordenada sin redimensionamiento (por inserción) y una lista de conversión de tamaño desordenada (por inserción).

Answer 9

Si necesita una complejidad constante de Add, Remove, ContainsKey y preservación de pedidos, entonces no existe tal genérico en .NET Framework 4.5.

Si estás de acuerdo con el código de tercera parte, echar un vistazo a mi repositorio (licencia MIT permisiva): https://github.com/OndrejPetrzilka/Rock.Collections

Hay OrderedDictionary<K,V> colección:

• código fuente basado en el clásico Dictionary<K,V> (de Core .NET)
• conserva orden de inserciones y permite reordenamiento manual de
• características revirtieron enumeración
• tiene mismas complejidades de operación como Dictionary<K,V>
• Add y Remove operaciones son ~ 20% más lento en comparación con Dictionary<K,V>
• consume 8 más bytes de memoria por artículo

Answer 10

Aquí hay un contenedor para no genéricoSystems.Collections.Specialized.OrderedDictionary tipo .

Este tipo devolverá secuencias de claves/valores/pares en orden de inserción, al igual que los hashes Ruby 2.0.

No requiere magia C# 6, cumple con IDictionary<TKey,TValue> (que también significa que el acceso a una clave no asignada arroja una excepción), y debe ser serializable.

Se le da el nombre 'IndexedDictionary' por nota en la respuesta de Adrián.

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