Why is there no SortedList<T> in .NET?

views:

165

answers:

+1 Q:

Why is there no SortedList<T> in .NET?

Why is there only a SortedList<TKey, TValue> which looks more like a dictionary, but no SortedList<T> that is actually just a list that is always sorted?

According to the MSDN documentation on SortedList, it is actually internally implemented as a dynamically-sized array of KeyValuePair<TKey, TValue> that is always sorted by the key. Wouldn’t the same class be more useful as a list of any type T? Wouldn’t that fit the name better, too?

It is a list with the sorting being done by the key. I'm just speculating but by providing the ability to specify the key separate from the element, your element doesn't have to be comparable -- only the key need be. I would imagine that in the general case this saves a fair amount of code being developed to implement IComparable since the key is likely a type that is already comparable.

tvanfosson 2010-09-08 00:09:06

This answer doesn’t make any sense. If you want to sort by something you need a comparer, irrespective of whether you happen to call the something a “key” or a “value”. If the key is a type that is already comparable, then obviously I could as well sort a list of just the keys, and if it isn’t, then clearly `SortedList<TK,TV>` doesn’t provide the desired functionality either.

Timwi 2010-09-08 00:29:37

My point is that, for most cases, with `SortedList<T>`, you'd end up having to implement IComparable for a class and that IComparable would simply re-implement (or delegate the functionality to) the comparability of a value type. That being the case, making the sort key explicit simplifies the implementation for the user of the class at the expense of some storage overhead -- assuming that the key is drawn from a class property. You can obviously keep a list of sorted keys and a list of associated values in the same order. I believe that's how SortedList is implemented. Not very efficient.

tvanfosson 2010-09-08 12:31:10

Hi Timwi,

RPM comments is quite valid. Also, with the Linq extensions, you can do sort by any property of T using the Sort extension method. I think that might be the main reasoning behind it.

Chers, Wagner.

Wagner Silveira 2010-09-08 00:10:29

There is no `Sort` extension method. If you meant `List<T>.Sort` (which is neither an extension method nor part of LINQ), then using this after every call to `Add` and `Insert` would be much slower than necessary. If you meant `OrderBy`, that’s *even* slower.

Timwi 2010-09-08 00:32:08

I think the reason is probably just that List<T> already has BinarySearch and Insert, which means implementing your own always-sorted list is trivial.

Not that this means a SortedList<T> class doesn't belong in the framework -- just that it probably wasn't a very high priority since it could easily be written quickly by any developer who needed it.

I think the same was true for HashSet<T>, which didn't originally exist because you could easily use a Dictionary<T, byte> (for example) to simulate one before .NET 3.5.

I know that's what I did in both cases: I had a UniqueSet<T> class and an AlwaysSortedList<T> class, which just wrapped a Dictionary<T, byte> and a List<T> (and used BinarySearch and Insert), respectively.

Dan Tao 2010-09-08 00:11:20

If such a `SortedList<T>` was too low-priority, then certainly `SortedList<TKey, TValue>`, which provides a strict subset of the functionality, would be even lower-priority.

Timwi 2010-09-08 00:33:46

@Timwi: I don't think that's *quite* accurate about `SortedList<TKey, TValue>`. I mean, in terms of its implementation, yeah, it appears to be the case. But that class is clearly meant to be used as a dictionary, hence all the comparisons between `SortedList<TKey, TValue>` and `SortedDictionary<TKey, TValue>` in MSDN's documentation (and the fact that `SortedList<TKey, TValue>` implements `IDictionary<TKey, TValue>`). I don't know *why* they would've prioritized this above a "real" sorted list; the fact remains that implementing one yourself takes practically no effort.

Dan Tao 2010-09-08 00:50:53

Isn't SortedSet what you are looking for?

Ray 2010-09-08 00:11:35

...unless duplicate elements are desired.

Will A 2010-09-08 00:18:13

As Will noted, there is a significant semantic difference between the two, so no.

Timwi 2010-09-08 00:22:37

A Set is different from a List. If you want the median element of a `SortedList s` you can ask for `s.Values[s.Count / 2]`, an O(1) operation. If you want the median element of a `SortedSet s`, you need to iterate halfway through the set.

Gabe 2010-09-08 00:37:14

Neither collection allows duplicates on the sorting key (the key in the list, and the element itself in the set). A SortedList<TKey, TValue> will allow the same value to be associated with multiple keys, which is cool, but take away the separate key and now the duplicate objects are (IMO) confusing. It seems to me that a SortedList<T> which allowed duplicates would not be very useful.

Ray 2010-09-08 00:37:35

@Gabe - good point - I guess, as usual, it depends on what you are going to use the list/set for. In some case, the SortedSet would be fine, in others, it would suck.

Ray 2010-09-08 00:42:32

@Ray: `List<T>`, `T[]`, `IEnumerable<T>` etc. all allow duplicates. Does that make them all “not very useful” and (IYO) “confusing”?

Timwi 2010-09-08 01:00:37

No, unless I actually added duplicates to them. maybe it's just a failure of imagination, but I can't think of a reason to have duplicates in a sorted list (or in most unsorted lists). I am sure there is some use for it, but I have never needed it. Anyway, my point was that if you are using a variant of a SortedSomething that does not allow dups, then your variant should not allow dups either. Maybe this semantic confusion is the real reason MS didn't create a SortedList<T>. btw - I like this kind of discussion - I usually learn something (even if it costs me a downvote)

Ray 2010-09-08 01:32:02

Although nobody can really tell you why there is no SortedList<T>, it is possible to discuss why SortedList takes a key and a value. A dictionary maps keys to values. The typical ways to do this are with a binary tree, a hash table, and a list (array), though hash tables are most common because they are O(1) for most operations.

The primary operation that it doesn't support in O(1) is getting the next key in order. If you want to be able to do that, you typically use a binary tree, giving you a sorted dictionary.

If you decide to implement the map as a list, you would keep the elements sorted by key so that lookup is O(lg n), giving you another sorted dictionary -- in the form of a sorted list. Of course the name SortedDictionary was already taken, but SortedList wasn't. I might have called it SortedListDictionary or SortedDictionaryList, but I didn't get to name it.

Gabe 2010-09-08 02:10:10

ansaurus

tags:

views:

answers:

Why is there no SortedList<T> in .NET?

related questions