[API Proposal]: System.Collections.Generic.SortedList<TKey, TValue> should have SetByIndex(Int32,TValue)

[rhaokiel]

Background and motivation

There is no way to set the value of an entry by index in the generic SortedList<TKey, TValue> like there is in the non-generic version. This causes code to incur a BinarySearch cost (log n) to set the value when the index is already known.

I'm rather surprised nobody has mentioned this here even though there is interest over on StackOverflow (4 years old).

API Proposal

(Updated to reflect API Review's conclusions)

namespace System.Collections.Generic
{
    public class SortedList<TKey, TValue>
    {
+       public TKey GetKeyAtIndex(int index)
-       private TKey GetKey(int index)
        { ... }

+       public TValue GetValueAtIndex(int index)
-       private TValue GetByIndex(int index)
        { ... }

+       public void SetValueAtIndex(int index, TValue value)
+       {
+           if (index < 0 || index >= _size)
+               throw new ArgumentOutOfRangeException(nameof(index), index, SR.ArgumentOutOfRange_Index);
+           values[index] = value;
+           version++;
+       }

Usage Examples

Allows an overriding class to handle complicated scenarios
Such as this example in which a binary search must be performed before deciding between a set or remove operation.

var index = this.IndexOfKey(key);
var newValue = this.Values[index] + incrValue;
if (newValue == 0) // or any condition that can only be decided once the index is known
    this.RemoveAt(index);
else
    this.SetValueByIndex(index, newValue);

Risks

The index of a particular key could change via another thread between acquisition and use. However, none of the other currently implemented methods in SortedList<TKey, TValue> take precautions to make the class thread-safe.

[ghost]

Tagging subscribers to this area: @eiriktsarpalis
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

There is no way to set the value of an entry by index in the generic SortedList<TKey, TValue> like there is in the non-generic version. While it is fine that GetByIndex is marked as private and can be accessed via SortList<TKey, TValue>.Values[index] as noted in #40450, it is not fine that there is no way to set the value by index. This causes my code to incur a BinarySearch cost (log n) to set the value when I already know the index.

I'm rather surprised nobody has mentioned this here even though there is interest over on StackOverflow.

API Proposal

namespace System.Collections.Generic
{
    public class SortedList<TKey, TValue>
    {
        ...

        public void SetByIndex(int index, TValue value)
        {
            if (index < 0 || index >= _size)
                throw new ArgumentOutOfRangeException(nameof(index), index, SR.ArgumentOutOfRange_Index);
            values[index] = value;
            version++;
        }

API Usage

list.SetByIndex(index)

Risks

No response

Author:	rhaokiel
Assignees:	-
Labels:	api-suggestion, area-System.Collections, untriaged
Milestone:	-

[eiriktsarpalis]

Updating the value of a dictionary without specifying the key feels a bit error-prone to me. That being said, I understand the motivation and there is precedent in the non-generic collection. @stephentoub should we be considering this?

[rhaokiel]

It might be the practical use of this is only applicable to a class override to further extend the functionality, which is my use case. So maybe protected is more appropriate?

Also, this class differs from a traditional dictionary in that it provides an indexed order as well. This is important functionality to the design of the class. If I didn't care about the index, then I would just use a dictionary.

[eiriktsarpalis]

We can investigate potentially marking as protected. Perhaps it might make sense to investigate the viability of a GetByIndex method as well. @rhaokiel could I ask you to update the OP following the API proposal template? We can then consider it for API review.

[krwq]

@rhaokiel ping

[rhaokiel]

My apologies for the delay. @eiriktsarpalis, I've updated the proposal to use protected as suggested and added an example. Are there any other concerns that need to be discussed?

[eiriktsarpalis]

I think this is ok, we can put it up for review.

[terrajobst]

Video

• It seems GetByIndex() can already be achieved by indexing into the Values and Keys properties.
  • So we don't need to expose GetByIndex, but feels good for symmetry
• The Values throws NotSupportedException on writes
  • We could make this writable but this would be odd
• We should add SetValueByIndex

namespace System.Collections.Generic
{
    public partial class SortedList<TKey, TValue>
    {
        public TKey GetKeyAtIndex(int index);
        public TValue GetValueAtIndex(int index);
        public void SetValueAtIndex(int index, TValue value);
    }
}

[eiriktsarpalis]

@rhaokiel would you be interested in contributing an implementation for the approved API?

[rhaokiel]

@eiriktsarpalis sure. I'm not very sure on the etiquette though. Do I submit a PR at this point? I believe the following changes would satisfying the approved API:

namespace System.Collections.Generic
{
    public class SortedList<TKey, TValue>
    {
+       public TKey GetKeyAtIndex(int index)
-       private TKey GetKey(int index)
        { ... }

+       public TValue GetValueAtIndex(int index)
-       private TValue GetByIndex(int index)
        { ... }

+       public void SetValueAtIndex(int index, TValue value)
+       {
+           if (index < 0 || index >= _size)
+               throw new ArgumentOutOfRangeException(nameof(index), index, SR.ArgumentOutOfRange_Index);
+           values[index] = value;
+           version++;
+       }


        public sealed class KeyList : IList<TKey>, ICollection
        {
            public TKey this[int index]
            {
                get
                {
+                    return _dict.GetKeyAtIndex(index);
-                    return _dict.GetKey(index);


        public sealed class ValueList : IList<TValue>, ICollection
        {
            public TValue this[int index]
            {
                get
                {
+                    return _dict.GetValueAtIndex(index);
-                    return _dict.GetByIndex(index);

[eiriktsarpalis]

Yes feel free to submit a PR, public API diff should match what was approved in #58962 (comment)

[stephentoub]

@eiriktsarpalis, can this be closed now?