SortedDictionary Kept Sorting My Insertion Order Away

A config loader I wrote was reading feature-flag rollout steps out of a file, keyed by flag name, and the order those steps are declared in actually matters. They get applied top to bottom. So I reached for SortedDictionary<string, int> without really thinking about it, because some lazy corner of my brain had filed "sorted dictionary" under "the dictionary that keeps its order." It does keep an order. Just not mine.

The flags came back alphabetised. checkout-v2 was first in the file and showed up third in the output, sitting behind ai-suggest and beta-dashboard, two flags I hadn't touched in weeks. SortedDictionary sorts by key. That's the entire point of the type, and it's right there in the name once you stop misreading it. My insertion order was gone the moment I added the second entry.

Here's the setup. Five steps, in the order they live in the file:

var steps = new (string Name, int Percent)[]
{
    ("checkout-v2", 5),
    ("new-search", 50),
    ("dark-mode", 100),
    ("beta-dashboard", 25),
    ("ai-suggest", 10),
};

var sorted = new SortedDictionary<string, int>();
foreach (var (name, pct) in steps) sorted[name] = pct;

And what it printed:

SortedDictionary order:
  ai-suggest = 10
  beta-dashboard = 25
  checkout-v2 = 5
  dark-mode = 100
  new-search = 50

Alphabetical. Exactly what SortedDictionary promises, and exactly wrong for what I wanted.

The one that actually remembers

For years the only built-in that kept insertion order was System.Collections.Specialized.OrderedDictionary, the non-generic one from back in 2005 that stores everything as object. It works. But every int you put in gets boxed, and you cast your way back out again. .NET 9 finally shipped a generic version, System.Collections.Generic.OrderedDictionary<TKey, TValue>, and it's the thing I should have grabbed in the first place.

var ordered = new OrderedDictionary<string, int>();
foreach (var (name, pct) in steps) ordered[name] = pct;

OrderedDictionary<string,int> order:
  checkout-v2 = 5
  new-search = 50
  dark-mode = 100
  beta-dashboard = 25
  ai-suggest = 10

Declaration order, untouched. It's still a dictionary, so you get O(1) lookup by key like always, and it happens to remember the sequence you added things in. Because it tracks that sequence, you also get index access on top of the key access:

ordered.GetAt(0).Key;         // "checkout-v2", the first step
ordered.IndexOf("dark-mode"); // 2

GetAt, SetAt, RemoveAt, IndexOf, Insert. The list-shaped API sits right next to the dictionary one. I've hand-rolled the "Dictionary<,> plus a List<string> of keys to remember order" dance more than once, and this deletes all of it.

What the boxing was costing

I got curious about what the old Specialized one had been charging people all these years, so I measured instead of guessing. A hundred thousand string -> int entries, built and then read straight back, with the keys generated up front so their string allocations stay off the scorecard. Best of five runs, GC.GetAllocatedBytesForCurrentThread() wrapped around each build, and a checksum on the way out so nothing gets optimised away. This is a cloud container on workstation GC, not a lab bench, so I care about the ratio and not the raw milliseconds.

Legacy OrderedDictionary (boxes)     10,154,696 bytes   checksum 4999950000
OrderedDictionary<string,int>         3,041,792 bytes   checksum 4999950000

Same answer, a third of the memory. The old one boxes a hundred thousand ints into a hundred thousand tiny heap objects. The generic one stores them inline and never allocates a single box. The figure came back byte-for-byte identical on every run, which is the one nice thing about counting allocations: it doesn't drift the way a stopwatch does.

So if you're still typing Specialized.OrderedDictionary out of muscle memory, the generic drop-in is nicer to use and cheaper. That's about as close to a free upgrade as these things ever get.

Where it isn't a free lunch

