Keine generische Implementierung von OrderedDictionary?

136

In .NET 3.5 scheint es keine generische Implementierung von OrderedDictionary(im System.Collections.SpecializedNamespace) zu geben. Gibt es eine, die ich vermisse?

Ich habe Implementierungen gefunden, um die Funktionalität bereitzustellen, habe mich aber gefragt, ob / warum es keine sofort einsatzbereite generische Implementierung gibt und ob jemand weiß, ob es sich um etwas in .NET 4.0 handelt.

AdaTheDev
quelle
1
Hier ist eine Implementierung von OrderedDictionary<T>: codeproject.com/Articles/18615/…
Tim Schmelter
Meine Implementierung von OrderedDictionary <T> hat O (1) Einfügen / Löschen, da es eine LinkedList anstelle von ArrayList verwendet, um die Einfügereihenfolge
Clinton
2
Wenn Sie nur in der Lage sein müssen, die Einträge in der Reihenfolge zu durchlaufen, in der sie hinzugefügt wurden, ist List <KeyValuePair <TKey, TValue >> möglicherweise gut genug. (Zugegeben, keine allgemeine Lösung, aber für einige Zwecke gut genug.)
Jojo
1
Es ist eine unglückliche Unterlassung. Es gibt andere gute Datentypen Systems.Collections.Generic. Fordern wir OrderedDictionary<TKey,TValue>.NET 5 an. Wie andere bereits betont haben, ist der Fall, dass der Schlüssel ein Int ist, entartet und erfordert besondere Sorgfalt.
Colonel Panic

Antworten:

60

Du hast recht. Es gibt kein generisches Äquivalent OrderedDictionaryim Framework selbst.

(Soweit mir bekannt ist, gilt dies auch für .NET 4.)

Sie können jedoch bei UserVoice von Visual Studio (04.10.2016) dafür stimmen!

LukeH
quelle
95

Die Implementierung eines Generikums OrderedDictionaryist nicht besonders schwierig, aber unnötig zeitaufwändig, und ehrlich gesagt ist diese Klasse ein großes Versehen von Microsoft. Es gibt mehrere Möglichkeiten, dies zu implementieren, aber ich habe mich für die Verwendung eines KeyedCollectionfür meinen internen Speicher entschieden. Ich habe mich auch dafür entschieden, verschiedene Methoden zum Sortieren zu implementieren, List<T>da dies im Wesentlichen eine hybride IList und ein IDictionary ist. Ich habe meine Implementierung hier für die Nachwelt aufgenommen.

Hier ist die Schnittstelle. Beachten Sie System.Collections.Specialized.IOrderedDictionary, dass dies die nicht generische Version dieser Schnittstelle ist, die von Microsoft bereitgestellt wurde.

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

}

Hier ist die Implementierung zusammen mit Hilfsklassen:

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

Und keine Implementierung wäre ohne ein paar Tests vollständig (aber tragischerweise lässt mich SO nicht so viel Code in einem Beitrag veröffentlichen), also muss ich Sie verlassen, um Ihre Tests zu schreiben. Aber ich habe ein paar davon gelassen, damit Sie eine Vorstellung davon bekommen, wie es funktioniert:

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

- UPDATE -

Quelle für diese und andere wirklich nützliche fehlende .NET-Kernbibliotheken hier: https://github.com/mattmc3/dotmore/blob/master/dotmore/Collections/Generic/OrderedDictionary.cs

mattmc3
quelle
6
Fragen Sie gemeinfrei, ob Sie es verwenden, ändern und so behandeln können, als ob es Ihnen Sorgen macht - ja. Fühlen Sie sich frei. Wenn du es lizenzieren und irgendwo hosten willst - nein ... es lebt hier erstmal auf SO.
Mattmc3
3
@ mattmc3 Vielen Dank für Ihren Code, Sir, aber Ihr Kommentar zu gemeinfreien Themen betrifft mich, als Sie im Kommentar sagten: "Wenn Sie es lizenzieren und irgendwo hosten wollen - nein ... es lebt hier nur auf SO. "" Haben Sie bei allem Respekt (wirklich gemeint) gegenüber dem Autor wirklich das Recht, diese Einschränkung vorzunehmen, sobald Sie den Code auf SO veröffentlicht haben? Hat beispielsweise einer von uns wirklich das Recht, zu verhindern, dass unser Code auf SO beispielsweise als Git-Gist veröffentlicht wird? Jemand?
Nicholas Petersen
6
@NicholasPetersen - Ich denke du hast es falsch verstanden. Als direkte Antwort auf Colonel Panic teilte ich ihm mit, dass ich es persönlich nicht lizenziert oder irgendwo anders gehostet habe. (Eigentlich habe ich, seit du es erwähnt hast, einen Kern gemacht: gist.github.com/mattmc3/6486878 ). Dies ist jedoch ein lizenzfreier Code. Nimm es und mach was du willst. Ich habe es zu 100% für meinen persönlichen Gebrauch geschrieben. Es ist unbelastet. Genießen. Wenn jemand von Microsoft dies jemals liest, erwarte ich von ihm, dass er seine Pflicht erfüllt und es schließlich in die nächste Version von .NET einfügt. Keine Zuschreibungen notwendig.
Mattmc3
2
Was passiert , wenn TKeyist int? Wie this[]wird in einem solchen Fall funktionieren?
VB
2
@klicker - Verwenden Sie einfach die reguläre Indizierung im Array-Stil. Die Einfügereihenfolge wird wie eine Liste beibehalten. Bei der Typkonvertierung wird festgelegt, ob Sie mit einem int indizieren oder über den Schlüsseltyp referenzieren möchten. Wenn der Schlüsseltyp ein int ist, müssen Sie die GetValue () -Methode verwenden.
Mattmc3
32

Für den Datensatz gibt es eine generische KeyedCollection , mit der Objekte durch ein int und einen Schlüssel indiziert werden können. Der Schlüssel muss in den Wert eingebettet sein.

Guillaume
quelle
2
Dadurch wird die Reihenfolge der Initialisierung nicht wie bei OrderedDictionary beibehalten! Schau dir meine Antwort an.
JoelFan
14
Die Reihenfolge des Hinzufügens / Einfügens wird beibehalten.
Guillaume
Ja, das tut es. Woher habt ihr die Vorstellung, dass die Schlüsselsammlung Gegenstände sortiert? Ich bin auf dieses zweite Mal
gestoßen
1
Die Reihenfolge der Initialisierung wird definitiv beibehalten. Zu den hilfreichen Links gehören stackoverflow.com/a/11802824/9344 und geekswithblogs.net/NewThingsILearned/archive/2010/01/07/… .
Ted
+1, Dies scheint die beste Lösung im Framework zu sein. Das Implementieren der abstrakten Klasse für jedes Typpaar, das Sie verwenden möchten, ist jedoch eine Art Drag. Sie könnten dies mit einer generischen Implementierung tun, für die eine Schnittstelle erforderlich ist, aber dann müssten Sie die Schnittstelle für jeden Typ implementieren, den Sie speichern möchten.
DCShannon
19

Hier ist ein bizarrer Fund: Der System.Web.Util-Namespace in System.Web.Extensions.dll enthält ein generisches 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

Ich bin mir nicht sicher, warum MS es dort anstelle des System.Collections.Generic-Pakets abgelegt hat, aber ich gehe davon aus, dass Sie den Code einfach kopieren, einfügen und verwenden können (er ist intern, kann ihn also nicht direkt verwenden). Die Implementierung verwendet anscheinend ein Standardwörterbuch und separate Schlüssel- / Wertelisten. Ziemlich einfach...

