没有 OrderedDictionary 的通用实现？

Question

.NET 3.5 中似乎没有 OrderedDictionary（位于 System.Collections.Specialized 命名空间中）的通用实现。我是否缺少一个？

我已经找到了提供该功能的实现，但想知道是否/为什么没有开箱即用的通用实现，以及是否有人知道它是否是 .NET 4.0 中的东西？

Answer 1

实现通用的 OrderedDictionary 并不是非常困难，但它不必要地耗费时间，坦率地说，这个类是 Microsoft 的一个巨大疏忽。有多种方法可以实现此目的，但我选择使用 KeyedCollection 作为我的内部存储。我还选择实现各种方法来按照 List 的方式进行排序，因为这本质上是 IList 和 IDictionary 的混合体。我已将我的实现包含在此处以供后代使用。

这是界面。请注意，它包括 System.Collections.Specialized.IOrderedDictionary，它是 Microsoft 提供的此接口的非通用版本。

// https://choosealicense.com/licenses/unlicense
// or https://choosealicense.com/licenses/mit/
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);
    }

}

这是实现以及辅助类：

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

如果没有一些测试，任何实现都是不完整的（但悲惨的是，所以不允许我在一篇文章中发布那么多代码），所以我不得不让你编写测试。但是，我留下了其中的一些内容，以便您可以了解它是如何工作的：

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

--更新--

此库和其他真正有用的缺失核心 .NET 库的来源：https://github.com/mattmc3/dotmore/blob/master /dotmore/Collections/Generic/OrderedDictionary.cs

更新要点链接：https://gist. github.com/mattmc3/6889f6b3fb1b5d74ebec7883f5825ea1

Answer 2

你说得对。框架本身没有 OrderedDictionary 的通用等效项。

（据我所知，.NET 4 也是如此。）

Answer 3

根据记录，有一个通用的 KeyedCollection 允许对对象建立索引通过一个 int 和一个键。键必须嵌入到值中。

Answer 4

这是一个奇怪的发现：System.Web.Extensions.dll 中的 System.Web.Util 命名空间包含一个通用的 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

不知道为什么 MS 将它放在那里而不是 System.Collections.Generic 包，但我假设您可以简单地复制粘贴代码并使用它（它是内部的，所以不能直接使用它）。看起来该实现使用了标准字典和单独的键/值列表。非常简单...

• 源代码： https://referencesource.microsoft .com/#System.Web.Extensions/Util/OrderedDictionary.cs
• System.Runtime.Collections 中的一个不同实现，它包装了非通用的 System.Collections.Specialized。 OrderedDictionary： https://referencesource .microsoft.com/#System.ServiceModel.Internals/System/Runtime/Collections/OrderedDictionary.cs

Answer 5

对于它的价值，这是我解决它的方法：

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

它可以像这样初始化：

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

并像这样访问：

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

// Guaranteed to print in the order of initialization

Answer 6

OrderedDictionary 的通用版本的一个主要概念问题是 OrderedDictionary 的用户希望能够使用 OrderedDictionary 对其进行数字索引>int，或使用 TKey 进行查找。当唯一的键类型是 Object 时，就像非泛型 OrderedDictionary 的情况一样，传递给索引器的参数类型足以区分什么类型应执行索引操作。但实际上，尚不清楚 OrderedDictionary 的索引器应如何运行。

如果像 Drawing.Point 这样的类建议并遵循分段可变结构应将其可变元素公开为字段而不是属性的规则，并且避免使用修改 this，然后 OrderedDictionary 可以有效地公开一个 ByIndex 属性，该属性返回一个 Indexer 结构，该结构保存对字典的引用，并且有一个索引属性，其 getter 和 setter 将对其调用 GetByIndex 和 SetByIndex 。因此，可以说类似 MyDict.ByIndex[5] += 3; 将 3 添加到字典的第六个元素。

不幸的是，为了让编译器接受这样的事情，有必要让 ByIndex 属性在每次调用时返回一个新的类实例而不是一个结构体，从而消除了通过避免装箱获得的优势。

在 VB.NET 中，可以通过使用命名索引属性来解决该问题（因此 MyDict.ByIndex[int] 将成为 MyDict 的成员，而不需要 < code>MyDict.ByIndex 成为包含索引器的 MyDict 的成员），但 C# 不允许这样的事情。

