C# SortedList Collection

SortedList stores elements in an ordered way.

It can be quickly searched with binary search. It has worse lookup performance than Dictionary collections. It allows you to use binary search with less development effort.

Example. We cover the methods and properties on the SortedList collection. You can use the SortedList in the same way as a Dictionary. It has a different implementation. It may require less memory for storage but more time for lookups.

Here: This example uses many methods and properties on SortedList, starting with the constructor.

C# program that uses SortedList

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	//
	// Created SortedList with three keys and values.
	//
	SortedList<string, int> sorted = new SortedList<string, int>();
	sorted.Add("deves", 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("deves", out value))
	{
	    Console.WriteLine("deves 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
deves key is = 3
dot key is = 1
[dot, 1]
[net, 2]
[deves, 3]
index of net (key) = 1
index of 3 (value) = 2
count is = 3

A new SortedList is allocated on the managed heap. This SortedList instance has two type parameters, string and int, that describe the requirements for the method calls to the further methods. This provides compile-time checking.

The Add method is invoked three times. The type of the variable parameters exactly matches the types embedded in the SortedList signature. You will get a compile-time error if you try to use a wrongly-typed parameter.

Compile-Time Error

ContainsKey and TryGetValue test the internal data structure (an array) in the SortedList instance. The ContainsKey actually looks up the value completely but only returns true or false in its public signature.

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

The indexer access invokes the this[key] property accessor in the type definition. You can see the actual source code from the disassembled SortedList that implements the indexer later in this document.

Indexer Examples

You can loop over the SortedList instance by using a foreach-loop construct over the variable itself. This internally invokes the enumerator implementation. You can specify the KeyValuePair type instead of the implicit var type.

Internals. Here we look inside a disassembled version of SortedList. This shows us exactly what the SortedList implementation does when you try to access a key with the indexer. The ContainsKey and TryGetValue methods use similar lookup code.

You can see the IndexOfKey method is invoked each time, and then the internal array is accessed at that index. The IndexOfKey method then uses the Array.BinarySearch generic method.

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;
}

The binary search algorithm is often superior to a linear search but in the real world it rarely is as fast as a good hash computation and lookup. For this reason, the SortedList will be slower than a Dictionary in many programs.

However: Because it uses no excess structures as the Dictionary does, it will use less memory. On small collections, it will not be slower.

For large collections and collections where the size is indeterminate at compile-time and may be large, you should prefer the Dictionary collection. The HybridDictionary and SortedList collections perform well on small data sets.

But: There is rarely a severe performance problem on small data sets. Why solve a performance problem that does not exist?

Strings. On a SortedList with string keys, you can improve performance—specify StringComparer.Ordinal as the comparison method. This instructs the SortedList to perform faster, ordinal string comparisons.

Tip: On some Dictionaries with random keys, this comparer improves performance by 17%.

Dictionary StringComparer

Methods. There are some more methods you will find on the SortedList class. You can see all of these members by typing in the SortedList variable identifier in Visual Studio and then pressing period.

Then: The IntelliSense feature in Visual Studio will display all the members of SortedList.

TrimExcess. This method internally multiplies the number of keys in the data structure by 90% and sees if that number is still larger than the capacity. If the number of keys is too large, it then adjusts the Capacity property.

Note: This usually performs two Array.Copy invocations to resize the internal data structure.

Caution: This is not often useful. Computers have so much memory that worrying about the arrays in a SortedList is not usually relevant.

The Clear method erases all the internal data structures. Another option is to simply reassign the variable in your program to a new, empty SortedList. This will offload the task of cleaning up the memory to the garbage collector.

Keys and Values. These properties can only be read from and not assigned to. 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.

Memory

Summary. We looked at the SortedList type. We saw the methods you can use on this type. SortedList will store an internally sorted data structure which it then queries with a BinarySearch method.

Tip: This class is not usually suited for optimal lookup performance. But it has other benefits.

Related Links