.netのSortedDictionaryは、内部でSortedSetを使っています。
そこらへんについて、ソースコードを読んで考えたメモを書いておきます。
SortedDictionaryは内部に、SortedSet<KeyValuePair<TKey,TValue>>を持っています。
SortedDictionaryのComparerは、TKeyに対する比較用のclassで、IComparer<T>を実装。<T>はキーの値の型です。
SortedDictionaryの内部のSortedSetのComaprerは、KeyValuePair<TKey,TValue>を比較するComparerが必要なので、SortedDictionaryのComparerをそのまま使うことはできません。
そこで、SortedDictionaryが、KeyValuePair<TKey,TValue>から、TKeyを取り出して、SortedDictionaryのComparerで比較する、以下のオブジェクトを作ります。
public sealed class KeyValuePairComparer : Comparer<KeyValuePair<TKey, TValue>>
さて、ここから考察です。
これがどのように動くのかということなのですが、その前に、SortedSetを考えます。
特に速度面についてですが、SortedSetのComparerは結構頻繁に呼び出されますが、IComparer.Compare(T x, T y)の様に、インタフェース経由で呼び出すので、インライン化がかからずメソッド呼出のコストがかかります。
戻って、SortedDictionaryでは、Comparerも、さらに内部のKeyValuePairComparerも、IComparer経由で呼ぶので、このコストが2倍です。
しかも、比較の度に、KeyValuePairをわざわざ渡してKeyのみ取り出す処理をしているわけですから、その点も勿体ない。
したがって、最速を目指すのであれば、SortedSetにValueを追加したものを作るべきだと思われます。
また、そもそもの.netのSortedDictionaryは、パフォーマンスを考えると、内部でSortedSetを持ったクラスにするのではなく、SortedSetのコピーし拡張した様なクラスとして実装した方が良い様に思えました。