Nenhuma implementação genérica do OrderedDictionary?

136

Não parece haver uma implementação genérica de OrderedDictionary(que está no System.Collections.Specializedespaço para nome) no .NET 3.5. Há um que estou perdendo?

Encontrei implementações disponíveis para fornecer a funcionalidade, mas me perguntei se / por que não há uma implementação genérica pronta para uso e se alguém sabe se é algo no .NET 4.0?

AdaTheDev
fonte
1
Aqui está uma implementação de um OrderedDictionary<T>: codeproject.com/Articles/18615/…
Tim Schmelter
Minha implementação do OrderedDictionary <T> tem O (1) insert / delete porque ele usa uma LinkedList em vez de ArrayList para manter a ordem de inserção: clintonbrennan.com/2013/12/…
Clinton
2
Se você apenas precisar percorrer as entradas na ordem em que foram adicionadas, a List <KeyValuePair <TKey, TValue >> pode ser boa o suficiente. (Concedido, não uma solução geral, mas bom o suficiente para algumas finalidades.)
yoyo
1
É uma omissão infeliz. Existem outros bons tipos de dados Systems.Collections.Generic. Vamos solicitar o OrderedDictionary<TKey,TValue>.NET 5. Como outros já apontaram, o caso da chave é um int degenerado e precisará de cuidados especiais.
Coronel Panic

Respostas:

60

Você está certo. Não há equivalente genérico deOrderedDictionary no próprio framework.

(Esse também ainda é o caso do .NET 4, pelo que sei.)

Mas você pode votar no UserVoice do Visual Studio (04-10-2016)!

LukeH
fonte
95

A implementação de um genérico OrderedDictionarynão é terrivelmente difícil, mas consome tempo desnecessariamente e, francamente, essa classe é uma grande supervisão da parte da Microsoft. Existem várias maneiras de implementar isso, mas eu escolhi usar a KeyedCollectionpara meu armazenamento interno. Também escolhi implementar vários métodos para classificar da maneira que List<T>faz, pois esse é essencialmente um IList e um IDictionary híbridos. Eu incluí minha implementação aqui para posteridade.

Aqui está a interface. Observe que ele inclui System.Collections.Specialized.IOrderedDictionary, que é a versão não genérica dessa interface fornecida pela 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);
    }

}

Aqui está a implementação junto com as classes 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; } }
    }
}

E nenhuma implementação seria completa sem alguns testes (mas, tragicamente, o SO não permitirá que eu publique tanto código em um post), então terei que deixar você escrever seus testes. Mas deixei alguns deles para que você pudesse ter uma idéia de como ele 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);
            }
        }

- ATUALIZAÇÃO -

Fonte para esta e outras bibliotecas principais do .NET ausentes realmente úteis aqui: https://github.com/mattmc3/dotmore/blob/master/dotmore/Collections/Generic/OrderedDictionary.cs

mattmc3
fonte
6
Por domínio público, você está perguntando se pode usá-lo, modificá-lo e tratá-lo como se fosse seu sem preocupações - sim. Fique à vontade. Se você quer licenciá-lo e hospedá-lo em algum lugar - não ... ele vive aqui no SO apenas por enquanto.
mattmc3
3
@ mattmc3 Obrigado pelo seu código, senhor, mas seu comentário sobre questões de domínio público me preocupa, quando você disse no comentário: "Se você quer licenciá-lo e hospedá-lo em algum lugar - não ... ele mora aqui no SO apenas por enquanto. " Com todo respeito (realmente destinado) ao autor, você realmente tem o direito de fazer essa restrição, depois de publicar o código no SO ??? Por exemplo, algum de nós realmente tem o direito de impedir que nosso código seja publicado, por exemplo, como um git git? Qualquer um?
Nicholas Petersen
6
@NicholasPetersen - Eu acho que você não entendeu. Em resposta direta ao coronel Panic, informei-o que pessoalmente não o licenciei ou hospedei em nenhum outro lugar. (Na verdade, desde que você mencionou, eu criei uma essência: gist.github.com/mattmc3/6486878 ). Mas este é um código sem licença. Pegue e faça o que quiser com ele. Eu escrevi 100% para meu uso pessoal. Não tem ônus. Aproveitar. De fato, se alguém da Microsoft ler isso, espero totalmente que cumpra seu dever e finalmente o coloque no próximo lançamento do .NET. Não são necessárias atribuições.
precisa saber é o seguinte
2
E se TKeyfor int? Como this[]vai funcionar nesse caso?
VB
2
@ Klicker - Basta usar a indexação de estilo de matriz regular. A ordem de inserção é mantida como uma lista. A conversão de tipo manipula a determinação de se você deseja indexar com um int ou fazer referência através do tipo da chave. Se o tipo da chave for int, você precisará usar o método GetValue ().
18113 mattmc3
32

Para o registro, existe um KeyedCollection genérico que permite que os objetos sejam indexados por um int e uma chave. A chave deve ser incorporada no valor.

Guillaume
fonte
2
Isso não mantém a ordem de inicialização como OrderedDictionary! Confira minha resposta.
JoelFan
14
Ele mantém a ordem de adição / inserção.
Guillaume
sim ele faz .. onde é que vocês tenho a noção de que o KeyedCollection classifica itens ... Eu sou deparei com este segundo tempo
Boppity Bop
1
Definitivamente, mantém a ordem de inicialização. Os links úteis incluem stackoverflow.com/a/11802824/9344 e geekswithblogs.net/NewThingsILearned/archive/2010/01/07/… .
Ted
+1, esta parece ser a melhor solução na estrutura. Porém, ter que implementar a classe abstrata para cada par de tipos que você deseja usar é meio chato. Você poderia fazer isso com uma implementação genérica que requer uma interface, mas seria necessário implementar a interface em cada tipo que você deseja armazenar.
DCShannon
19

Aqui está uma descoberta bizarra: o espaço para nome System.Web.Util em System.Web.Extensions.dll contém um 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

Não sei por que a MS o colocou lá em vez do pacote System.Collections.Generic, mas presumo que você possa simplesmente copiar e colar o código e usá-lo (é interno, por isso não pode usá-lo diretamente). Parece que a implementação usa um dicionário padrão e listas de chave / valor separadas. Bem direto...

Ismail Degani
fonte
2
System.Runtime.Collectionstambém contém um interno OrderedDictionary<TKey, TValue>que envolve apenas a versão não genérica
VB
1
System.Web.Util.OrderedDictionary<TKey, TValue>é implementado internamente em torno de genéricos Dictionary. Estranhamente, ele não implementa, IListmasICollection<KeyValuePair<TKey, TValue>>
Mikhail
1
@rboy Como eu disse - foi interno e envolveu a implementação não genérica. Mas foi há mais de 3 anos ... Para tamanhos abaixo de algumas centenas, a pesquisa linear List<KeyValuePair<TKey,TValue>>será competitiva devido ao padrão de acesso à memória, para tamanhos maiores, use a mesma lista + Dictionary<TKey,int>como uma pesquisa. AFAIK não existe uma estrutura de dados com melhor desempenho em termos de velocidade / memória no BigO.
VB
1
@rboy aqui está o link para o genérico , ele faz referência a um não genérico que usa HashTable. Eu realmente aposto que para tamanhos pequenos, usando a pesquisa linear em listas / matrizes genéricas, será mais rápido.
VB
1
@PeterMortensen System.Collections.Specialized.OrderedDictionarynão é um tipo genérico. Veja ma, sem colchetes angulares na página do documento que você vinculou: P
user7610 4/19/19
17

Pelo que vale, aqui está como eu resolvi:

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

Pode ser inicializado assim:

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

e acessado assim:

foreach (var pair in pairList)
{
    Console.WriteLine("position: {0}, player: {1}",
        pair.Key, pair.Value);
}

// Guaranteed to print in the order of initialization
JoelFan
fonte
3
Obrigado! Eu não tinha percebido que inicializadores de coleção eram apenas sintaxe especial para Addmétodos.
19412 Sam
10
Este não é um dicionário. Dicionário significa indexação por chave e sem chaves duplicadas .
Nawfal # 31/13
ainda se acontecer de indexação não precisa de chave (o que não é muito difícil para adicionar) e as chaves dupliacte isso vem a calhar
Stijn
1
Você tem um problema com chamadas de código pairList.Add(new KeyValuePair<K,V>())(ou seja, o método na Listclasse). Nesse caso, o itsIndexdicionário não é atualizado e agora a lista e o dicionário estão fora de sincronia. Podia esconder o List.Addmétodo por criar um new PairList.Add(KeyValuePair<K,V>)método, ou poderia usar composição em vez de herança e apenas implementar todos os Listmétodos novamente ... um código muito mais ...
neizan
1
@nawfal, para resolver a sua preocupação, apenas um poderia adicionar uma verificação como: if (itsindex.Contains(key)) return;para o início do Addpara evitar duplicatas
JoelFan
14

Um grande problema conceitual com uma versão genérica de OrderedDictionaryé que os usuários de a OrderedDictionary<TKey,TValue>esperariam poder indexá-lo numericamente usando um intou pesquisando usando a TKey. Quando o único tipo de chave era Object, como foi o caso não genérico OrderedDictionary, o tipo de argumento passado para o indexador seria suficiente para distinguir se o tipo de operação de indexação deveria ser executada. No entanto, não está claro como o indexador de um OrderedDictionary<int, TValue>deve se comportar.

Se classes como Drawing.Point recomendaram e seguiram uma regra em que estruturas mutáveis ​​por partes deveriam expor seus elementos mutáveis ​​como campos, em vez de propriedades, e se absterem de usar setters de propriedades que modificam this, então um OrderedDictionary<TKey,TValue>poderia expor com eficiência uma ByIndexpropriedade que retornasse uma Indexerestrutura que continha uma referência a o dicionário e tinha uma propriedade indexada cujo getter e setter chamariam GetByIndexe SetByIndexsobre ele. Assim, pode-se dizer algo como MyDict.ByIndex[5] += 3;adicionar 3 ao sexto elemento do dicionário.

Infelizmente, para o compilador aceitar uma coisa dessas, seria necessário fazer com que a ByIndexpropriedade retornasse uma nova instância de classe em vez de uma estrutura toda vez que for chamada, eliminando as vantagens que uma pessoa obteria ao evitar o boxe.

No VB.NET, era possível contornar esse problema usando uma propriedade indexada nomeada (portanto, MyDict.ByIndex[int]seria um membro de MyDict, em vez de exigir MyDict.ByIndexque ele seja um membro MyDictque inclui um indexador), mas o C # não permite tais coisas.

Ainda poderia valer a pena oferecer um OrderedDictionary<TKey,TValue> where TKey:class, mas grande parte do motivo para fornecer genéricos em primeiro lugar era permitir o uso deles com tipos de valor.

supercat
fonte
É bom ressaltar que intas chaves do tipo representam um desafio, mas isso pode ser evitado seguindo o exemplo do SortedList<TKey, TValue>tipo relacionado : suporte chaves apenas com [...]e requer o uso de .Values[...]para acesso pelo índice. ( SortedDictionary<TKey, TValue>Em contraste, o que não está optimizado para o acesso indexada, requer o uso de .ElementAt(...).Value)
mklement0
7

Para muitos propósitos, descobri que se pode sobreviver com um List<KeyValuePair<K, V>>. (Não se você precisar estender Dictionary, obviamente, e não se precisar melhor do que a pesquisa de valor-chave O (n).)

David Moles
fonte
Apenas cheguei à mesma conclusão!
Peter
1
Como eu disse, "para muitos propósitos".
David Moles
2
Você também pode usar um Tuple<T1, T2>se eles não tiverem um relacionamento de valor-chave.
cdmckay
1
Qual é o sentido de ter pares de valores-chave se você não pode indexar por chave?
DCShannon
1
@DCShannon Você ainda pode mapear chaves para valores, mas não pode procurá-las mais rápido que O (n) (ou lidar automaticamente com chaves duplicadas). Para pequenos valores de n, isso às vezes é bom o suficiente, especialmente em situações nas quais você normalmente está iterando todas as chaves.
David Moles
5

Existe SortedDictionary<TKey, TValue>. Embora semanticamente próximo, não estou afirmando que é o mesmo que OrderedDictionarysimplesmente porque não é. Mesmo a partir de características de desempenho. No entanto, a diferença muito interessante e muito importante entre Dictionary<TKey, TValue>(e nessa extensão OrderedDictionarye implementações fornecidas nas respostas) e SortedDictionaryé que o último está usando a árvore binária por baixo. Essa é uma distinção crítica porque torna a classe imune a restrições de memória aplicadas à classe genérica. Veja este tópico sobreOutOfMemoryExceptions lançada quando a classe genérica é usada para lidar com um grande conjunto de pares de valores-chave.

Como descobrir o valor máximo para o parâmetro de capacidade passado ao construtor Dictionary para evitar OutOfMemoryException?

Schultz9999
fonte
Existe uma maneira de obter chaves ou valores de a SortedDictionary na ordem em que foram adicionados ? Isso é o que OrderedDictionarypermite. Conceito diferente do que classificado . (Eu cometi esse erro no passado; eu pensei que fornecer um construtor Comparer to OrderedDictionary o classificaria, mas tudo o que ele faz com o Comparer é determinar a igualdade de chaves; por exemplo, comparador insensível a cadeias permite a pesquisa de chaves insensíveis a cadeias.)
Você está em
5

Certo, é uma omissão infeliz. Sinto falta do OrderedDict do Python

Um dicionário que lembra a ordem em que as chaves foram inseridas pela primeira vez. Se uma nova entrada substitui uma entrada existente, a posição de inserção original permanece inalterada. A exclusão de uma entrada e a reinserção a moverá para o final.

Então, eu escrevi minha própria OrderedDictionary<K,V>classe em c #. Como funciona? Ele mantém duas coleções - um dicionário não ordenado de baunilha e uma lista ordenada de chaves. Com esta solução, as operações padrão de dicionário mantêm suas complexidades rápidas e a pesquisa por índice também é rápida.

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

Aqui está a interface

/// <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
fonte
3

Como acompanhamento do comentário de @VB, aqui está uma implementação acessível do System.Runtime.Collections.OrderedDictionary <,> . Inicialmente, eu ia acessá-lo por reflexão e fornecê-lo através de uma fábrica, mas a dll em que está inserida não parece ser muito acessível, então apenas puxei a própria fonte.

Uma coisa a observar é que o indexador aqui não será lançado KeyNotFoundException . Eu absolutamente odeio essa convenção e essa foi a liberdade que tomei nesta implementação. Se isso é importante para você, basta substituir a linha por return default(TValue);. Usa C # 6 ( compatível com o 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;
    }
}

Solicitações / discussões de recebimento aceitas no GitHub

Chris Marisic
fonte
3

Para quem procura uma opção de pacote "oficial" no NuGet, a implementação de um OrderedDictionary genérico foi aceita no .NET CoreFX Lab. Se tudo der certo, o tipo será eventualmente aprovado e integrado ao repositório principal do .NET CoreFX.

Existe a possibilidade de que essa implementação seja rejeitada.

A implementação confirmada pode ser referenciada aqui https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary.cs

O pacote NuGet que definitivamente possui esse tipo disponível para uso pode ser encontrado aqui https://www.nuget.org/packages/Microsoft.Experimental.Collections/1.0.6-e190117-3

