SortedDictionary Implementation in C#
The SortedDictionary class in C# is a collection type that represents a collection of key-value pairs. It is identical to the Dictionary class but differs significantly because SortedDictionary keeps the elements ordered according to the keys. The SortedDictionary objective is to offer an effective method for storing and retrieving key-value pairs while keeping a sorted order. It is frequently used when the order of the components matters, such as when you need to quickly discover elements based on their keys or iterate over the items in a particular order.
The functionality of SortedDictionary includes the capacity to insert, delete, and retrieve elements under their keys. Additionally, it enables many operations, like looking for a certain key or value, verifying the existence of a key, and iterating through the items in sorted order. Internally, SortedDictionary uses a binary search tree data structure to preserve the keys' sorted order. This makes insertion, deletion, and lookup operations efficient. The SortedDictionary's keys, which determine the elements' order, must be distinct from other keys. The keys are automatically sorted in ascending order when adding elements to a SortedDictionary.
Here is the syntax for creating a SortedDictionary
SortedDictionary<TKey, TValue> sortedDictionary = new SortedDictionary<TKey, TValue>();
The syntax has:
- SortedDictionary is the name of the class.
- <TKey, TValue> represents the generic type parameters for the key and value types. It would be best to replace TKey with the desired key type and TValue with the desired value type.
- sortedDictionary is the variable's name that will hold the instance of the SortedDictionary.
- new SortedDictionary<TKey, TValue>() is the constructor call to create a new instance of the SortedDictionary.
Here's the C# implementation of a SortedDictionary that demonstrates creating an instance, adding and removing elements, accessing and modifying elements, and iterating over the dictionary:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Creating an instance of SortedDictionary
SortedDictionary<string, int> scores = new SortedDictionary<string, int>();
// Adding elements to the SortedDictionary
scores.Add("Vardhan", 90);
scores.Add("Vikram", 85);
scores.Add("Sai Reddy", 95);
// Removing an element from the SortedDictionary
scores.Remove("Vikram");
// Accessing and modifying elements in the SortedDictionary
int aliceScore = scores["Sai Reddy"];
scores["Vardhan"] = 100;
// Iterating over the SortedDictionary
foreach (KeyValuePair<string, int> pair in scores)
{
Console.WriteLine(pair.Key + ": " + pair.Value);
}
}
}
Output:
In this example, a SortedDictionary object with string keys and int values is created. The Add method is used to add elements to the SortedDictionary. Using the Remove technique, we eliminate an element. Using the indexer [], we can access an element by its key and change it by giving it a new value. Finally, we use a foreach loop to go over the SortedDictionary and print the key-value pairs.
Sorting Behavior in SortedDictionary
Here is an illustration of how a SortedDictionary sorts and orders its entries.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Default sorting based on keys
SortedDictionary<int, string> defaultSortedDict = new SortedDictionary<int, string>();
defaultSortedDict.Add(3, "C");
defaultSortedDict.Add(1, "A");
defaultSortedDict.Add(2, "B");
Console.WriteLine("Default SortedDictionary:");
foreach (var pair in defaultSortedDict)
{
Console.WriteLine(pair.Key + ": " + pair.Value);
}
Console.WriteLine();
// Custom sorting using Comparer or IComparer interface
SortedDictionary<int, string> customSortedDict = new SortedDictionary<int, string>(new DescendingComparer());
customSortedDict.Add(3, "C");
customSortedDict.Add(1, "A");
customSortedDict.Add(2, "B");
Console.WriteLine("Custom SortedDictionary:");
foreach (var pair in customSortedDict)
{
Console.WriteLine(pair.Key + ": " + pair.Value);
}
}
}
// Custom comparer for sorting in descending order
class DescendingComparer : IComparer<int>
{
public int Compare(int x, int y)
{
return y.CompareTo(x);
}
}
Output:
In this example, we first use the default constructor to create a SortedDictionary with int keys and string values. The elements are automatically sorted by the SortedDictionary according to their keys, ascending. We print each element after adding them with various keys.
The elements are then arranged in descending order using the keys in a new SortedDictionary made using a custom comparer called DescendingComparer. After adding them, we print them.
The sorting behaviour and order of the elements depending on the keys can be customised by passing a special comparer to the SortedDictionary constructor.
How to use different types of keys and values in SortedDictionary?
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// SortedDictionary with different types of keys and values
SortedDictionary<string, int> dictionary = new SortedDictionary<string, int>();
dictionary.Add("Mango", 10);
dictionary.Add("Black Grapes", 5);
dictionary.Add("Apples", 3);
Console.WriteLine("SortedDictionary with different types for keys and values:");
foreach (var pair in dictionary)
{
Console.WriteLine(pair.Key + ": " + pair.Value);
}
}
}
In this example, a SortedDictionary with string keys and int values is created. We add elements with keys that are strings that represent fruits and values that are integers that reflect the weights of the fruits. The key-value pairs are then printed after iterating over the dictionary. The output will be:
Choosing proper key types that facilitate comparison and sorting is crucial when using different types for keys and values. In this example, we employ naturally sortable keys: strings. The default ordering for value types, such as integers, is determined by their natural numeric order.
Both reference types and value types can be handled by the SortedDictionary class. Key-value pairs for value kinds are directly stored in the SortedDictionary. The SortedDictionary contains references to the items for reference types. It's important to remember that the SortedDictionary could not be aware of the change in ordering when adjusting reference types, such as changing the characteristics of an object used as a key. To preserve correct sorting and behaviour, it is suggested that you refrain from making changes to key objects after they have been added to the SortedDictionary.
Time Complexity
Add method: O(log n) average case, where n is the number of elements in the dictionary.
Remove method: O(log n) average case.
Searching for an element using the ContainsKey method: O(log n) average case.
Accessing an element using the indexer: O(log n) average case.
The SortedDictionary uses additional memory to preserve the order of the elements. Memory stores each entry in the SortedDictionary, including memory for the key, the value, and the underlying binary search tree structure. Comparing SortedDictionary to a standard Dictionary, the memory use is typically larger.