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

  • Where the business performance of their mobile app portfolios are concerned, most companies are flying blind. While traditional application portfolios are held to all kinds of ROI measure, the investment plan for mobile apps -- increasingly the more crucial bet -- is made by guesswork and dart-throwing. This interactive e-book investigates how mobile is driving the need for app and portfolio measures unlike any we saw in the days of web. Good mobile analytics must deliver leading indicators of user experience …

  • Live Event Date: August 14, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT Data protection has long been considered "overhead" by many organizations in the past, many chalking it up to an insurance policy or an extended warranty you may never use. The realities of today make data protection a must-have, as we live in a data driven society. The digital assets we create, share, and collaborate with others on must be managed and protected for many purposes. Check out this upcoming eSeminar and join eVault Chief Technology …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds