SortedList
This C# collection stores elements in an ordered way. This enables binary search. We do not need to write custom code for the search.
SortedList
has worse lookup performance than a Dictionary
. It allows us to use binary search with less development effort.
It is possible use the SortedList
in the same way as a Dictionary
. In programs, the SortedList
may require less memory for storage.
SortedList
instance has 2 type parameters (string
and int
) that describe the requirements for elements.ContainsKey
and TryGetValue
test the internal data structure (an array) in the SortedList
instance.using System; using System.Collections.Generic; // Create SortedList with 3 keys and values. var sorted = new SortedList<string, int>(); sorted.Add("zebra", 3); sorted.Add("cat", 1); sorted.Add("dog", 2); // Use ContainsKey. bool contains1 = sorted.ContainsKey("?"); Console.WriteLine("contains ? = " + contains1); // Use TryGetValue. int value; if (sorted.TryGetValue("zebra", out value)) { Console.WriteLine("zebra = " + value); } // Use item indexer. Console.WriteLine("cat = " + sorted["cat"]); // Loop over SortedList data. foreach (var pair in sorted) { Console.WriteLine(pair); } // Get index of key and then index of value. int index1 = sorted.IndexOfKey("cat"); Console.WriteLine("index of cat = " + index1); int index2 = sorted.IndexOfValue(3); Console.WriteLine("index of 3 (value) = " + index2); // Display Count. Console.WriteLine("count = " + sorted.Count);contains ? = False zebra = 3 cat = 1 [cat, 1] [dog, 2] [zebra, 3] index of cat = 0 index of 3 (value) = 2 count = 3
Here we look inside a disassembled version of SortedList
. This shows us exactly what the class
does when you try to access a key.
IndexOfKey
method is invoked each time. The internal array is accessed at that index.public TValue this[TKey key] { get { int index = this.IndexOfKey(key); if (index >= 0) { return this.values[index]; } ThrowHelper.ThrowKeyNotFoundException(); return default(TValue); } } public int IndexOfKey(TKey key) { if (key == null) { ThrowHelper.ThrowArgumentNullException( ExceptionArgument.key); } int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer); if (num < 0) { return -1; } return num; }
The binary search algorithm is often superior to a linear search. But in the real world it is rarely as fast as a hash lookup.
SortedList
will be slower than a Dictionary
in many programs.Dictionary
.HybridDictionary
and SortedList
collections perform well on small data sets.On a SortedList
with string
keys, you can improve performance. Specify StringComparer.Ordinal
as the comparison method. Pass this in as an argument to the constructor.
TrimExcess
This multiplies the number of keys in the data structure by 90%. It sees if that number is still larger than the capacity. It may adjust the Capacity
property.
Keys
, ValuesThese properties can only be read from. They allocate the KeyList
data structure and the ValueList
data structure before returning the elements.
SortedList
will store an internally sorted data structure which it then queries with a BinarySearch
method. It does not provide optimal lookup performance.