SortedList and KeyedCollection

Learn custom-indexed collections with SortedList and KeyedCollection.

SortedList<K,V>

A SortedList<K,V> is an array-based collection that keeps keys sorted. Like SortedDictionary<K,V> it iterates in order, but it uses two sorted arrays instead of a tree.

For small collections with sparse access SortedList uses less memory. Insertion is O(n) because it shifts the array. With frequent inserts SortedDictionary is the better fit.

KeyedCollection<K,T>

A KeyedCollection<K,T> is a dictionary whose key is extracted from a field of the item. Each item carries its own key; you do not supply a separate key value. You override GetKeyForItem to extract the key.

Example: a Person class has an Id property as key. You derive KeyedCollection<int, Person> and write GetKeyForItem(person) => person.Id. The expression people[5] returns the person whose Id is 5.

Exercise Print sorted keys with SortedList

The prices below is a SortedList<string, int>. Use foreach to print each key in sorted order with Console.WriteLine.

Show example solution

Iterate with foreach over a kvp variable, print kvp.Key each step.
Example solution:
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var prices = new SortedList<string, int>();
        prices.Add("cherry", 2);
        prices.Add("apple", 5);
        prices.Add("pear", 3);
        foreach (var kvp in prices)
        {
            Console.WriteLine(kvp.Key);
        }
    }
}

Test yourself

Match the collection to its backing

Dictionary<K,V>

Hash table
SortedDictionary<K,V>

Tree-based
SortedList<K,V>

Array-based
When is SortedList advantageous?
- Few items, sparse access
- Frequent insertion
- Unordered iteration
- Infinite sequences
Show answer

Few items, sparse access — Correct. SortedList uses less memory for few items.

Derive KeyedCollection

class People : KeyedCollection<____, Person>

Show answer

class People : KeyedCollection<int, Person>

Next lesson: Summary - Advanced collections

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies