Pas d'implémentation générique de OrderedDictionary?

136

Il ne semble pas y avoir d'implémentation générique de OrderedDictionary(qui se trouve dans l' System.Collections.Specializedespace de noms) dans .NET 3.5. Y en a-t-il un qui me manque?

J'ai trouvé des implémentations pour fournir la fonctionnalité, mais je me suis demandé si / pourquoi il n'y avait pas d'implémentation générique prête à l'emploi et si quelqu'un sait si c'est quelque chose dans .NET 4.0?

AdaTheDev
la source
1
Voici une implémentation d'un OrderedDictionary<T>: codeproject.com/Articles/18615/…
Tim Schmelter
Mon implémentation de OrderedDictionary <T> a O (1) insérer / supprimer car elle utilise une LinkedList au lieu de ArrayList pour maintenir l'ordre d'insertion: clintonbrennan.com/2013/12
Clinton
2
Si vous avez juste besoin de pouvoir parcourir les entrées dans l'ordre dans lequel elles ont été ajoutées, alors List <KeyValuePair <TKey, TValue >> peut être suffisant. (Certes, pas une solution générale, mais assez bien pour certaines raisons.)
yoyo
1
C'est une omission malheureuse. Il existe d'autres bons types de données Systems.Collections.Generic. Demandons OrderedDictionary<TKey,TValue>.NET 5. Comme d'autres l'ont souligné, le cas où la clé est un int est dégénéré et nécessitera une attention particulière.
Colonel Panic

Réponses:

95

L'implémentation d'un générique OrderedDictionaryn'est pas terriblement difficile, mais cela prend inutilement du temps et franchement cette classe est un énorme oubli de la part de Microsoft. Il existe plusieurs façons de l'implémenter, mais j'ai choisi d'utiliser un KeyedCollectionpour mon stockage interne. J'ai également choisi d'implémenter diverses méthodes pour trier comme cela, List<T>car il s'agit essentiellement d'un IList et d'un IDictionary hybrides. J'ai inclus ma mise en œuvre ici pour la postérité.

Voici l'interface. Notez qu'il inclut System.Collections.Specialized.IOrderedDictionary, qui est la version non générique de cette interface qui a été fournie par 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);
    }

}

Voici l'implémentation avec les classes d'assistance:

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

Et aucune implémentation ne serait complète sans quelques tests (mais tragiquement, SO ne me laissera pas publier autant de code dans un seul post), donc je vais devoir vous laisser écrire vos tests. Mais, j'en ai laissé quelques-uns pour que vous puissiez avoir une idée de son fonctionnement:

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

-- METTRE À JOUR --

Source pour cela et d'autres bibliothèques .NET de base manquantes vraiment utiles ici: https://github.com/mattmc3/dotmore/blob/master/dotmore/Collections/Generic/OrderedDictionary.cs

mattmc3
la source
6
Par domaine public, demandez-vous si vous pouvez l'utiliser, le modifier et le traiter comme si c'était le vôtre sans souci - oui. N'hésitez pas. Si vous voulez dire une licence et l'héberger quelque part - non ... il ne vit ici que pour l'instant.
mattmc3
3
@ mattmc3 Merci pour votre code monsieur, mais votre commentaire sur les problèmes du domaine public me préoccupe, lorsque vous avez dit dans le commentaire: "Si vous voulez dire une licence et l'héberger quelque part - non ... il ne vit ici que pour l'instant. " Avec tout le respect (vraiment destiné) à l'auteur, avez-vous vraiment le droit de faire cette restriction, une fois que vous avez publié le code sur SO ??? Par exemple, l'un de nous a-t-il vraiment le droit de restreindre la publication de notre code sur SO, par exemple, en tant que git? N'importe qui?
Nicholas Petersen
6
@NicholasPetersen - Je pense que vous avez mal compris. En réponse directe au colonel Panic, je l'ai informé que personnellement je ne l' ai pas autorisé ni hébergé ailleurs. (En fait, depuis que vous l'avez mentionné, j'ai fait un résumé : gist.github.com/mattmc3/6486878 ). Mais c'est un code sans licence. Prenez-le et faites-en ce que vous voulez. Je l'ai écrit à 100% pour mon usage personnel. C'est libre. Prendre plaisir. En fait, si quelqu'un de Microsoft lit un jour ceci, je m'attends à ce qu'il fasse son devoir et le place enfin dans la prochaine version de .NET. Aucune attribution nécessaire.
mattmc3
2
Et si TKeyc'est int? Comment this[]fonctionnera dans un tel cas?
VB
2
@klicker - Utilisez simplement l'indexation de style tableau normal. L'ordre d'insertion est conservé comme une liste. La conversion de type gère la détermination de votre intention d'indexer avec un int ou de faire référence via le type de la clé. Si le type de la clé est un int, vous devez utiliser la méthode GetValue ().
mattmc3
32

