7

As far as I know, there is no way to get a List<T> with the capacity to sort itself. If I add a element, I want the data-structure to insert it in the right position (based on the associated IComparer<T>). I am looking for something with the same logic than SortedSet<T>.

I am aware of System.Collections.Generic.SortedList<TKey, TValue> but it is more a kind of Dictionary.

I don't really need one (it is not very difficult to implement). I just wonder whether a such data-structure exists and if not, why?

source:

11
  • Probably because List<T> already contains two Sort methods and a BinarySearch method, effectively making it already a SortedList<T> Oct 7, 2015 at 4:53
  • 5
    @Robert but with O(n) insertion cost. Oct 7, 2015 at 5:56
  • What is the use case of SortedList?
    – Siyuan Ren
    Oct 7, 2015 at 12:54
  • 2
    ... for some reason it does exist (docs), though as an IDictonary rather than an IList. This confuses me. Especially since the IList Add method (docs) doesn't have anything about appending to the end of the list (compare Java). Having the List be defined as 'append' makes a SortedList a violation of the contract (which isn't the case in C# and thus my 'why not?')
    – user40980
    Oct 7, 2015 at 13:24
  • @CodesInChaos: In a List<T>? I doubt it. Oct 7, 2015 at 15:07

1 Answer 1

18

It would break the IList interface.

You retrieve elements out of a list by index, if the indices for the elements keep changing this is useless, also Insert would be useless.

Item[Int32] - Gets or sets the element at the specified index.

Insert(Int32, T) - Inserts an item to the IList<T> at the specified index.

So the reason there is no SortedList<T> implementation is because other ADTs can handle the functionality in a more rational and efficient manner.

1
  • 2
    It could implement ICollection and IReadOnly List instead May 17, 2018 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.