1. При итерации по элементам в любом из двух элементы будут отсортированы. Не так с Dictionary<T,V>.

2. MSDN устраняет разницу между SortedList<T,V> и SortedDictionary<T,V>:

Универсальный класс SortedDictionary (TKey, TValue) представляет собой двоичное дерево поиска с извлечением O (log n). , где n - количество элементов в словаре. В этом отношении он похож на универсальный класс SortedList (TKey, TValue). Эти два класса имеют похожие объектные модели, и оба имеют извлечение O (log n). Разница между этими двумя классами заключается в использовании памяти и скорости вставки и удаления:

SortedList (TKey, TValue) использует меньше памяти, чем SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) имеет более быстрые операции вставки и удаления для несортированных данных: O (log n) в отличие от O (n) для SortedList (TKey, TValue).

Если список заполняется сразу из отсортированных данных, SortedList (TKey, TValue) работает быстрее, чем SortedDictionary (TKey, TValue).

Отмечу разницу между словарями.

На рисунке выше показано, что Dictionary<K,V> в каждом случае равно или быстрее, чем аналог Sorted, но если требуется порядок элементов, например для их печати выбирается Sorted один.

Источник: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html.

Чтобы обобщить результаты Тест производительности - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable, результаты от лучшего к худшему для разных сценариев:

Использование памяти:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Вставки:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Поисковые операции:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

операции цикла foreach

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

Я вижу, что предлагаемые ответы сосредоточены на производительности. В статье, представленной ниже, нет ничего нового в отношении производительности, но в ней объясняются лежащие в основе механизмы. Также обратите внимание, что он не фокусируется на трех Collection Типах, упомянутых в вопросе, но обращается ко всем Типам пространства имен System.Collections.Generic.

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Выписки:

Словарь ‹>

Словарь, вероятно, является наиболее часто используемым ассоциативным контейнерным классом. Словарь - это самый быстрый класс для ассоциативного поиска / вставки / удаления, поскольку он использует скрытую хеш-таблицу. Поскольку ключи хешируются, тип ключа должен правильно реализовывать GetHashCode () и Equals () соответственно, или вам следует предоставить внешний IEqualityComparer для словаря при построении. Время вставки / удаления / поиска элементов в словаре амортизируется постоянным временем - O (1) - что означает, что независимо от того, насколько велик словарь, время, необходимое для поиска чего-либо, остается относительно постоянным. Это очень желательно для высокоскоростного поиска. Единственным недостатком является то, что словарь, по своей природе использующий хеш-таблицу, неупорядочен, поэтому вы не можете легко перемещаться по элементам в Словаре по порядку.

SortedDictionary ‹>

SortedDictionary похож на Dictionary по использованию, но сильно отличается по реализации. SortedDictionary использует двоичное дерево под обложками для упорядочения элементов по ключу. Как следствие сортировки, используемый для ключа тип должен правильно реализовывать IComparable, чтобы ключи можно было правильно отсортировать. Сортированный словарь использует немного времени поиска для возможности поддерживать элементы в порядке, поэтому время вставки / удаления / поиска в отсортированном словаре является логарифмическим - O (log n). Вообще говоря, с помощью логарифмического времени вы можете удвоить размер коллекции, и для поиска элемента требуется только одно дополнительное сравнение. Используйте SortedDictionary, если вам нужен быстрый поиск, но вы также хотите иметь возможность поддерживать коллекцию в порядке по ключу.

SortedList ‹>

SortedList - это еще один класс сортированных ассоциативных контейнеров в общих контейнерах. И снова SortedList, как и SortedDictionary, использует ключ для сортировки пар ключ-значение. Однако, в отличие от SortedDictionary, элементы в SortedList хранятся как отсортированный массив элементов. Это означает, что вставки и удаления являются линейными - O (n) - потому что удаление или добавление элемента может привести к перемещению всех элементов вверх или вниз в списке. Однако время поиска равно O (log n), потому что SortedList может использовать двоичный поиск, чтобы найти любой элемент в списке по его ключу. Так зачем тебе вообще это нужно? Что ж, ответ заключается в том, что если вы собираетесь загрузить SortedList заранее, вставки будут медленнее, но поскольку индексирование массива происходит быстрее, чем следование ссылкам на объекты, поиск выполняется немного быстрее, чем SortedDictionary. Еще раз я бы использовал это в ситуациях, когда вам нужен быстрый поиск и вы хотите поддерживать коллекцию в порядке по ключу, и где вставки и удаления редки.

Предварительное резюме основных процедур

Отзывы приветствуются, поскольку я уверен, что не все понял.

• Все массивы имеют размер n.
• Несортированный массив = .Add / .Remove равен O (1), но .Item (i) равен O (n).
• Сортированный массив = .Add / .Remove равен O (n), но .Item (i) равен O (log n).

Словарь

Память

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

Добавить

1. Добавить HashArray(n) = Key.GetHash # O (1)
2. Добавить KeyArray(n) = PointerToKey # O (1)
3. Добавить ItemArray(n) = PointerToItem # O (1)

Удалить

1. For i = 0 to n, найдите i где HashArray(i) = Key.GetHash # O (log n) (отсортированный массив)
2. Удалить HashArray(i) # O (n) (отсортированный массив)
3. Удалить KeyArray(i) # O (1)
4. Удалить ItemArray(i) # O (1)

Получить элемент

1. For i = 0 to n, найдите i где HashArray(i) = Key.GetHash # O (log n) (отсортированный массив)
2. Возврат ItemArray(i)

Цикл

1. For i = 0 to n, возврат ItemArray(i)

Сортированный словарь

Память

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

Добавить

1. Добавить KeyArray(n) = PointerToKey # O (1)
2. Добавить ItemArray(n) = PointerToItem # O (1)
3. For i = 0 to n, найдите i, где KeyArray(i-1) < Key < KeyArray(i) (используя ICompare) # O (n)
4. Добавить OrderArray(i) = n # O (n) (отсортированный массив)

Удалить

1. For i = 0 to n, найдите i, где KeyArray(i).GetHash = Key.GetHash # O (n)
2. Удалить KeyArray(SortArray(i)) # O (n)
3. Удалить ItemArray(SortArray(i)) # O (n)
4. Удалить OrderArray(i) # O (n) (отсортированный массив)

Получить элемент

1. For i = 0 to n, найдите i, где KeyArray(i).GetHash = Key.GetHash # O (n)
2. Возврат ItemArray(i)

Цикл

1. For i = 0 to n, возврат ItemArray(OrderArray(i))

SortedList

Память

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

Добавить

1. For i = 0 to n, найдите i, где KeyArray(i-1) < Key < KeyArray(i) (используя ICompare) # O (log n)
2. Добавить KeyArray(i) = PointerToKey # O (n)
3. Добавить ItemArray(i) = PointerToItem # O (n)

Удалить

1. For i = 0 to n, найдите i, где KeyArray(i).GetHash = Key.GetHash # O (log n)
2. Удалить KeyArray(i) # O (n)
3. Удалить ItemArray(i) # O (n)

Получить элемент

1. For i = 0 to n, найдите i, где KeyArray(i).GetHash = Key.GetHash # O (log n)
2. Возврат ItemArray(i)

Цикл

1. For i = 0 to n, возврат ItemArray(i)

1. Когда вы хотите, чтобы коллекция сортировалась по ключу при итерации по ней. Если вам не нужно сортировать данные, вам лучше использовать словарь, он будет работать лучше.

2. SortedList и SortedDictionary в значительной степени делают одно и то же, но реализованы по-разному, поэтому имеют разные сильные и слабые стороны объяснено здесь.

Пытаясь присвоить оценку производительности каждому случаю, представленному @Lev, я использовал следующие значения:

• O(1) = 3
• O (журнал п) = 2
• O(n) = 1
• O(1) or O(n) = 2
• O (log n) или O (n) = 1,5

Результаты (выше = лучше):

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

Конечно, в каждом сценарии использования определенным операциям будет уделяться больше внимания.