¿Ninguna implementación genérica de OrderedDictionary?

136

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

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

AdaTheDev
fuente
1
Aquí hay una implementación de un OrderedDictionary<T>: codeproject.com/Articles/18615/…
Tim Schmelter
Mi implementación de OrderedDictionary <T> tiene O (1) insertar / eliminar porque usa una LinkedList en lugar de ArrayList para mantener el orden de inserción: clintonbrennan.com/2013/12/…
Clinton
2
Si solo necesita poder iterar sobre las entradas en el orden en que se agregaron, entonces List <KeyValuePair <TKey, TValue >> puede ser lo suficientemente bueno. (De acuerdo, no es una solución general, pero es lo suficientemente buena para algunos propósitos.)
yoyo
1
Es una omisión desafortunada. Hay otros buenos tipos de datos Systems.Collections.Generic. Solicitemos OrderedDictionary<TKey,TValue>.NET 5. Como otros han señalado, el caso de que la clave sea int es degenerada y necesitará cuidados especiales.
Coronel Panic

Respuestas:

60

Tienes razón. No hay un equivalente genérico OrderedDictionaryen el marco en sí.

(Ese es el caso de .NET 4 también, por lo que yo sé).

¡Pero puedes votarlo en UserVoice de Visual Studio (04/10/2016)!

LukeH
fuente
95

Implementar un genérico OrderedDictionaryno es terriblemente difícil, pero lleva mucho tiempo innecesariamente y, francamente, esta clase es un gran descuido por parte de Microsoft. Hay varias formas de implementar esto, pero elegí usar a KeyedCollectionpara mi almacenamiento interno. También elegí implementar varios métodos para ordenar de la manera que lo List<T>hace, ya que esto es esencialmente un IList e IDictionary híbrido. He incluido mi implementación aquí para la posteridad.

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

// http://unlicense.org
using System;
using System.Collections.Generic;
using System.Collections.Specialized;

namespace mattmc3.Common.Collections.Generic {

