C# 保留插入顺序的通用键/值对集合？

Generic Key/Value pair collection in that preserves insertion order?

提问by FlySwat

I'm looking for something like a Dictionary<K,V> however with a guarantee that it preserves insertion order. Since Dictionary is a hashtable, I do not think it does.

我正在寻找类似 Dictionary<K,V> 的东西，但保证它保留插入顺序。由于 Dictionary 是一个哈希表，我认为它不是。

Is there a generic collection for this, or do I need to use one of the old .NET 1.1 collections?

是否有一个通用集合，或者我是否需要使用旧的 .NET 1.1 集合之一？

采纳答案by McAden

There is not. However, System.Collections.Specialized.OrderedDictionaryshould solve most need for it.

那没有。但是，System.Collections.Specialized.OrderedDictionary应该可以解决它的大部分需求。

EDIT: Another option is to turn this into a Generic. I haven't tested it but it compiles (C# 6) and should work. However, it will still have the same limitations that Ondrej Petrzilka mentions in comments below.

编辑：另一个选择是把它变成一个通用的。我还没有测试过它，但它可以编译（C# 6）并且应该可以工作。但是，它仍然具有 Ondrej Petrzilka 在下面的评论中提到的相同限制。

    public class OrderdDictionary<T, K>
    {
        public OrderedDictionary UnderlyingCollection { get; } = new OrderedDictionary();

        public K this[T key]
        {
            get
            {
                return (K)UnderlyingCollection[key];
            }
            set
            {
                UnderlyingCollection[key] = value;
            }
        }

        public K this[int index]
        {
            get
            {
                return (K)UnderlyingCollection[index];
            }
            set
            {
                UnderlyingCollection[index] = value;
            }
        }
        public ICollection<T> Keys => UnderlyingCollection.Keys.OfType<T>().ToList();
        public ICollection<K> Values => UnderlyingCollection.Values.OfType<K>().ToList();
        public bool IsReadOnly => UnderlyingCollection.IsReadOnly;
        public int Count => UnderlyingCollection.Count;
        public IDictionaryEnumerator GetEnumerator() => UnderlyingCollection.GetEnumerator();
        public void Insert(int index, T key, K value) => UnderlyingCollection.Insert(index, key, value);
        public void RemoveAt(int index) => UnderlyingCollection.RemoveAt(index);
        public bool Contains(T key) => UnderlyingCollection.Contains(key);
        public void Add(T key, K value) => UnderlyingCollection.Add(key, value);
        public void Clear() => UnderlyingCollection.Clear();
        public void Remove(T key) => UnderlyingCollection.Remove(key);
        public void CopyTo(Array array, int index) => UnderlyingCollection.CopyTo(array, index);
    }

回答by adrianbanks

There is an OrderedDictionaryclass that is a dictionary but can be indexed in insertion order, but it is not generified. There is not a generified one in the .Net framework at present.

有一个OrderedDictionary类，它是一个字典，但可以按插入顺序索引，但不能泛化。目前.Net框架中没有泛化的。

I have read a comment somewhere from someone on the .Net team that said that they mayimplement a generified version in the future, but if so it would most likely be called IndexableDictionaryinstead of OrderedDictionaryto make its behaviour more obvious.

我在某处读过 .Net 团队的某个人的评论，说他们可能会在未来实现一个泛型版本，但如果是这样，它很可能会被调用IndexableDictionary而不是OrderedDictionary使其行为更加明显。

EDIT:found the quote. It was on the MSDN page for OrderedDictionary, attributed to David M. Kean from Microsoft:

编辑：找到报价。它在 MSDN 页面上OrderedDictionary，归功于来自 Microsoft 的 David M. Kean：

This type is actually misnamed; it is not an 'ordered' dictionary as such, but rather an 'indexed' dictionary. Although, today there is no equivalent generic version of this type, if we add one in the future it is likely that we will name such as type 'IndexedDictionary'.

这种类型实际上被错误地命名；它本身不是“有序”字典，而是“索引”字典。虽然，今天没有这种类型的等效泛型版本，如果我们将来添加一个，我们很可能会命名为诸如“IndexedDictionary”类型。

回答by Sam Saffron

There is a generic implementation on code projectwhich comes with a reasonable amount of test cases.

代码项目有一个通用的实现，它带有合理数量的测试用例。

The author chose a rather funny name (KeyedList) which makes it pretty hard to find.

作者选择了一个相当有趣的名字（KeyedList），这使得它很难找到。

回答by duffymo

I know you're writing C#, but Java has a class called LinkedHashMap that uses a private LinkedList to maintain the order of insertion of keys. If you can't find a suitable generic solution, perhaps that would be a start on implementing your own.

我知道您正在编写 C#，但 Java 有一个名为 LinkedHashMap 的类，它使用私有 LinkedList 来维护键的插入顺序。如果您找不到合适的通用解决方案，也许这将是实现您自己的解决方案的开始。

回答by Eugene Beresovsky

There actually is one, which is generic and has been around since .net 2.0. It's called ">KeyedCollection<TKey, TItem>. However, it comes with the restriction that it constructs the keys from the values, so it is not a generic Key/Value pair collection. (Although you can of course use it like KeyedCollection<TKey, Tuple<TKey, TItem>>as a workaround).

实际上有一个，它是通用的，自 .net 2.0 以来一直存在。它被称为">KeyedCollection<TKey, TItem>。但是，它带有从值构造键的限制，因此它不是通用的键/值对集合。（尽管您当然可以将其KeyedCollection<TKey, Tuple<TKey, TItem>>用作解决方法）。

If you need it as an IDictionary<TKey, TItem>, it has a .Dictionaryproperty.

如果你需要它作为IDictionary<TKey, TItem>，它有一个.Dictionary属性。

A somewhat minor issue that I have with it is that it is an abstract class and you have to subclass it and implement:

我对它的一个小问题是它是一个抽象类，您必须对其进行子类化并实现：

protected abstract TKey GetKeyForItem(TItem item)

I'd rather just pass a lambda into the constructor for this purpose, but then again, I guess a virtual method is slightly faster than a lambda (any comments on this appreciated).

为此，我宁愿将 lambda 传递给构造函数，但话又说回来，我猜虚拟方法比 lambda 稍快（对此表示赞赏）。

EditAs the question came up in the comments: KeyedCollectionpreserves order, as it inherits from Collection<T>, which does (it derives from IList<T>. See also the documentation of the Add method: Adds an object to the end of the Collection.).

编辑当问题出现在评论中时：KeyedCollection保留顺序，因为它继承自Collection<T>，它确实（它派生自IList<T>。另请参阅 Add 方法的文档：将对象添加到集合的末尾。）。

回答by Carlos A Merighe

Code:

代码：

//A SortedDictionary is sorted on the key (not value)
System.Collections.Generic.SortedDictionary<string, string> testSortDic = new SortedDictionary<string, string>();

//Add some values with the keys out of order
testSortDic.Add("key5", "value 1");
testSortDic.Add("key3", "value 2");
testSortDic.Add("key2", "value 3");
testSortDic.Add("key4", "value 4");
testSortDic.Add("key1", "value 5"); 

//Display the elements.  
foreach (KeyValuePair<string, string> kvp in testSortDic)
{
    Console.WriteLine("Key = {0}, value = {1}", kvp.Key, kvp.Value);
}

Output:

输出：

Key = key1, value = value 5
Key = key2, value = value 3
Key = key3, value = value 2
Key = key4, value = value 4
Key = key5, value = value 1     

回答by John S.

Another option for a Generic Key/Value pair that preserves insertion is to use something like:

保留插入的通用键/值对的另一个选项是使用类似的东西：

Queue<KeyValuePair<string, string>>

This would be a guaranteed ordered list. You can en-queue and dequeue in an ordered faction similar to Add/Remove of dictionary as opposed to resizing an Array. It can often serve as a middle ground between a non-resizing ordered (by insertion) array and an autoresizing unordered (by insertion) list.

这将是一个有保证的有序列表。您可以在类似于添加/删除字典的有序派系中入队和出队，而不是调整数组的大小。它通常可以作为非调整大小的有序（通过插入）数组和自动调整大小的无序列（通过插入）列表之间的中间地带。

回答by Ondrej Petrzilka

If you need constant complexity of Add, Remove, ContainsKeyand order preservation, then there's no such generic in .NET Framework 4.5.

如果你需要不断的复杂性Add，Remove，ContainsKey和订单保存，那么就没有这样的通用在.NET框架4.5。

