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>