[API Proposal]: Add an SortedList.TryAdd and TryGetValue overload that returns the int-based index of an entry

[Ilchert]

Background and motivation

This proposal is similar to OrderedDictionary.TryAdd https://github.com/dotnet/runtime/issues/107947

The CollectionsMarshal.GetValueRefOrAddDefault method for dictionaries provides a powerful mechanism for adding or updating a dictionary entry using only one lookup. The SortedList<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, look up nearest value and update its value using the GetKeyAtIndex/GetValueAtIndex and SetValueAtIndex methods, respectively.

API Proposal

namespace System.Collections.Generic;

public partial class SortedList<TKey, TValue>
{
    public void Add(TKey key, TValue value);
+   public bool TryAdd(TKey key, TValue value, out int index);
    public bool TryGetValue (TKey key, [MaybeNullWhen(false)] out TValue value);
+   public bool TryGetValue (TKey key, [MaybeNullWhen(false)] out TValue value, out int index);
}

API Usage

var list = new SortedList<int, string>()
{{ 1994, "Forrest Gump"},  {2000,"Gladiator" }, { 2003, "The Lord of the Rings: The Return of the King" } };

var from = 1990;
var to = 2000;

list.TryGetValue(from, out _, out var startIndex);
if (startIndex < 0)
    startIndex = ~startIndex;
list.TryGetValue(to, out _, out var endIndex);
if (endIndex < 0)
    endIndex = ~endIndex;

endIndex = Math.Min(endIndex, list.Count - 1);

for (int i = startIndex; i <= endIndex; i++)
    Console.WriteLine(list.GetValueAtIndex(i));

Alternative Designs

Alternate solution is exposing keys array from SortedList and use binary search directly.

public static class CollectionsMarshal
{
    public static Span<T> AsSpan<T>(List<T>? list)
+   public static Span<TKey> KeysAsSpan<TKey,TValue>(SortedList<TKey,TValue>? list)
+   public static Span<TValue> ValuesAsSpan<TKey,TValue>(SortedList<TKey,TValue>? list)
}

Usage

var list = new SortedList<int, string>()
{{ 1994, "Forrest Gump"},  {2000,"Gladiator" }, { 2003, "The Lord of the Rings: The Return of the King" } };

var from = 1990;
var to = 2000;
var keys = CollectionsMarshal.KeysAsSpan(list);
var startIndex = keys.BinarySearch(from);
if (startIndex < 0)
    startIndex = ~startIndex;
var endIndex = keys.BinarySearch(to);
if (endIndex < 0)
    endIndex = ~endIndex;

endIndex = Math.Min(endIndex, list.Count - 1);

for (int i = startIndex; i <= endIndex; i++)
    Console.WriteLine(list.GetValueAtIndex(i));

Risks

No response

[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.

[julealgon]

I'm super confused about the "Try" in the TryAdd method. Does this have a "failure state" that the "Try" is avoiding? When would adding an element fail? A void TryX method that doesn't also avoid some sort of exception makes zero sense to me.

Maybe I completely misunderstood the intended semantics. Apologies if so.

[Ilchert]

Hello @julealgon , thanks for noticing. It was a missprint, it should return bool like original one.

Addings fails with duplicates https://github.com/dotnet/runtime/blob/5535e31a712343a63f5d7d796cd874e563e5ac14/src/libraries/System.Collections/src/System/Collections/Generic/SortedList.cs#L184-L185

[julealgon]

it should return bool like original one.

Addings fails with duplicates

Ahh that makes a lot more sense! Thanks for clarifying @Ilchert .