SetByIndex equivalent for System.Collections.Generic.SortedList

Question

System.Collections.SortedList has a SetByIndex method that is cheap, O(1) owing to the nature of the data structure. The generic version of this class does not have a SetByIndex method. I am looking for the equivalent operation for the SortedList implementation in System.Collections.Generic.

Both classes implement a dictionary using sorted arrays. Since the underlying structure is an array, the entries can be efficiently accessed by index. The non-generic version also offers a GetByIndex method that retrieves a value by index (as opposed to key). The generic SortedList also supports retrieval by index through the .Values property. When I try to modify an element through the .Values property, I get an exception that says "This operation is not supported on SortedList nested types because they require modifying the original SortedList."

I'm not an expert on object-oriented design, but why not just let me modify the value through the "nested type" returned by the SortedList?

For this project, I am on .NET 4.0. I need the SortedList so I can iterate through the items in sorted order. Based on profiling, the very most expensive call tree in the program involves iterating through the items in a bunch of small SortedLists by index (and so in sort order by key) and modifying certain values. Currently to perform that value modification step, I have to assign using the key, which involves log(n) string comparison operations to locate the proper slot than simply assigning the value by index (i.e. SetByIndex) which would be zero comparisons. I am not changing the key so nothing would affect the position of the value in the array.

19% (exclusive) total program time spent in System.String.CompareTo(string), almost all of which is from the method that modifies the values.

Sample code to illustrate:

class Container
{
    readonly System.Collections.Generic.SortedList<string, MapEntryValueType> map;
    void Merge(IncomingData data)
    {
        for(int i=0; i < map.Count; i++)
            if(data.ExamineKeyForMatch(map.Keys[i])) //O(1)
            {
                MapEntryValueType entry = map.Values[i]; //O(1)
                entry.something = data.something;
                //map.Values[i] = entry; //O(1) no can do, error "This operation is not supported..."
                //map.SetByIndex(i, entry); //O(1) no can do, no such method
                map[map.Keys[i]] = entry; //O(log n) yucky and slow but works
            }
    }
}

score 2 · Accepted Answer · answered Dec 01 '21 at 10:41

2

This feature request was opened as https://github.com/dotnet/runtime/issues/58962 on 2021-09-10 and implemented by https://github.com/dotnet/runtime/pull/60520 on 2021-11-15. It isn't present in .NET 6.0 or earlier.

answered Dec 01 '21 at 10:41

Chris Culter

4,470
2
15
30

ZippyZippedUp · Answer 2 · 2017-05-31T22:26:37.120

0

Use the Values property on SortedList<TKey, TValue> to get an IList<TValue> of all values in the sorted list. You can then get the value by index, which is an O(1) operation e.g. mySortedList.Values[i]

https://msdn.microsoft.com/en-us/library/ms132380(v=vs.110).aspx

If your value type is a struct, you could pass it to a method using ref along with the new property value and update the property in the method. It's not really recommended to use mutable structs, though, as described here: pass c# struct by reference?

edited May 31 '17 at 22:26

answered May 31 '17 at 19:38

ZippyZippedUp

458
5
14

3

Yes, I can GET a value by index, in exactly the manner you suggested, illustrated in the sample code. The question is about SETting a value by index. Trying to SET through the IList.Values raises a "This operation is not supported on SortedList nested types because they require modifying the original SortedList." error – Chris Smith May 31 '17 at 19:58
I've edited the answer with a possibility on how the value could then be set. This might not be the ideal solution, but hopefully some food for thought. – ZippyZippedUp May 31 '17 at 22:28
2

Getting a struct value using the property accessor on the SortedList will copy the value, so passing by ref will not modify the value on the SortedList, it will only modify the retrieved copy. – Orestis P. Sep 15 '20 at 21:30

SetByIndex equivalent for System.Collections.Generic.SortedList

2 Answers2