Add string keyed dictionary ReadOnlySpan<char> lookup support

[TylerBrinkley]

UPDATED 1/22/2024 by @stephentoub

Option 1 (recommended)

namespace System.Collections.Generic
{
    public static class CollectionExtensions
    {
+       public static Dictionary<TKey, TValue>.MappedLookup<TMappedKey> GetMappedLookup<TKey, TValue, TMappedKey>(
+           this Dictionary<TKey, TValue> dictionary)
+           where TKey : notnull where TMappedKey : allow ref struct;
+       public static bool TryGetMappedLookup<TKey, TValue, TMappedKey>(
+           this Dictionary<TKey, TValue> dictionary,
+           out Dictionary<TKey, TValue>.MappedLookup<TMappedKey> lookup)
+           where TKey : notnull where TMappedKey : allow ref struct;

+       public static HashSet<T>.MappedLookup<TMapped> GetMappedLookup<TMapped>(
+           this HashSet<T> set)
+           where TMapped : allow ref struct;
+       public static bool TryGetMappedLookup(
+           this HashSet<T> set, out HashSet<T>.MappedLookup<TMapped> lookup)
+           where TMapped : allow ref struct;
    }

    public class Dictionary<TKey, TValue>
    {
+       public readonly struct MappedLookup<TMappedKey> where TMappedKey : allow ref struct
+       {
+           public bool ContainsKey(TMappedKey key);
+           public bool TryAdd(TMappedKey  key, TValue value);
+           public bool TryGetValue(TMappedKey key, [MaybeNullWhen(false)] out TValue value);
+           public bool TryGetValue<TKey, TValue, TMappedKey>(TMappedKey  key, [NotNullWhen(true)] out TKey? actualKey, [MaybeNullWhen(false)] out TValue value);
+           public bool Remove(TMappedKey key);
+           public bool Remove(TMappedKey  key, [MaybeNullWhen(false)] out TValue value));
+       }
    }

    public class HashSet<T>
    {
+       public readonly struct MappedLookup<TMapped>
+       {
+           public bool Add(TMapped item);
+           public bool Contains(TMapped item);
+           public bool Remove(TMapped item);
+           public bool TryGetValue(TMapped equalValue, [MaybeNullWhen(false)] out T actualValue);
+       }
    }
}

namespace System.Runtime.InteropServices
{
    public static class CollectionsMarshal
    {
+       public static ref TValue? GetValueRefOrAddDefault<TKey, TValue, TMappedKey>(
+           Dictionary<TKey, TValue>.MappedLookup<TMappedKey> dictionary,
+           TMappedKey key, out bool exists)
+           where TKey : notnull where TMappedKey : allow ref struct;
+       public static ref TValue GetValueRefOrNullRef<TKey, TValue, TMappedKey>(
+           Dictionary<TKey, TValue>.MappedLookup<TMappedKey> dictionary,
+           TMappedKey key)
+           where TKey : notnull where TMappedKey : allow ref struct;
    }
}

namespace System.Collections.Concurrent
{
    public class ConcurrentDictionary<TKey, TValue>
+   {
+       public ConcurrentDictionary<TKey, TValue>.MappedLookup<TMappedKey> GetMappedLookup<TMappedKey>() 
+           where TMappedKey : allow ref struct;
+       public bool TryGetMappedLookup<TMappedKey>(
+           out ConcurrentDictionary<TKey, TValue>.MappedLookup<TMappedKey> lookup)
+           where TMappedKey : allow ref struct;

+       public readonly struct MappedLookup<TMappedKey>
+       {
+           public bool ContainsKey<TKey, TValue, TMappedKey>(TMappedKey key);
+           public bool TryAdd<TKey, TValue, TMappedKey>(TMappedKey key, TValue value);
+           public bool TryGetValue<TKey, TValue, TMappedKey>(TMappedKey key, [MaybeNullWhen(false)] out TValue value);
+           public bool TryGetValue<TKey, TValue, TMappedKey>(TMappedKey key, [NotNullWhen(true)] out TKey? actualKey, [MaybeNullWhen(false)] out TValue value);
+           public bool TryRemove<TKey, TValue, TMappedKey>(TMappedKey key, [MaybeNullWhen(false)] out TValue value);
+           public bool TryRemove<TKey, TValue, TMappedKey>(TMappedKey key, [NotNullWhen(true) out TKey? actualKey, [MaybeNullWhen(false)] out TValue value);
+       }
+   }
}

namespace System.Collections.Immutable
{
    public class FrozenDictionary<TKey, TValue>
    {
+       public FrozenDictionary<TKey, TValue>.MappedLookup<TMappedKey> GetMappedLookup<TMappedKey>()
+           where TMappedKey : allow ref struct;
+       public bool TryGetMappedLookup<TMappedKey>(
+           out FrozenDictionary<TKey, TValue>.MappedLookup<TMappedKey> lookup)
+           where TMappedKey : allow ref struct;

+       public readonly struct MappedLookup<TMappedKey>
+       {
+           public bool ContainsKey<TKey, TValue, TMappedKey>(TMappedKey key);
+           public bool TryGetValue<TKey, TValue, TMappedKey>(TMappedKey key, [MaybeNullWhen(false)] out TValue value);
+           public bool TryGetValue<TKey, TValue, TMappedKey>(TMappedKey key, [NotNullWhen(true)] out TKey? actualKey, [MaybeNullWhen(false)] out TValue value);
+       }
    }

    public class FrozenSet<T>
    {
+       public FrozenSet<T>.MappedLookup<TMapped> GetMappedLookup<TMapped>()
+           where TMappedKey : allow ref struct;
+       public bool TryGetMappedLookup<TMappedKey>(
+           out FrozenSet<T>.MappedLookup<TMapped> lookup)
+           where TMappedKey : allow ref struct;

+       public readonly struct MappedLookup<TMapped>
+       {
+           public bool Contains(TMapped item);
+           public bool TryGetValue(TMapped equalValue, [MaybeNullWhen(false)] out T actualValue);
+       }
    }
}

Pros of Option 1:

• Keeps refstruct-based APIs separated out
• Enables caching any lookup costs
• Makes a "Try" method more tolerable, which is important in cases where you're handed a dictionary, have a span you want to use for lookup, and want to use the span if possible or else ToString or equivalent and use that

Cons of Option 1:

• Poor type inference on With
• Because of the above, makes working with anonymous TValues complicated

Option 2

namespace System.Collections.Generic
{
    public static class CollectionExtensions
    {
+       public static bool ContainsKey<TKey, TValue, TMappedKey>(
+           this Dictionary<TKey, TValue> dictionary, TMappedKey key)
+           where TKey : notnull where TMappedKey : allow ref struct
+       public static bool Remove<TKey, TValue, TMappedKey>(
+           this Dictionary<TKey, TValue> dictionary, TMappedKey key)
+           where TKey : notnull where TMappedKey : allow ref struct
+       public static bool Remove<TKey, TValue, TMappedKey>(
+           this Dictionary<TKey, TValue> dictionary, TMappedKey  key, [MaybeNullWhen(false)] out TValue value))
+           where TKey : notnull where TMappedKey : allow ref struct
+       public static bool TryAdd<TKey, TValue, TMappedKey>(
+           this Dictionary<TKey, TValue> dictionary, TMappedKey  key, TValue value)
+           where TKey : notnull where TMappedKey : allow ref struct
+       public static bool TryGetValue<TKey, TValue, TMappedKey>(
+           this Dictionary<TKey, TValue> dictionary, TMappedKey key, [MaybeNullWhen(false)] out TValue value)
+           where TKey : notnull where TMappedKey : allow ref struct
+       public static bool TryGetValue<TKey, TValue, TMappedKey>(
+           this Dictionary<TKey, TValue> dictionary, TMappedKey  key, [NotNullWhen(true)] out TKey? actualKey, [MaybeNullWhen(false)] out TValue value)
+           where TKey : notnull where TMappedKey : allow ref struct

+       public static bool Add<T, TMapped>(this HashSet<T> set, TMapped item) where TMapped : allow ref struct;
+       public static bool Contains<T, TMapped>(this HashSet<T> set, TMapped item) where TMapped : allow ref struct;
+       public static bool Remove<T, TMapped>(this HashSet<T> set, TMapped item) where TMapped : allow ref struct;
+       public static bool TryGetValue<T, TMapped>(this HashSet<T> set, TMapped equalValue, [MaybeNullWhen(false)] out T actualValue) where TMapped : allow ref struct;
    }
}

namespace System.Runtime.InteropServices
{
    public static class CollectionsMarshal
    {
+       public static ref TValue? GetValueRefOrAddDefault<TKey, TValue, TMappedKey>(Dictionary<TKey, TValue> dictionary, TMappedKey key, out bool exists) where TKey : notnull where TMappedKey : allow ref struct;
+       public static ref TValue GetValueRefOrNullRef<TKey, TValue, TMappedKey>(Dictionary<TKey, TValue> dictionary, TMappedKey key) where TKey : notnull where TMappedKey : allow ref struct;
    }
}

namespace System.Collections.Concurrent
{
+   public static class ConcurrentCollectionExtensions
+   {
+       public static bool ContainsKey<TKey, TValue, TMappedKey>(
+           this ConcurrentDictionary<TKey, TValue> dictionary, TMappedKey key)
+           where TKey : notnull;
+       public static bool TryAdd<TKey, TValue, TMappedKey>(
+           this ConcurrentDictionary<TKey, TValue> dictionary, TMappedKey key, TValue value)
+           where TKey : not null;
+       public static bool TryGetValue<TKey, TValue, TMappedKey>(
+           this ConcurrentDictionary<TKey, TValue> dictionary, TMappedKey key, [MaybeNullWhen(false)] out TValue value) 
+           where TKey : not null;
+       public static bool TryGetValue<TKey, TValue, TMappedKey>(
+           this ConcurrentDictionary<TKey, TValue> dictionary, TMappedKey key, [NotNullWhen(true)] out TKey? actualKey, [MaybeNullWhen(false)] out TValue value)
+           where TKey : not null where TMappedKey : allow ref struct;
+       public static bool TryRemove<TKey, TValue, TMappedKey>(
+           this ConcurrentDictionary<TKey, TValue> dictionary, TMappedKey key, [MaybeNullWhen(false)] out TValue value) 
+           where TKey : notnull;
+   }
}

namespace System.Collections.Immutable
{
    public class FrozenDictionary<TKey, TValue>
    {
+       public bool ContainsKey<TMappedKey>(TMappedKey key) where TKey : notnull where TMappedKey : allow ref struct;
+       public bool TryGetValue<TMappedKey>(TMappedKey key, [NotNullWhen(true)] out TKey? actualKey, [MaybeNullWhen(false)] out TValue value) where TKey : not null where TMappedKey : allow ref struct;
+       public bool TryGetValue<TMappedKey>(TMappedKey key, [MaybeNullWhen(false)] out TValue value) where TKey : not null where TMappedKey : allow ref struct;
    }

    public class FrozenSet<T>
    {
+       public bool Contains<TMapped>(TMapped item);
+       public bool TryGetValue<TMapped>(TMapped equalValue, [MaybeNullWhen(false)] out T actualValue);
    }
}

Pros of Option 2:

• Fewer types
• Can index directly into the collection with the key without needing the separate lookup
• Inference "just works"

Cons of Option 2:

• More expensive at runtime; every call does a type check
• Worse usability when you have something that casts to ReadOnlySpan<T>, e.g. a Span<T>; calls bind to the instance members if not exact match to the extensions
• Would be a lot more surface area (and confusing in some cases) to add Try variants where false means the dictionary doesn't support the mapped lookup type

Regardless of approach:

namespace System.Collections.Generic
{
    // implemented by all string-related comparers, e.g. the comparer instances returned from StringComparer.Ordinal, EqualityComparer<string>.Default, etc.
+   public interface IMappedEqualityComparer<TMapped, T> where TMapped : allow ref struct
+   {
+       bool Equals(TMapped mapped, T other);
+       int GetHashCode(TMapped span);
+       TKey Map(TMapped mapped);
+   }
}

