OrderedDictionary没有generics实现？
在.NET 3.5中似乎没有OrderedDictionary （它在System.Collections.Specialized命名空间中）的通用实现。 有没有我失踪的？
我发现那里提供了实现的function，但是想知道为什么没有一个通用的实现，如果有人知道它是否在.NET 4.0中？
你是对的。 在框架本身中没有OrderedDictionary的generics等价物。
（就我所知，.NET4也是如此。）
编辑 ：但是你可以投票它在Visual Studio的UserVoice ！
实现一个generics的OrderedDictionary并不是非常困难，但是这不需要耗费时间，并且坦率地说，这个类对于微软来说是一个巨大的监督。 有多种方式来实现这一点，但我select使用KeyedCollection作为我的内部存储。 我也select实现各种方法来sortingList<T>的方式，因为这本质上是一个混合的IList和IDictionary。 我已经在这里包括我的实现后代。
这是界面。 请注意，它包含System.Collections.Specialized.IOrderedDictionary ，它是Microsoft提供的此接口的非通用版本。
// http://unlicense.org using System; using System.Collections.Generic; using System.Collections.Specialized; namespace mattmc3.Common.Collections.Generic { public interface IOrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IOrderedDictionary { new TValue this[int index] { get; set; } new TValue this[TKey key] { get; set; } new int Count { get; } new ICollection<TKey> Keys { get; } new ICollection<TValue> Values { get; } new void Add(TKey key, TValue value); new void Clear(); void Insert(int index, TKey key, TValue value); int IndexOf(TKey key); bool ContainsValue(TValue value); bool ContainsValue(TValue value, IEqualityComparer<TValue> comparer); new bool ContainsKey(TKey key); new IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator(); new bool Remove(TKey key); new void RemoveAt(int index); new bool TryGetValue(TKey key, out TValue value); TValue GetValue(TKey key); void SetValue(TKey key, TValue value); KeyValuePair<TKey, TValue> GetItem(int index); void SetItem(int index, TValue value); } }
以下是辅助类的实现：
// 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; } } } }
没有一些testing，没有一个实现是完整的（但是不幸的是，不会让我在一篇文章中发布太多的代码），所以我不得不离开你去写testing。 但是，我留下了其中的一些，以便您可以了解它是如何工作的：
// 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
对于logging，有一个通用的KeyedCollection ，它允许通过int和一个键索引对象。 密钥必须embedded在值中。
为了什么是值得的，这里是我如何解决它（编辑，以改善我的第一次尝试）：
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
这是一个奇怪的发现：System.Web.Extensions.dll中的System.Web.Util命名空间包含一个generics的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包，但我认为你可以简单地复制粘贴代码并使用它（它是内部的，所以不能直接使用它）。 看起来像实现使用一个标准的字典和单独的键/值列表。 非常简单…
OrderedDictionary的generics版本的一个主要概念性问题是OrderedDictionary<TKey,TValue>用户期望能够使用int来数字化，或者使用TKey进行查找。 当唯一types的键是Object ，与非genericsOrderedDictionary ，传递给索引器的参数types足以区分是否应执行哪种types的索引操作。 但是，现在还不清楚OrderedDictionary<int, TValue>的索引器应该如何工作。
如果像Drawing.Point这样的类推荐并遵循了一个规则，即分段可变结构应该将其可变元素作为字段而不是属性公开，并避免使用修改this属性的属性设置器，那么OrderedDictionary<TKey,TValue>可以有效地公开ByIndex属性返回一个Indexer结构，该结构持有对字典的引用，并且有一个索引属性，其getter和setter将在其上调用GetByIndex和SetByIndex 。 因此，可以说MyDict.ByIndex[5] += 3; 在字典的第6个元素中加3。 不幸的是，为了让编译器接受这样的事情，有必要使ByIndex属性在每次调用时都返回一个新的类实例而不是一个结构体，从而消除了避免装箱的好处。 在vb.net中，可以使用命名索引属性来解决这个问题（所以MyDict.ByIndex[int]将是MyDict的成员，而不是要求MyDict.ByIndex是包含索引器的MyDict的成员），但C＃不允许这样的事情。
OrderedDictionary<TKey,TValue> where TKey:class提供OrderedDictionary<TKey,TValue> where TKey:class可能还是值得的，但是首先提供generics的大部分原因是允许它们使用值types。
出于很多目的，我发现可以通过List<KeyValuePair<K, V>> 。 （如果你需要扩展Dictionary ，那么不是，如果你需要比O（n）键值查找更好的话。
有SortedDictionary<TKey, TValue> 。 尽pipe在语义上接近，但我并没有声称它和OrderedDictionary一样，因为它们不是。 即使从性能特点。 然而， Dictionary<TKey, TValue> （以及在这种程度上OrderedDictionary和答案中提供的实现）和SortedDictionary之间的非常有趣和相当重要的区别在于后者使用下面的二叉树。 这是至关重要的区别，因为它使类不受应用于generics类的内存限制的影响。 请参阅此线程，了解使用generics类处理大型键值对时OutOfMemoryExceptions 。
如何计算传递给Dictionary构造函数的容量参数的最大值以避免OutOfMemoryException？
对，这是一个不幸的遗漏。 我错过了Python的OrderedDict
一个字典，记住键首次插入的顺序。 如果新条目覆盖现有条目，原始插入位置保持不变。 删除一个条目并重新插入它将会移动到最后。
所以我在C＃中编写了自己的OrderedDictionary<K,V>类。 它是如何工作的？ 它维护两个集合 – 一个香草无序的字典和一个有序的键列表。 有了这个解决scheme，标准的字典操作保持其快速的复杂性，并且按索引查找也是快速的。
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); }
I implemented generic OrderedDictionary<TKey, TValue> by wraping around SortedList<TKey, TValue> and adding private Dictionary<TKey, int> _order . Then I created internal implementation of Comparer<TKey> passing reference to the _order dictionary. Then I use this comparer for internal SortedList. This class keeps order of elements passed to constructor and order of additions.
This implementation has almost the same BigO characteristics as SortedList<TKey, TValue> since Adding and Removing to _order is O(1). Each element will take (according to the book 'C# 4 in a Nutshell', p. 292, table 7-1) additional memory space of 22 (overhead) + 4 (int order) + TKey size (let assume 8) = 34. Together with SortedList<TKey, TValue> overhead of 2 bytes the total overhead is 36 bytes, while the same book says that non-generic OrderedDictionary has overhead of 59 bytes.
If I pass sorted=true to constructor, then _order is not used at all, the OrderedDictionary<TKey, TValue> is exactly SortedList<TKey, TValue> with minor overhead for wrapping, if at all meaningful.
I am going to store not-so-many large reference objects in the OrderedDictionary<TKey, TValue> , so for me this c.36 bytes overhead is tolerable.
The main code is below. The complete updated code is on this 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 prder 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 // ... }
As a follow up to the comment from @VB here's an accessible implementation of the System.Runtime.Collections.OrderedDictionary<,> . I was originally going to access it by reflection and provide it via a factory but the dll this is in does not seem to be very accessible at all so I just pulled the source itself.
One thing to note is the indexer here will not throw KeyNotFoundException . I absolutely hate that convention and that was the 1 liberty i took in this implementation. If that's important to you, just replace the line for return default(TValue); 。 Uses C# 6 ( compatible with 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 requests/discussion accepted on GitHub
I'm not sure if I misunderstood your question, but there is a .NET implementation of OrderedDictionary in System.Collections.Generic.OrderedDictionary apparently available since .NET 2.0, the reference is here: http://msdn.microsoft.com/en-us/library/f7fta44c%28v=vs.80%29.aspx