    public interface IOrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IOrderedDictionary {
        new TValue this[int index] { get; set; }
        new TValue this[TKey key] { get; set; }
        new int Count { get; }
        new ICollection<TKey> Keys { get; }
        new ICollection<TValue> 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<TValue> comparer);
        new bool ContainsKey(TKey key);
        new IEnumerator<KeyValuePair<TKey, TValue>> 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<TKey, TValue> GetItem(int index);
        void SetItem(int index, TValue value);
    }

}

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

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

    /// <summary>
    /// 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.
    /// </summary>
    public class OrderedDictionary<TKey, TValue> : IOrderedDictionary<TKey, TValue> {

        #region Fields/Properties

        private KeyedCollection2<TKey, KeyValuePair<TKey, TValue>> _keyedCollection;

        /// <summary>
        /// Gets or sets the value associated with the specified key.
        /// </summary>
        /// <param name="key">The key associated with the value to get or set.</param>
        public TValue this[TKey key] {
            get {
                return GetValue(key);
            }
            set {
                SetValue(key, value);
            }
        }

        /// <summary>
        /// Gets or sets the value at the specified index.
        /// </summary>
        /// <param name="index">The index of the value to get or set.</param>
        public TValue this[int index] {
            get {
                return GetItem(index).Value;
            }
            set {
                SetItem(index, value);
            }
        }

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

        public ICollection<TKey> Keys {
            get {
                return _keyedCollection.Select(x => x.Key).ToList();
            }
        }

        public ICollection<TValue> Values {
            get {
                return _keyedCollection.Select(x => x.Value).ToList();
            }
        }

        public IEqualityComparer<TKey> Comparer {
            get;
            private set;
        }

        #endregion

        #region Constructors

        public OrderedDictionary() {
            Initialize();
        }

        public OrderedDictionary(IEqualityComparer<TKey> comparer) {
            Initialize(comparer);
        }

        public OrderedDictionary(IOrderedDictionary<TKey, TValue> dictionary) {
            Initialize();
            foreach (KeyValuePair<TKey, TValue> pair in dictionary) {
                _keyedCollection.Add(pair);
            }
        }

        public OrderedDictionary(IOrderedDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) {
            Initialize(comparer);
            foreach (KeyValuePair<TKey, TValue> pair in dictionary) {
                _keyedCollection.Add(pair);
            }
        }

        #endregion

        #region Methods

        private void Initialize(IEqualityComparer<TKey> comparer = null) {
            this.Comparer = comparer;
            if (comparer != null) {
                _keyedCollection = new KeyedCollection2<TKey, KeyValuePair<TKey, TValue>>(x => x.Key, comparer);
            }
            else {
                _keyedCollection = new KeyedCollection2<TKey, KeyValuePair<TKey, TValue>>(x => x.Key);
            }
        }

        public void Add(TKey key, TValue value) {
            _keyedCollection.Add(new KeyValuePair<TKey, TValue>(key, value));
        }

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

        public void Insert(int index, TKey key, TValue value) {
            _keyedCollection.Insert(index, new KeyValuePair<TKey, TValue>(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<TValue> comparer) {
            return this.Values.Contains(value, comparer);
        }

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

        public KeyValuePair<TKey, TValue> 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];
        }

        /// <summary>
        /// Sets the value at the index specified.
        /// </summary>
        /// <param name="index">The index of the value desired</param>
        /// <param name="value">The value to set</param>
        /// <exception cref="ArgumentOutOfRangeException">
        /// Thrown when the index specified does not refer to a KeyValuePair in this object
        /// </exception>
        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<TKey, TValue>(_keyedCollection[index].Key, value);
            _keyedCollection[index] = kvp;
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> 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);
        }

        /// <summary>
        /// Gets the value associated with the specified key.
        /// </summary>
        /// <param name="key">The key associated with the value to get.</param>
        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;
        }

        /// <summary>
        /// Sets the value associated with the specified key.
        /// </summary>
        /// <param name="key">The key associated with the value to set.</param>
        /// <param name="value">The the value to set.</param>
        public void SetValue(TKey key, TValue value) {
            var kvp = new KeyValuePair<TKey, TValue>(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<TKey> comparer) {
            _keyedCollection.SortByKeys(comparer);
        }

        public void SortKeys(Comparison<TKey> comparison) {
            _keyedCollection.SortByKeys(comparison);
        }

        public void SortValues() {
            var comparer = Comparer<TValue>.Default;
            SortValues(comparer);
        }

        public void SortValues(IComparer<TValue> comparer) {
            _keyedCollection.Sort((x, y) => comparer.Compare(x.Value, y.Value));
        }

        public void SortValues(Comparison<TValue> comparison) {
            _keyedCollection.Sort((x, y) => comparison(x.Value, y.Value));
        }
        #endregion

        #region IDictionary<TKey, TValue>

        void IDictionary<TKey, TValue>.Add(TKey key, TValue value) {
            Add(key, value);
        }

        bool IDictionary<TKey, TValue>.ContainsKey(TKey key) {
            return ContainsKey(key);
        }

        ICollection<TKey> IDictionary<TKey, TValue>.Keys {
            get { return Keys; }
        }

        bool IDictionary<TKey, TValue>.Remove(TKey key) {
            return Remove(key);
        }

        bool IDictionary<TKey, TValue>.TryGetValue(TKey key, out TValue value) {
            return TryGetValue(key, out value);
        }

        ICollection<TValue> IDictionary<TKey, TValue>.Values {
            get { return Values; }
        }

        TValue IDictionary<TKey, TValue>.this[TKey key] {
            get {
                return this[key];
            }
            set {
                this[key] = value;
            }
        }

        #endregion

        #region ICollection<KeyValuePair<TKey, TValue>>

        void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item) {
            _keyedCollection.Add(item);
        }

        void ICollection<KeyValuePair<TKey, TValue>>.Clear() {
            _keyedCollection.Clear();
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item) {
            return _keyedCollection.Contains(item);
        }

        void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) {
            _keyedCollection.CopyTo(array, arrayIndex);
        }

        int ICollection<KeyValuePair<TKey, TValue>>.Count {
            get { return _keyedCollection.Count; }
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
            get { return false; }
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item) {
            return _keyedCollection.Remove(item);
        }

        #endregion

        #region IEnumerable<KeyValuePair<TKey, TValue>>

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

        #endregion

        #region IEnumerable

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

        #endregion

        #region IOrderedDictionary

        IDictionaryEnumerator IOrderedDictionary.GetEnumerator() {
            return new DictionaryEnumerator<TKey, TValue>(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<TKey, TValue>(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<TKey, TItem> : KeyedCollection<TKey, TItem> {
        private const string DelegateNullExceptionMessage = "Delegate passed cannot be null";
        private Func<TItem, TKey> _getKeyForItemDelegate;

        public KeyedCollection2(Func<TItem, TKey> getKeyForItemDelegate)
            : base() {
            if (getKeyForItemDelegate == null) throw new ArgumentNullException(DelegateNullExceptionMessage);
            _getKeyForItemDelegate = getKeyForItemDelegate;
        }

        public KeyedCollection2(Func<TItem, TKey> getKeyForItemDelegate, IEqualityComparer<TKey> 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<TKey>.Default;
            SortByKeys(comparer);
        }

        public void SortByKeys(IComparer<TKey> keyComparer) {
            var comparer = new Comparer2<TItem>((x, y) => keyComparer.Compare(GetKeyForItem(x), GetKeyForItem(y)));
            Sort(comparer);
        }

        public void SortByKeys(Comparison<TKey> keyComparison) {
            var comparer = new Comparer2<TItem>((x, y) => keyComparison(GetKeyForItem(x), GetKeyForItem(y)));
            Sort(comparer);
        }

        public void Sort() {
            var comparer = Comparer<TItem>.Default;
            Sort(comparer);
        }

        public void Sort(Comparison<TItem> comparison) {
            var newComparer = new Comparer2<TItem>((x, y) => comparison(x, y));
            Sort(newComparer);
        }

        public void Sort(IComparer<TItem> comparer) {
            List<TItem> list = base.Items as List<TItem>;
            if (list != null) {
                list.Sort(comparer);
            }
        }
    }

    public class Comparer2<T> : Comparer<T> {
        //private readonly Func<T, T, int> _compareFunction;
        private readonly Comparison<T> _compareFunction;

        #region Constructors

        public Comparer2(Comparison<T> 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<TKey, TValue> : IDictionaryEnumerator, IDisposable {
        readonly IEnumerator<KeyValuePair<TKey, TValue>> impl;
        public void Dispose() { impl.Dispose(); }
        public DictionaryEnumerator(IDictionary<TKey, TValue> 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 permitirá publicar tanto código en una publicación), por lo que tendré que dejarlo para que escriba sus pruebas. Pero, dejé algunos de ellos para que puedas tener 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<string, string> GetAlphabetDictionary(IEqualityComparer<string> comparer = null) {
            OrderedDictionary<string, string> alphabet = (comparer == null ? new OrderedDictionary<string, string>() : new OrderedDictionary<string, string>(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<KeyValuePair<string, string>> GetAlphabetList() {
            var alphabet = new List<KeyValuePair<string, string>>();
            for (var a = Convert.ToInt32('a'); a <= Convert.ToInt32('z'); a++) {
                var c = Convert.ToChar(a);
                alphabet.Add(new KeyValuePair<string, string>(c.ToString(), c.ToString().ToUpper()));
            }
            Assert.AreEqual(26, alphabet.Count);
            return alphabet;
        }

        [TestMethod]
        public void TestAdd() {
            var od = new OrderedDictionary<string, string>();
            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<string, string>();

            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<string, string>();

            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<string> 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 bibliotecas de .NET faltantes realmente útiles aquí: https://github.com/mattmc3/dotmore/blob/master/dotmore/Collections/Generic/OrderedDictionary.cs

mattmc3
fuente
66
Por dominio público, ¿está preguntando si puede usarlo, modificarlo y tratarlo como si fuera suyo sin preocupaciones? Sí. Sentirse libre. Si te refieres a licenciarlo y alojarlo en algún lugar, no ... vive aquí en SO solo por ahora.
mattmc3
3
@ mattmc3 Gracias por su código, señor, pero su comentario sobre cuestiones de dominio público me preocupa, cuando dijo en el comentario: "Si se refiere a licenciarlo y alojarlo en algún lugar, no ... vive aquí en SO solo por ahora. " Con todo respeto (verdaderamente) al autor, ¿realmente tiene derecho a hacer esa restricción, una vez que haya publicado el código en SO? Por ejemplo, ¿alguno de nosotros realmente tiene derecho a restringir que nuestro código en SO se publique, por ejemplo, como un git gist? ¿Nadie?
Nicholas Petersen
66
@NicholasPetersen - Creo que entendiste mal. En respuesta directa al Coronel Panic, le informé que personalmente no lo licenciaba ni lo alojaba en ningún otro lugar. (En realidad, desde que lo mencionaste, hice una idea esencial: gist.github.com/mattmc3/6486878 ). Pero este es un código sin licencia. Tómalo y haz lo que quieras con él. Lo escribí 100% para mi uso personal. No está gravado. Disfrutar. De hecho, si alguien de Microsoft lee esto, espero que cumpla con su deber y finalmente lo ponga en la próxima versión de .NET. No se requieren atribuciones.
mattmc3
2
¿Y si TKeyes así int? ¿Cómo this[]funcionará en tal caso?
VB
2
@klicker: solo use la indexación de estilo de matriz regular El orden de inserción se mantiene como una lista. La conversión de tipo maneja la determinación de si desea indexar con un int o hacer referencia a través del tipo de clave. Si el tipo de clave es un int, debe usar el método GetValue ().
mattmc3
32

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

Guillaume
fuente
2
¡Esto no mantiene el orden de inicialización como OrderedDictionary! Mira mi respuesta.
JoelFan
14
Mantiene el orden de agregar / insertar.
Guillaume
sí lo hace .. en lo que ustedes ya ha recibido esta idea de que el KeyedCollection ordena los elementos ... estoy topé con esta segunda vez
Boppity Bop
1
Definitivamente mantiene el orden de inicialización. Los enlaces útiles incluyen stackoverflow.com/a/11802824/9344 y geekswithblogs.net/NewThingsILearned/archive/2010/01/07/… .
Ted
+1, esta parece ser la mejor solución en el marco. Sin embargo, tener que implementar la clase abstracta para cada par de tipos que desea usar es una especie de arrastre. Podría hacerlo con una implementación genérica que requiere una interfaz, pero luego tendría que implementar la interfaz en cada tipo que quisiera poder almacenar.
DCShannon
19

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<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable

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

Ismail Degani
fuente
2
System.Runtime.Collectionstambién contiene un interno OrderedDictionary<TKey, TValue>que simplemente envuelve la versión no genérica
VB
1
System.Web.Util.OrderedDictionary<TKey, TValue>se implementa internamente alrededor de genéricos Dictionary. Curiosamente no se implementa IListperoICollection<KeyValuePair<TKey, TValue>>
Mikhail
1
@rboy Como dije, era interno y envolvía la implementación no genérica. Pero fue hace más de 3 años ... Para tamaños inferiores a un par de cientos, la búsqueda lineal List<KeyValuePair<TKey,TValue>>será competitiva debido al patrón de acceso a la memoria, para tamaños más grandes solo use la misma lista + Dictionary<TKey,int>como búsqueda. AFAIK no existe una estructura de datos que funcione mejor en términos de velocidad / memoria en BigO.
VB
1
@rboy aquí está el enlace al genérico , hace referencia a uno no genérico que usa HashTable. Realmente apuesto a que para los tamaños pequeños, el uso de la búsqueda lineal en listas / matrices genéricas será más rápido.
VB
1
@PeterMortensen System.Collections.Specialized.OrderedDictionaryno es un tipo genérico. Mira ma, no hay corchetes angulares en la página del documento que
vinculaste
17

Por lo que vale, así es como lo resolví:

   public class PairList<TKey, TValue> : List<KeyValuePair<TKey, TValue>> {
        Dictionary<TKey, int> itsIndex = new Dictionary<TKey, int>();

        public void Add(TKey key, TValue value) {
            Add(new KeyValuePair<TKey, TValue>(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<string, string>
    {
        { "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
JoelFan
fuente
3
¡Gracias! No me había dado cuenta de que los inicializadores de colección eran solo una sintaxis especial para los Addmétodos.
Sam
10
Esto no es un diccionario. Diccionario significa indexación con clave y sin claves duplicadas .
nawfal
sin embargo, si le sucede a la indexación no se necesita por la llave (que no es demasiado difícil añadir) y las teclas dupliacte esto viene muy bien
Stijn
1
Tiene un problema con las llamadas de código pairList.Add(new KeyValuePair<K,V>())(es decir, el método en la Listclase). En ese caso, el itsIndexdiccionario no se actualiza y ahora la lista y el diccionario no están sincronizados. Podría ocultar el List.Addmétodo creando un new PairList.Add(KeyValuePair<K,V>)método, o podría usar la composición en lugar de la herencia y simplemente implementar todos los Listmétodos nuevamente ... mucho más código ...
neizan
1
@nawfal, para abordar su inquietud, uno podría agregar un cheque como: if (itsindex.Contains(key)) return;al comienzo de Addpara evitar duplicados
JoelFan
14

Un problema conceptual importante con una versión genérica de OrderedDictionaryes que los usuarios de a OrderedDictionary<TKey,TValue>esperarían poder indexarlo numéricamente usando una into mediante una búsqueda usando a TKey. Cuando el único tipo de clave era Object, como era el caso con los no genéricos OrderedDictionary, el tipo de argumento pasado al indexador sería suficiente para distinguir si qué tipo de operación de indexación debería realizarse. Sin embargo, tal como están las cosas, no está claro cómo OrderedDictionary<int, TValue>debería comportarse el indexador de un .

Si las clases como Drawing.Pointhabían recomendado y seguido una regla de que las estructuras mutables por partes deberían exponer sus elementos mutables como campos en lugar de propiedades, y abstenerse de usar establecedores de propiedades que modifiquen this, entonces OrderedDictionary<TKey,TValue>podría exponer eficientemente una ByIndexpropiedad que devolvió una Indexerestructura que tenía una referencia a el diccionario, y tenía una propiedad indexada cuyo getter y setter llamarían GetByIndexy SetByIndexsobre él. Por lo tanto, se podría decir algo así como MyDict.ByIndex[5] += 3;agregar 3 al sexto elemento del diccionario.

Desafortunadamente, para que el compilador acepte tal cosa, sería necesario hacer que la ByIndexpropiedad 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 solucionar ese problema utilizando una propiedad indexada con nombre (por MyDict.ByIndex[int]lo que sería un miembro MyDict, en lugar de requerir MyDict.ByIndexque sea un miembro MyDictque incluya un indexador), pero C # no permite tales cosas.

Todavía podría haber valido la pena ofrecer un OrderedDictionary<TKey,TValue> where TKey:class, pero en gran parte la razón para proporcionar genéricos en primer lugar fue permitir su uso con tipos de valor.

Super gato
fuente
Un buen punto es que intlas teclas de tipo presentan un desafío, pero podría evitarse siguiendo el ejemplo del SortedList<TKey, TValue>tipo relacionado : solo admite teclas con [...], y requiere el uso de .Values[...]para acceso por índice. ( SortedDictionary<TKey, TValue>por el contrario, que no está optimizado para el acceso indexado, requiere el uso de .ElementAt(...).Value)
mklement0
7

Para muchos propósitos, he encontrado que uno puede sobrevivir con un List<KeyValuePair<K, V>>. (No, si lo necesita para ampliar Dictionary, obviamente, y no si necesita algo mejor que la búsqueda de valor-clave O (n)).

David Moles
fuente
¡Acabo de llegar a la misma conclusión!
Peter
1
Como dije, "para muchos propósitos".
David Moles
2
También puede usar a Tuple<T1, T2>si no tienen una relación clave-valor.
cdmckay
1
¿Cuál es el punto de tener pares de valores clave si no puede indexar por clave?
DCShannon
1
@DCShannon Aún puede asignar claves a valores, simplemente no puede buscarlas más rápido que O (n) (o tratar automáticamente con claves duplicadas). Para valores pequeños de n que a veces es lo suficientemente bueno, especialmente en situaciones en las que comúnmente se itera a través de todas las claves de todos modos.
David Moles
5

Existe SortedDictionary<TKey, TValue>. Aunque semánticamente cerca, no estoy afirmando que sea lo mismo que OrderedDictionarysimplemente porque no lo son. Incluso a partir de las características de rendimiento. Sin embargo, la diferencia muy interesante y bastante importante entre Dictionary<TKey, TValue>(y hasta ese punto OrderedDictionaryy las implementaciones proporcionadas en las respuestas) y SortedDictionaryes que este último está utilizando un árbol binario debajo. Esta es una distinción crítica porque hace que la clase sea inmune a las restricciones de memoria aplicadas a la clase genérica. Vea este hilo sobre el OutOfMemoryExceptionslanzamiento cuando la clase genérica se utiliza para manejar un gran conjunto de pares clave-valor.

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

Schultz9999
fuente
¿Hay alguna forma de obtener claves o valores de a SortedDictionary en el orden en que se agregaron ? Eso es lo que OrderedDictionarypermite. Concepto diferente al ordenado . (He cometido este error en el pasado; pensé que proporcionar un comparador al constructor OrderedDictionary lo ordenaría, pero todo lo que hace con el comparador es determinar la igualdad de clave; por ejemplo, el comparador insensible a cadenas permite la búsqueda de claves insensibles a cadenas)
ToolmakerSteve
5

Correcto, es una omisión desafortunada. Echo de menos el Orden ordenado 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 volver a insertarla la moverá hasta el final.

Entonces escribí mi propia OrderedDictionary<K,V>clase en C #. ¿Como funciona? Mantiene dos colecciones: un diccionario vainilla desordenado y una lista ordenada de claves. Con esta solución, las operaciones de diccionario estándar mantienen su complejidad rápida, y la búsqueda por índice también es rápida.

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

Aquí está la interfaz

/// <summary>
/// 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.
/// </summary>
/// <typeparam name="TKey">The type of keys</typeparam>
/// <typeparam name="TValue">The type of values</typeparam>
public interface IOrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    /// <summary>
    /// The value of the element at the given index.
    /// </summary>
    TValue this[int index] { get; set; }

    /// <summary>
    /// Find the position of an element by key. Returns -1 if the dictionary does not contain an element with the given key.
    /// </summary>
    int IndexOf(TKey key);

    /// <summary>
    /// Insert an element at the given index.
    /// </summary>
    void Insert(int index, TKey key, TValue value);

    /// <summary>
    /// Remove the element at the given index.
    /// </summary>
    void RemoveAt(int index);
}
Coronel Panic
fuente
3

Como seguimiento al comentario de @VB, aquí hay una implementación accesible de System.Runtime.Collections.OrderedDictionary <,> . Originalmente iba a acceder a él por reflexión y proporcionarlo a través de una fábrica, pero el dll en el que se encuentra no parece ser muy accesible, así que simplemente saqué la fuente en sí.

Una cosa a tener en cuenta es que el indexador aquí no arrojará KeyNotFoundException . Absolutamente odio esa convención y esa fue la primera libertad que tomé en esta implementación. Si eso es importante para usted, simplemente reemplace la línea para return default(TValue);. Utiliza C # 6 ( compatible con Visual Studio 2013 )

/// <summary>
///     System.Collections.Specialized.OrderedDictionary is NOT generic.
///     This class is essentially a generic wrapper for OrderedDictionary.
/// </summary>
/// <remarks>
///     Indexer here will NOT throw KeyNotFoundException
/// </remarks>
public class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary
{
    private readonly OrderedDictionary _privateDictionary;

    public OrderedDictionary()
    {
        _privateDictionary = new OrderedDictionary();
    }

    public OrderedDictionary(IDictionary<TKey, TValue> 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<TKey> Keys
    {
        get
        {
            var keys = new List<TKey>(_privateDictionary.Count);

            keys.AddRange(_privateDictionary.Keys.Cast<TKey>());

            return keys.AsReadOnly();
        }
    }

    public ICollection<TValue> Values
    {
        get
        {
            var values = new List<TValue>(_privateDictionary.Count);

            values.AddRange(_privateDictionary.Values.Cast<TValue>());

            return values.AsReadOnly();
        }
    }

    public void Add(KeyValuePair<TKey, TValue> 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<TKey, TValue> 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<TKey, TValue>[] 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, TValue>((TKey) entry.Key, (TValue) entry.Value);
            index++;
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (DictionaryEntry entry in _privateDictionary)
        {
            yield return 
                new KeyValuePair<TKey, TValue>((TKey) entry.Key, (TValue) entry.Value);
        }
    }

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

    public bool Remove(KeyValuePair<TKey, TValue> 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;
    }
}

Solicitudes de extracción / discusión aceptadas en GitHub

Chris Marisic
fuente
3

Para aquellos que buscan una opción de paquete "oficial" en NuGet, se ha aceptado una implementación de un OrderedDictionary genérico en .NET CoreFX Lab. Si todo va bien, el tipo eventualmente será aprobado e integrado al repositorio principal de .NET CoreFX.

Existe la posibilidad de que esta implementación sea rechazada.

La implementación comprometida se puede consultar aquí https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary.cs

El paquete NuGet que definitivamente tiene este tipo disponible para su uso se puede encontrar aquí https://www.nuget.org/packages/Microsoft.Experimental.Collections/1.0.6-e190117-3

O puede instalar el paquete dentro de Visual Studio. Busque el paquete "Microsoft.Experimental.Collections" y asegúrese de que la casilla de verificación "Incluir versión preliminar" esté seleccionada.

Actualizará esta publicación siempre que el tipo esté oficialmente disponible.

Charlie
fuente
¿Puedes estimar cuándo se lanzará?
mvorisek
No estoy participando en el desarrollo de esta biblioteca, así que desafortunadamente no tengo idea. Es probable que sea una colección de framework integrada si alguna vez se "aprueba".
charlie
1

Implementé un genérico OrderedDictionary<TKey, TValue>envolviendo SortedList<TKey, TValue>y agregando un privado Dictionary<TKey, int> _order. Luego creé una implementación interna de Comparer<TKey>, pasando una referencia al diccionario _order. Luego uso este comparador para la SortedList interna. Esta clase mantiene el orden de los elementos pasados ​​al constructor y el orden de las adiciones.

Esta implementación tiene casi las mismas características grandes de O que SortedList<TKey, TValue>desde que agregar y eliminar a _order es O (1). Cada elemento tomará (de acuerdo con el libro 'C # 4 in a Nutshell', p. 292, tabla 7-1) espacio de memoria adicional de 22 (sobrecarga) + 4 (int orden) + tamaño de la tecla T (supongamos que 8) = 34 Junto con SortedList<TKey, TValue>la sobrecarga de dos bytes, la sobrecarga total es de 36 bytes, mientras que el mismo libro dice que no genérico OrderedDictionarytiene una sobrecarga de 59 bytes.

Si paso sorted=trueal constructor, entonces _order no se usa en absoluto, OrderedDictionary<TKey, TValue>es exactamente SortedList<TKey, TValue>con una sobrecarga menor para el ajuste, si es que tiene sentido.

Voy a almacenar no tantos objetos de referencia grandes en el OrderedDictionary<TKey, TValue>, así que para mí esto ca. Sobrecarga de 36 bytes es tolerable.

El código principal está abajo. El código actualizado completo está en esta esencia .

public class OrderedList<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary
{
    private readonly Dictionary<TKey, int> _order;
    private readonly SortedList<TKey, TValue> _internalList;

    private readonly bool _sorted;
    private readonly OrderComparer _comparer;

    public OrderedList(IDictionary<TKey, TValue> dictionary, bool sorted = false)
    {
        _sorted = sorted;

        if (dictionary == null)
            dictionary = new Dictionary<TKey, TValue>();

        if (_sorted)
        {
            _internalList = new SortedList<TKey, TValue>(dictionary);
        }
        else
        {
            _order = new Dictionary<TKey, int>();
            _comparer = new OrderComparer(ref _order);
            _internalList = new SortedList<TKey, TValue>(_comparer);
            // Keep order of the IDictionary
            foreach (var kvp in dictionary)
            {
                Add(kvp);
            }
        }
    }

    public OrderedList(bool sorted = false)
        : this(null, sorted)
    {
    }

    private class OrderComparer : Comparer<TKey>
    {
        public Dictionary<TKey, int> Order { get; set; }

        public OrderComparer(ref Dictionary<TKey, int> 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
    // ...
}
VB
fuente
Hay al menos cuatro casos de uso diferentes que puedo ver para algo como OrderedDictionary, con respecto a las inserciones o eliminaciones: (1) Nunca habrá eliminaciones; (2) habrá eliminaciones, pero lo importante es que los elementos se enumeren en el orden agregado; no hay necesidad de acceso por índice; (3) el índice numérico de un artículo debe (o al menos puede) permanecer constante, y no se agregarán más de 2 mil millones de artículos durante la vida útil de la colección, por lo que si se elimina el artículo # 7, nunca más habrá un artículo 7; (4) el índice de un artículo debe ser su rango con respecto a los sobrevivientes.
supercat
1
Los escenarios # 1 podrían manejarse usando una matriz en paralelo con el Dictionary. Los escenarios # 2 y # 3 podrían manejarse haciendo que cada elemento mantenga un índice que indique cuándo se agregó y los enlaces a los elementos agregados antes o después. El escenario # 4 es el único que parecería que no debería ser capaz de lograr el rendimiento O (1) para operaciones en secuencia arbitraria. Dependiendo de los patrones de uso, # 4 puede ser ayudado mediante el uso de varias estrategias de actualización diferida (mantener los recuentos en un árbol y hacer que los cambios en un nodo invaliden en lugar de actualizar el nodo y sus padres).
supercat
1
Internal SortedList tiene elementos en orden de inserción debido al uso de un comparador personalizado. Puede ser lento, pero su comentario sobre la enumeración es incorrecto. Mostrar las pruebas sobre enumeración ...
VB
1
¿De qué línea con ToDictionary estás hablando? No afecta a la lista interna, solo ordena el diccionario.
VB
1
@VB Disculpas, me perdí las dos. Como tal, no lo he probado. Entonces el único problema sería con la suma. Dos búsquedas de diccionario, así como dos inserciones. Cancelaré el voto negativo.
nawfal