[API Proposal]: SortedSet<T>.GetAlternateLookup()

[terrajobst]

Background and motivation

We added GetAlternateLookup() to many collection types, including Dictionary<TKey, TValue> and HashSet<T>. We should add it to SortedSet<T> as well, for symmetry. In my case, I often use SortedSet<string> over HashSet<T> because I'm persisting data to disk and I'd like to have a stable order to make diffs less jarring.

API Proposal

namespace System.Collections.Generic;

public partial class SortedSet<T>
{
    public readonly struct AlternateLookup<TAlternate>
    {
        public SortedSet<T> Set { get; }
        public bool Add(TAlternate item);
        public bool Contains(TAlternate item);
        public bool Remove(TAlternate item);
        public bool TryGetValue(TAlternate equalValue, [MaybeNullWhen(false)] out T actualValue);
    }

    public AlternateLookup<TAlternate> GetAlternateLookup<TAlternate>();
    public bool TryGetAlternateLookup<TAlternate>(out AlternateLookup<TAlternate> lookup);
}

API Usage

var set = new SortedSet<string>() { "Immo", "Landwerth" };
var lookup = set.GetAlternateLookup<ReadOnlySpan<char>>();

var span = "Immo".AsSpan();
lookup.Contains(span);

Alternative Designs

No response

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.

[huoyaoyuan]

A side question: is there any interface support for the alternate lookups? For example, can I use the Dictionary<TKey, TValue>.AlternateLookup<TAlternateKey> as a IDictionary<TAlternateKey, TValue>? The api surface on alternate lookups doesn't naturally provide Keys in alternate key or kvp support, but they can be easily filled. For ISet<T>, the api surface on alternate lookup is significantly smaller.

[PaulusParssinen]

I attempted API proposal for this at https://github.com/dotnet/runtime/issues/101694 but I folded pretty quick

[eiriktsarpalis]

I will repeat the feedback I put in the original issue. Do allocation-heavy tree-based sets with $\mathcal O(\log n)$ lookup warrant the performance improvement of span-based lookups? If we think that it's necessary, don't we also need an IAlternateComparer<T, TAlternate> complement to IComparer<T> that mirrors the IAlternateEqualityComparer<T, TAlternate> interface? Should we extend this to immutable sorted collections?

[stephentoub]

If we think that it's necessary, don't we also need an IAlternateComparer<T, TAlternate> complement to IComparer that mirrors the IAlternateEqualityComparer<T, TAlternate> interface?

For what purpose?

[eiriktsarpalis]

Don't we need a mechanism that determines whether the proposed GetAlternateLookup<TAlternate>(); call succeeds for a particular set?

[stephentoub]

Don't we need a mechanism that determines whether the proposed GetAlternateLookup<TAlternate>(); call succeeds for a particular set?

If we add the Get, we should add the TryGet, too.

[eiriktsarpalis]

I suspect this would be difficult to sign off on without a PoC created ahead of time. @terrajobst should we mark it needs-work or do we want to review the proposal in principle first?

[terrajobst]

If we do the work, we probably want to all comparison-based data structures, such as:

• SortedSet<T>
• OrderedDictionary<TKey, TValue>
• SortedDictionary<TKey, TValue>
• SortedList<TKey, TValue>
• Immutable?

[eiriktsarpalis]

As well as all binary search methods that accept IComparer<T>.

[bartonjs]

Video

• SortedSet is based on a tree implementation using Compare, not Equals, so the existing IAlternateEqualityComparer is not sufficient.
  • This can realistically only go forward with an IAlternateComparer.
  • It's probably on the order of the same amount of work as when we introduced IAlternateEqualityComparer.
  • And should probably look for other places we could use that.

namespace System.Collections.Generic;

public partial class SortedSet<T>
{
    public readonly struct AlternateLookup<TAlternate>
    {
        public SortedSet<T> Set { get; }
        public bool Add(TAlternate item);
        public bool Contains(TAlternate item);
        public bool Remove(TAlternate item);
        public bool TryGetValue(TAlternate equalValue, [MaybeNullWhen(false)] out T actualValue);
    }

    public AlternateLookup<TAlternate> GetAlternateLookup<TAlternate>();
    public bool TryGetAlternateLookup<TAlternate>(out AlternateLookup<TAlternate> lookup);
}