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

  • When individual departments procure cloud service for their own use, they usually don't consider the hazardous organization-wide implications. Read this paper to learn best practices for setting up an internal, IT-based cloud brokerage function that service the entire organization. Find out how this approach enables you to retain top-down visibility and control of network security and manage the impact of cloud traffic on your WAN.

  • U.S. companies are desperately trying to recruit and hire skilled software engineers and developers, but there is simply not enough quality talent to go around. Tiempo Development is a nearshore software development company. Our headquarters are in AZ, but we are a pioneer and leader in outsourcing to Mexico, based on our three software development centers there. We have a proven process and we are experts at providing our customers with powerful solutions. We transform ideas into reality.

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date