没有 OrderedDictionary 的通用实现？

中似乎没有 OrderedDictionary的通用实现(在 System.Collections.Specialized名称空间中)。NET 3.5.有没有我漏掉的？

我已经找到了可以提供这些功能的实现，但是我想知道是否/为什么没有一个开箱即用的通用实现，以及是否有人知道它是否包含这些功能。NET 4.0？

53417 次浏览
小开
最佳答案

你是对的。在框架本身中没有 OrderedDictionary的通用等价物。

(据我所知，.NET 4也是如此。)

小开

对于很多目的，我已经发现一个可以通过与 List<KeyValuePair<K, V>>。(当然，如果您需要它来扩展 Dictionary，并且需要比 O (n)键值查找更好的方法，就不需要它。)

小开

对于记录，有一个通用的 KeyedCollection，它允许对象通过 int 和 key 进行索引。键必须嵌入到值中。

小开

不管怎样，我是这么解决的:

   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
小开

实现一个通用的 OrderedDictionary并不是非常困难，但是它不必要地耗费时间，坦率地说，这个类是微软的一个巨大的疏忽。有多种实现方法，但是我选择使用 KeyedCollection作为内部存储。我还选择实现各种方法来按照 List<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; } }
}
}

如果没有几个测试，任何实现都是不完整的(但不幸的是，SO 不允许我在一篇文章中发布那么多代码) ，因此我将不得不让您自己编写测试。但是，我留了一些在里面，这样你就可以知道它是如何工作的:

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

小开

OrderedDictionary通用版本的一个主要概念性问题是，OrderedDictionary<TKey,TValue>的用户希望能够使用 int对其进行数字索引，或者使用 TKey进行查找。当键的唯一类型是 Object时，就像非泛型 OrderedDictionary的情况一样，传递给索引器的参数类型将足以区分是否应该执行什么类型的索引操作。尽管如此，目前还不清楚 OrderedDictionary<int, TValue>的索引器应该如何工作。

如果像 Drawing.Point这样的类推荐并遵循一个规则，即分段可变的结构应该将它们的可变元素作为字段而不是属性公开，并避免使用修改 this的属性设置器，那么 OrderedDictionary<TKey,TValue>可以有效地公开返回 Indexer结构的 ByIndex属性，该结构包含对字典的引用，并且有一个索引属性，其 getter 和 setter 将对该属性调用 GetByIndex和 SetByIndex。因此，我们可以使用类似于 MyDict.ByIndex[5] += 3;的代码将3添加到字典的第六个元素中。

不幸的是，为了让编译器接受这样的事情，每次调用 ByIndex属性时都需要返回一个新的类实例，而不是一个结构，这样就消除了避免装箱的好处。

在 VB.NET 中，可以通过使用命名索引属性来解决这个问题(因此 MyDict.ByIndex[int]将是 MyDict的成员，而不是要求 MyDict.ByIndex是包含索引器的 MyDict的成员) ，但是 C # 不允许这样做。

提供一个 OrderedDictionary<TKey,TValue> where TKey:class可能仍然是值得的，但是首先提供泛型的主要原因是允许它们与值类型一起使用。

小开

我通过包装 SortedList<TKey, TValue>并添加一个私有的 Dictionary<TKey, int> _order来实现一个通用的 OrderedDictionary<TKey, TValue>。然后，我创建了 Comparer<TKey>的内部实现，传递了对 _ order 字典的引用。然后我将这个比较器用于内部 SortedList。此类保持传递给构造函数的元素的顺序和添加的顺序。

这个实现具有与 SortedList<TKey, TValue>几乎相同的大 O 特征，因为添加和删除 to _ order 是 O (1)。每个元素都需要额外的内存空间(根据《 C # 4 in a Nutshell 》 ，第292页，表7-1)22(开销) + 4(整数顺序) + TKey size (让我们假设8) = 34。加上 SortedList<TKey, TValue>两个字节的开销，总开销为36字节，而同一本书说，非通用 OrderedDictionary的开销为59字节。

如果我将 sorted=true传递给构造函数，那么根本不使用 _ order，那么 OrderedDictionary<TKey, TValue>就是 SortedList<TKey, TValue>，只有很少的包装开销，如果有意义的话。

我将在 OrderedDictionary<TKey, TValue>中存储不太多的大型引用对象，所以对我来说，大约36字节的开销是可以忍受的。

主代码如下。完整的更新代码在这个 大意上。

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
// ...
}
小开

好吧，这是个不幸的遗漏，我想念巨蟒的 命令

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

所以我用 C # 编写了自己的 OrderedDictionary<K,V>类。它是怎么工作的？它维护两个集合——一个普通的无序字典和一个有序的键列表。该方案保持了标准字典操作的快速复杂性，并且通过索引进行查找的速度也很快。

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);
}
小开

这里有一个奇怪的发现: System.Web.Extensions.dll中的 System.Web.Util名称空间包含一个通用的 OrderedDictionary<TKey,TValue>

// 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 把它放在那里而不是系统。收款。泛型包，但是我假设您可以简单地复制粘贴代码并使用它(它是内部的，所以不能直接使用它)。看起来这个实现使用了一个标准字典和单独的键/值列表。非常简单。

小开

有 SortedDictionary<TKey, TValue>。尽管在语义上很接近，但我并不是说它们与 OrderedDictionary是相同的，因为它们不是。即使从性能特征来看。然而，Dictionary<TKey, TValue>和 SortedDictionary之间非常有趣而且非常重要的区别在于，后者在底层使用的是二叉树(在这个范围内，OrderedDictionary和答案中提供的实现)。这是至关重要的区别，因为它使类免疫应用于泛型类的内存约束。当泛型类用于处理大量键-值对时，请参阅关于 OutOfMemoryExceptions的此线程。

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

小开

作为@V 评论的后续。这是 System.Runtime.Collections.OrderedDictionary < ，> 的一个可访问的实现。我原本打算通过反射访问它，并通过工厂提供它，但是这里的 dll 似乎根本不是很容易访问，所以我只是提取了源代码本身。

需要注意的一点是这里的索引器 不会扔 KeyNotFoundException。我非常讨厌那个公约，那是我在这个实现中采取的一个自由。如果这对您很重要，只需替换 return default(TValue);的行。使用 C # 6(与 VisualStudio2013兼容)

/// <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 上接受的请求/讨论

小开

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

这种实现可能会被拒绝。

这里可以引用已提交的实现 Https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft。实验性。收藏/微软/收藏/扩展/ ordereddictionary.cs

这里可以找到确定具有此类型可用的 NuGet 包 Https://www.nuget.org/packages/microsoft 实验收藏/1.0.6-e190117-3

或者可以在 VisualStudio 中安装该包。浏览软件包“ Microsoft。实验性的。并确保选中了“包含预发布”复选框。

将更新这篇文章，如果和当类型是正式可用的。

小开

这不是 OrderedDictionary<,>的另一个版本/解决方案，而是我做的一个实验，测试了答案中提到的4个版本:@Colonel Panic,@mattmc3,@V。B@Chris Marisic.这是一种反馈。部分原因是因为我必须承认我没有仔细分析过代码所以可能在功能和安全检查上有所不同。但是，我仍然认为反馈对他们的表现是有用的。你会看到时间从几毫秒变成了一刻钟。 然后，我用 O (n)搜索的方法草草写了一个简单的最小版本，其中包含2个键和值类对象列表，只是为了看看 O (1)访问的好处有多大。

Testbed 是 Microsoft Visual Studio Community 2019，具有 Unity 3D，每个测试连续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到 iterations迭代集合，并且从头到尾搜索。我以毫秒为单位测量了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 |
+----------+----------------+----------------+--------------------------------+

提交答案