提供一个 OrderedDictionary 可能仍然是值得的。其中 TKey:class，但首先提供泛型的大部分原因是允许它们与值类型一起使用。

Answer 7

对于很多目的，我发现可以使用 List> 来实现。 （显然，如果您需要它来扩展Dictionary，则不需要，如果您需要比 O(n) 更好的键值查找，则不需要。）

Answer 8

对于那些在 NuGet 中寻找“官方”包选项的人来说，通用 OrderedDictionary 的实现已被 .NET CoreFX 实验室接受。如果一切顺利，该类型最终将获得批准并集成到主 .NET CoreFX 存储库中。

此实现有可能会被拒绝。

可以在此处引用已提交的实现
https://github .com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary.cs

可以在此处找到明确可供使用的此类型的 NuGet 包
https://www.nuget.org/packages/Microsoft .Experimental.Collections/1.0.6-e190117-3

或者您可以在 Visual Studio 中安装该包。浏览包“Microsoft.Experimental.Collections”并确保选中“包括预发布”复选框。

如果该类型正式可用，我们将更新这篇文章。

Answer 9

是的，这是一个不幸的遗漏。我怀念 Python 的 OrderedDict

记住键首次插入顺序的字典。如果新条目覆盖现有条目，则原始插入位置保持不变。删除条目并重新插入会将其移动到末尾。

所以我用 C# 编写了自己的 OrderedDictionary 类。它是如何运作的？它维护两个集合 - 一个普通的无序字典和一个有序的键列表。通过这个解决方案，标准字典操作保持了其快速的复杂性，并且通过索引查找也很快。

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

这是界面

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

Answer 10

有SortedDictionary。尽管在语义上很接近，但我并不是说它与 OrderedDictionary 相同，因为它们并非如此。即使从性能特征来看。然而， Dictionary （以及在某种程度上 OrderedDictionary 和答案中提供的实现）和 SortedDictionary 之间非常有趣且非常重要的区别是后者在下面使用二叉树。这是至关重要的区别，因为它使类不受应用于泛型类的内存约束的影响。请参阅此线程，了解使用泛型类处理大量键值对时抛出的 OutOfMemoryExceptions。

如何计算最大值传递给 Dictionary 构造函数以避免 OutOfMemoryException 的容量参数值？

Answer 11

作为 @VB 评论的后续，这里有一个可访问的实现 System.Runtime.Collections.OrderedDictionary<,>。我最初打算通过反射访问它并通过工厂提供它，但是它所在的 dll 似乎根本无法访问，所以我只是提取源代码本身。

需要注意的一件事是这里的索引器不会抛出 KeyNotFoundException。我绝对讨厌那个约定，这是我在这个实现中所采取的第一个自由。如果这对您很重要，只需替换 return default(TValue); 行即可。使用 C# 6（与 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;
    }
}

GitHub 上接受的拉取请求/讨论

Answer 12

我通过环绕 SortedList 并添加私有 Dictionary 实现了通用 OrderedDictionary _order。然后，我创建了 Comparer 的内部实现，传递对 _order 字典的引用。然后我将此比较器用于内部 SortedList。此类保留传递给构造函数的元素的顺序以及添加的顺序。

此实现具有与 SortedList 几乎相同的大 O 特性，因为添加和删除 _order 的时间复杂度为 O(1)。每个元素将占用（根据《C# 4 in a Nutshell》一书，第 292 页，表 7-1）额外的内存空间 22（开销）+ 4（int order）+ TKey 大小（假设 8）= 34加上SortedList的两个字节的开销，总开销是36字节，而同一本书上说非泛型OrderedDictionary有开销。 59 字节。

如果我将 sorted=true 传递给构造函数，则根本不使用 _order，OrderedDictionary 正是 SortedList< /code> 如果有意义的话，包装的开销很小。

我将在 OrderedDictionary 中存储不多的大型引用对象，所以对我来说这个 ca. 36 字节的开销是可以接受的。

主要代码如下。完整的更新代码位于此 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
    // ...
}

Answer 13

这不是 OrderedDictionary<,> 的另一个版本/解决方案，而是我测试答案中提到的 4 个版本中的每一个的实验：@Colonel Panic、@mattmc3、@VB @Chris Marisic 。这是一种反馈。好吧，部分是因为我必须承认我没有剖析代码，所以功能或安全检查可能存在差异。但我仍然认为反馈对他们的表现很有用。正如您将看到的，时间可以从几毫秒到一刻钟。
然后我用 O(n) 搜索编写了一个简单的最小版本，其中包含 2 个键和值类对象列表，只是为了看看 O(1) 访问的好处的大小。

测试平台是带有 Unity 3D 的 Microsoft Visual Studio Community 2019，每次测试连续 4 次，我想在其中复制真实场景的代码是

using System.Text;
using UnityEngine;

public class TessyOne : MonoBehaviour
{
    public const int iterations = 50000;
    private System.Diagnostics.Stopwatch stopwatch;
    private System.Random random;
    public float stopwatchDuration;

    public class Ala
    {
        public int inta;
        public float fla;
        public string stra;
        public Ben bena;

        public Ala(int i, float f, string s, Ben b)
        {
            inta = i; fla = f; stra = s; bena = b;
        }
    }

    public class Ben
    {
        public int inte;
        public float fle;
        public string stre;

        public Ben(int i, float f, string s)
        {
            inte = i; fle = f; stre = s;
        }
    }

    //public Naive.OrderedDictionary<Ala, Ben> alasToBens = new Naive.OrderedDictionary<Ala, Ben>();
    //public Hickford.OrderedDictionary<Ala, Ben> alasToBens = new Hickford.OrderedDictionary<Ala, Ben>();
    //public Mattmc3.OrderedDictionary<Ala, Ben> alasToBens = new Mattmc3.OrderedDictionary<Ala, Ben>();
    public Marisic.OrderedDictionary<Ala, Ben> alasToBens = new Marisic.OrderedDictionary<Ala, Ben>();
    //public VB.OrderedList<Ala, Ben> alasToBens = new VB.OrderedList<Ala, Ben>(null, false);

    Ala[] alarray = new Ala[iterations];
    Ben[] berray = new Ben[iterations];

    // This is the entry point of the application 
    private void Start()
    {
        stopwatch = new System.Diagnostics.Stopwatch();
        random = new System.Random(2020);

        for(int i = 0; i < iterations; ++i)
        {
            berray[i] = new Ben(random.Next(),
                                (float)random.NextDouble(),
                                MakeRandomString((ushort)random.Next(1, 10)));
            alarray[i] = new Ala(random.Next(),
                                 (float)random.NextDouble(),
                                  MakeRandomString((ushort)random.Next(1, 10)),
                                  berray[i]);
            // uncomment for testing ContainsKey() and Remove(), comment for Add()
            alasToBens.Add(alarray[i], berray[i]);
        }
    
        stopwatch.Start();
        for(int i = iterations - 1; i > -1; --i)
        {
            //alasToBens.Add(alarray[i], berray[i]);
            //alasToBens.ContainsKey(alarray[i]);
            alasToBens.Remove(alarray[i]);
        }
        stopwatch.Stop();
        stopwatchDuration = stopwatch.ElapsedMilliseconds;
    }

    public string MakeRandomString(ushort length)
    {
        StringBuilder sb = new StringBuilder();
        for(ushort u = 0; u < length; ++u)
        {
            sb.Append((char)Random.Range(33, 126)); // regular ASCII chars
        }
        return sb.ToString();
    }
}

请注意，测试至少针对初始版本的最坏情况场景，因为它从索引 0 到迭代遍历集合，并且搜索是从结束到开始完成的。我以毫秒为单位测量了包含 50000 个条目的字典的 Add()、ContainsKey() 和 Remove()。
结果：

+----------+----------------+----------------+--------------------------------+
|    ms    |     Add()      | ContainsKey()  |            Remove()            |
+----------+----------------+----------------+--------------------------------+
| Hickford |     7, 8, 7, 8 |     2, 2, 3, 2 |         7400, 7503, 7419, 7421 |
| Mattmc3  | 23, 24, 24, 23 |     3, 3, 3, 3 | 890404, 913465, 875387, 877792 |
| Marisic  | 27, 28, 28, 27 |     4, 4, 4, 4 |     27401, 27627, 27341, 27349 |
| V.B.     | 76, 76, 75, 75 | 59, 60, 60, 60 |                 66, 67, 67, 67 |
|          |                |                |                                |
| Naive    |   19651, 19761 |   25335, 25416 |                   25259, 25306 |
+----------+----------------+----------------+--------------------------------+

Answer 14

.NET 9 将包含一个通用的 OrderedDictionary。这是合并的拉取请求： https://github.com/dotnet/runtime/pull/103309< /a>