Ismail Degani
quelle
2
System.Runtime.Collectionsenthält auch eine interne, OrderedDictionary<TKey, TValue>die nur die nicht generische Version
umschließt
1
System.Web.Util.OrderedDictionary<TKey, TValue>wird intern um generisch implementiert Dictionary. Merkwürdig ist es nicht umzusetzen , IListsondernICollection<KeyValuePair<TKey, TValue>>
Mikhail
1
@rboy Wie gesagt - es war intern und verpackte die nicht generische Implementierung. Aber es war vor mehr als 3 Jahren ... Bei Größen unter einigen Hundert ist die lineare Suche List<KeyValuePair<TKey,TValue>>aufgrund des Speicherzugriffsmusters wettbewerbsfähig. Bei größeren Größen verwenden Sie einfach dieselbe Liste + Dictionary<TKey,int>als Suche. AFAIK Es gibt keine solche Datenstruktur, die in BigO hinsichtlich Geschwindigkeit / Speicher besser abschneidet.
VB
1
@rboy hier ist der Link zum generischen , er verweist auf den nicht generischen , der HashTable verwendet. Ich wette wirklich, dass bei kleinen Größen die lineare Suche auf generischen Listen / Arrays schneller sein wird.
VB
1
@PeterMortensen System.Collections.Specialized.OrderedDictionaryist kein generischer Typ. Schauen Sie ma, keine spitzen Klammern auf der von Ihnen verlinkten
Dokumentseite
17

Für das, was es wert ist, habe ich es folgendermaßen gelöst:

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

Es kann folgendermaßen initialisiert werden:

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

und wie folgt zugegriffen:

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

// Guaranteed to print in the order of initialization
JoelFan
quelle
3
Vielen Dank! Ich hatte nicht bemerkt, dass Sammlungsinitialisierer nur eine spezielle Syntax für AddMethoden sind.
Sam
10
Dies ist kein Wörterbuch. Dictionary steht für Keyed Indexing und keine doppelten Schlüssel .
Nawfal
Wenn Sie jedoch keine Indizierung nach Schlüsseln (was nicht allzu schwer hinzuzufügen ist) und doppelte Schlüssel benötigen, ist dies praktisch
Uhr
1
Sie haben ein Problem mit Codeaufrufen pairList.Add(new KeyValuePair<K,V>())(dh der Methode für die ListKlasse). In diesem Fall wird das itsIndexWörterbuch nicht aktualisiert, und jetzt sind die Liste und das Wörterbuch nicht mehr synchron. Könnte die List.AddMethode durch Erstellen einer new PairList.Add(KeyValuePair<K,V>)Methode ausblenden oder könnte Komposition anstelle von Vererbung verwenden und einfach alle ListMethoden erneut implementieren ... viel mehr Code ...
Neizan
1
@nawfal, um Ihr Anliegen anzusprechen, könnte man einfach einen Scheck hinzufügen wie: if (itsindex.Contains(key)) return;am Anfang Add, um Duplikate zu verhindern
JoelFan
14

Ein großes konzeptionelles Problem bei einer generischen Version von OrderedDictionaryist, dass Benutzer von a OrderedDictionary<TKey,TValue>erwarten, dass sie es entweder numerisch mit a intoder durch Nachschlagen mit a indizieren können TKey. Wenn der einzige Schlüsseltyp war Object, wie dies bei nicht generischen Schlüsseln der Fall war OrderedDictionary, würde der an den Indexer übergebene Argumenttyp ausreichen, um zu unterscheiden, ob welche Art von Indexierungsoperation ausgeführt werden soll. Es ist jedoch unklar, wie sich der Indexer eines OrderedDictionary<int, TValue>verhalten soll.

Wenn wie Klassen Drawing.Pointempfohlen hatte , und folgte eine Regel , dass stückweise-veränderbare Strukturen ihre veränderbare Elemente wie Felder aussetzen sollte , anstatt Eigenschaften und verzichten auf Eigenschaft Setter , die ändern this, dann ein OrderedDictionary<TKey,TValue>könnte effizient eine aussetzen ByIndexEigenschaft , die ein zurück IndexerStruktur , die eine Referenz gehalten das Wörterbuch und hatte eine indizierte Eigenschaft, deren Getter und Setter GetByIndexund SetByIndexauf sie aufrufen würden . Man könnte also so etwas wie MyDict.ByIndex[5] += 3;3 zum sechsten Element des Wörterbuchs hinzufügen.

