Here is a VERY basic SortedSet wrapper for .NET 3.5
The SortedSet is one of the few new features of the .NET Framework 4.0 that I hate to go without. I recently had to drop a Class Library from 4.0 to 3.5, and the SortedSet was the only thing missing. So, I just created my own SortedSet
Here is my implementation – if you need any of the really fancy features, you will need to implement them yourself.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | public class SortedSet<T> : SortedList<T,byte>{ public SortedSet() : base() { } public T Min { get { if ((base.Count) >= 1) { return base.Keys[0]; } else { return default(T); } } } public T Max { get { if ((base.Count) >= 1) { return base.Keys[base.Keys.Count - 1]; } else { return default(T); } } } public bool Contains(T value) { return base.ContainsKey(value); } public void Add(T value) { base.Add(value, 0); }} |
Actually that’s definitely different from the .net 4 SortedSet.
1 – SortedSet is implemented as Red-Black tree
i.e. insert, delete, search are O(log(n)), indexing is O(n)
SortedList is a binary tree
i.e. worst-case performance: insert, delete are O(n), search and indexing is O(n)
(all are worst-case complexities)
To be more similar, you should use SortedDictionary that is implemented as Red-black tree
2 – null can be added to SortedSet, while cannot be used as Key in the SortedList
Thanks for the info digEmAll – I confess runtime performance was less important than getting it done quickly.
Typo correction: search and indexing is O(log(n)) for Sortedlist
I was going to look into redoing it using the SortedDictionary, but the .NET 3.5 documentation changed my mind.
1. SortedList and SortedDictionary Keyed retreival is the same – O(log n)
2. Insertion and deletion is faster in the dict, but only when populated randomly, and the dict uses more memory
3. Indexed retreival of the Keys[] and Values[] collections is more efficient with the SortedList, and the Keys collection is used by the max and min properties. (The main reason I needed the SortedSet was for the max and min)
4. Neither SortedList not SortedDictionary permits null keys
I guess it all depends what you are after.