Keeping Your Data Sorted Using Generic SortedSet in .NET Framework 4

Introduction

.NET Framework 3.5 introduced a generic hash set class System.Collections.HashSet for representing a set of values. It provided high performance set operations. Though it did not contain duplicate elements, it was not sorted. One would have to call OrderBy overload to sort the elements of the HashSet.

In .NET Framework 4.0, the Base Class Libraries folks in the Common Language Runtime team added the SortedSet class in the System.Collections.Generic namespace. The BCL team claims that the class was arrived at by implementing self-balancing red-black trees, which would give the benefits of O-log-n algorithmic complexity for inserts, lookups and deletes.

Benefits of Sorted Sets

By using SortedSet class in .NET framework 4.0, users will not have to sort their data after every insert, update or delete. Let us consider a hypothetical company which issues paychecks by seniority. Say, the seniority of a person in the company is determined by the <employee id> value which is assigned serially on joining the company. So, the newest employee will get the largest possible of all existing employee-ID values and the senior-most employee will have an Employee-ID with the lowest value.

Hands On

Let us see how SortedSet makes it so easy to keep the contents sorted. First, let us see how we will have to do this with a HashSet

  // Listing 1
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using System.Collections;
  
  namespace HashSetExample
  {
      class Program
      {
          static void Main(string[] args)
          {
              HashSet<int> myHashSet = new HashSet<int>();
              myHashSet.Add(5);
              myHashSet.Add(4);
              myHashSet.Add(6);
              myHashSet.Add(1);
              myHashSet.Add(10);
              myHashSet.Add(3);
              Console.WriteLine("Default Payorder with HashSet will be as under");
              foreach (int i in myHashSet)
              {
                  Console.WriteLine(i);
              }
              Console.WriteLine("Payorder with HashSet after Orderby will be as under");
  
              IEnumerable orderedHashSet = myHashSet.OrderBy(a => a);
              foreach(int i in orderedHashSet)
              {
                  Console.WriteLine(i);
              }
  
              myHashSet.Add(2);
              Console.WriteLine("Order of Pay after an insert on HashSet");
              foreach (int i in myHashSet)
              {
                  Console.WriteLine(i);
              }
              
              Console.WriteLine("Sorting the second time");
              foreach (int i in orderedHashSet)
              {
                  Console.WriteLine(i);
              }
  
  
          }
      }
  }

We can see that if we just have a HashSet and we need to sort the data, we will have to call OrderBy. To keep our data sorted, we will have to call OrderBy after each add/update/modify.

Let us now see how easy it will be with SortedSet to keep our data sorted.

  // Listing 2
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  
  namespace SortedSetExample
  {
      class Program
      {
          static void Main(string[] args)
          {
              SortedSet<int> mySortedSet = new SortedSet<int>();
              mySortedSet.Add(5);
              mySortedSet.Add(4);
              mySortedSet.Add(6);
              mySortedSet.Add(1);
              mySortedSet.Add(10);
              mySortedSet.Add(3);
              Console.WriteLine("Payorder after initial insert");
              foreach (int i in mySortedSet)
              {
                  Console.WriteLine(i);
              }
              mySortedSet.Add(2);
              Console.WriteLine("Payorder after subsequent insert");
              foreach (int i in mySortedSet)
              {
                  Console.WriteLine(i);
              }
          }
      }
  }

We see how we no longer have to keep track of when we make edits to the data, the SortedSet class infrastructure will keep track and sort the data.

Ensures Uniqueness

One of the facets of the SortedSet class is that it will ignore values added that are duplicates of existing values.

  // Listing 3
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  
  namespace SortedSetAutoRemovalOfDuplicates
  {
      class Program
      {
          static void Main(string[] args)
          {
              SortedSet<int> mySortedSet = new SortedSet<int>();
              mySortedSet.Add(5);
              mySortedSet.Add(4);
              mySortedSet.Add(6);
              mySortedSet.Add(1);
              mySortedSet.Add(10);
              mySortedSet.Add(3);
              Console.WriteLine("Payorder after initial insert");
              foreach (int i in mySortedSet)
              {
                  Console.WriteLine(i);
              }
              // Let us add a value already in the set
              Console.WriteLine("Let us add a value which already exists in the set. The SortedSet class will ignore this add operation.");
              mySortedSet.Add(5);
              Console.WriteLine("Payorder after subsequent insert");
              foreach (int i in mySortedSet)
              {
                  Console.WriteLine(i);
              }
          }
      }
  }

To ensure that the add operation succeeds, one should check the return value of the Add operation. If the return value is true, the item was added, else it was rejected.

To get the maximum and minimum values of the set, we can use the Max and Min properties to get the value.

Summary

In this article, we saw the new SortedSet class and how it helps to keep your data sorted. Hopefully this article will help you use the new class in your upcoming projects and application.

Related Articles



About the Author

Vipul Vipul Patel

Vipul Patel is a Software Engineer currently working at Microsoft Corporation, working in the Office Communications Group and has worked in the .NET team earlier in the Base Class libraries and the Debugging and Profiling team. He can be reached at vipul_d_patel@hotmail.com

Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Managing your company's financials is the backbone of your business and is vital to the long-term health and viability of your company. To continue applying the necessary financial rigor to support rapid growth, the accounting department needs the right tools to most efficiently do their job. Read this white paper to understand the 10 essentials of a complete financial management system and how the right solution can help you keep up with the rapidly changing business world.

  • With 81% of employees using their phones at work, companies have stopped asking: "Is corporate data leaking from personal devices?" and started asking: "How do we effectively prevent corporate data from leaking from personal devices?" The answer has not been simple. ZixOne raises the bar on BYOD security by not allowing email data to reside on the device. In addition, Zix allows employees to maintain complete control of their personal device, therefore satisfying privacy demands of valued employees and the …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds