I need to sort some objects according to their contents (in fact according to one of their properties, which is NOT the key and may be duplicated between different objects).
.NET provides two classes (SortedDictionary and SortedList), and both are implemented using a binary tree. The only differences between them are
- SortedList uses less memory than SortedDictionary.
- SortedDictionary has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList.
- If the list is populated all at once from sorted data, SortedList is faster than SortedDictionary.
I could achieve what I want using a List, and then using its Sort() method with a custom implementation of IComparer, but it would not be time-efficient as I would sort the whole List each time I want to insert a new object, whereas a good SortedList would just insert the item at the right position.
What I need is a SortedList class with a RefreshPosition(int index) to move only the changed (or inserted) object rather than resorting the whole list each time an object inside changes.
Am I missing something obvious ?
Best Answer
Maybe I'm slow, but isn't this the easiest implementation ever?
http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
Unfortunately,
Add
wasn't overrideable so I had tonew
it which isn't so nice when you haveList<T> list = new SortedList<T>;
which I actually needed to do.... so I went ahead and rebuilt the whole thing...Or perhaps something like this is a more appropriate
Remove
function...Assuming items can compare equal but not be equal...