Damit der Compiler so etwas akzeptieren kann, muss die ByIndexEigenschaft leider jedes Mal, wenn sie aufgerufen wird, eine neue Klasseninstanz anstelle einer Struktur zurückgeben, wodurch die Vorteile beseitigt werden, die sich aus der Vermeidung des Boxens ergeben.

In VB.NET könnte man dieses Problem umgehen, indem man eine benannte indizierte Eigenschaft verwendet ( MyDict.ByIndex[int]wäre also ein Mitglied von MyDict, anstatt MyDict.ByIndexein Mitglied zu sein, MyDictdas einen Indexer enthält), aber C # erlaubt solche Dinge nicht.

Es mag sich immer noch gelohnt haben, ein Produkt anzubieten OrderedDictionary<TKey,TValue> where TKey:class, aber der Hauptgrund für die Bereitstellung von Generika bestand darin, ihre Verwendung mit Werttypen zuzulassen.

Superkatze
quelle
Ein guter Punkt, dass intSchlüssel vom SortedList<TKey, TValue>Typ "Typ" eine Herausforderung darstellen. Sie können jedoch vermieden werden, indem Sie dem Beispiel des zugehörigen Typs folgen : Schlüssel nur mit [...]unterstützen und .Values[...]für den Zugriff per Index verwenden. (Im SortedDictionary<TKey, TValue>Gegensatz dazu erfordert die Verwendung, die nicht für den indizierten Zugriff optimiert ist, die Verwendung von .ElementAt(...).Value)
mklement0
7

Für viele Zwecke habe ich festgestellt, dass man mit einem auskommen kann List<KeyValuePair<K, V>>. (Natürlich nicht, wenn Sie es benötigen, um es zu erweitern Dictionary, und nicht, wenn Sie eine bessere Suche nach O (n) -Schlüsselwerten benötigen.)

David Moles
quelle
Bin gerade selbst zu dem gleichen Schluss gekommen!
Peter
1
Wie gesagt, "für viele Zwecke."
David Moles
2
Sie können auch a verwenden, Tuple<T1, T2>wenn sie keine Schlüssel-Wert-Beziehung haben.
CDMckay
1
Was bringt es, Schlüsselwertpaare zu haben, wenn Sie nicht nach Schlüssel indizieren können?
DCShannon
1
@DCShannon Sie können Schlüssel weiterhin Werten zuordnen, Sie können sie jedoch nicht schneller als O (n) nachschlagen (oder automatisch mit doppelten Schlüsseln umgehen). Für kleine Werte von n ist das manchmal gut genug, insbesondere in Situationen, in denen Sie normalerweise ohnehin alle Schlüssel durchlaufen.
David Moles
5

Es gibt SortedDictionary<TKey, TValue>. Obwohl semantisch nahe, behaupte ich nicht, dass es dasselbe ist wie OrderedDictionaryeinfach, weil sie es nicht sind. Auch von Leistungsmerkmalen. Der sehr interessante und sehr wichtige Unterschied zwischen Dictionary<TKey, TValue>(und insoweit OrderedDictionaryund den in den Antworten angegebenen Implementierungen) SortedDictionarybesteht jedoch darin, dass letzterer einen darunter liegenden Binärbaum verwendet. Dies ist eine kritische Unterscheidung, da die Klasse dadurch immun gegen Speicherbeschränkungen ist, die auf generische Klassen angewendet werden. In diesem Thread wird beschrieben, wie OutOfMemoryExceptionsausgelöst wird, wenn eine generische Klasse für die Verarbeitung einer großen Anzahl von Schlüssel-Wert-Paaren verwendet wird.

Wie kann der maximale Wert für den Kapazitätsparameter ermittelt werden, der an den Dictionary-Konstruktor übergeben wird, um OutOfMemoryException zu vermeiden?

