Brak ogólnej implementacji OrderedDictionary?

136

Wygląda na to, że nie ma ogólnej implementacji OrderedDictionary(która znajduje się w System.Collections.Specializedprzestrzeni nazw) w .NET 3.5. Czy jest taki, którego mi brakuje?

Znalazłem implementacje zapewniające tę funkcjonalność, ale zastanawiałem się, czy / dlaczego nie ma standardowej implementacji od razu po wyjęciu z pudełka i czy ktoś wie, czy jest to coś w .NET 4.0?

AdaTheDev
źródło
1
Oto implementacja OrderedDictionary<T>: codeproject.com/Articles/18615/…
Tim Schmelter
Moja implementacja OrderedDictionary <T> ma O (1) wstaw / usuń, ponieważ używa LinkedList zamiast ArrayList do utrzymania kolejności wstawiania: clintonbrennan.com/2013/12/ ...
Clinton
2
Jeśli potrzebujesz tylko mieć możliwość iteracji wpisów w kolejności, w jakiej zostały dodane, wtedy List <KeyValuePair <TKey, TValue >> może być wystarczająco dobre. (To prawda, nie jest to ogólne rozwiązanie, ale wystarczające do niektórych celów.)
jojo.
1
To niefortunne pominięcie. Istnieją inne dobre typy danych Systems.Collections.Generic. Poprośmy OrderedDictionary<TKey,TValue>o .NET 5. Jak inni zauważyli, przypadek, w którym klucz jest int jest zdegenerowany i będzie wymagał szczególnej uwagi.
Colonel Panic

Odpowiedzi:

95

Wdrożenie generycznego OrderedDictionarynie jest strasznie trudne, ale jest niepotrzebnie czasochłonne i szczerze mówiąc, ta klasa jest ogromnym niedopatrzeniem ze strony Microsoftu. Jest na to wiele sposobów, ale zdecydowałem się użyć jako KeyedCollectionpamięci wewnętrznej. Zdecydowałem się również zaimplementować różne metody sortowania, List<T>ponieważ jest to zasadniczo hybryda IList i IDictionary. Umieściłem tutaj moją implementację dla potomności.

Oto interfejs. Zauważ, że zawiera System.Collections.Specialized.IOrderedDictionary, która jest nieogólną wersją tego interfejsu dostarczoną przez firmę 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);
    }

}

Oto implementacja wraz z klasami pomocniczymi:

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

Żadna implementacja nie byłaby kompletna bez kilku testów (ale tragicznie, SO nie pozwoli mi opublikować tak dużo kodu w jednym poście), więc będę musiał zostawić Ci napisanie testów. Ale zostawiłem kilka z nich, abyś mógł zorientować się, jak to działa:

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

-- AKTUALIZACJA --

Źródło dla tej i innych naprawdę przydatnych brakujących podstawowych bibliotek .NET tutaj: https://github.com/mattmc3/dotmore/blob/master/dotmore/Collections/Generic/OrderedDictionary.cs

mattmc3
źródło
6
W domenie publicznej, czy pytasz, czy możesz go używać, modyfikować i traktować tak, jakby był twój, bez obaw - tak. Nie krępuj się. Jeśli masz na myśli licencję na to i gdzieś go hostuj - nie ... mieszka tutaj na SO tylko na razie.
mattmc3
3
@ mattmc3 Dziękuję za kod, proszę pana, ale niepokoi mnie pański komentarz dotyczący kwestii związanych z domeną publiczną, kiedy powiedział Pan w komentarzu: „Jeśli masz na myśli licencję i gdzieś go hostować - nie ... to na razie żyje na SO. " Z całym szacunkiem (naprawdę) dla autora, czy naprawdę masz prawo wprowadzić takie ograniczenie, kiedy już umieścisz kod na SO ??? Np. Czy ktokolwiek z nas naprawdę ma prawo do ograniczenia wysyłania naszego kodu na SO, na przykład jako sedno gita? Ktoś?
Nicholas Petersen
6
@NicholasPetersen - Myślę, że źle zrozumiałeś. W bezpośredniej odpowiedzi Colonel Panic poinformowałem go, że osobiście nie udzielam licencji ani nie hostuję go nigdzie indziej. (Właściwie, skoro o tym wspomniałeś, podsumowałem : gist.github.com/mattmc3/6486878 ). Ale to jest kod bez licencji. Weź to i rób z nim, co chcesz. Napisałem to w 100% na własny użytek. To nieobciążone. Cieszyć się. W rzeczywistości, jeśli ktoś z Microsoftu kiedykolwiek to przeczyta, w pełni oczekuję, że wywiąże się ze swojego obowiązku i ostatecznie umieści to w następnej wersji .NET. Żadne atrybucje nie są konieczne.
mattmc3
2
A jeśli TKeytak int? Jak this[]będzie działać w takim przypadku?
VB
2
@klicker - po prostu użyj zwykłego indeksowania w stylu tablic. Kolejność reklamowa jest utrzymywana tak jak lista. Konwersja typów obsługuje określenie, czy zamierzasz indeksować za pomocą int, czy odwoływać się za pomocą typu klucza. Jeśli typ klucza to int, musisz użyć metody GetValue ().
mattmc3
32

Dla rekordu istnieje ogólny KeyedCollection, który umożliwia indeksowanie obiektów za pomocą int i klucza. Klucz musi być osadzony w wartości.

Guillaume
źródło
2
Nie zachowuje to kolejności inicjalizacji, takiej jak OrderedDictionary! Sprawdź moją odpowiedź.
JoelFan
14
Zachowuje kolejność dodawania / wstawiania.
Guillaume,
tak, to prawda ... skąd wy myślicie, że kolekcja keyedcollection sortuje przedmioty ... natknęłam się na ten drugi raz
Boppity Bop
1
Z pewnością zachowuje kolejność inicjalizacji. Pomocne linki obejmują stackoverflow.com/a/11802824/9344 i geekswithblogs.net/NewThingsILearned/archive/2010/01/07/… .
Ted
+1, to wydaje się być najlepszym rozwiązaniem we frameworku. Konieczność zaimplementowania klasy abstrakcyjnej dla każdej pary typów, których chcesz użyć, jest jednak pewnym utrudnieniem. Możesz to zrobić za pomocą jednej ogólnej implementacji, która wymaga interfejsu, ale wtedy musiałbyś zaimplementować interfejs na każdym typie, który chciałbyś mieć możliwość przechowywania.
DCShannon
19

Oto dziwne znalezisko: przestrzeń nazw System.Web.Util w pliku System.Web.Extensions.dll zawiera ogólny OrderedDictionary

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

Nie jestem pewien, dlaczego MS umieściło go tam zamiast pakietu System.Collections.Generic, ale zakładam, że możesz po prostu skopiować, wkleić kod i użyć go (jest wewnętrzny, więc nie można go używać bezpośrednio). Wygląda na to, że implementacja korzysta ze standardowego słownika i oddzielnych list kluczy / wartości. Całkiem proste ...

Ismail Degani
źródło
2
System.Runtime.Collectionszawiera również wewnętrzną, OrderedDictionary<TKey, TValue>która po prostu otacza nieogólną wersję
VB
1
System.Web.Util.OrderedDictionary<TKey, TValue>jest wewnętrznie zaimplementowany wokół generycznego Dictionary. Dziwne to nie realizuje, IListaleICollection<KeyValuePair<TKey, TValue>>
Michaił
1
@rboy Jak powiedziałem - było to wewnętrzne i opakowane w nieogólną implementację. Ale to było ponad 3 lata temu ... Dla rozmiarów poniżej kilkuset, wyszukiwanie liniowe List<KeyValuePair<TKey,TValue>>będzie konkurencyjne ze względu na wzorzec dostępu do pamięci, dla większych rozmiarów po prostu użyj tej samej listy + Dictionary<TKey,int>jako wyszukiwania. AFAIK nie ma takiej struktury danych, która radziłaby sobie lepiej pod względem szybkości / pamięci w BigO.
VB
1
@rboy tu jest link do rodzajowego jednego , to odwołuje nierodzajową jeden , który wykorzystuje HashTable. Naprawdę założę się, że dla małych rozmiarów korzystanie z wyszukiwania liniowego na ogólnej liście / tablicach będzie szybsze.
VB
1
@PeterMortensen System.Collections.Specialized.OrderedDictionarynie jest typem ogólnym. Spójrz, bez nawiasów kątowych na stronie z dokumentem, z którą łączysz się: P
user7610,
17

Warto, oto jak to rozwiązałem:

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

Można go zainicjować w następujący sposób:

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

i dostępne w ten sposób:

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

