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.
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.