Ctor of sorted collection classes should support IReadOnlyDictionary or IEnumerable

[craigwardman]

I'd like to suggest changes, in the corefx repo, to add readonly/enumerable dictionary implementations of the ctors - which requires changes to the API of several of the System.Collections.* classes.

Namely:

System.Collections.Generic.SortedDictionary
System.Collections.Generic.SortedList
System.Collections.SortedList

Rationale and Usage

There are existing ctors in the above classes which accept IDictionary<>/IDictionary in order to clone a collection into a new concrete instance of the chosen type. This can be a useful feature, but does not actually require modifying the original collection and therefore could have been based on the IReadOnlyDictionary<>/IEnumerable<> interface.

Currently in order to instantiate one of the above classes from an IReadOnlyDictionary<> would require first to create a new mutable dictionary and then create above class from that instance, or to manually implement a cloning mechanism.

I would posit that in today's code dealing with the immutable interface is more common than the mutable one and therefore changes should be made to accommodate cloning directly from this interface.

Proposed API

public class SortedDictionary<TKey, TValue>
{
+   public SortedDictionary(System.Collections.Generic.IReadOnlyDictionary<TKey, TValue> dictionary) { }
+   public SortedDictionary(System.Collections.Generic.IReadOnlyDictionary<TKey, TValue> dictionary, System.Collections.Generic.IComparer<TKey> comparer) { }
}

// System.Collections.Generic.SortedList
public class SortedList<TKey, TValue>
{
+   public SortedList(System.Collections.Generic.IReadOnlyDictionary<TKey, TValue> dictionary) { }
+   public SortedList(System.Collections.Generic.IReadOnlyDictionary<TKey, TValue> dictionary, System.Collections.Generic.IComparer<TKey> comparer) { }
}

Details

The implementation of the cloning mechanism within both SortedList varieties are written in such a way that it would not be compatible with the IReadOnlyDictionary<> interface and therefore will need to have a new implementation (it uses Keys.CopyTo).

The implementation within SortedDictionary<> actually only relies on the IEnumerable<> interface of the IDictionary<> so it could be boiled down to that common interface/implementation.

For backward compatibility I assume that the original interface will need to be left in place, however there may be room for standardising the cloning process.

Side notes / Questions

• Interestingly the ConcurrentDictionary<> API expects an IEnumerable<KeyValuePair<TKey, TValue>> making it accessible for any type of source collection. However, I guess for compatibility the "old" interface must be maintained so not sure whether adding
  IReadOnlyDictionary<> to fit with the old model is better than switching to the concurrent style of
  using IEnumerable<> (plus it would allow the usage of the Count property for initializing the collection size -could also use IList<>)

• For the non-generic SortedList there is no ideal API for me to suggest, given that there is no non-generic readonly dictionary. Possibly can be achieved using 2x IEnumerable (keys/values), 2x IList (to keep capacity count) or by creating an immutable IReadOnlyDictionary interface/implementation in the non-generic namespace. So I'd like to get some community feedback on this and will update accordingly.

[ericstj]

I bet there are more collections than just this that could benefit from this treatment. Dictionary, ConcurrentDictionary, SortedDictionary.

Might also make sense to consider IReadOnlyList and IReadOnlyCollection as possible constructor parameters where their corresponding R/W interfaces are already accepted.

[safern]

@craigwardman makes sense. Thanks for your proposal. Could you please format the issue description following the API propsal guidelines? here is an example on how it should look (that one is very detailed).

Also, might be worth including other constructors as @ericstj suggested.

[craigwardman]

@craigwardman makes sense. Thanks for your proposal. Could you please format the issue description following the API propsal guidelines? here is an example on how it should look (that one is very detailed).

Also, might be worth including other constructors as @ericstj suggested.

Thanks Safern, I've updated my proposal to include the types I could see that might need updating. I think the non-generic SortedList needs some thinking about though before tabling a proposal so I've left that TBD. Hopefully within this issue some recommendations can be found.

[GrabYourPitchforks]

API review: We can't add the desired ctor because it would conflict with the .ctor(IDictionary<TKey, TValue>, ...) ctor and would be a compile-time breaking change. We might be able to get away with using one of the existing ctors and instead adding a method AddRange(IEnumerable<KeyValuePair<TKey, TValue>>), so the call site would look like:

IReadOnlyDictionary<TKey, TValue> myDict = GetDictionary();
var sortedDictionary = new SortedDictionary<TKey, TValue>(comparer);
sortedDictionary.AddRange(myDict);

Perhaps a ctor that takes a capacity would also benefit here, that way the instance is already sized appropriately for the data that will be added to it.

Would this proposed API be sufficient for your scenarios?

[craigwardman]

API review: We can't add the desired ctor because it would conflict with the .ctor(IDictionary<TKey, TValue>, ...) ctor and would be a compile-time breaking change. We might be able to get away with using one of the existing ctors and instead adding a method AddRange(IEnumerable<KeyValuePair<TKey, TValue>>), so the call site would look like:

IReadOnlyDictionary<TKey, TValue> myDict = GetDictionary();
var sortedDictionary = new SortedDictionary<TKey, TValue>(comparer);
sortedDictionary.AddRange(myDict);

Perhaps a ctor that takes a capacity would also benefit here, that way the instance is already sized appropriately for the data that will be added to it.

Would this proposed API be sufficient for your scenarios?

Hi, I suppose that would be a start - however as noted in the issue, the actual implementation of the current ctor does not rely on such a strong interface:

public SortedDictionary(IDictionary<TKey, TValue> dictionary, IComparer<TKey>? comparer)
        {
            if (dictionary == null)
            {
                throw new ArgumentNullException(nameof(dictionary));
            }

            _set = new TreeSet<KeyValuePair<TKey, TValue>>(new KeyValuePairComparer(comparer));

            foreach (KeyValuePair<TKey, TValue> pair in dictionary)
            {
                _set.Add(pair);
            }
        }

As you can see it's just a foreach loop, so surely IEnumerable<KeyValuePair<TKey, TValue>> would suffice? In which case this signature would fit all purposes without any breaking change? (assuming all implementations of IDictionary<TKey, TValue> already implement IEnumerable<KeyValuePair<TKey, TValue>>

[GrabYourPitchforks]

I had forgotten to include an example earlier of code which breaks:

public static void Main()
{
    Foo(new Dictionary<string, Object>()); // ambiguous call since both interfaces implemented, compiler error
}

public static void Foo(IDictionary<String, object> dict)
{
}

public static void Foo(IReadOnlyDictionary<String, object> dict)
{
}

Adding a constructor which takes IEnumerable<KeyValuePair<TKey, TValue>> would possibly work. The IDictionary<TKey, TValue> ctor would be preferred over the IEnumerable<...> ctor in all cases I can think of, so it wouldn't be a source breaking change.

[ghost]

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of the experimental issue cleanup initiative we are currently trialing in a limited number of areas. Please share any feedback you might have in the linked issue.

[ghost]

This issue will now be closed since it had been marked no recent activity but received no further activity in the past 14 days. It is still possible to reopen or comment on the issue, but please note that the issue will be locked if it remains inactive for another 30 days.