Runtime: Adding EnsureCapacity and TrimExcess APIs to SortedSet

[maryamariyan]

We want to add the EnsureCapacity and TrimExcess APIs to SortedSet.

The following APIs were approved earlier by @terrajobst at https://github.com/dotnet/corefx/issues/24445#issuecomment-352869027

public int EnsureCapacity(int capacity);
public void TrimExcess(); // Calls the other passing Count
public void TrimExcess(int capacity);

cc: @terrajobst @danmosemsft

[maryamariyan]

We've added EnsureCapacity and TrimExcess APIs to Dictionary and HashSet as of corefx issue https://github.com/dotnet/corefx/issues/24445.

@terrajobst for HashSet and Dictionary we could already set capacity from their constructors:

public HashSet(int capacity);
public HashSet(int capacity, IEqualityComparer<T> comparer);

public Dictionary(int capacity);
public Dictionary(int capacity, IEqualityComparer<TKey> comparer);

But this is a bit different for SortedSet. SortedSet has no constructor taking capacity as input. Given this knowledge, are these two APIs still needed for SortedSet?

[svick]

SortedSet<T> is implemented as a tree:

https://github.com/dotnet/corefx/blob/92c204f51d208ae9dc854a59fcc01afa90264205/src/System.Collections/src/System/Collections/Generic/SortedSet.cs#L48-L52

https://github.com/dotnet/corefx/blob/92c204f51d208ae9dc854a59fcc01afa90264205/src/System.Collections/src/System/Collections/Generic/SortedSet.cs#L1676

https://github.com/dotnet/corefx/blob/92c204f51d208ae9dc854a59fcc01afa90264205/src/System.Collections/src/System/Collections/Generic/SortedSet.cs#L1690-L1694

Since there is no backing array that you could resize, I don't think it makes sense to set the capacity of SortedSet<T>. I think that's why SortedSet<T> doesn't currently have a capacity constructor and it's also why the proposed methods shouldn't be added.

[terrajobst]

@maryamariyan

But this is a bit different for SortedSet. SortedSet has no constructor taking capacity as input. Given this knowledge, are these two APIs still needed for SortedSet<T>?

Our primary goal with the comment was to ensure we’re applying the concept consistently across our core types. If the concept doesn’t make sense for a specific type I see no problem with dropping it. However, if they just happen to not be applicable due to the current implementation but they make sense, we should consider tweaking the implementation to enable the scenario too. But if it’s not a tweak but would require re-architecting the implementation, I would just punt the APIs. The reason being that it’s a lot of work and high risk with marginal gains.

Based on @svick’s comment it seems we cannot support these APIs without performing a massive architectural change (i.e. changing the tree-based store to an array-based store). I suggest we just punt the APIs for SortedSet<T> and revisit this if there is a strong need for them.