Schultz9999
quelle
Gibt es eine Möglichkeit, Schlüssel oder Werte von a SortedDictionary in der Reihenfolge abzurufen, in der sie hinzugefügt wurden ? Das OrderedDictionaryerlaubt es. Anderes Konzept als sortiert . (Ich habe diesen Fehler in der Vergangenheit gemacht, ich dachte einen Comparer OrderedDictionary Konstruktor liefern würde es sortiert, aber alle mit dem Comparer tut , ist Gleichheit der Schlüssel zu bestimmen, zB String unempfindlichen Vergleich ermöglicht String unempfindlichen Schlüsselsuche.)
ToolmakerSteve
5

Richtig, es ist eine unglückliche Unterlassung. Ich vermisse Pythons OrderedDict

Ein Wörterbuch, das sich an die Reihenfolge erinnert, in der die Schlüssel zuerst eingefügt wurden. Wenn ein neuer Eintrag einen vorhandenen Eintrag überschreibt, bleibt die ursprüngliche Einfügeposition unverändert. Wenn Sie einen Eintrag löschen und erneut einfügen, wird er an das Ende verschoben.

Also habe ich meine eigene OrderedDictionary<K,V>Klasse in C # geschrieben. Wie funktioniert es? Es werden zwei Sammlungen verwaltet - ein ungeordnetes Vanille-Wörterbuch und eine geordnete Liste von Schlüsseln. Mit dieser Lösung behalten die Standardwörterbuchoperationen ihre schnelle Komplexität bei, und das Nachschlagen nach Index ist ebenfalls schnell.

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

Hier ist die Schnittstelle

/// <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);
}
Oberst Panik
quelle
3

Im Anschluss an den Kommentar von @VB finden Sie hier eine barrierefreie Implementierung des System.Runtime.Collections.OrderedDictionary <,> . Ich wollte ursprünglich durch Reflektion darauf zugreifen und es über eine Factory bereitstellen, aber die DLL, in der sich diese befindet, scheint überhaupt nicht sehr zugänglich zu sein, also habe ich einfach die Quelle selbst gezogen.

Eine Sache zu beachten ist, dass der Indexer hier nicht wirft KeyNotFoundException . Ich hasse diese Konvention absolut und das war die Freiheit, die ich mir bei dieser Implementierung genommen habe. Wenn Ihnen das wichtig ist, ersetzen Sie einfach die Leitung für return default(TValue);. Verwendet C # 6 ( kompatibel mit 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;
    }
}

Pull-Anfragen / Diskussion auf GitHub akzeptiert

Chris Marisic
quelle
3

Für diejenigen, die nach einer "offiziellen" Paketoption in NuGet suchen, wurde eine Implementierung eines generischen OrderedDictionary in .NET CoreFX Lab akzeptiert. Wenn alles gut geht, wird der Typ schließlich genehmigt und in das Haupt-Repo von .NET CoreFX integriert.

Es besteht die Möglichkeit, dass diese Implementierung abgelehnt wird.

Auf die festgeschriebene Implementierung kann hier verwiesen werden: https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary

Das NuGet-Paket, für das dieser Typ definitiv verfügbar ist, finden Sie hier https://www.nuget.org/packages/Microsoft.Experimental.Collections/1.0.6-e190117-3

Oder Sie können das Paket in Visual Studio installieren. Suchen Sie nach dem Paket "Microsoft.Experimental.Collections" und stellen Sie sicher, dass das Kontrollkästchen "Prerelease einschließen" aktiviert ist.

Aktualisiert diesen Beitrag, wenn der Typ offiziell verfügbar gemacht wird.

Charlie
quelle
Können Sie abschätzen, wann es veröffentlicht wird?
Mvorisek
Ich beteilige mich nicht an der Entwicklung dieser Bibliothek, daher habe ich leider keine Ahnung. Es ist wahrscheinlich, dass es sich um eine integrierte Framework-Sammlung handelt, falls sie jemals "genehmigt" wird.
Charlie
1

