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

  • On-demand Event Event Date: September 10, 2014 Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild." This loop of continuous delivery and continuous feedback is how the best mobile …

  • Information is data with context. The era of Big Data has begun demonstrating to information security that there is more that can, and must, be done to identify threats, reduce risk, address fraud, and improve compliance monitoring activities by bringing better context to data and thereby creating information for actionable intelligence. This analyst report sets the stage and provides insights into IT and information security practitioners' perceptions of the impediments to, and the solutions necessary for, …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds