Как я понимаю, все эти коллекции являются реализацией ассоциативного массива. Но я не особо понимаю в чём между ними разница. Везде можно хранить пары ключ-значение в отсортированном виде, единственное что я понял что в их основе лежат разные структуры данных, но практические отличия мне не понятны
Во-первых, SortedSet - это не словарь, а множество. Этот тип не реализует IDictionary, а реализует ISet. С точки зрения api, можно составить, так сказать, пропорцию: SortedSet так же относится к SortedDictionary, как HashSet относится к Dictionary.
Зачем вообще SortedSet и SortedDictionary нужны? Они нужны если вам важен порядок перечисления элементов. В теории, с деревьями, которые там внутри, можно сделать много интересных вещей, но SortedSet и SortedDictionary этого делать не позволяют; так что если вам нужно именно дерево - в сторону Sorted-коллекций даже не смотрите.
Теперь SortedList. SortedList - это такая странная реализация IDictionary, которая неплохо работает на чтение (быстрее чем SortedDictionary, но всё ещё медленнее Dictionary), но крайне медленна при изменениях. В принципе, этого было бы достаточно чтобы вообще никогда её не использовать, но у неё есть одно достоинство: крайняя компактность по памяти. Там внутри массив ключей, массив значений и несколько служебных полей, всё!
Применений у SortedList два. Во-первых, если вам нужен словарь из малого числа элементов - SortedList прекрасно подойдёт. Во-вторых, если вам нужен компактный неизменяемый словарь - SortedList тоже сработает, только не забудьте упорядочить содержимое перед укладыванием в SortedList, и следить за неизменяемостью вам придётся тоже самому.
Чтобы понять, когда использовать SotedSet, SortedDictionary или SortedList, сначала рассмотрим, когда вообще нужны SortedX, а не обычный Dictionary.
Dicitonary даёт вставку за O(1), удаление за O(1), и взятие элемента по ключу, тоже за O(1). Что ещё нужно для счастья? Ну например вернуть ключи-значения отсортированными по ключу. Dictionary сам не умеет, поэтому во-первых придётся потратить дополнительную память, чтобы выполнить эту сортировку. И сама сортировка обойдётся в O(n*log(n)).
Так вот, SortedX сделают это за O(n) и почти без дополнительной памяти. Причём SortedList должен справится даже быстрее SortedDictionary(SortedSet), так как он основан на массиве, а с ними процессоры работают быстрее, чем с деревьями, на которых основан второй.
Но дело в том что за это преимущество вы возможно уже заплатили при вставке. Если вставлять не все элементы сразу в SortedX, а по одному, то суммарно вставки обойдутся:
O(n)O(n*log(n))O(n*n)Отсюда вывод по выбору:
Теперь что такое SortedDictionary<TKey, TValue>. Это такая обёртка над SortedSet<KeyValuePair<TKey, TValue>>, но многие возможности кастрированы. Благо, можно вернуть себе отрезанные возможности, достаточно просто использовать второй вместо первого и позаимствовать код KeyValuePairComparer из SortedDictionary. Суть компаратора проста - для сравнений используем дефолтный компаратор по типу ключа и сравниваем только ключи.
С чем ещё плохо справляется стандартный Dictionary? Он бесполезен при поиске по диапазону значений. Придётся сделать полный перебор O(n).
SortedDictinary тут бессилен только из-за интерфейса.
SortedList отлично подойдёт, если границы диапазона это ключи. O(log(n)) на найти границы, и O(m) на перебрать диапазон, где m - число вхождений в диапазоне. Если же границы, это не ключи, то можно уложиться в ту же сложность, но встроенных интерфейсов для этого нет.
SortedSet изначально имеет метод на получение подмножества по произвольному диапазону - GetViewBetween. SortedSet<KeyValuePair<TKey, TValue>> с компаратором тоже позволит пользоваться этой фичей. Сложность плюс-минус такая же, как у SortedList.
Ещё Dictionary не умеет выдавать максимальный-минимальны элемент без полного перебора O(n). SortedSet и SortedList смогут за O(1). SortedDictionary - мог бы, но спасибо разработчикам, они похоже хотели скрыть, что там дерево, и спрятали эти возможности так же.