C# SortedList

Use the SortedList class, which enables binary search. Call the ContainsKey and IndexOfKey methods.

SortedList. This collection stores elements in an ordered way. This enables binary search. We do not need to write custom code for the search.

Some notes. SortedList has worse lookup performance than a Dictionary. It allows us to use binary search with less development effort.

An example. We cover the SortedList collection. You can use the SortedList in the same way as a Dictionary. It may require less memory for storage.

Types: The SortedList instance has 2 type parameters (string and int) that describe the requirements for elements.

Generic Class, Method

Info: You will get a compile-time error if you try to use a wrongly-typed parameter.

Tip: ContainsKey and TryGetValue test the internal data structure (an array) in the SortedList instance.

TryGetValue: This can obtain the value associated with the key if it is found in the data structure. It can boost performance on lookups.

C# program that uses SortedList using System; using System.Collections.Generic; class Program { static void Main() { // // Create SortedList with 3 keys and values. // SortedList<string, int> sorted = new SortedList<string, int>(); sorted.Add("Codex", 3); sorted.Add("dot", 1); sorted.Add("net", 2); // // Test SortedList with ContainsKey method. // bool contains1 = sorted.ContainsKey("java"); Console.WriteLine("contains java = " + contains1); // // Use TryGetValue method. // int value; if (sorted.TryGetValue("Codex", out value)) { Console.WriteLine("Codex key is = " + value); } // // Use item indexer. // Console.WriteLine("dot key is = " + sorted["dot"]); // // 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("net"); Console.WriteLine("index of net (key) = " + index1); int index2 = sorted.IndexOfValue(3); Console.WriteLine("index of 3 (value) = " + index2); // // Display Count property. // Console.WriteLine("count is = " + sorted.Count); } } Output contains java = False Codex key is = 3 dot key is = 1 [dot, 1] [net, 2] [Codex, 3] index of net (key) = 1 index of 3 (value) = 2 count is = 3

Internals. 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: You can see the IndexOfKey method is invoked each time. The internal array is accessed at that index.

Indexer

Lookup implementation for SortedList: C# 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; }

Notes, binary search. 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.

And: For this reason, the SortedList will be slower than a Dictionary in many programs.

Info: For large collections and collections where the size is indeterminate at compile-time and may be large, consider a Dictionary.

Dictionary

Further: The HybridDictionary and SortedList collections perform well on small data sets.

HybridDictionary

Strings. 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.Capacity

Clear. This erases all the internal data structures. Another option is to simply reassign the variable in your program to a new, empty SortedList.

Keys, Values. These properties can only be read from. They allocate the KeyList data structure and the ValueList data structure before returning the elements.

Note: These allocations will only copy the element references. They won't copy all the strings if you use that type as the key or value.

Summary. SortedList will store an internally sorted data structure which it then queries with a BinarySearch method. It does not provide optimal lookup performance.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# SortedList

Related Links:

.Net

Java

Related Links