Ich habe ein Generikum implementiert, OrderedDictionary<TKey, TValue>indem ich es umwickelt SortedList<TKey, TValue>und ein privates hinzugefügt habe Dictionary<TKey, int> _order. Dann habe ich eine interne Implementierung von erstellt Comparer<TKey>und einen Verweis auf das _order-Wörterbuch übergeben. Dann benutze ich diesen Komparator für die interne SortedList. Diese Klasse behält die Reihenfolge der an den Konstruktor übergebenen Elemente und die Reihenfolge der Ergänzungen bei.

Diese Implementierung hat fast die gleichen großen O-Eigenschaften wie das SortedList<TKey, TValue>Hinzufügen und Entfernen von _order zu O (1). Jedes Element benötigt (gemäß dem Buch 'C # 4 in a Nutshell', S. 292, Tabelle 7-1) zusätzlichen Speicherplatz von 22 (Overhead) + 4 (int order) + TKey size (nehmen wir 8 an) = 34 Zusammen mit SortedList<TKey, TValue>dem Overhead von zwei Bytes beträgt der Gesamt-Overhead 36 Bytes, während das gleiche Buch besagt, dass nicht generische OrderedDictionaryeinen Overhead von 59 Bytes haben.

Wenn ich an sorted=trueden Konstruktor übergebe, wird _order überhaupt nicht verwendet, das OrderedDictionary<TKey, TValue>ist genau SortedList<TKey, TValue>mit geringem Aufwand für das Umbrechen, wenn überhaupt sinnvoll.

Ich werde nicht so viele große Referenzobjekte in der aufbewahren OrderedDictionary<TKey, TValue>. 36 Bytes Overhead sind tolerierbar.

Der Hauptcode ist unten. Der vollständige aktualisierte Code befindet sich in diesem Kern .

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
quelle
Es gibt mindestens vier verschiedene Anwendungsfälle, die ich für so etwas wie OrderedDictionaryEinfügungen oder Löschungen sehen kann: (1) Es wird niemals Löschungen geben; (2) es wird Löschungen geben, aber wichtig ist, dass die Elemente in der hinzugefügten Reihenfolge aufgelistet werden; Der Zugriff per Index ist nicht erforderlich. (3) Der numerische Index eines Artikels sollte (oder kann zumindest konstant bleiben), und während der Lebensdauer der Sammlung werden nicht mehr als 2 Milliarden Artikel hinzugefügt. Wenn also Artikel 7 entfernt wird, wird es nie wieder einen geben Artikel # 7; (4) Der Index eines Gegenstands sollte sein Rang in Bezug auf Überlebende sein.
Supercat
1
Szenario Nr. 1 könnte mithilfe eines Arrays parallel zum Dictionary. Die Szenarien Nr. 2 und Nr. 3 können behandelt werden, indem jedes Element einen Index verwaltet, der angibt, wann es hinzugefügt wurde, und Links zu Elementen enthält, die davor oder danach hinzugefügt wurden. Szenario 4 ist das einzige, das anscheinend nicht in der Lage sein sollte, eine O (1) -Leistung für Operationen in beliebiger Reihenfolge zu erzielen. Abhängig von den Verwendungsmustern kann # 4 durch die Verwendung verschiedener verzögerter Aktualisierungsstrategien unterstützt werden (Anzahl in einem Baum beibehalten und Änderungen an einem Knoten ungültig machen, anstatt den Knoten und seine Eltern zu aktualisieren).
Supercat
1
Interne SortedList enthält Elemente in Einfügereihenfolge aufgrund der Verwendung eines benutzerdefinierten Vergleichers. Es mag langsam sein, aber Ihr Kommentar zur Aufzählung ist falsch. Zeigen Sie die Tests über die Aufzählung ...
VB
1
Über welche Zeile mit ToDictionary sprechen Sie? Es wirkt sich nicht auf die interne Liste aus, sondern nur auf das Bestellwörterbuch.
VB
1
@VB Entschuldigung, ich habe beide verpasst. Als solches habe ich es nicht getestet. Dann wäre das einzige Problem die Addition. Zwei Wörterbuchsuchen sowie zwei Einfügungen. Ich werde die Abstimmung ablehnen.
Nawfal