TL;DR

  • Use SortedList for small, stable datasets needing indexed and sorted access.
  • Use SortedDictionary for larger or frequently updated sorted collections.
  • Use Lookup for grouping data with multiple values per key and safe, read-only access.
  • SortedList offers indexed access; SortedDictionary is faster for updates; Lookup is immutable and ideal for LINQ groupings.
  • Choose the collection based on dataset size, update frequency, and whether you need grouping or indexed access.

Choosing the right collection can make the difference between smooth performance and a sluggish application. While most C# developers reach for Dictionary<TKey, TValue> by default, there are times when you need sorted data or grouped results. That’s where SortedList, SortedDictionary, and LINQ’s Lookup come into play.

SortedList: Fast Lookups with Index Access

SortedList<TKey, TValue> keeps keys sorted and gives you indexed access like an array. It’s built on two arrays internally, making lookups fast but insertions potentially expensive:

var scores = new SortedList<string, int>
{
    ["Alice"] = 95,
    ["Bob"] = 87,
    ["Charlie"] = 92
};

// Access by key (fast)
Console.WriteLine(scores["Bob"]); // 87

// Access by index (unique to SortedList)
Console.WriteLine(scores.Keys[0]);   // Alice (alphabetically first)
Console.WriteLine(scores.Values[1]); // 92 (Charlie's score)

You’ll notice that SortedList maintains alphabetical order automatically. This is useful when you need both fast key lookups and the ability to iterate in sorted order or access elements by position.

SortedDictionary: Better for Frequent Updates

SortedDictionary<TKey, TValue> uses a red-black tree internally, making insertions and deletions faster than SortedList but without indexed access:

var inventory = new SortedDictionary<string, int>
{
    ["Apples"] = 50,
    ["Bananas"] = 30,
    ["Oranges"] = 25
};

// Frequent updates are more efficient here
inventory["Grapes"] = 40;     // O(log n) - faster than SortedList
inventory.Remove("Bananas");  // O(log n) - faster than SortedList

foreach (var (product, quantity) in inventory)
{
    Console.WriteLine($"{product}: {quantity}"); // Still sorted output
}

A quick gotcha here is that you can’t access elements by index like you can with SortedList. If you need inventory[0], you’ll have to use inventory.First().

Lookup: Immutable Grouping Results

LINQ’s Lookup<TKey, TElement> is different, it’s designed for grouping data and creates an immutable result. Think of it as a dictionary where each key can have multiple values:

var students = new[]
{
    new { Name = "Alice", Grade = "A" },
    new { Name = "Bob", Grade = "B" },
    new { Name = "Charlie", Grade = "A" },
    new { Name = "David", Grade = "B" }
};

// Group students by grade
var studentsByGrade = students.ToLookup(s => s.Grade, s => s.Name);

// Access all students with grade "A"
foreach (var name in studentsByGrade["A"])
{
    Console.WriteLine(name); // Alice, Charlie
}

// Check if a grade exists
if (studentsByGrade.Contains("C"))
{
    Console.WriteLine("Found grade C students");
} // Won't print - no grade C students

Unlike dictionaries, Lookup never throws when accessing a missing key, it returns an empty sequence instead.

Performance Comparison

CollectionSorted?Indexed Access?Grouping?Insert/RemoveBest For
SortedListYesYes ([0], [1])NoO(n)Small datasets, need indexing
SortedDictionaryYesNoNoO(log n)Frequent updates, larger datasets
LookupNo*NoYesImmutableGrouping operations, read-only

*Lookup preserves insertion order within each group

When to Use Which

Use CaseSortedListSortedDictionaryLookup
Best forSmall datasets (under 100 items), need indexed access, infrequent insert/deleteLarger datasets, frequent add/remove, sorted iteration without indexingGrouping data, multiple values per key, read-only results, safe missing key access
Indexed AccessYesNoNo
Key-based LookupYesYesYes
Insert/Delete SpeedSlow (O(n))Fast (O(log n))Immutable (no insert/delete after creation)
Sorted IterationYesYesNo (preserves insertion order within group)
Grouping SupportNoNoYes
Safe Missing Key AccessNo (throws exception)No (throws exception)Yes (returns empty sequence)
MutabilityMutableMutableImmutable

The rule of thumb: SortedList for small, stable datasets with indexing needs; SortedDictionary for larger, dynamic sorted collections; Lookup for grouping operations where you need multiple values per key.

FAQ

How do you choose between SortedList and SortedDictionary in C#?

SortedList uses arrays internally, provides indexed access, and is best for small datasets with infrequent updates. SortedDictionary uses a red-black tree, making insertions and deletions faster for larger or dynamic datasets, but does not support indexed access.

How does the performance of SortedList compare to SortedDictionary?

SortedList offers fast lookups and indexed access but slow insertions and deletions (O(n)). SortedDictionary provides O(log n) performance for inserts and deletes, making it better for frequent updates.

When is SortedList a better choice than SortedDictionary?

Use SortedList for small, stable datasets where you need both sorted keys and indexed access. Avoid it for large or frequently updated collections.

Can you access items by index in SortedDictionary?

No, SortedDictionary does not support indexed access. If you need to access elements by position, use SortedList or convert the dictionary to a list.

What is Lookup in C#, and when should you use it?

Use Lookup when you need to group data by key and allow multiple values per key. It is immutable and ideal for read-only grouping operations, such as the result of a LINQ ToLookup().

What makes Lookup different from Dictionary for key lookups?

Lookup returns an empty sequence when a key is missing, instead of throwing an exception like Dictionary. This makes it safer for grouping scenarios.

Is Lookup mutable or immutable in C#?

Lookup is immutable after creation. You cannot add or remove elements, making it suitable for read-only grouped data.

Which C# collection should you use for grouping operations?

Lookup is designed for grouping, allowing multiple values per key and safe access to missing keys. Use it for LINQ groupings and read-only scenarios.

Can Lookup replace Dictionary in your applications?

No, Lookup is for grouping and is immutable. Use Dictionary for key-value storage with updates, and Lookup for read-only grouped results.

How do you decide between SortedList, SortedDictionary, and Lookup for sorted or grouped data?

Choose SortedList for small datasets and infrequent updates; choose SortedDictionary for larger datasets or when you need efficient insertions and deletions.

Related Posts