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?
7 Answers
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 theSortedList<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 thanSortedDictionary<TKey, TValue>
.
SortedDictionary<TKey, TValue>
has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) forSortedList<TKey, TValue>
.If the list is populated all at once from sorted data,
SortedList<TKey, TValue>
is faster thanSortedDictionary<TKey, TValue>
.
(SortedList
actually maintains a sorted array, rather than using a tree. It still uses binary search to find elements.)
-
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. :) Commented Jun 1, 2009 at 16:56
-
2I think the SortedList definition should be corrected as I don't believe it's a binary search tree ... ?– nchaudCommented Feb 5, 2013 at 19:38
-
1I looked using reflector and found that it didn't use a binary search tree. Commented Feb 23, 2013 at 5:54
-
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– GhosterCommented Aug 15, 2019 at 3:52
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.
-
Note that if you want good performance and relatively low memory usage and indexed retrieval, consider
BDictionary<Key,Value>
in LoycCore instead ofSortedDictionary
.– QwertieCommented Feb 26, 2016 at 6:13 -
1Yes, look at the bottom part of this article. It turns out
BDictionary
is usually slower thanSortedDictionary
except for very large sizes, but it is faster thanSortedList
if there are over 700 items or so. Memory use should be only slightly higher thanSortedList
(much lower thanSortedDictionary
), due to the use of arrays in the leaves of the tree.– QwertieCommented Mar 15, 2016 at 3:08 -
1It'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. Commented Nov 6, 2020 at 17:10
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++;
}
Enough is said already on the topic, however to keep it simple, here's my take.
Sorted dictionary should be used when-
- More inserts and delete operations are required.
- Data in un-ordered.
- Key access is enough and index access is not required.
- Memory is not a bottleneck.
On the other side, Sorted List should be used when-
- More lookups and less inserts and delete operations are required.
- Data is already sorted (if not all, most).
- Index access is required.
- Memory is an overhead.
Hope this helps!!
Check out the MSDN page for SortedList:
From Remarks section:
The
SortedList<(Of <(TKey, TValue>)>)
generic class is a binary search tree withO(log n)
retrieval, wheren
is the number of elements in the dictionary. In this, it is similar to theSortedDictionary<(Of <(TKey, TValue>)>)
generic class. The two classes have similar object models, and both haveO(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 thanSortedDictionary<(Of <(TKey, TValue>)>)
.
SortedDictionary<(Of <(TKey, TValue>)>)
has faster insertion and removal operations for unsorted data,O(log n)
as opposed toO(n)
forSortedList<(Of <(TKey, TValue>)>)
.If the list is populated all at once from sorted data,
SortedList<(Of <(TKey, TValue>)>)
is faster thanSortedDictionary<(Of <(TKey, TValue>)>)
.
-
9The quoted text is wrong (and was updated on MSDN): SortedList is not a "binary search tree", it is an "array of key/value pairs". Commented Aug 19, 2012 at 23:24
This is visual representation of how performances compare to each other.
-
1Where 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. Commented Jan 29, 2019 at 11:18
-
1@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.– BenCommented Jan 9, 2021 at 3:15
-
1@alexkostin
Dictionary<K, V>
does not preserve the insertion order of its elements, where asSortedList<K, V>
andSortedDictionary<K, V>
order by a givenIComparer<K>
. Commented Feb 4, 2022 at 3:37
Index access (mentioned here) is the practical difference. If you need to access the successor or predecessor, you need SortedList. SortedDictionary cannot do that so you are fairly limited with how you can use the sorting (first / foreach).
SortedList<TKey,TValue>
rather than oneSortedList<T>
? Why doesn't it implementIList<T>
?SortedList<TKey, TValue>
doesn't implementIList
itself, itsKey
andValue
members implementIList<TKey>
andIList<TValue>
, respectively.