Add a generic OrderedDictionary class

[TylerBrinkley]

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>, IList<KeyValuePair<TKey, TValue>>, IReadOnlyList<KeyValuePair<TKey, TValue>>
+{
+    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, 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, 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>
+    {
+        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>
+    {
+        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

• Insert allows index to be equal to Count to insert the element at the end.
• SetAt(int index, TValue value) requires index to be less than Count but SetAt(int index, TKey key, TValue value) allows index to be equal to Count similar to Insert.
• 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).

Open Questions

• Should the namespace be System.Collections.Generic when it could easily be System.Collections.Specialized where 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, 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.

[sharwell]

📝 Technically SortedList<TKey, TValue> is an ordered dictionary. My implementation of SortedTreeDictionary<TKey, TValue> is based on the API from this type.

Edit: (And removing my related comments that followed) I was not aware of the semantics of the non-generic OrderedDictionary when I posted this. I was instead thinking this request was either for SortedList<TKey, TValue> or for something like LinkedHashMap<K, V>. The OrderedDictionary.Insert method semantics cleared things up for me.

[TylerBrinkley]

@sharwell SortedList and SortedDictionary are not hash tables but trees resulting in O(log(n)) lookups instead of O(1) for Dictionary.

[TylerBrinkley]

Related to dotnet/corefx#26638

[danmoseley]

Would the implementation optimize for retrieval (presumably array + hashtable) or for space (presumably a tree/heap) ? Are there scenarios for both? What complexity do you hope for for lookup, Add, Remove, and ContainsKey (and ContainsValue if we have that)

[snipped example table in favor of @TylerBrinkley 's below]

[TylerBrinkley]

Thanks for putting that chart together. The implementation will be nearly identical to Dictionary<K,V> with a bucket and entries array except the entries in the entries array will be contiguous and ordered.

Below is the chart filled out

Operation	Dictionary<K,V>	SortedDictionary<K,V>	SortedList<K,V>	OrderedDictionary<K,V>
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)
ContainsValue(value)	O(n)	O(n)	O(n)	O(n)
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
Insert/Remove sorted data	n/a	O(log n)	O(n)	n/a
From sorted data	n/a	?	better?	n/a

[sharwell]

💭 I almost prefer the indexer for this type be based on the "bias" implied by the type name. To me, OrderedDictionary<TKey, TValue> would bias towards dictionary, which means this[key] would be the only indexer. Indexed access could be achieved by calling GetAt(index) or by casting to IList<TValue> (or IList<KeyValuePair<TKey, TValue>>?) and using the indexer there.

[TylerBrinkley]

If we only have one I'd agree that the this[key] indexer would be the one to stay. Like you said, indexed access could still be achieved with the GetAt and SetAt methods and then the GetValue and SetValue methods could be removed. I'm torn on this because a this[index] indexer would be very intuitive to users and a vast majority of time would not be an issue.

[TylerBrinkley]

FYI, if this gets approved I'd happily implement it.

[JustArchi]

I'd also be interested in seeing generic variant of OrderedDictionary, I was seriously confused when I found out that there is no such thing as of now, while non-generic version already exists.

Thank you in advance for considering this.

[prajaybasu]

Hello, I too would like to see a generic version of this, and have it moved to the System.Collections.Generic namespace.
A quick Google Search shows that the generic version is implemented by a lot of library authors themselves:

• Wintellect.PowerCollections
• IBM.WebSphere.Caching
• Accord.Collections
• Cadenza.Collections

and so on..

So it would be nice to have this type implemented in the framework.

[shaggygi]

I still think it would be beneficial to have Immutable Parent/Child Collection, but understand it is not specifically related to this thread.

[wanton7]

Just had need for this today. Any news if/when this will be implemented?

[TylerBrinkley]

Moved to corefxlab#2456 as part of the specialized collections initiative.

[eiriktsarpalis]

Reopening in place of #29570. For context this has already been included in corefxlab via dotnet/corefxlab#2525

[c0nd3v]

Bump

[ahdung]

Any news?

[eiriktsarpalis]

We have no plans on adding such a type in our immediate roadmap. We will post an update on this thread as soon as anything changes.

[alelom]

This has been around in various forms and other issues for years now. Is there really no priority in closing a glaring gap in Microsoft Collections? Especially given that it has been done time and time again, and with a general messiness in its placement - moved from a repo to another, without a stable nuget available. I dislike having to resort to third-party implementations for stuff like this.

[AndriySvyryd]

Also consider adding these methods

void Sort()
void Sort(IComparer<TKey> Comparer)
void SortedInsert(TKey key, TValue value)
void SortedInsert(TKey key, TValue value, IComparer<TKey> Comparer)

[JoshuaNitschke]

Came here to say I would like this too.

[claudiudc]

Thanks for putting that chart together. The implementation will be nearly identical to Dictionary<K,V> with a bucket and entries array except the entries in the entries array will be contiguous and ordered.

Below is the chart filled out
Operation Dictionary<K,V> SortedDictionary<K,V> SortedList<K,V> OrderedDictionary<K,V>
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)
ContainsValue(value) O(n) O(n) O(n) O(n)
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
Insert/Remove sorted data n/a O(log n) O(n) n/a
From sorted data n/a ? better? n/a

Why Remove(key) and RemoveAt(index) are O(n) for OrderedDictionary?
They should be O(1)

Implementation should keep the index as a (int, TValue) in the value of the key itself.

[tjpalmer]

Different solutions are possible, and remove is the hard part of ordered dictionaries.

• Keeping the index with the entry makes for fast add and remove but slow iteration. Also potentially limits the lifetime of a dictionary with lots of add and remove.
• Current non-generic OrderedDictionary instead has O(n) removal but allows for O(1) ordered access.
• Allowing sparsity in the entry array (like in CPython and V8, if I understand correctly) allows for faster removal at increased memory cost.
• Other options like the Rust crate IndexMap lose insertion order on remove but are fast otherwise.
• LinkedHashMap in Java needs lots of individually allocated objects and has to jump around for iteration.
• Making a dense array of entries with indices for linked list avoid lots of objects but has a bit more overhead than just the order number and still requires jumping around on iteration.

Different decisions make different presumptions about how something's being used and/or what the user cares about.

[claudiudc]

This is just a possible impl(not smart enough) of such a need, however without having detailed checking, sync for updates, sync of capacity(size of dict + list) and many more. And the concept can be optimized a lot to use less than 3 objects(self and 2 collections)
I will try to see if I can get some time to give a clean one

Short objective: an ordered dictionary(dictionary + ordered elements used in foreach, based on insertion order)

• so not an ordered dictionary + an ordered list that overcomplicates thinks with indexes, we don't need indexes for this requirement.

Obs: I do not see a problem on iterations
I do not see a lifetime problem
So: add, set, remove, iterate would have O(1), when the capacity of collection has not extended beyond the allocated size
Of course, you pay for what you need: memory

[DebuggerDisplay($"{{{nameof(ToDebuggerDisplay)}(),nq}}")]
internal class SortedDictionary<Tkey,TValue> :IReadOnlyCollection<TValue>
{
    [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
    private readonly LinkedList<TValue> _valuesNodes;
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    private readonly Dictionary<Tkey, LinkedListNode<TValue>> _toProbePropertyNodesByName;

    public SortedDictionary()
    {
        _valuesNodes = new LinkedList<TValue>();
        _toProbePropertyNodesByName = new Dictionary<Tkey, LinkedListNode<TValue>>();
    }

    IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator()
    {
        return _valuesNodes.GetEnumerator();
    }

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


    public void Add(Tkey key, TValue value)
    {
        lock (_valuesNodes)
        {
            ref LinkedListNode<TValue> valueByRef = ref CollectionsMarshal.GetValueRefOrAddDefault(_toProbePropertyNodesByName, key, out bool exists);
            if (exists)
            {
                throw new ArgumentException($"An item with the same key has already been added. Key: {key}'");
            }
            else
            {
                valueByRef = _valuesNodes.AddLast(value);
            }
        }
    }

    public bool Remove(Tkey key)
    {
        bool entryWasRemoved;
        lock (_valuesNodes)
        {
            entryWasRemoved = _toProbePropertyNodesByName.Remove(key, out var removedValue);
            if (entryWasRemoved)
            {
                _valuesNodes.Remove(removedValue);
            }
        }
        return entryWasRemoved;
    }

    public IEnumerator<TValue> GetEnumerator()
    {
        return _valuesNodes.GetEnumerator();
    }

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public int Count
    {
        get { return _valuesNodes.Count; }
    }

    public TValue this[Tkey key]
    {
        get { return Get(key); }
        set { Set(key, value); }
    }

    public bool Contains(Tkey key)
    {
        return _toProbePropertyNodesByName.ContainsKey(key);
    }

    public TValue Get(Tkey key)
    {
        ref LinkedListNode<TValue> valueByRef = ref CollectionsMarshal.GetValueRefOrNullRef(_toProbePropertyNodesByName, key);
        if (Unsafe.IsNullRef(ref valueByRef))
        {
            throw new KeyNotFoundException($"The given property name '{key}' was not present in the collection.");
        }
        else
        {
            return valueByRef.Value;
        }
    }

    public void Set(Tkey key, TValue value)
    {
        lock (_valuesNodes)
        {
            ref LinkedListNode<TValue> valueByRef = ref CollectionsMarshal.GetValueRefOrAddDefault(_toProbePropertyNodesByName, key, out bool exists);
            if (exists)
            {
                valueByRef.Value = value;
            }
            else
            {
                
                valueByRef = _valuesNodes.AddLast(value);
            }
        }
    }

    public bool TryGet(Tkey key, out TValue value)
    {
        ref LinkedListNode<TValue> valueByRef = ref CollectionsMarshal.GetValueRefOrNullRef(_toProbePropertyNodesByName, key);
        if (Unsafe.IsNullRef(ref valueByRef))
        {
            value = default;
            return false;
        }
        else
        {
            value = valueByRef.Value;
            return true;
        }
    }

    internal string ToDebuggerDisplay()
    {
        return $"Count = {_valuesNodes.Count}";
    }
}

And of course, this can be easily adjusted to implement IReadOnlyCollection<KeyValuePair<TKey,TValue>>

[tjpalmer]

LinkedHashMap in Java needs lots of individually allocated objects and has to jump around for iteration.

[tjpalmer]

From .NET documentation:

Each element of the LinkedList collection is a LinkedListNode.

Also:

public sealed class LinkedListNode

Lots of individually allocated objects.

[claudiudc]

From .NET documentation:

Each element of the LinkedList collection is a LinkedListNode.

Also:

public sealed class LinkedListNode

Lots of individually allocated objects.

As I said, this is just a possible idea, do not take it 1:1, I am aware that a linked node is allocated for every entry.
I do not have enough time to write an impl from scratch but as I mention, similar(it does not have to be base on linked list) can be made and in my view should be made with o(1) remove by key.

[MV10]

Interesting that only 73 issues have been tagged with the wishlist label (and just 36 if you also include api-suggestion). I'd have expected such a small number of features to get a bit more attention.

[ian-g-holm-intel]

I too am in need of this. I need to be able to serialize an OrderedDictionary. Currently we're using the non-generic version and it requires every value object to include the type information. If there was a generic OrderedDictionary<> the type information would only be serialized once with the dictionary object type.

[alexrp]

I am actually genuinely curious what it would take to move this forward. It's entirely unclear to me what the criteria might be, given these observations:

• In the time that this issue has existed, it has accumulated more upvotes than the accepted and implemented priority queue and frozen collections proposals combined.
  • See also [API Proposal]: LinkedDictionary #64829 which is similar, but not quite the same thing.
• The BCL already has a non-generic version and the (rather unfortunate) recommendation you'll often see online is to use a generic wrapper around it and eat the boxing penalty.
• This EF Core pull request is also telling and it's a first-party project.
• The BCL itself could apparently use it.
• This GitHub code search speaks for itself, I think.
• I don't know if the offer still stands, but @TylerBrinkley offered in 2018 to do the implementation work.
• Microsoft.Experimental.Collections (containing Tyler's implementation) has quite a lot of downloads and some notable dependents for an experimental package.
• This isn't even getting into other platforms like SO and Discord where an ordered dictionary is a very common ask.

Evidently there is real-world demand here. It is not a niche ask. It seems like the only real blocker is getting this through API review? Why can that not happen? I would just like to get some insight into the decision-making process here, because all available indicators leave me very confused.

[eiriktsarpalis]

You're right to point out that the primary bottleneck is getting the proposal lined up for API review. This does require some prep-work, including evaluating prototypes and ensuring that the API shape is on par with other designs that have already been shipped. Not all API proposals are created equal from a complexity standpoint however, and championing brand new collection types can be a long-running and expensive process. It's unlikely we could get around to such a proposal unless it registers high in our prioritization.

[alexrp]

Thanks for the reply! I totally understand and agree with most of what you bring up, save for this point:

It's unlikely we could get around to such a proposal unless it registers high in our prioritization.

This is the part I was really getting at. What would make it register high in your prioritization? As I mentioned, it's unclear to me how e.g. frozen collections could have registered higher going by the indicators I posted. (I don't say that to knock them, by the way - I use them myself! - they're just an example to illustrate the point.)

If the answer is "we simply decided we really cared about maximizing read performance for collections in that release cycle" then, hey, fair enough. Like I said, I'm just looking for some insight into the process here. I think a lot of folks have the impression that prioritization of API proposals is to a large extent driven by the volume of demand. If that isn't the case, I think it would be good to just clarify what the different factors are, and maybe their relative importance.

[eiriktsarpalis]

What would make it register high in your prioritization? As I mentioned, it's unclear to me how e.g. frozen collections could have registered higher going by the indicators I posted.

While our planning does take upvotes into consideration, it is not the only driving factor. In the interest of transparency, frozen collections were added because they were a first-party team requirement at the time. There are other factors as well: as you mention an implementation is already available via a NuGet package which plays a role as well. Not everything needs to be part of the BCL, or at least it doesn't urgently need to be part of the BCL.

[eiriktsarpalis]

If the answer is "we simply decided we really cared about maximizing read performance for collections in that release cycle" then, hey, fair enough. I think a lot of folks have the impression that prioritization of API proposals is to a large extent driven by the volume of demand.

It goes without saying that our resources aren't infinite and our backlog is substantial. Oftentimes we might not invest on collections at all in a particular release cycle, simply because the team is pursuing different opportunities.

[alexrp]

To this particular point:

There are other factors as well: as you mention an implementation is already available via a NuGet package which plays a role as well.

This is true of course, but with some caveats: Microsoft.Experimental.Collections is pre-release, so you will get NU5104 if you use package validation. There's also the fact that, with corefxlab archived, the package is deprecated and unmaintained, and even finding the source code requires a fair bit of digging.

To be fair, nothing stops anyone from taking that code and publishing a new package. But I suspect part of the problem here is that, rightly or wrongly, .NET doesn't really have a culture of publishing small utility packages that are narrowly focused on one specific thing, as you'd see in e.g. Node.js and Rust. And on top of that, maintainers of libraries don't seem to like taking dependencies on such small utility packages. So, many who aren't using Microsoft.Experimental.Collections just end up copying an implementation into their project. I think several of the links I provided earlier at least partially substantiate this line of thinking.

[danmoseley]

NET doesn't really have a culture of publishing small utility packages that are narrowly focused on one specific thing, as you'd see in e.g. Node.js and Rust.

I wonder why this is. But that is off topic ..

[stephentoub]

We should just do this. As has been noted, there a plethora of implementations floating around, including very close to home in System.IO.Packaging, EF Core, WCF, MAUI, and WPF, and then also as noted there a multitude of implementations in a myriad of other projects. We can do it once in the core libraries and avoid all that duplication, for something where we already have a non-generic implementation and just need a generic one. We can also start a more minimal surface area and add to it in the future if we're missing anything.

Some notes on the original proposal:

• We should not have an indexer for both int and TKey: that's ambiguous if TKey is an int.
• The KeyCollection should have its Contains be public.
• I don't know why Dictionary's KeyCollection/ValueCollection have public ctors. That should not be necessary there or here.
• There's no need for GetValue or SetValue: that's just the indexer.
• Rather than two overloads of GetAt, I suggest there's just one that returns a KeyValuePair.

I've updated the top proposal and marked it ready for review.

[TylerBrinkley]

When TKey is an int C# will prefer the explicit int overload instead of TKey but I can see how that could cause users problems so if we're not including both indexers that seems okay.

[stephentoub]

When TKey is an int C# will prefer the explicit int overload instead of TKey but I can see how that could cause users problems so if we're not including both indexers that seems okay.

The ambiguity is there are then two overloads with the exact same arguments but that do two completely different things, e.g. this will successfully augment a histogram:

public static void AddToHistogram(OrderedDictionary<string, int> counts, IEnumerable<string> source)
{
    foreach (var item in source) counts[item] = counts.TryGetValue(item, out int count) ? count + 1 : 1;
}

but this, with the exact same method body, will likely either blow up or produce meaningless results:

public static void AddToHistogram(OrderedDictionary<int, int> counts, IEnumerable<int> source)
{
    foreach (var item in source) counts[item] = counts.TryGetValue(item, out int count) ? count + 1 : 1;
}

[TylerBrinkley]

Thanks, yeah I agree it would likely cause issues for some users and using the GetAt and SetAt methods instead is not too burdensome even if it wouldn't be necessary for most collections when TKey is not an int.