C# SortedDictionary

Introduction

The SortedDictionary<TKey, TValue> is a specialized collection in C# that stores key-value pairs in a sorted order based on the keys. Unlike the regular Dictionary<TKey, TValue> which organizes elements for fast lookup without any guaranteed order, the SortedDictionary automatically maintains its elements sorted by key.

This collection is part of the System.Collections.Generic namespace and provides an efficient way to store data when you need both the benefits of key-value pair organization and ordered traversal.

Key Features of SortedDictionary

• Automatic Sorting: Elements are automatically kept in sorted order by key
• Unique Keys: Each key must be unique within the collection
• Fast Retrieval: Offers O(log n) lookup time for retrievals and insertions
• Key-Value Storage: Stores elements as key-value pairs
• Generic Implementation: Supports any data types for both keys and values

Creating a SortedDictionary

Let's start by creating a simple SortedDictionary:

csharp

// Import required namespace
using System.Collections.Generic;

// Create a SortedDictionary with string keys and int values
SortedDictionary<string, int> studentScores = new SortedDictionary<string, int>();

// Add elements
studentScores.Add("Alice", 95);
studentScores.Add("Charlie", 85);
studentScores.Add("Bob", 90);
studentScores.Add("David", 88);

// Displaying elements - notice they are automatically sorted by key
Console.WriteLine("Student Scores (alphabetically sorted):");
foreach (KeyValuePair<string, int> student in studentScores)
{
    Console.WriteLine($"{student.Key}: {student.Value}");
}

Output:

Student Scores (alphabetically sorted):
Alice: 95
Bob: 90
Charlie: 85
David: 88

Notice that although we added "Charlie" before "Bob", the output shows them in alphabetical order. This is because SortedDictionary automatically maintains its elements sorted by key.

Common Operations on SortedDictionary

Adding Elements

You can add elements using the Add() method or the indexer syntax:

csharp

SortedDictionary<int, string> colorCodes = new SortedDictionary<int, string>();

// Method 1: Using Add method
colorCodes.Add(3, "Green");
colorCodes.Add(1, "Red");

// Method 2: Using indexer syntax
colorCodes[2] = "Blue";
colorCodes[4] = "Yellow";

// Display elements
foreach (var color in colorCodes)
{
    Console.WriteLine($"Code {color.Key}: {color.Value}");
}

Output:

Code 1: Red
Code 2: Blue
Code 3: Green
Code 4: Yellow

Accessing Elements

You can access elements using their keys:

csharp

SortedDictionary<string, double> productPrices = new SortedDictionary<string, double>()
{
    { "Apple", 1.99 },
    { "Banana", 0.99 },
    { "Orange", 2.49 },
    { "Grape", 3.99 }
};

// Access an element by key
if (productPrices.TryGetValue("Apple", out double applePrice))
{
    Console.WriteLine($"Price of Apple: ${applePrice}");
}

// Using indexer (throws exception if key doesn't exist)
try
{
    double bananaPrice = productPrices["Banana"];
    Console.WriteLine($"Price of Banana: ${bananaPrice}");
    
    // This will throw KeyNotFoundException
    double pearPrice = productPrices["Pear"];
}
catch (KeyNotFoundException)
{
    Console.WriteLine("Pear is not in the product list!");
}

Output:

Price of Apple: $1.99
Price of Banana: $0.99
Pear is not in the product list!

Removing Elements

You can remove elements by their key:

csharp

SortedDictionary<int, string> employees = new SortedDictionary<int, string>()
{
    { 101, "John Doe" },
    { 105, "Jane Smith" },
    { 103, "Bob Johnson" },
    { 102, "Alice Brown" }
};

Console.WriteLine("Before removal:");
foreach (var emp in employees)
{
    Console.WriteLine($"ID: {emp.Key}, Name: {emp.Value}");
}

// Remove an element
employees.Remove(103);

Console.WriteLine("\nAfter removing employee with ID 103:");
foreach (var emp in employees)
{
    Console.WriteLine($"ID: {emp.Key}, Name: {emp.Value}");
}

Output:

Before removal:
ID: 101, Name: John Doe
ID: 102, Name: Alice Brown
ID: 103, Name: Bob Johnson
ID: 105, Name: Jane Smith

After removing employee with ID 103:
ID: 101, Name: John Doe
ID: 102, Name: Alice Brown
ID: 105, Name: Jane Smith

Checking for Elements

You can check if a specific key or value exists in the collection:

csharp

SortedDictionary<string, string> countryCapitals = new SortedDictionary<string, string>()
{
    { "USA", "Washington D.C." },
    { "UK", "London" },
    { "France", "Paris" },
    { "Japan", "Tokyo" }
};

// Check if a key exists
bool hasJapan = countryCapitals.ContainsKey("Japan");
Console.WriteLine($"Contains Japan as a key: {hasJapan}");

// Check if a value exists (slower operation)
bool hasBerlin = countryCapitals.ContainsValue("Berlin");
Console.WriteLine($"Contains Berlin as a value: {hasBerlin}");

Output:

Contains Japan as a key: True
Contains Berlin as a value: False

Custom Sorting with SortedDictionary

By default, SortedDictionary uses the default comparer for the key type. However, you can provide a custom comparer to change the sorting behavior:

csharp

// Custom comparer for string keys (case-insensitive, reverse alphabetical order)
class ReverseStringComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        // Use string.Compare with reversed arguments for reverse ordering
        // and ignoring case for case-insensitivity
        return string.Compare(y, x, StringComparison.OrdinalIgnoreCase);
    }
}

// Using the custom comparer
SortedDictionary<string, int> fruitInventory = new SortedDictionary<string, int>(new ReverseStringComparer());

fruitInventory.Add("apple", 150);
fruitInventory.Add("Banana", 75);
fruitInventory.Add("orange", 100);
fruitInventory.Add("Grape", 200);

Console.WriteLine("Fruit inventory (reverse alphabetical order, case-insensitive):");
foreach (var item in fruitInventory)
{
    Console.WriteLine($"{item.Key}: {item.Value} units");
}

Output:

Fruit inventory (reverse alphabetical order, case-insensitive):
orange: 100 units
Grape: 200 units
Banana: 75 units
apple: 150 units

SortedDictionary vs Dictionary vs SortedList

Let's compare these similar collections to understand when to use each:

Feature	SortedDictionary	Dictionary	SortedList
Sorting	Automatically sorted by keys	Unsorted	Automatically sorted by keys
Lookup Speed	O(log n)	O(1) average	O(log n)
Insert/Delete	O(log n)	O(1) average	O(n)
Memory Usage	Higher	Medium	Lower
Implementation	Self-balancing binary search tree	Hash table	Sorted array of key-value pairs

When to use SortedDictionary:

• When you need elements sorted by key
• When you need good performance for frequent insertions and deletions
• When you need to access both the smallest and largest keys regularly

Real-World Applications

Example 1: Word Frequency Counter with Alphabetical Output

csharp

string text = "This is a sample text. This text will be analyzed for word frequency. " +
              "The most frequent words will be displayed in alphabetical order.";

// Split the text into words and clean them
string[] words = text.ToLower()
                     .Replace(".", "")
                     .Replace(",", "")
                     .Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);

// Count word frequency
SortedDictionary<string, int> wordFrequency = new SortedDictionary<string, int>();

foreach (string word in words)
{
    if (wordFrequency.ContainsKey(word))
    {
        wordFrequency[word]++;
    }
    else
    {
        wordFrequency[word] = 1;
    }
}

// Display word frequency in alphabetical order
Console.WriteLine("Word frequency (alphabetically):");
foreach (var pair in wordFrequency)
{
    Console.WriteLine($"'{pair.Key}': {pair.Value} time(s)");
}

Output:

Word frequency (alphabetically):
'a': 1 time(s)
'analyzed': 1 time(s)
'be': 2 time(s)
'displayed': 1 time(s)
'for': 1 time(s)
'frequent': 1 time(s)
'in': 1 time(s)
'is': 1 time(s)
'most': 1 time(s)
'order': 1 time(s)
'sample': 1 time(s)
'text': 2 time(s)
'the': 1 time(s)
'this': 2 time(s)
'will': 2 time(s)
'words': 1 time(s)

Example 2: Task Scheduler by Priority

csharp

// Task class to represent a scheduled task
class Task
{
    public string Name { get; set; }
    public string Description { get; set; }
    
    public Task(string name, string description)
    {
        Name = name;
        Description = description;
    }
    
    public override string ToString()
    {
        return $"{Name}: {Description}";
    }
}

// Priority-based task scheduler using SortedDictionary
class TaskScheduler
{
    // Lower number = higher priority
    private SortedDictionary<int, List<Task>> _tasks = new SortedDictionary<int, List<Task>>();
    
    public void AddTask(int priority, Task task)
    {
        if (!_tasks.ContainsKey(priority))
        {
            _tasks[priority] = new List<Task>();
        }
        
        _tasks[priority].Add(task);
    }
    
    public void DisplayTasksByPriority()
    {
        Console.WriteLine("Tasks by priority (highest to lowest):");
        
        foreach (var priorityGroup in _tasks)
        {
            Console.WriteLine($"\nPriority {priorityGroup.Key}:");
            
            foreach (Task task in priorityGroup.Value)
            {
                Console.WriteLine($"  - {task}");
            }
        }
    }
}

// Using the task scheduler
TaskScheduler scheduler = new TaskScheduler();

scheduler.AddTask(1, new Task("Fix critical bug", "Fix authentication issue in login form"));
scheduler.AddTask(3, new Task("Update documentation", "Update README with new features"));
scheduler.AddTask(1, new Task("Fix security vulnerability", "Address XSS vulnerability in forms"));
scheduler.AddTask(2, new Task("Implement feature", "Add dark mode support"));
scheduler.AddTask(3, new Task("Code refactoring", "Refactor payment processing class"));

scheduler.DisplayTasksByPriority();

Output:

Tasks by priority (highest to lowest):

Priority 1:
  - Fix critical bug: Fix authentication issue in login form
  - Fix security vulnerability: Address XSS vulnerability in forms

Priority 2:
  - Implement feature: Add dark mode support

Priority 3:
  - Update documentation: Update README with new features
  - Code refactoring: Refactor payment processing class

Performance Considerations

• Insertion/Deletion: Better than SortedList for frequent insertions and removals
• Memory Usage: Uses more memory than SortedList but less than Dictionary for many entries
• Retrieval: O(log n) performance for lookups, slower than Dictionary's O(1) average
• Bulk Operations: For batch operations with pre-sorted data, SortedList may be more efficient

Summary

The SortedDictionary<TKey, TValue> in C# is a powerful collection that combines the features of a dictionary (key-value pairs) with automatic sorting by keys. It's particularly useful when you need to maintain sorted data while still having efficient lookup capabilities.

Key points to remember:

• Elements are always sorted by key
• Keys must be unique
• Performance is O(log n) for most operations
• Best used when frequent insertions and deletions are required
• Consumes more memory than some alternatives

Choose SortedDictionary when you need both a sorted view of your data and efficient modification operations, especially if you're dealing with a dynamic collection that changes frequently.

Exercises

1. Create a program that uses SortedDictionary to implement a student grade book, keeping students sorted alphabetically.

2. Implement a custom comparer for SortedDictionary that sorts integers in descending order, and use it to create a "Top Scores" leaderboard.

3. Create a program that reads a text file and counts the frequency of each word, then displays the top 10 most common words (hint: you'll need to use SortedDictionary and then sort by value).

4. Implement a simple phone book application using SortedDictionary that allows adding, removing, and looking up contacts.

5. Compare the performance of SortedDictionary vs. Dictionary vs. SortedList for a large dataset with various operations.

Additional Resources

• Microsoft Documentation on SortedDictionary<TKey,TValue>
• C# Collection Types - When to Use What
• Guidelines for Collection Usage