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

  • With JRebel, developers get to see their code changes immediately, fine-tune their code with incremental changes, debug, explore and deploy their code with ease (both locally and remotely), and ultimately spend more time coding instead of waiting for the dreaded application redeploy to finish. Every time a developer tests a code change it takes minutes to build and deploy the application. JRebel keeps the app server running at all times, so testing is instantaneous and interactive.

  • Download the Information Governance Survey Benchmark Report to gain insights that can help you further establish business value in your Records and Information Management (RIM) program and across your entire organization. Discover how your peers in the industry are dealing with this evolving information lifecycle management environment and uncover key insights such as: 87% of organizations surveyed have a RIM program in place 8% measure compliance 64% cannot get employees to "let go" of information for …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds