SortedSet wrapper for .net 3.5

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 that is build on the SortedList where TValue is a byte,

Here is my implementation – if you need any of the really fancy features, you will need to implement them yourself.

[csharp]
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);
}
}

[/csharp]

4 thoughts on “SortedSet wrapper for .net 3.5”

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

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

Leave a Comment

Your email address will not be published. Required fields are marked *