If you're okay with 3rd party code, take a look at my repository (permissive MIT license): https://github.com/OndrejPetrzilka/Rock.Collections

如果您对 3rd 方代码没问题，请查看我的存储库（MIT 许可许可）：https: //github.com/OndrejPetrzilka/Rock.Collections

There's OrderedDictionary<K,V>collection:

有OrderedDictionary<K,V>收藏：

• source code based on classic Dictionary<K,V>(from .NET Core)
• preserves order of insertionsand allows manual reordering
• features reversed enumeration
• has same operation complexitiesas Dictionary<K,V>
• Addand Removeoperations are ~20% slower compared to Dictionary<K,V>
• consumes 8 more bytes of memory per item

• 基于经典的源代码Dictionary<K,V>（来自.NET Core）
• 保留插入顺序并允许手动重新排序
• 特征反向枚举
• 具有相同的操作复杂性的Dictionary<K,V>
• Add与Remove操作相比，操作慢了约 20%Dictionary<K,V>
• 每个项目多消耗 8 个字节的内存

回答by user2864740

Here is a wrapper for the non-genericSystems.Collections.Specialized.OrderedDictionarytype.

这是非泛型Systems.Collections.Specialized.OrderedDictionary类型的包装器。

This type will return keys/value/pairs sequences in insertion order, much like Ruby 2.0 hashes.

这种类型将按插入顺序返回键/值/对序列，很像 Ruby 2.0 哈希。

It does not require C#6 magic, conforms to IDictionary<TKey,TValue>(which also means that accessing a non-assigned key throws an exception), and ought to be serializable.

它不需要 C#6 魔法，符合IDictionary<TKey,TValue>（这也意味着访问未分配的键会引发异常），并且应该是可序列化的。

It is given the name 'IndexedDictionary' per note on Adrian's answer.

在 Adrian 的回答中，每个注释都将其命名为“IndexedDictionary”。

YMMV.

天啊。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;

/// <summary>
/// A dictionary that maintains insertion ordering of keys.
/// 
/// This is useful for emitting JSON where it is preferable to keep the key ordering
/// for various human-friendlier reasons.
/// 
/// There is no support to manually re-order keys or to access keys
/// by index without using Keys/Values or the Enumerator (eg).
/// </summary>
[Serializable]
public sealed class IndexedDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    // Non-generic version only in .NET 4.5
    private readonly OrderedDictionary _backing = new OrderedDictionary();

    private IEnumerable<KeyValuePair<TKey, TValue>> KeyValuePairs
    {
        get
        {
            return _backing.OfType<DictionaryEntry>()
                .Select(e => new KeyValuePair<TKey, TValue>((TKey)e.Key, (TValue)e.Value));
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return KeyValuePairs.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        _backing[item.Key] = item.Value;
    }

    public void Clear()
    {
        _backing.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        return _backing.Contains(item.Key);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        KeyValuePairs.ToList().CopyTo(array, arrayIndex);
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        TValue value;
        if (TryGetValue(item.Key, out value)
            && Equals(value, item.Value))
        {
            Remove(item.Key);
            return true;
        }
        return false;
    }

    public int Count
    {
        get { return _backing.Count; }
    }

    public bool IsReadOnly
    {
        get { return _backing.IsReadOnly; }
    }

    public bool ContainsKey(TKey key)
    {
        return _backing.Contains(key);
    }

    public void Add(TKey key, TValue value)
    {
        _backing.Add(key, value);
    }

    public bool Remove(TKey key)
    {
        var result = _backing.Contains(key);
        if (result) {
            _backing.Remove(key);
        }
        return result;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        object foundValue;
        if ((foundValue = _backing[key]) != null
            || _backing.Contains(key))
        {
            // Either found with a non-null value, or contained value is null.
            value = (TValue)foundValue;
            return true;
        }
        value = default(TValue);
        return false;
    }

    public TValue this[TKey key]
    {
        get
        {
            TValue value;
            if (TryGetValue(key, out value))
                return value;
            throw new KeyNotFoundException();
        }
        set { _backing[key] = value; }
    }

    public ICollection<TKey> Keys
    {
        get { return _backing.Keys.OfType<TKey>().ToList(); }
    }

    public ICollection<TValue> Values
    {
        get { return _backing.Values.OfType<TValue>().ToList(); }
    }
}