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.

    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);
        }
    }

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 Reply