Ou você pode instalar o pacote no Visual Studio. Procure o pacote "Microsoft.Experimental.Collections" e verifique se a caixa de seleção "Incluir pré-lançamento" está marcada.

Atualizará esta postagem se e quando o tipo for disponibilizado oficialmente.

charlie
fonte
Você pode estimar quando será lançado?
Mvorisek 25/05/19
Não estou participando do desenvolvimento desta biblioteca. Infelizmente, não faço ideia. É provável que seja uma coleção de estruturas incorporada se alguma vez for "aprovada".
charlie
1

Eu implementei um genérico OrderedDictionary<TKey, TValue>, envolvendo SortedList<TKey, TValue>e adicionando um privado Dictionary<TKey, int> _order. Então eu criei uma implementação interna de Comparer<TKey>, passando uma referência ao dicionário _order. Então eu uso esse comparador para o SortedList interno. Essa classe mantém a ordem dos elementos passados ​​para o construtor e a ordem das adições.

Essa implementação possui quase as mesmas características grandes de O, SortedList<TKey, TValue>já que a adição e remoção de _order é O (1). Cada elemento ocupará (de acordo com o livro 'C # 4 em poucas palavras', p. 292, tabela 7-1) um espaço de memória adicional de 22 (sobrecarga) + 4 (ordem int) + tamanho da chave (vamos assumir 8) = 34 Juntamente com SortedList<TKey, TValue>a sobrecarga de dois bytes, a sobrecarga total é de 36 bytes, enquanto o mesmo livro diz que não genérico OrderedDictionarypossui uma sobrecarga de 59 bytes.

Se eu passar sorted=truepara o construtor, o _order não é usado, o que OrderedDictionary<TKey, TValue>é exatamente SortedList<TKey, TValue>com uma sobrecarga menor para o agrupamento, se é que tem algum significado.

Vou armazenar não tantos objetos de referência grandes no OrderedDictionary<TKey, TValue>, então para mim este ca. A sobrecarga de 36 bytes é tolerável.

O código principal está abaixo. O código completo atualizado está nesta essência .

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
fonte
Há pelo menos quatro casos de uso diferentes que posso ver em algo como OrderedDictionary, com relação a inserções ou exclusões: (1) Nunca haverá exclusões; (2) haverá exclusões, mas o importante é que os itens sejam enumerados na ordem adicionada; não há necessidade de acesso por índice; (3) o índice numérico de um item deve (ou pelo menos pode) permanecer constante e não mais de 2 bilhões de itens serão adicionados durante a vida útil da coleção; portanto, se o item # 7 for removido, nunca mais haverá um item # 7; (4) o índice de um item deve ser sua classificação em relação aos sobreviventes.
precisa
1
Os cenários 1 podem ser tratados usando uma matriz em paralelo com o Dictionary. Os cenários 2 e 3 podem ser gerenciados, mantendo cada item um índice informando quando foi adicionado e links para itens adicionados antes ou depois dele. O cenário 4 é o único que parece que não deveria conseguir o desempenho O (1) para operações em sequência arbitrária. Dependendo dos padrões de uso, o nº 4 pode ser ajudado usando várias estratégias de atualização lenta (manter as contagens em uma árvore e fazer com que as alterações em um nó sejam invalidadas em vez de atualizar o nó e seus pais).
Supercat 22/06/13
1
Internal SortedList possui elementos na ordem de inserção devido ao uso do comparador personalizado. Pode ser lento, mas seu comentário sobre enumeração está errado. Mostre os testes sobre enumeração ...
VB
1
De que linha com o ToDictionary você está falando? Não afeta a lista interna, mas apenas o dicionário de pedidos.
VB
1
Desculpas @VB, eu perdi ambos. Como tal, não o testei. Então o único problema seria com adição. Duas pesquisas de dicionário, bem como duas inserções. Eu vou cancelar o voto negativo.
Nawfal