Corefxlab: Add a generic OrderedDictionary class

[TylerBrinkley]

Moved from corefx#26634.

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

c# namespace Microsoft.Collections.Extensions { public class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IReadOnlyDictionary<TKey, TValue>, IList<KeyValuePair<TKey, TValue>>, IReadOnlyList<KeyValuePair<TKey, TValue>> { 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> { public struct Enumerator : IEnumerator<TKey> { public TKey Current { get; } public void Dispose(); public bool MoveNext(); } public int Count { get; } public TKey this[int index] { get; } public Enumerator GetEnumerator(); } public sealed class ValueCollection : IList<TValue>, IReadOnlyList<TValue> { public struct Enumerator : IEnumerator<TValue> { public TValue Current { get; } public void Dispose(); public bool MoveNext(); } public int Count { get; } public TValue this[int index] { get; } public Enumerator GetEnumerator(); } public OrderedDictionary(); public OrderedDictionary(int capacity); public OrderedDictionary(IEqualityComparer<TKey> comparer); public OrderedDictionary(int capacity, 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 int Count { get; } public KeyCollection Keys { get; } public ValueCollection Values { get; } public TValue this[int index] { get; set; } public TValue this[TKey key] { get; set; } public void Add(TKey key, TValue value); public void Clear(); public bool ContainsKey(TKey key); public int EnsureCapacity(int capacity); public Enumerator GetEnumerator(); public TValue GetOrAdd(TKey key, TValue value); public TValue GetOrAdd(TKey key, Func<TValue> valueFactory); public int IndexOf(TKey key); public void Insert(int index, TKey key, TValue value); public void Move(int fromIndex, int toIndex); public void MoveRange(int fromIndex, int toIndex, int count); public bool Remove(TKey key); public bool Remove(TKey key, out TValue value); public void RemoveAt(int index); public void TrimExcess(); public void TrimExcess(int capacity); public bool TryAdd(TKey key, TValue value); public bool TryGetValue(TKey key, out TValue value); } }

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. If the user needs to access elements by key they can use the explicit GetValue and SetValue methods.

API Details

• Insert allows index to be equal to Count to insert the element at the end.
• The key indexer will insert if needed, similar to the Dictionary indexer.
• Performance will be the same as Dictionary for all operations except Remove which will necessarily be O(n). Insert and RemoveAt which aren't members of Dictionary will also be O(n).

Performance Characteristics Comparison

Operation | Dictionary | SortedDictionary | SortedList | OrderedDictionary
-- | -- | -- | -- | --
this[key] | O(1) | O(log n) | O(log n) or O(n) | O(1)
this[index] | n/a | n/a | n/a | O(1)
Add(key,value) | O(1) | O(log n) | O(n) | O(1)
Remove(key) | O(1) | O(log n) | O(n) | O(n)
RemoveAt(index) | n/a | n/a | n/a | O(n)
ContainsKey(key) | O(1) | O(log n) | O(log n) | O(1)
IndexOf(key) | n/a | n/a | n/a | O(1)
Insert(index,key,value) | n/a | n/a | n/a | O(n)
Space efficiency | good | worst | medium | good

Open Questions

• Should the non-generic interfaces ICollection, IList, IDictionary, and IOrderedDictionary be implemented?

Updates

• Added constructor overloads for IEnumerable<KeyValuePair<TKey, TValue>>.
• Added ContainsValue method due to being needed for the ValueCollection.Contains method.
• Proposal no longer advocates for throwing an exception when using an indexer while the key is an int.
• Changed namespace for corefxlab.
• Removed IDictionary<TKey, TValue> constructor overloads as they can be handled in the IEnumerable<KeyValuePair<TKey, TValue>> overload.
• Removed ContainsValue method as it's being implemented in the ValueCollection.Contains method.
• Made KeyCollection and ValueCollection's CopyTo method use explicit interface implementation.
• Added EnsureCapacity(int capacity) and TrimExcess(int capacity) methods.
• Added Move and MoveRange methods.
• Added the SetAt(int, TKey, TValue) method overload.
• Added ref returning methods.
• Removed ref returning methods as the ref return values become invalidated when the internal array resizes.
• Made KeyCollection and ValueCollection constructors internal as it doesn't seem valuable.
• Added getter-only indexers to KeyCollection and ValueCollection.
• Removed GetAt, GetValue, SetAt, and SetValue methods as they're unnecessary with the indexers.

[TylerBrinkley]

I've implemented an OrderedDictionary<TKey, TValue> in my dev branch. It still needs tests and documentation but it's a start.

[danmoseley]

@TylerBrinkley as you say several mutation operations are O(n) because they keep the entries array ordered. Did you decide against a binary tree because of O(log(n)) lookup? It depends on the application of course, but if the size becomes large, mutations would be slow and allocatey.

[TylerBrinkley]

Yes, O(1) lookups are very important to me. From my experience, collections are initialized and aren't modified after that point so mutation performance isn't as important to me. I know I don't speak for everyone but that has been my experience.

It would have the same performance characteristics besides removal as Dictionary, which is probably the most used collection besides List which in my opinion is due to its O(1) lookups.

[MelnikovIG]

@danmosemsft Hello, when this change will be available in .net core?

[danmoseley]

@MelnikovIG right now you need to get the nuget package
https://www.nuget.org/packages/Microsoft.Experimental.Collections

As with anything in corefxlab, it may go into .NET Core proper in future. It depends on things like how widely used the package is, whether we feel good about the implementation and API, whether it feels like a good fit (eg is there a reason why a package couldn't be used indefinitely)

We welcome any feedback or PR's meantime. (In a new issue)

Hope this helps.

[SoftCircuits]

@MelnikovIG right now you need to get the nuget package
https://www.nuget.org/packages/Microsoft.Experimental.Collections

I don't see where the documentation for this package says anything about an OrderedDictionary class. Did I miss it?

BTW, here's the code I came up with. But seems like it should be part of .NET.

public class OrderedDictionary<TKey, TValue> : IEnumerable<TValue>
{
    private readonly Dictionary<TKey, int> IndexLookup;
    private readonly List<TValue> Items;

    public OrderedDictionary()
    {
        IndexLookup = new Dictionary<TKey, int>();
        Items = new List<TValue>();
    }

    public OrderedDictionary(IEqualityComparer<TKey> comparer)
    {
        IndexLookup = new Dictionary<TKey, int>(comparer);
        Items = new List<TValue>();
    }

    public int Add(TKey key, TValue value)
    {
        int index = Items.Count;
        IndexLookup.Add(key, index);
        Items.Add(value);
        return index;
    }

    public void AddRange(IEnumerable<KeyValuePair<TKey, TValue>> collection)
    {
        foreach (var pair in collection)
            Add(pair.Key, pair.Value);
    }

    public void AddRange(OrderedDictionary<TKey, TValue> collection)
    {
        AddRange(collection.GetKeyValuePairs());
    }

    public TValue this[int index]
    {
        get => Items[index];
        set => Items[index] = value;
    }

    public TValue this[TKey key]
    {
        get => Items[IndexLookup[key]];
        set => Items[IndexLookup[key]] = value;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        if (IndexLookup.TryGetValue(key, out int index))
        {
            value = Items[index];
            return true;
        }
        value = default;
        return false;
    }

    public void Clear()
    {
        Items.Clear();
        IndexLookup.Clear();
    }

    public int Count => Items.Count;

    public bool ContainsKey(TKey key) => IndexLookup.ContainsKey(key);

    public int IndexOf(TKey key) => IndexLookup.TryGetValue(key, out int index) ? index : -1;

    public List<TKey> Keys => new List<TKey>(IndexLookup.Keys);

    public List<TValue> Values => new List<TValue>(Items);      // Don't return original list

    public IEnumerable<KeyValuePair<TKey, TValue>> GetKeyValuePairs() => IndexLookup.Keys.Select(k => new KeyValuePair<TKey, TValue>(k, Items[IndexLookup[k]]));

    #region IEnumerable

    public IEnumerator<TValue> GetEnumerator() => Items.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => Items.GetEnumerator();

    #endregion

}

[danmoseley]

@SoftCircuits the OrderedDictionary is in that package. Not sure what documentation you're referring to.

[SoftCircuits]

@SoftCircuits the OrderedDictionary is in that package. Not sure what documentation you're referring to.

I clicked https://www.nuget.org/packages/Microsoft.Experimental.Collections and then clicked Project Site. And the documentation on that page (README.md) says nothing about OrderedDictionary.

[danmoseley]

@SoftCircuits ah right. 😸 If you find the type useful and would like to offer a PR to fix that README.md, we'd welcome it. DictionarySlim is also in there but not mentioned in the readme.