What's the difference between SortedList and SortedDictionary?

Question

Is there any real practical difference between a SortedList<TKey,TValue> and a SortedDictionary<TKey,TValue>? Are there any circumstances where you would specifically use one and not the other?

Solution 1

Yes - their performance characteristics differ significantly. It would probably be better to call them SortedList and SortedTree as that reflects the implementation more closely.

Look at the MSDN docs for each of them (SortedList, SortedDictionary) for details of the performance for different operations in different situtations. Here's a nice summary (from the SortedDictionary docs):

The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

• SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<TKey, TValue>.

• If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

(SortedList actually maintains a sorted array, rather than using a tree. It still uses binary search to find elements.)

Solution 2

Here is a tabular view if it helps...

From a performance perspective:

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | O(n)**  | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

  * Insertion is O(log n) for data that are already in sort order, so that each 
    element is added to the end of the list. If a resize is required, that element
    takes O(n) time, but inserting n elements is still amortized O(n log n).
    list.
** Available through enumeration, e.g. Enumerable.ElementAt.

From an implementation perspective:

+------------+---------------+----------+------------+------------+------------------+
| Underlying | Lookup        | Ordering | Contiguous | Data       | Exposes Key &    |
| structure  | strategy      |          | storage    | access     | Value collection |
+------------+---------------+----------+------------+------------+------------------+
| 2 arrays   | Binary search | Sorted   | Yes        | Key, Index | Yes              |
| BST        | Binary search | Sorted   | No         | Key        | Yes              |
+------------+---------------+----------+------------+------------+------------------+

To roughly paraphrase, if you require raw performance SortedDictionary could be a better choice. If you require lesser memory overhead and indexed retrieval SortedList fits better. See this question for more on when to use which.

You can read more here, here, here, here and here.

Solution 3

I cracked open Reflector to have a look at this as there seems to be a bit of confusion about SortedList. It is in fact not a binary search tree, it is a sorted (by key) array of key-value pairs. There is also a TKey[] keys variable which is sorted in sync with the key-value pairs and used to binary search.

Here is some source (targeting .NET 4.5) to backup my claims.

Private members

// Fields
private const int _defaultCapacity = 4;
private int _size;
[NonSerialized]
private object _syncRoot;
private IComparer<TKey> comparer;
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
private KeyList<TKey, TValue> keyList;
private TKey[] keys;
private const int MaxArrayLength = 0x7fefffff;
private ValueList<TKey, TValue> valueList;
private TValue[] values;
private int version;

SortedList.ctor(IDictionary, IComparer)

public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer)
{
    if (dictionary == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
    }
    dictionary.Keys.CopyTo(this.keys, 0);
    dictionary.Values.CopyTo(this.values, 0);
    Array.Sort<TKey, TValue>(this.keys, this.values, comparer);
    this._size = dictionary.Count;
}

SortedList.Add(TKey, TValue) : void

public void Add(TKey key, TValue value)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer);
    if (num >= 0)
    {
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
    }
    this.Insert(~num, key, value);
}

SortedList.RemoveAt(int) : void

public void RemoveAt(int index)
{
    if ((index < 0) || (index >= this._size))
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);
        Array.Copy(this.values, index + 1, this.values, index, this._size - index);
    }
    this.keys[this._size] = default(TKey);
    this.values[this._size] = default(TValue);
    this.version++;
}

Solution 4

This is visual representation of how performances compare to each other.

Solution 5

Check out the MSDN page for SortedList:

From Remarks section:

The SortedList<(Of <(TKey, TValue>)>) generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedDictionary<(Of <(TKey, TValue>)>) generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

• SortedList<(Of <(TKey, TValue>)>) uses less memory than SortedDictionary<(Of <(TKey, TValue>)>).

• SortedDictionary<(Of <(TKey, TValue>)>) has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<(Of <(TKey, TValue>)>).

• If the list is populated all at once from sorted data, SortedList<(Of <(TKey, TValue>)>) is faster than SortedDictionary<(Of <(TKey, TValue>)>).

View more solutions

Comments

[Liam]

Related: When to use a SortedList or a SortedDictionary

[Colonel Panic]

I'm confused. Why does SortedList have two type parameters SortedList<TKey,TValue> rather than one SortedList<T>? Why doesn't it implement IList<T>?

[nawfal]

@ColonelPanic because functionally SortedList is a map, not a linear collection. Dont let the name fool you. Just like a dictionary, you pass in a key, you get a value back. While dictionary is unordered, SortedList is ordered in its natural sorted order.

[Shaul Behr]

Thanks v much to all for the pointers. I guess I'm just too lazy to RTFM... much easier to ask the nice folks on SO... ;) I voted you both up for the answers; Jon gets answer credit for being first on the trigger. :)

[Eldritch Conundrum]

The quoted text is wrong (and was updated on MSDN): SortedList is not a "binary search tree", it is an "array of key/value pairs".

[nchaud]

I think the SortedList definition should be corrected as I don't believe it's a binary search tree ... ?

[Daniel Imms]

I looked using reflector and found that it didn't use a binary search tree.

[Qwertie]

Note that if you want good performance and relatively low memory usage and indexed retrieval, consider BDictionary<Key,Value> in LoycCore instead of SortedDictionary.

[Qwertie]

Yes, look at the bottom part of this article. It turns out BDictionary is usually slower than SortedDictionary except for very large sizes, but it is faster than SortedList if there are over 700 items or so. Memory use should be only slightly higher than SortedList (much lower than SortedDictionary), due to the use of arrays in the leaves of the tree.

[alex kostin]

Where did you take that info from? From this scheme we can see that Dictinary is better in any way, so there is no reason for others to exist.

[Ghoster]

I think the Sorteddictionary is an AVL-tree or Red-Blacktree( all operation cost O(logn). And the SortedList is a binary-search (it costs o(n) time in the worst case)l

[relatively_random]

It's unfortunate that ordered insertion into SortedList is O(log n) per element. Making it O(1) would have been easy to implement with just one check before performing a binary search.

[Ben]

@alexkostin Maybe a bit late but see stackoverflow.com/a/19702706/7224691. I was having issues with the source link but i could find it on the wayback machine.

[Steve Guidi]

@alexkostin Dictionary<K, V> does not preserve the insertion order of its elements, where as SortedList<K, V> and SortedDictionary<K, V> order by a given IComparer<K>.