Pour mémoire, il existe un KeyedCollection générique qui permet aux objets d'être indexés par un int et une clé. La clé doit être intégrée dans la valeur.

Guillaume
la source
2
Cela ne maintient pas l'ordre d'initialisation comme OrderedDictionary! Regardez ma réponse.
JoelFan
14
Il maintient l'ordre d'ajout / d'insertion.
Guillaume
oui, il le fait .. où avez-vous cette idée que la collection keyedcollection trie les éléments ... je suis tombé sur cette deuxième fois
Boppity Bop
1
Il maintient définitivement l'ordre d'initialisation. Les liens utiles incluent stackoverflow.com/a/11802824/9344 et geekswithblogs.net/NewThingsILearned/archive/2010/01/07/… .
Ted
+1, cela semble être la meilleure solution dans le cadre. Cependant, devoir implémenter la classe abstraite pour chaque paire de types que vous souhaitez utiliser est une sorte de glissement. Vous pouvez le faire avec une implémentation générique qui nécessite une interface, mais vous devrez ensuite implémenter l'interface sur chaque type que vous souhaitez pouvoir stocker.
DCShannon
19

Voici une découverte bizarre: l'espace de noms System.Web.Util dans System.Web.Extensions.dll contient un OrderedDictionary générique

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

Je ne sais pas pourquoi MS l'a placé là au lieu du package System.Collections.Generic, mais je suppose que vous pouvez simplement copier-coller le code et l'utiliser (il est interne, vous ne pouvez donc pas l'utiliser directement). Il semble que l'implémentation utilise un dictionnaire standard et des listes de clés / valeurs séparées. Assez simple...

Ismail Degani
la source
2
System.Runtime.Collectionscontient également un interne OrderedDictionary<TKey, TValue>qui entoure juste la version non générique
VB
1
System.Web.Util.OrderedDictionary<TKey, TValue>est implémenté en interne autour de generic Dictionary. Curieusement, il ne met pas en œuvre IListmaisICollection<KeyValuePair<TKey, TValue>>
Mikhail
1
@rboy Comme je l'ai dit - c'était interne et enveloppait l'implémentation non générique. Mais c'était il y a plus de 3 ans ... Pour les tailles inférieures à quelques centaines, la recherche linéaire List<KeyValuePair<TKey,TValue>>sera compétitive en raison du modèle d'accès à la mémoire, pour les tailles plus grandes, utilisez simplement la même liste + Dictionary<TKey,int>comme une recherche. AFAIK, il n'y a pas de telle structure de données qui fasse mieux en termes de vitesse / mémoire dans BigO.
VB
1
@rboy voici le lien vers le générique , il fait référence à celui non générique qui utilise HashTable. Je parie vraiment que pour les petites tailles, l'utilisation de la recherche linéaire sur des listes / tableaux génériques sera plus rapide.
VB
1
@PeterMortensen System.Collections.Specialized.OrderedDictionaryn'est pas un type générique. Regardez ma, pas de crochets à la page de documentation que vous avez liée: P
user7610
17

Pour ce que ça vaut, voici comment je l'ai résolu:

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

Il peut être initialisé comme ceci:

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

et accédé comme ceci:

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

// Guaranteed to print in the order of initialization
JoelFan
la source
3
Merci! Je n'avais pas réalisé que les initialiseurs de collection n'étaient qu'une syntaxe spéciale pour les Addméthodes.
Sam
10
Ce n'est pas un dictionnaire. Dictionary signifie indexation à clé et aucune clé en double .
nawfal
Pourtant, si vous n'avez pas besoin d'indexation par clé (ce qui n'est pas trop difficile à ajouter) et de clés dupliquées, cela est pratique
stijn
1
Vous avez un problème avec les appels de code pairList.Add(new KeyValuePair<K,V>())(c'est-à-dire la méthode sur la Listclasse). Dans ce cas, le itsIndexdictionnaire n'est pas mis à jour et maintenant la liste et le dictionnaire sont désynchronisés. Pourrait cacher la List.Addméthode en créant une new PairList.Add(KeyValuePair<K,V>)méthode, ou pourrait utiliser la composition au lieu de l'héritage et implémenter à nouveau toutes les Listméthodes ... beaucoup plus de code ...
neizan
1
@nawfal, pour répondre à votre inquiétude, il suffit d'ajouter une coche comme: if (itsindex.Contains(key)) return;au début de Addpour éviter les doublons
JoelFan
14

Un problème conceptuel majeur avec une version générique de OrderedDictionaryest que les utilisateurs de a OrderedDictionary<TKey,TValue>s'attendent à pouvoir l'indexer soit numériquement à l'aide d'un int, soit par recherche à l'aide d'un TKey. Lorsque le seul type de clé était Object, comme ce fut le cas avec non générique OrderedDictionary, le type d'argument passé à l'indexeur serait suffisant pour distinguer si le type d'opération d'indexation doit être effectué. Dans l'état actuel des choses, cependant, on ne sait pas comment l'indexeur d'un OrderedDictionary<int, TValue>doit se comporter.

Si des classes comme Drawing.Pointavaient recommandé et suivi une règle selon laquelle les structures mutables par morceaux devraient exposer leurs éléments mutables comme des champs plutôt que des propriétés, et s'abstenir d'utiliser des setters de propriété qui modifient this, alors un OrderedDictionary<TKey,TValue>pourrait exposer efficacement une ByIndexpropriété qui retournait une Indexerstructure qui contenait une référence à le dictionnaire, et avait une propriété indexée dont le getter et le setter feraient appel GetByIndexet SetByIndexsur lui. Ainsi, on pourrait dire quelque chose comme MyDict.ByIndex[5] += 3;ajouter 3 au sixième élément du dictionnaire.

Malheureusement, pour que le compilateur accepte une telle chose, il serait nécessaire de faire en sorte que la ByIndexpropriété renvoie une nouvelle instance de classe plutôt qu'une structure à chaque fois qu'elle est invoquée, éliminant ainsi les avantages que l'on obtiendrait en évitant la boxe.

Dans VB.NET, on pourrait contourner ce problème en utilisant une propriété indexée nommée (donc MyDict.ByIndex[int]serait membre de MyDict, plutôt que d'exiger MyDict.ByIndexd'être un membre MyDictdont inclut un indexeur), mais C # ne permet pas de telles choses.

Il aurait peut-être encore valu la peine d’offrir un OrderedDictionary<TKey,TValue> where TKey:class, mais la raison pour laquelle on a fourni des génériques en premier lieu était d’autoriser leur utilisation avec des types de valeur.

supercat
la source
Bon point que les intclés -typées présentent un défi, mais cela pourrait être évité en suivant l'exemple du SortedList<TKey, TValue>type associé : ne supporte les clés qu'avec [...], et nécessite l'utilisation de .Values[...]pour l'accès par index. ( SortedDictionary<TKey, TValue>, en revanche, qui n'est pas optimisé pour l'accès indexé, nécessite l'utilisation de .ElementAt(...).Value)
mklement0
7

Pour de nombreuses raisons, j'ai trouvé que l'on pouvait s'en sortir avec un List<KeyValuePair<K, V>>. (Pas si vous en avez besoin pour étendre Dictionary, évidemment, et pas si vous avez besoin d'une recherche de valeur-clé meilleure que O (n).)

David Moles
la source
Je viens juste d'arriver à la même conclusion moi-même!
Peter
1
Comme je l'ai dit, «pour de nombreuses raisons».
David Moles
2
Vous pouvez également utiliser a Tuple<T1, T2>s'ils n'ont pas de relation clé-valeur.
cdmckay
1
Quel est l'intérêt d'avoir des paires clé-valeur si vous ne pouvez pas indexer par clé?
DCShannon
1
@DCShannon Vous pouvez toujours mapper des clés à des valeurs, vous ne pouvez tout simplement pas les rechercher plus rapidement que O (n) (ou traiter automatiquement les clés en double). Pour les petites valeurs de n, c'est parfois assez bon, en particulier dans les situations où vous répétez généralement toutes les touches de toute façon.
David Moles
5

Il y a SortedDictionary<TKey, TValue>. Bien que sémantiquement proches, je ne prétends pas que c'est la même chose que OrderedDictionarysimplement parce qu'ils ne le sont pas. Même à partir des caractéristiques de performance. Cependant, la différence très intéressante et assez importante entre Dictionary<TKey, TValue>(et dans cette mesure OrderedDictionaryet les implémentations fournies dans les réponses) et SortedDictionaryest que ce dernier utilise l'arbre binaire en dessous. Il s'agit d'une distinction critique car elle rend la classe immunisée contre les contraintes de mémoire appliquées à la classe générique. Consultez ce thread à propos de la OutOfMemoryExceptionslevée lorsque la classe générique est utilisée pour gérer un grand ensemble de paires clé-valeur.

Comment déterminer la valeur maximale du paramètre de capacité passé au constructeur de dictionnaire pour éviter OutOfMemoryException?

Schultz9999
la source
Existe-t-il un moyen d'obtenir les clés ou les valeurs de a SortedDictionary dans l'ordre dans lequel elles ont été ajoutées ? C'est ce qui OrderedDictionarypermet. Concept différent de celui trié . (J'ai fait cette erreur dans le passé; je pensais que fournir un constructeur Comparer à OrderedDictionary le ferait trier, mais tout ce qu'il fait avec le Comparer est de déterminer l'égalité des clés; par exemple, le comparateur insensible aux chaînes permet la recherche de clés insensibles aux chaînes.)
ToolmakerSteve
5

C'est vrai, c'est une omission malheureuse. OrderedDict de Python me manque

Un dictionnaire qui se souvient de l'ordre dans lequel les clés ont été insérées pour la première fois. Si une nouvelle entrée écrase une entrée existante, la position d'insertion d'origine reste inchangée. Supprimer une entrée et la réinsérer la déplacera à la fin.

J'ai donc écrit ma propre OrderedDictionary<K,V>classe en C #. Comment ça marche? Il maintient deux collections - un dictionnaire non ordonné vanille et une liste ordonnée de clés. Avec cette solution, les opérations de dictionnaire standard conservent leur complexité rapide et la recherche par index est également rapide.

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

Voici l'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);
}
Colonel Panic
la source
3

Pour faire suite au commentaire de @VB, voici une implémentation accessible de System.Runtime.Collections.OrderedDictionary <,> . J'allais à l'origine y accéder par réflexion et le fournir via une usine mais la dll dans laquelle il se trouve ne semble pas du tout très accessible, alors j'ai juste extrait la source elle-même.

Une chose à noter est que l'indexeur ici ne lancera pas KeyNotFoundException . Je déteste absolument cette convention et c'est la 1 liberté que j'ai prise dans cette mise en œuvre. Si c'est important pour vous, remplacez simplement la ligne par return default(TValue);. Utilise C # 6 ( compatible avec 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;
    }
}

Demandes d'extraction / discussion acceptées sur GitHub

Chris Marisic
la source
3

Pour ceux qui recherchent une option de package "officielle" dans NuGet, une implémentation d'un OrderedDictionary générique a été acceptée dans .NET CoreFX Lab. Si tout se passe bien, le type sera finalement approuvé et intégré au référentiel principal .NET CoreFX.

Il est possible que cette implémentation soit rejetée.

L'implémentation validée peut être référencée ici https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary.cs

Le package NuGet qui a définitivement ce type disponible pour une utilisation peut être trouvé ici https://www.nuget.org/packages/Microsoft.Experimental.Collections/1.0.6-e190117-3

Ou vous pouvez installer le package dans Visual Studio. Recherchez le package "Microsoft.Experimental.Collections" et assurez-vous que la case "Inclure la version préliminaire" est cochée.

Mettra à jour ce message si et quand le type est rendu officiellement disponible.

Charlie
la source
Pouvez-vous estimer quand il sera publié?
mvorisek
Je ne participe pas au développement de cette bibliothèque donc malheureusement je n'en ai aucune idée. Il est probable que ce soit une collection de frameworks intégrée si elle est "approuvée".
charlie
1

J'ai implémenté un générique OrderedDictionary<TKey, TValue>en enveloppant SortedList<TKey, TValue>et en ajoutant un private Dictionary<TKey, int> _order. Ensuite, j'ai créé une implémentation interne de Comparer<TKey>, en passant une référence au dictionnaire _order. Ensuite, j'utilise ce comparateur pour la SortedList interne. Cette classe conserve l'ordre des éléments passés au constructeur et l'ordre des ajouts.

Cette implémentation a presque les mêmes caractéristiques de gros O que SortedList<TKey, TValue>depuis que l'ajout et la suppression de _order sont O (1). Chaque élément prendra (selon le livre 'C # 4 in a Nutshell', p. 292, tableau 7-1) un espace mémoire supplémentaire de 22 (overhead) + 4 (int order) + TKey size (supposons 8) = 34 Avec SortedList<TKey, TValue>la surcharge de deux octets, la surcharge totale est de 36 octets, tandis que le même livre dit que le non-générique OrderedDictionarya une surcharge de 59 octets.

Si je passe sorted=trueau constructeur, alors _order n'est pas du tout utilisé, le OrderedDictionary<TKey, TValue>est exactement SortedList<TKey, TValue>avec une surcharge mineure pour l'encapsulation, voire pas du tout significative.

Je vais stocker pas tellement de gros objets de référence dans le OrderedDictionary<TKey, TValue>, donc pour moi ça ca. Une surcharge de 36 octets est tolérable.

Le code principal est ci-dessous. Le code mis à jour complet est sur cet essentiel .

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
la source
Il y a au moins quatre cas d'utilisation différents que je peux voir pour quelque chose comme OrderedDictionary, en ce qui concerne les insertions ou les suppressions: (1) Il n'y aura jamais de suppressions; (2) il y aura des suppressions, mais ce qui est important, c'est que les éléments sont énumérés dans l'ordre ajouté; il n'y a pas besoin d'accès par index; (3) l'index numérique d'un élément doit (ou au moins peut) rester constant, et pas plus de 2 milliards d'éléments ne seront ajoutés pendant la durée de vie de la collection, donc si l'élément n ° 7 est supprimé, il n'y aura plus jamais un article n ° 7; (4) l'index d'un item devrait être son rang par rapport aux survivants.
supercat
1
Les scénarios n ° 1 peuvent être gérés en utilisant un tableau en parallèle avec le Dictionary. Les scénarios n ° 2 et n ° 3 pourraient être gérés en demandant à chaque élément de conserver un index indiquant quand il a été ajouté et des liens vers des éléments ajoutés avant ou après. Le scénario n ° 4 est le seul qui semble ne pas pouvoir atteindre les performances O (1) pour les opérations dans une séquence arbitraire. Selon les modèles d'utilisation, # 4 peut être aidé en utilisant diverses stratégies de mise à jour paresseuse (garder les décomptes dans une arborescence et faire invalider les modifications d'un nœud plutôt que de mettre à jour le nœud et ses parents).
supercat
1
Internal SortedList a des éléments dans l'ordre d'insertion en raison de l'utilisation d'un comparateur personnalisé. Cela peut être lent mais votre commentaire sur l'énumération est faux. Afficher les tests sur l'énumération ...
VB
1
De quelle ligne avec ToDictionary parlez-vous? Cela n'affecte pas la liste interne, mais uniquement le dictionnaire de commande.
VB
1
@VB Apologies, j'ai raté les deux. En tant que tel, je ne l'ai pas testé. Alors le seul problème serait avec l'addition. Deux recherches dans le dictionnaire, ainsi que deux insertions. J'annule le vote défavorable.
nawfal