CODEWITHSUNDEEP
c#listsortedlist
RE6
RE6

Reputation: 2724

How does C# SortedList internally work?

I was wondering, how does the SortedList work. I know that a regular List is based on a dynamic array, but what is SortedList based on?

And what sorting algorithm it uses?

Thanks

Upvotes: 3

Views: 4527

Answers (4)

Maxim Popov
Maxim Popov

Reputation: 165

SortedList class source code can be found here.

According to this source, SortedList keeps data in two plain arrays of keys and values:

private TKey[] keys;
private TValue[] values;

Sort order is maintained on the array of keys. When a new item (key/value pair) is added, SortedList first finds proper index in the sorted array of keys (using Array.BinarySearch), then moves partial contents of both key and value arrays (using Array.Copy) starting from this index upward to create a gap where both key and value are inserted. Likewise, when an item is deleted by its key, SortedList searches for the item's index in the array of keys, then moves partial contents of both arrays from this index downward to close the gap.

So, one thing to keep in mind is that when adding to or deleting from a large SortedList, a lot of data may be moved around. On the positive side, retrieving items by index is always fast regardless of the list size.

Upvotes: 3

JustABearoz
JustABearoz

Reputation: 1

If you are interested in the internals of how it works, get yourself any half decent decompiler, such as .Net Reflector.

A quick look shows that internally, SortedList maintains it's sorted state by keeping an internal array sorted at all times. When an item is added using the Add Method, it uses a binary search on the keys to identify the correct index to insert the new item.

Upvotes: 0

Rohit
Rohit

Reputation: 10236

A SortedList is an object that maintain's two array to store the element's of the list.

One array store's the Key and the other array store's its associated values.

The element's in the SortedList are sorted either according to a specific IComparer implementation specified when the SortedList is created or according to the IComparable implementation provided by the keys themselves. They cannot contain duplicate keys.

Whenever any element is added or removed the index is adjusted accordingly as a result operations related to SortedList are slower.

Upvotes: 0

ps2goat
ps2goat

Reputation: 8475

From the sortedlist documentation: "SortedList is implemented as an array of key/value pairs, sorted by the key."
http://msdn.microsoft.com/en-us/library/e7a8xew6%28v=vs.110%29.aspx

If you use the default constructor (no parameters): "Initializes a new instance of the SortedList class that is empty, has the default initial capacity, and is sorted according to the IComparable interface implemented by each key added to the SortedList object."
http://msdn.microsoft.com/en-us/library/cxb97few%28v=vs.110%29.aspx

Or you can pass a custom comparer:

Initializes a new instance of the SortedList class that is empty, has the default initial capacity, and is sorted according to the specified IComparer interface. http://msdn.microsoft.com/en-us/library/e7a8xew6%28v=vs.110%29.aspx

Other constructor options: http://msdn.microsoft.com/en-us/library/System.Collections.SortedList.SortedList%28v=vs.110%29.aspx

How to use IComparer interface: http://msdn.microsoft.com/en-us/library/system.collections.icomparer%28v=vs.110%29.aspx

Upvotes: 2

Related Questions