One honest caveat, because OrderedDictionary<,> is not just "Dictionary<,> but better at everything." To keep its order, it stores entries in an array underneath. Inserting or removing anywhere other than the end shifts everything after it, which is O(n) work that a plain Dictionary would never do. RemoveAt(0) on a big one moves every remaining entry down a slot. If your access pattern is a lot of churn in the middle of the collection, that cost is real, and you'll want to feel it coming before you reach for this type.

My rule of thumb: use it when the order is part of the data. Config, column definitions, a pipeline of steps, anything you're going to hand back to someone who expects it the way they wrote it. For a hot lookup table where the order means nothing, plain Dictionary<,> is still the right call. The mistake was never picking SortedDictionary. It was picking it for a job the type never claimed it could do.

Here's the full runnable sample if you want to poke at the numbers yourself. It's a console app on net10.0. Drop it in a folder and dotnet run -c Release:

using System.Collections.Generic;
using LegacyOrderedDictionary = System.Collections.Specialized.OrderedDictionary;

var steps = new (string Name, int Percent)[]
{
    ("checkout-v2", 5),
    ("new-search", 50),
    ("dark-mode", 100),
    ("beta-dashboard", 25),
    ("ai-suggest", 10),
};

Console.WriteLine("== Does it keep insertion order? ==\n");

var sorted = new SortedDictionary<string, int>();
foreach (var (name, pct) in steps) sorted[name] = pct;

Console.WriteLine("SortedDictionary order:");
foreach (var kv in sorted) Console.WriteLine($"  {kv.Key} = {kv.Value}");

var ordered = new OrderedDictionary<string, int>();
foreach (var (name, pct) in steps) ordered[name] = pct;

Console.WriteLine("\nOrderedDictionary<string,int> order:");
foreach (var kv in ordered) Console.WriteLine($"  {kv.Key} = {kv.Value}");

Console.WriteLine($"\nFirst declared step via GetAt(0): {ordered.GetAt(0).Key}");
Console.WriteLine($"Index of 'dark-mode': {ordered.IndexOf("dark-mode")}");

Console.WriteLine("\n== Building 100,000 ordered entries (string -> int) ==\n");

const int N = 100_000;
var keys = new string[N];
for (int i = 0; i < N; i++) keys[i] = $"flag-{i}";

long legacyBytes = Measure(() =>
{
    var d = new LegacyOrderedDictionary(N);
    for (int i = 0; i < N; i++) d.Add(keys[i], i);       // int boxed on the way in
    long sum = 0;
    for (int i = 0; i < N; i++) sum += (int)d[keys[i]]!;  // unboxed on the way out
    return sum;
}, out long legacyChecksum);

long genericBytes = Measure(() =>
{
    var d = new OrderedDictionary<string, int>(N);
    for (int i = 0; i < N; i++) d.Add(keys[i], i);       // no boxing
    long sum = 0;
    for (int i = 0; i < N; i++) sum += d[keys[i]];
    return sum;
}, out long genericChecksum);

Console.WriteLine($"Legacy OrderedDictionary (boxes)   {legacyBytes,12:n0} bytes   checksum {legacyChecksum}");
Console.WriteLine($"OrderedDictionary<string,int>      {genericBytes,12:n0} bytes   checksum {genericChecksum}");
Console.WriteLine($"\nRatio: {(double)legacyBytes / genericBytes:0.0}x");

static long Measure(Func<long> build, out long checksum)
{
    checksum = 0;
    long best = long.MaxValue;
    for (int run = 0; run < 5; run++)
    {
        GC.Collect();
        GC.WaitForPendingFinalizers();
        GC.Collect();
        long before = GC.GetAllocatedBytesForCurrentThread();
        checksum = build();
        long after = GC.GetAllocatedBytesForCurrentThread();
        best = Math.Min(best, after - before);
    }
    return best;
}

Anyone else been hauling the Dictionary plus List<string> ordering hack around out of pure habit? I'm curious how many quiet little corners this new type replaces.

— still benchmarking things nobody asked me to measure