Menu
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
}
}
}
354
In SortedList, an element can be accessed by its key or by its index. A SortedList object internally maintains two arrays to store the elements of the list, i.e, one array for the keys and another array for the associated values. Here, a key cannot be null, but a value can be.
A sorted list is a combination of an array and a hash table. It contains a list of items that can be accessed using a key or an index. If you access items using an index, it is an ArrayList, and if you access items using a key, it is a Hashtable. The collection of items is always sorted by the key value.
C# - SortedList<TKey, TValue> The SortedList<TKey, TValue> , and SortedList are collection classes that can store key-value pairs that are sorted by the keys based on the associated IComparer implementation.
SortedDictionary is implemented with Binary Search Tree, while SortedList is implemented with two internal arrays for keys and values, respectively. SortedList is more memory-efficient than SortedDictionary, and SortedList is faster than SortedDictionary when it needs to go through all items at once.
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.
79
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