// Guaranteed to print in the order of initialization
JoelFan
źródło
3
Dzięki! Nie zdawałem sobie sprawy, że inicjatory kolekcji były po prostu specjalną składnią dla Addmetod.
Sam
10
To nie jest słownik. Słownik oznacza indeksowanie z kluczem i brak zduplikowanych kluczy .
nawfal
ale jeśli nie potrzebujesz indeksowania według klucza (co nie jest zbyt trudne do dodania) i duplikatów kluczy, jest to przydatne
stijn
1
Masz problem z wywołaniami kodu pairList.Add(new KeyValuePair<K,V>())(tj. Metoda na Listklasie). W takim przypadku itsIndexsłownik nie jest aktualizowany, a lista i słownik nie są zsynchronizowane. Może ukryć List.Addmetodę, tworząc new PairList.Add(KeyValuePair<K,V>)metodę, lub może użyć kompozycji zamiast dziedziczenia i po prostu ponownie zaimplementować wszystkie Listmetody ... dużo więcej kodu ...
neizan
1
@nawfal, aby rozwiązać problem, można po prostu dodać czek, taki jak: if (itsindex.Contains(key)) return;na początku, Addaby zapobiec duplikatom
JoelFan
14

Głównym problemem koncepcyjnym związanym z ogólną wersją programu OrderedDictionaryjest to, że użytkownicy OrderedDictionary<TKey,TValue>oczekiwaliby, że będą mogli indeksować go numerycznie przy użyciu intlub wyszukując przy użyciu rozszerzenia TKey. Gdy jedynym typem klucza był Object, tak jak to było w przypadku nieogólnego OrderedDictionary, typ argumentu przekazywany do indeksatora byłby wystarczający do rozróżnienia, czy należy wykonać operację indeksowania. W obecnej sytuacji nie jest jednak jasne, jak OrderedDictionary<int, TValue>powinien zachowywać się indeksator .

Gdyby klasy takie jak Drawing.Pointzalecały i stosowały się do reguły, zgodnie z którą struktury podlegające zmianom fragmentarycznym powinny uwidaczniać swoje zmienne elementy jako pola, a nie właściwości, i powstrzymywać się od używania metod ustawiających właściwości, które modyfikują this, wówczas OrderedDictionary<TKey,TValue>mógłby efektywnie ujawnić ByIndexwłaściwość, która Indexerzwraca strukturę, która zawiera odniesienie do słownik i miał indeksowaną właściwość, której metody pobierające i ustawiające będą wywoływać GetByIndexi SetByIndexna niej. Można by więc powiedzieć coś w rodzaju MyDict.ByIndex[5] += 3;dodania 3 do szóstego elementu słownika.

Niestety, aby kompilator zaakceptował coś takiego, należałoby sprawić, by ByIndexwłaściwość zwracała nową instancję klasy, a nie strukturę za każdym razem, gdy jest wywoływana, eliminując korzyści, które można by uzyskać unikając pudełkowania.

W VB.NET można obejść ten problem, używając nazwanej, indeksowanej właściwości (więc MyDict.ByIndex[int]należałoby do niej MyDict, a nie wymagałoby MyDict.ByIndexbycia członkiem, MyDictktóry zawiera indeksator), ale C # nie zezwala na takie rzeczy.

Mimo wszystko warto było oferować OrderedDictionary<TKey,TValue> where TKey:class, ale głównym powodem wprowadzenia leków generycznych w pierwszej kolejności było umożliwienie ich używania z typami wartości.

superkat
źródło
intSłuszna uwaga, że klucze typu -ty stanowią wyzwanie, ale można by tego uniknąć, postępując zgodnie z przykładem pokrewnego SortedList<TKey, TValue>typu: obsługuj klucze tylko z [...]i wymagają użycia w .Values[...]celu uzyskania dostępu przez indeks. ( SortedDictionary<TKey, TValue>dla kontrastu, który nie jest zoptymalizowany pod kątem dostępu indeksowanego, wymaga użycia .ElementAt(...).Value)
mklement0
7

Z wielu powodów odkryłem, że można sobie poradzić z plikiem List<KeyValuePair<K, V>>. ( DictionaryOczywiście nie, jeśli potrzebujesz go rozszerzyć , a nie, jeśli potrzebujesz lepszego niż O (n) wyszukiwania klucza i wartości).

David Moles
źródło
Właśnie doszedłem do tego samego wniosku!
Peter
1
Jak powiedziałem, „do wielu celów”.
David Moles
2
Możesz również użyć a, Tuple<T1, T2>jeśli nie mają relacji klucz-wartość.
cdmckay
1
Jaki jest sens posiadania par klucz-wartość, jeśli nie można indeksować według klucza?
DCShannon,
1
@DCShannon Nadal możesz mapować klucze na wartości, po prostu nie możesz ich wyszukiwać szybciej niż O (n) (lub radzić sobie automatycznie z powielonymi kluczami). W przypadku małych wartości n czasami jest to wystarczające, szczególnie w sytuacjach, w których i tak często iterujesz przez wszystkie klucze.
David Moles
5

Jest SortedDictionary<TKey, TValue>. Chociaż semantycznie blisko, nie twierdzę, że to to samo, co OrderedDictionarypo prostu dlatego, że tak nie jest. Nawet z cech wydajności. Jednak bardzo interesująca i dość istotna różnica pomiędzy Dictionary<TKey, TValue>(iw tym zakresie OrderedDictionaryimplementacjami podanymi w odpowiedziach) a SortedDictionarypolega na tym, że ta ostatnia używa pod spodem drzewa binarnego. Jest to krytyczne rozróżnienie, ponieważ czyni klasę odporną na ograniczenia pamięciowe stosowane do klasy ogólnej. Zobacz ten wątek na temat OutOfMemoryExceptionszgłaszanych, gdy klasa ogólna jest używana do obsługi dużego zestawu par klucz-wartość.

Jak obliczyć maksymalną wartość parametru pojemności przekazanego do konstruktora Dictionary, aby uniknąć wyjątku OutOfMemoryException?

Schultz9999
źródło
Czy istnieje sposób, aby uzyskać klucze lub wartości SortedDictionary w kolejności, w jakiej zostały dodane ? To właśnie OrderedDictionarypozwala. Koncepcja inna niż posortowana . (Zrobiłem ten błąd w przeszłości, myślałem, dostarczając porównywarka do OrderedDictionary konstruktora pozwoliłoby sortowane, ale wszystko robi z porównywarka jest ustalenie klucza równości, np string-niewrażliwy comparer pozwala string-niewrażliwe wyszukiwanie kluczy.)
ToolmakerSteve
5

Racja, to niefortunne pominięcie. Brakuje mi OrderedDict w Pythonie

Słownik zapamiętujący kolejność wstawiania kluczy. Jeśli nowy wpis zastępuje istniejący wpis, pierwotna pozycja wstawienia pozostaje niezmieniona. Usunięcie wpisu i ponowne jego włożenie spowoduje przeniesienie go na koniec.

Więc napisałem własną OrderedDictionary<K,V>klasę w C #. Jak to działa? Utrzymuje dwie kolekcje - nieuporządkowany słownik waniliowy i uporządkowaną listę kluczy. Dzięki temu rozwiązaniu standardowe operacje słownikowe zachowują szybką złożoność, a wyszukiwanie według indeksu jest również szybkie.

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

Oto interfejs

/// <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
źródło
3

W następstwie komentarza @VB jest dostępna implementacja metody System.Runtime.Collections.OrderedDictionary <,> . Pierwotnie zamierzałem uzyskać do niego dostęp przez odbicie i udostępnić go przez fabrykę, ale plik dll, w którym się znajduje, nie wydaje się być w ogóle dostępny, więc po prostu pobrałem samo źródło.

Należy zwrócić uwagę na to, że indeksator tutaj nie zgłosi KeyNotFoundException . Absolutnie nienawidzę tej konwencji i to była pierwsza wolność, jaką przyjąłem w tej implementacji. Jeśli jest to dla Ciebie ważne, po prostu zamień wiersz na return default(TValue);. Używa C # 6 ( zgodne z 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;
    }
}

Żądania pull / dyskusja akceptowane w GitHub

Chris Marisic
źródło
3

Dla tych, którzy szukają opcji pakietu „oficjalnego” w NuGet, implementacja generycznego OrderedDictionary została zaakceptowana w .NET CoreFX Lab. Jeśli wszystko pójdzie dobrze, typ zostanie ostatecznie zatwierdzony i zintegrowany z głównym repozytorium .NET CoreFX.

Istnieje możliwość, że ta implementacja zostanie odrzucona.

Do zatwierdzonej implementacji można się odwołać tutaj https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary.cs

Pakiet NuGet, który definitywnie ma ten typ dostępny do użycia, można znaleźć tutaj https://www.nuget.org/packages/Microsoft.Experimental.Collections/1.0.6-e190117-3

Możesz też zainstalować pakiet w programie Visual Studio. Wyszukaj pakiet „Microsoft.Experimental.Collections” i upewnij się, że pole wyboru „Uwzględnij wersję wstępną” jest zaznaczone.

Zaktualizuje ten post, jeśli i kiedy typ zostanie oficjalnie udostępniony.

Charlie
źródło
Czy potrafisz oszacować, kiedy zostanie wydany?
mvorisek
Nie biorę udziału w rozwoju tej biblioteki, więc niestety nie mam pojęcia. Prawdopodobnie będzie to zbiór wbudowanych frameworków, jeśli kiedykolwiek zostanie „zatwierdzony”.
charlie
1

Zaimplementowałem rodzaj ogólny OrderedDictionary<TKey, TValue>, zawijając SortedList<TKey, TValue>i dodając prywatny plik Dictionary<TKey, int> _order. Następnie stworzyłem wewnętrzną implementację Comparer<TKey>, przekazując referencję do słownika _order. Następnie używam tej funkcji porównującej do wewnętrznej SortedList. Ta klasa zachowuje kolejność elementów przekazanych do konstruktora i kolejność dodawania.

Ta implementacja ma prawie taką samą charakterystykę dużego O, jak SortedList<TKey, TValue>ponieważ dodawanie i usuwanie do _order jest O (1). Każdy element zajmie (zgodnie z książką „C # 4 w pigułce”, s. 292, tabela 7-1) dodatkową przestrzeń pamięci 22 (narzut) + 4 (w kolejności) + TKey size (przyjmijmy 8) = 34 Razem z SortedList<TKey, TValue>narzutem 2 bajtów, całkowity narzut wynosi 36 bajtów, podczas gdy ta sama książka mówi, że nieogólne OrderedDictionaryma narzut 59 bajtów.

Jeśli przejdę sorted=truedo konstruktora, to _order w ogóle nie jest używany, OrderedDictionary<TKey, TValue>jest dokładnie SortedList<TKey, TValue>z niewielkim narzutem na zawijanie, jeśli w ogóle ma sens.

Mam zamiar przechowywać w formacie nie tak wiele dużych obiektów referencyjnych OrderedDictionary<TKey, TValue>, więc dla mnie to ok. 36 bajtów narzutu jest do przyjęcia.

Główny kod znajduje się poniżej. Kompletny kod jest aktualizowany na tym GIST .

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
źródło
Są co najmniej cztery różne przypadki użycia, które widzę dla czegoś takiego jak OrderedDictionarywstawienia lub usunięcia: (1) Nigdy nie będzie żadnych usunięć; (2) nastąpi usunięcie, ale ważne jest, aby pozycje były wymienione w kolejności dodawania; nie ma potrzeby dostępu według indeksu; (3) numeryczny indeks pozycji powinien (lub przynajmniej może) pozostać stały, a nie więcej niż 2 miliardy pozycji zostanie dodanych w okresie istnienia kolekcji, więc jeśli pozycja # 7 zostanie usunięta, nigdy więcej nie będzie przedmiot nr 7; (4) indeks elementu powinien być jego rangą w odniesieniu do ocalałych.
supercat
1
Scenariusze nr 1 można obsługiwać przy użyciu tablicy równoległej z Dictionary. Scenariusze # 2 i # 3 można by obsłużyć, utrzymując indeks każdego elementu, informujący o tym, kiedy został dodany i łącza do elementów dodanych przed lub po nim. Scenariusz # 4 jest jedynym, który wydaje się, że nie powinien być w stanie osiągnąć wydajności O (1) dla operacji w dowolnej kolejności. W zależności od wzorców użycia, # 4 może być pomocny przy użyciu różnych strategii leniwej aktualizacji (utrzymywanie liczników w drzewie i wprowadzanie zmian w węźle do unieważniania zamiast aktualizowania węzła i jego rodziców).
supercat
1
Wewnętrzna SortedList zawiera elementy w kolejności reklamowej ze względu na użycie niestandardowej funkcji porównującej. Może to być powolne, ale Twój komentarz dotyczący wyliczania jest błędny. Pokaż testy dotyczące wyliczania ...
VB
1
O jakim wersecie z ToDictionary mówisz? Nie ma to wpływu na listę wewnętrzną, ale tylko na słownik zamówień.
VB
1
@VB Przepraszamy, brakowało mi obu. W związku z tym nie przetestowałem tego. Wtedy jedyny problem byłby z dodawaniem. Dwa wyszukiwania w słowniku, a także dwa wstawienia. Odwołam głos przeciw.
nawfal