Add an `OrderedDictionary.TryAdd` overload that returns the `int`-based index of an entry if the key already exists

[eiriktsarpalis]

Motivation

The CollectionsMarshal.GetValueRefOrAddDefault method for dictionaries provides a powerful mechanism for adding or updating a dictionary entry using only one lookup. The newly added OrderedDictionary<TKey, TValue> collection would similarly benefit from a such an API, however we don't need to make it as unsafe; simply knowing the int-based index of an entry makes it possible to very cheaply look up or update its value using the GetAt and SetAt methods, respectively.

API Proposal

namespace System.Collections.Generic;

public partial class OrderedDictionary<TKey, TValue>
{
    public bool TryAdd(TKey key, TValue value);
+   public bool TryAdd(TKey key, TValue value, out int index);
}

API Usage

See this conversation for a motivating use case.

Before

if (!dict.TryAdd(propertyName, value))
{
    int index = dict.IndexOf(propertyName); // Second lookup operation
    Debug.Assert(index >= 0);
    JsonNode? replacedValue = dict.GetAt(index).Value;
    DetachParent(replacedValue);
    dict.SetAt(index, value);
}

After

if (!dict.TryAdd(propertyName, value, out int index))
{
    JsonNode? replacedValue = dict.GetAt(index).Value;
    DetachParent(replacedValue);
    dict.SetAt(index, value);
}

[dotnet-policy-service[bot]]

Tagging subscribers to this area: @dotnet/area-system-collections See info in area-owners.md if you want to be subscribed.

[aromaa]

I find the parameter name foundIndex a bit convoluted. Does this only cover use cases where a duplicate one was found? What is the value for successful insert? In any case, it would be useful to return the index in both cases and rename it to index.

Technically the just inserted one would always be Count - 1 but this avoid the need to special case and the possibility of oversight.

[eiriktsarpalis]

Good idea, I was originally thinking that it should be returning -1 if returning true but I like your suggestion better.

[terrajobst]

Video

• We should also have an overload for TryGetValue

namespace System.Collections.Generic;

public partial class OrderedDictionary<TKey, TValue>
{
    // Existing
    // public bool TryAdd(TKey key, TValue value);
    // public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value);
    public bool TryAdd(TKey key, TValue value, out int index);
    public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value, out int index);
}

[Ilchert]

Will index be filled if TryGetValue returns false? It would be great if it will return nearest index like BinarySearch.

[aromaa]

It would be great if it will return nearest index like BinarySearch.

The entries of OrderedDictionary are sorted by the insertion order, not by the key. What you are describing is the SortedDictionary,