The above is based on the assumption that we will be getting a ref struct anti-constraint in for .NET 9 / C# 13. If that ends up not happening, this will be revamped to look almost the same, except using ReadOnlySpan<TKeyElement> instead of TMappedKey.

---

UPDATED 1/3/2024 by @stephentoub.

namespace System.Collections.Generic
{
    // implemented by all string-related comparers, e.g. the comparer instances
    // returned from StringComparer.Ordinal, EqualityComparer<string>.Default, etc.
+   public interface IMappedSpanEqualityComparer<TSpanElement, T>
+   {
+       bool Equals(ReadOnlySpan<TSpanElement> span, T other);
+       int GetHashCode(ReadOnlySpan<TSpanElement> span);
+       T Map(ReadOnlySpan<TSpanElement> span);
+   }

    public static class CollectionExtensions
    {
+       public static bool ContainsKey<TKey, TValue, TSpanElement>(this Dictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key) where TKey : notnull;
+       public static bool Remove<TKey, TValue, TSpanElement>(this Dictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key) where TKey : notnull;
+       public static bool Remove<TKey, TValue, TSpanElement>(this Dictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key, [MaybeNullWhen(false)] out TValue value) where TKey : notnull;
+       public static bool TryAdd<TKey, TValue, TSpanElement>(this Dictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key, TValue value) where TKey : not null;
+       public static bool TryGetValue<TKey, TValue, TSpanElement>(this Dictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key, [MaybeNullWhen(false)] out TValue value) where TKey : notnull;
+       public static bool TryGetValue<TKey, TValue, TSpanElement>(this Dictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key, [NotNullWhen(true)] out TKey? actualKey, [MaybeNullWhen(false)] out TValue value) where TKey : notnull;

+       public static bool Add<T, TSpanElement>(this HashSet<T> set, ReadOnlySpan<TSpanElement> item);
+       public static bool Contains<T, TSpanElement>(this HashSet<T> set, ReadOnlySpan<TSpanElement> item);
+       public static bool Remove<T, TSpanElement>(this HashSet<T> set, ReadOnlySpan<TSpanElement> item);
+       public static bool TryGetValue<T, TSpanElement>(this HashSet<T> set, ReadOnlySpan<TSpanElement> equalValue, [MaybeNullWhen(false)] out T actualValue);
    }
}

namespace System.Runtime.InteropServices
{
    public static class CollectionsMarshal
    {
+       public static ref TValue? GetValueRefOrAddDefault<TKey, TValue, TSpanElement>(Dictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key, out bool exists) where TKey : notnull;
+       public static ref TValue GetValueRefOrNullRef<TKey, TValue, TSpanElement>(Dictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key) where TKey : notnull;
    }
}

namespace System.Collections.Concurrent
{
+   public static class ConcurrentCollectionExtensions
+   {
+       public static bool ContainsKey<TKey, TValue, TSpanElement>(this ConcurrentDictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key) where TKey : notnull;
+       public static bool TryAdd<TKey, TValue, TSpanElement>(this ConcurrentDictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key, TValue value) where TKey : not null;
+       public static bool TryGetValue<TKey, TValue, TSpanElement>(this ConcurrentDictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key, [MaybeNullWhen(false)] out TValue value) where TKey : not null;
+       public static bool TryRemove<TKey, TValue, TSpanElement>(this ConcurrentDictionary<TKey, TValue> dictionary, ReadOnlySpan<TSpanElement> key, [MaybeNullWhen(false)] out TValue value) where TKey : notnull;
+   }
}

If .NET 9 and C# 13 and up supporting ref struct constraints, we would tweak these APIs to instead take a TMappingKey : ref struct rather than a ReadOnlySpan<TElement>. See #27229 (comment) for more details.

Open issues:

• Name of the interface.
• Name of the element generic method parameter.
• Extension methods vs instance methods. We could make these methods generic methods on the target type instead. Should we? Are we still concerned about lots of new methods on a type like Dictionary (e.g. asm code bloat)? Any concerns about (non-virtual) generic methods on a generic type?
• Do we want Span overloads in addition to ReadOnlySpan overloads? If we keep these as extension methods, you have to explicitly cast to ReadOnlySpan if you have a span, or else the compiler will try and fail to use the instance methods.
• Any other collection types really important to support initially?

---

Moved from corefxlab#2438 as the proposed changes could not be implemented in a separate library.

Motivation

I would like to perform dictionary lookups using a ReadOnlySpan<char> value on a string keyed dictionary without having to allocate a string.

There are two different design approaches proposed, add extension methods to Dictionary<string, TValue> or add a new Type .

Extension Method Proposed API

 namespace System.Collections.Generic {
+    public static class DictionaryExtensions {
+        public static bool ContainsKey<TValue>(this Dictionary<string, TValue> dictionary, ReadOnlySpan<char> key);
+        public static bool Remove<TValue>(this Dictionary<string, TValue> dictionary, ReadOnlySpan<char> key);
+        public static bool TryGetValue<TValue>(this Dictionary<string, TValue> dictionary, ReadOnlySpan<char> key, out TValue value);
+        public static T GetValue<TValue>(this Dictionary<string, TValue> dictionary, ReadOnlySpan<char> key);
+    }
 }
 namespace System {
      public abstract class StringComparer : IComparer<string>, IEqualityComparer<string>, IComparer, IEqualityComparer {
+        public virtual bool Equals(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
+        public virtual int GetHashCode(ReadOnlySpan<char> obj);
      }
     public sealed class CultureAwareComparer : StringComparer {
+        public override bool Equals(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
+        public override int GetHashCode(ReadOnlySpan<char> obj);
     }
     public class OrdinalComparer : StringComparer {
+        public override bool Equals(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
+        public override int GetHashCode(ReadOnlySpan<char> obj);
     }
 }

Implementation Details

• Internal details of Dictionary<TKey, TValue> would need to be exposed with the internal modifier to implement the ReadOnlySpan<char> overloads.
• Only StringComparers that are passed into the constructor would be able to be optimized to not allocate a string.
• The default implementation of the new virtual methods on StringComparer would convert the ReadOnlySpan<char> to a string and use the string methods instead.

New Type Proposed API

 namespace System.Collections.Specialized {
+    public class StringKeyedDictionary<TValue> : Dictionary<string, TValue> {
+        public StringKeyedDictionary();
+        public StringKeyedDictionary(StringComparer comparer);
+        public StringKeyedDictionary(int capacity);
+        public StringKeyedDictionary(int capacity, StringComparer comparer);
+        public StringKeyedDictionary(IDictionary<string, TValue> dictionary);
+        public StringKeyedDictionary(IDictionary<string, TValue> dictionary, StringComparer comparer);
+        public StringKeyedDictionary(IEnumerable<KeyValuePair<string, TValue>> collection);
+        public StringKeyedDictionary(IEnumerable<KeyValuePair<string, TValue>> collection, StringComparer comparer);
+        public new StringComparer Comparer { get; }
+        public T this[ReadOnlySpan<char> key] { get; }
+        public bool ContainsKey(ReadOnlySpan<char> key);
+        public bool Remove(ReadOnlySpan<char> key);
+        public bool TryGetValue(ReadOnlySpan<char> key, out TValue value);
+    }
 }
 namespace System {
      public abstract class StringComparer : IComparer<string>, IEqualityComparer<string>, IComparer, IEqualityComparer {
+        public virtual bool Equals(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
+        public virtual int GetHashCode(ReadOnlySpan<char> obj);
      }
     public sealed class CultureAwareComparer : StringComparer {
+        public override bool Equals(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
+        public override int GetHashCode(ReadOnlySpan<char> obj);
     }
     public class OrdinalComparer : StringComparer {
+        public override bool Equals(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
+        public override int GetHashCode(ReadOnlySpan<char> obj);
     }
 }

Implementation Details

• Internal details of Dictionary<TKey, TValue> would need to be exposed with the private protected modifier to implement the ReadOnlySpan<char> overloads.
• The default implementation of the new virtual methods on StringComparer would convert the span to a string and use the string methods instead.
• A null comparer passed to the constructor would default to StringComparer.Ordinal.

Possible Addition

While not specifically needed for this request a ReadOnlySpan<char> Compare overload should probably be added as well while we're updating StringComparer.

 namespace System {
     public abstract class StringComparer : IComparer, IEqualityComparer, IComparer<string>, IEqualityComparer<string> {
+        public virtual int Compare(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
     }
     public sealed class CultureAwareComparer : StringComparer {
+        public override int Compare(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
     }
     public class OrdinalComparer : StringComparer {
+        public override int Compare(ReadOnlySpan<char> x, ReadOnlySpan<char> y);
     }
 }

Open Questions

• Should the additional ReadOnlySpan<char> Compare overload be included?
• Should NonRandomizedStringEqualityComparer now derive from StringComparer in order to be supported?
• Should a TryAdd overload be added as it has the possibility of not requiring to be converted to a string if an equal key is found?

Discussion Summary.

We have two different design approaches, add a new Type or add extension methods to Dictionary<string, TValue>.

Here's a comparison of the pro's and con's of the different design approaches.

	Extension Methods	StringKeyedDictionary
Pros	No new type introduced.	No performance penalty due to casting the comparer.
	Existing code exposing a string keyed Dictionary needs no changes to use which is helpful when they can't easily be changed.	Indexer support.
	More scalable
Cons	Performance penalty of casting the comparer.	New type introduced meaning an additional staple of the .NET ecosystem to know.
	No indexer support, must use a GetValue method instead.	Existing code that exposes a string keyed Dictionary may not easily be changed to using the new type.
	Dictionary internals exposed with the internal modifier.	Dictionary internals exposed with the private protected modifier.
	Somewhat opaque to user as to knowing the comparer must derive from StringComparer.

Updates

• Updated namespaces back to System.Collections.Specialized.
• Changed extension class name to DictionaryExtensions from StringKeyedDictionaryExtensions.
• Removed proposed IStringEqualityComparer interface and instead relies on comparer deriving from StringComparer.
• Reordered design approaches to better promote my preference. 😄

[svick]

Would it be better to instead have a set of extension methods on Dictionary<string, T>? That way, the new methods could be used on any string-keyed Dictionary, not just on some special type.

[Wraith2]

Dictionary<TKey,TValue> is implemented in Coreclr and the is a high bar for new types because of library size issues. Do you intend or this implementation not to be collision resistant or do you have a method to store the key without the span somehow? convert it into a ReadOnlyMemory?

[benaadams]

Would it be better to instead have a set of extension methods on Dictionary<string, T>?

How would it perform the search (using hashcode + equals) against the current Dictionary api surface?

do you have a method to store the key without the span somehow? convert it into a ReadOnlyMemory?

ROS<char>.ToString()

[svick]

@benaadams

Would it be better to instead have a set of extension methods on Dictionary<string, T>?

How would it perform the search (using hashcode + equals) against the current Dictionary api surface?

It wouldn't use the public API surface, it would use some new internal members on Dictionary. That's worse than StringKeyedDictionary, which would probably use new private protected members, but I think not by much.

[benaadams]

Ah.. so something like?

static class StringKeyedDictionaryExtensions 
{
    static bool ContainsKey<TValue>(this Dictionary<string, TValue> dictionary, ReadOnlySpan<char> key);
    static bool Remove<TValue>(this Dictionary<string, TValue> dictionary, ReadOnlySpan<char> key);
    static bool TryGetValue<TValue>(this Dictionary<string, TValue> dictionary, ReadOnlySpan<char> key, out TValue value);
}

[Wraith2]

Right, I think I missed the point then. The idea is to have the standard dictionary at the back end but methods which allow you to use ROS as the key to search for avoiding the allocation to check if something exists. So it needs access to the internals because the comparer needs to understand that it can do ROS-string comparisons which aren't currently possible.

[svick]

@benaadams Yup. Plus probably an extension method version of the indexer:

public static T GetValue<TValue>(this Dictionary<string, TValue> dictionary, ReadOnlySpan<char> key);

Though that's an advantage of the StringKeyedDictionary design: it can have a real indexer.

[safern]

Also if they're extension methods we would need to provide overrides to specify a custom Comparer that can compare ROS right? Or that would be achieved by adding the StringEqualityComparer type and interface and in the extension methods check if Comparer is IStringEqualityComparer then use the ROS overrides if not the string ones?

Also with override methods Adding values through the indexer or TryAdd/Add apis, we wouldn't be able to take advantage of the ROS comparisons right?

[benaadams]

Also if they're extension methods we would need to provide overrides to specify a custom Comparer that can compare ROS right?

Dictionary is based on IEqualityComparer<T> so not sure if it could work... (even if default interfaces implementations pulling up the slack, not sure how it could work for other types as a ROS comparison would be exposed on the interface, which probably wouldn't make sense?)

Also with override methods Adding values through the indexer or TryAdd/Add apis, we wouldn't be able to take advantage of the ROS comparisons right?

Can covert the string to a ROS at nominal cost for the comparison; if it didn't exist the ROS<char> could be turned into a string for persistent key use; so that wouldn't necessarily be a problem.

[safern]

Dictionary is based on IEqualityComparer so not sure if it could work... (even if default interfaces implementations pulling up the slack, not sure how it could work for other types as a ROS comparison would be exposed on the interface, which probably wouldn't make sense?)

Yes, but people could just use StringEqualityComparer and since it would implement IEqualityComparer it can be passed through the constructor. However in order to use the ROS overloads if we go through the Extension methods route we would need to cast the Comparer to IStringEqualityComparer

I think if we want to use the ROS comparison features and other of its features through a custom Comparer we should not use Extension methods, unless I’m missing something we could do in a different way without overriding implementation.

[TylerBrinkley]

Here's a comparison of the pro's and con's of the different design approaches.

	Extension Methods	StringKeyedDictionary
Pros	No new type introduced.	No performance penalty due to casting the comparer.
	Existing code exposing a string keyed Dictionary needs no changes to use which is helpful when they can't easily be changed.	Indexer support.
Cons	Performance penalty of casting the comparer.	New type introduced meaning an additional staple of the .NET ecosystem to know.
	No indexer support, must use a GetValue method instead.	Existing code that exposes a string keyed Dictionary may not easily be changed to using the new type.
	Dictionary internals exposed with the internal modifier.	Dictionary internals exposed with the private protected modifier.
	Somewhat opaque to user as to knowing it uses IStringEqualityComparer.

Honestly, I'm kind of torn on this. Adding a new foundational Type to the ecosystem is costly in terms of what developers need to know. I'm feeling this even more now with the addition of all the types introduced with Spans and Pipelines. Additionally, I could easily see this expanding to others such as HashSet, SortedDictionary, SortedSet, OrderedDictionary & OrderedSet if they ever get implemented, and ConcurrentDictionary.

If the performance isn't an issue I now think I'd prefer the extension method route.

[safern]

@TylerBrinkley thanks for the great summary, I just updated the issue description and included this comparison in there. Will mark as ready for review now.

[TylerBrinkley]

I've updated the first post to correct formatting and make it a little easier to understand.

[cdmihai]

Overloads for ConcurrentDictionary would also be nice :)

[terrajobst]

Video

On the surface, the extension approach looks more appealing because it would allow the lookups to work against any instance of a dictionary (at least in principle, the current design only works if the dictionary was instantiated with a comparer that implements IStringEqualityComparer).

However, this also complicates the implementation and might have performance implications if we have to expose more methods that only make sense when TKey happens to be string. Also, one could argue that in the hot paths where people would be inclined to lookup with spans that they do in fact control their dictionary and whether they need to pass in the correct comparer or use a derived type of Dictionary<,> doesn't matter.

I totally buy the scenario, but adding a new collection type (even if derived from Dictionary<,>) feels heavy handed, but maybe I'm overthinking this. Maybe just putting it in S.C.Specialized is good enough.

What do others think?