Description
EDITED on 4/10/2024 by @stephentoub to update proposal
Often times I've come across places when needing a Dictionary where the insertion order of the elements is important to me. Unfortunately, .NET does not currently have a generic OrderedDictionary class. We've had a non-generic OrderedDictionary class since .NET Framework 2.0 which oddly enough was when generics were added but no generic equivalent. This has forced many to roll their own solution, typically by using a combination of a List and Dictionary field resulting in the worst of both worlds in terms of performance and resulting in larger memory usage, and even worse sometimes users instead rely on implementation details of Dictionary for ordering which is quite dangerous.
Proposed API
namespace System.Collections.Generic;
public class OrderedDictionary<TKey, TValue> :
IDictionary<TKey, TValue>, IReadOnlyDictionary<TKey, TValue>, IDictionary,
IList<KeyValuePair<TKey, TValue>>, IReadOnlyList<KeyValuePair<TKey, TValue>>, IList
where TKey : not null
{
public OrderedDictionary();
public OrderedDictionary(int capacity);
public OrderedDictionary(IEqualityComparer<TKey>? comparer);
public OrderedDictionary(int capacity, IEqualityComparer<TKey>? comparer);
public OrderedDictionary(IDictionary<TKey, TValue> dictionary);
public OrderedDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey>? comparer);
public OrderedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection);
public OrderedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey>? comparer);
public IEqualityComparer<TKey> Comparer { get; }
public OrderedDictionary<TKey, TValue>.KeyCollection Keys { get; }
public OrderedDictionary<TKey, TValue>.ValueCollection Values { get; }
public int Count { get; }
public TValue this[TKey key] { get; set; }
public void Add(TKey key, TValue value);
public void Clear();
public bool ContainsKey(TKey key);
public bool ContainsValue(TValue value);
public KeyValuePair<TKey, TValue> GetAt(int index);
public OrderedDictionary<TKey, TValue>.Enumerator GetEnumerator();
public int IndexOf(TKey key);
public void Insert(int index, TKey key, TValue value);
public bool Remove(TKey key);
public bool Remove(TKey key, [MaybeNullWhen(false)] out TValue value);
public void RemoveAt(int index);
public void SetAt(int index, TValue value);
public void SetAt(int index, TKey key, TValue value);
public void TrimExcess();
public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value);
public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
{
public KeyValuePair<TKey, TValue> Current { get; }
public void Dispose();
public bool MoveNext();
}
public sealed class KeyCollection : IList<TKey>, IReadOnlyList<TKey>, IList
{
public int Count { get; }
public bool Contains(TKey key);
public void CopyTo(TKey[] array, int arrayIndex);
public OrderedDictionary<TKey, TValue>.KeyCollection.Enumerator GetEnumerator();
public struct Enumerator : IEnumerator<TKey>
{
public TKey Current { get; }
public bool MoveNext();
public void Dispose();
}
}
public sealed class ValueCollection : IList<TValue>, IReadOnlyList<TValue>, IList
{
public int Count { get; }
public void CopyTo(TValue[] array, int arrayIndex);
public OrderedDictionary<TKey, TValue>.ValueCollection.Enumerator GetEnumerator();
public struct Enumerator : IEnumerator<TValue>
{
public TValue Current { get; }
public bool MoveNext();
public void Dispose();
}
}
}Perhaps one of the reasons there was no generic OrderedDictionary added initially was due to issues with having both a key and index indexer when the key is an int. A call to the indexer would be ambiguous. Roslyn prefers the non-generic parameter so in this case the index indexer will be called.
API Details
Insertallowsindexto be equal toCountto insert the element at the end.SetAt(int index, TValue value)requiresindexto be less thanCountbutSetAt(int index, TKey key, TValue value)allowsindexto be equal toCountsimilar toInsert.- Performance will be the same as
Dictionaryfor all operations exceptRemovewhich will necessarily beO(n).InsertandRemoveAtwhich aren't members ofDictionarywill also beO(n).
Open Questions
- Should the namespace be
System.Collections.Genericwhen it could easily beSystem.Collections.Specializedwhere the non-generic version is located? I just felt this collection is far more useful to be relegated to that namespace. - Should the non-generic interfaces
ICollection,IList, andIOrderedDictionarybe implemented?
Updates
- Added constructor overloads for
IEnumerable<KeyValuePair<TKey, TValue>>. - Added
ContainsValuemethod due to being needed for theValueCollection.Containsmethod. - Proposal no longer advocates for throwing an exception when using an indexer while the key is an int.