Где я могу узнать о различных типах списков.NET?

Question

Кто-нибудь знает хороший ресурс, чтобы кратко объяснить различные типы списков, доступных в C#, и когда их использование уместно?

Например, List, Hashtable, Словари и т. Д.

Я никогда не совсем уверен, когда я должен использовать что.

Answer 1

Это не все списки, хотя они все коллекции. Вот краткое резюме.

Неуниверсальные коллекции (API в терминах object , Типы значений в штучной упаковке.

Они в основном находятся в пространстве имен System.Collections:

• ArrayList: список элементов, поддерживаемых массивом. Быстрый случайный доступ для чтения / записи. Быстрое добавление в конец, если буфер не нуждается в изменении размера.
• Hashtable: Карта от ключа к значению. Ключи уникальны, значения не должны быть. Использует метод GetHashCode, чтобы получить почти O(1) доступ для чтения / записи (кроме неприятных случаев, когда все элементы имеют одинаковый хэш, или требуется перестроить хранилище резервных копий). Перебор пар ключ / значение дает непредсказуемый порядок. (Ну, по сути, непредсказуемо.)
• SortedList: Как и Hashtable, но записи всегда возвращаются в порядке сортировки по ключу. Хранится в виде списка пар ключ / значение.
• Стек: коллекция "первым пришел - первым вышел"
• Очередь: коллекция "первым пришел - первым вышел"
• Массив: фиксированный размер O(1) произвольного доступа; не универсальный, но также имеет строго типизированные формы

Родовые коллекции. (Строго типизированный API, не будет упаковывать типы значений (при условии подходящего T).

Это в основном в пространстве имен System.Collections.Generic:

• List ;: лайк ArrayList
• Словарь ;: как Hashtable
• SortedList ;: как SortedList
• SortedDictionary ;: аналогично SortedList, но хранится в виде дерева пар ключ / значение, что обеспечивает лучшую производительность во многих ситуациях. Смотрите документы для более подробной информации.
• LinkedList ;: двусвязный список (быстрый доступ к голове и хвосту)
• Стек ;: как стек
• Очередь ;: Like Queue
• ReadOnlyCollection ;: похож на List , но дает представление только для чтения

Возможно, наиболее важным интерфейсом коллекции является IEnumerable (и IEnumerable ;). Это представляет последовательность элементов так же, как поток представляет последовательность байтов. Там нет произвольного доступа, просто чтение вперед. LINQ to Objects основан на этом, и почти все типы коллекций реализуют его.

Answer 2

Чтобы изложить более ранний ответ Тобсена, в C5 Generic Collection Library есть большое количество коллекций. Я опишу некоторые из них здесь:

Очередь / Stack

• CircularQueue<T>: Этот класс обеспечивает строго функциональность очереди и стека. Кроме того, эффективный O(1) доступ к любому элементу в стеке / очереди доступен с помощью индексатора: cq[0] (где 0 - самый старый элемент, следующий за ним должен быть снят, последний должен быть извлечен).

Списки

Замечания: ArrayList а также LinkedList может также функционировать как очередь / стеки

• ArrayList<T>: Аналогично своему аналогу в System.Collections.Generic (SCG), List<T>это поддерживается массивом, гарантирующим индексирование O(1), но вставкой O(n) в худшем случае.O(n), чтобы найти предмет.
• LinkedList<T>: Аналогично своему аналогу SCG.LinkedList<T>, Использование двусвязного списка гарантирует вставку O(1), но индексирование O(n) в худшем случае (на практике пропорционально расстоянию от начала или конца списка). Также O(n), чтобы найти предмет. Сортировка использует стабильную сортировку слиянием.
• HashedArrayList<T>: Аналогично ArrayList<T> выше, но не допускает дублирование. Выгода, которую вы получаете взамен, заключается в том, что время на поиск предмета и его индекса сокращается до O(1).
• HashedLinkedList<T>: Аналогично LinkedList<T> выше, но не допускает дублирование. Как и раньше, время для поиска элемента сокращается до O(1), но время для поиска его индекса остается O(n).
• WrappedArray<T>: Довольно похоже на ArrayList<T>, это действует как обертка вокруг массива, который реализует C5.IList<T>, но выдает исключения, если предпринята попытка изменить коллекцию (IsFixedSize это правда и Add, Remove, Insert не работать; Sort, Shuffle, а также Reverse делать, однако, так как они на месте операции).

Списки также предоставляют функциональность "Просмотр", которая представляет сегмент базового списка, позволяя выполнять локальные операции. Используя шаблоны, предложенные в книге C5, операции могут выполняться с использованием представлений, которые эффективны как для массива, так и для связанных списков. Любая операция со списком также может быть выполнена в представлении, ограничивая их влияние подмножеством базового списка.

Сортированные Коллекции

• SortedArray<T>: Похоже на ArrayList<T> за исключением того, что он сохраняет свои элементы отсортированными и не допускает дублирования. Обратите внимание, что случайные вставки и удаления в этой коллекции происходят медленно. Эта коллекция лучше всего подходит, если число элементов мало или редко изменяется, но к ним часто обращаются по индексу или значению элемента.
• TreeSet<T>: Используется красно-черная древовидная структура для сортировки элементов. Как набор, это не позволяет дублировать. Доступ по индексу или значению элемента и вставке / удалению занимает O(log n).
• TreeBag<T>: Использует красно-черное дерево, сохраняя элементы отсортированными. Как мешок, он допускает дубликаты, но не хранит дубликаты в дереве, а сохраняет их путем подсчета.

И то и другое TreeSet<T> а также TreeBag<T> предоставить возможность эффективно делать "снимки" или постоянные копии дерева в O(1), позволяя выполнять итерацию по снимку при изменении базового дерева. Обратите внимание, что каждый снимок дерева добавляет снижение производительности для обновлений дерева, но эти эффекты исчезают при удалении снимка.

Хэш Коллекции

• HashSet<T>: Коллекция, использующая простую хеш-таблицу для хранения. Доступ по значению элемента занимает O(1). Как набор, это не позволяет дублировать. Обеспечивает функцию BucketCostDistribution() это может помочь вам определить эффективность функции хеширования элементов.
• HashBag<T>: Аналогично HashSet<T>, но имеет семантику мешка, что означает, что дубликаты разрешены, но дубликаты сохраняются только путем подсчета.

Очередь приоритетов

• IntervalHeap<T>: Обеспечивает приоритетную очередь. Нахождение максимума и минимума - это O(1) операций, удаление максимума, минимума, добавление и обновление - это O(log n) операций. Позволяет дубликаты, сохраняя их явно (не считая).

Словари

• HashDictionary<H,K>: Аналогично SCG.Dictionary<H,K>, обеспечивает доступ к записи, вставку и удаление в O(1). Также обеспечивает BucketCostDistribution() функционировать как HashSet<T> выше. Не гарантирует какой-либо конкретный порядок перечисления.
• TreeDictionary<H,K>: Аналогично SCG.SortedDictionary<H,K>, обеспечивает постоянно отсортированный словарь с использованием красно-черного дерева. Доступ к записи, вставка и удаление занимает O(log n). Гарантирует, что нумерация словаря соответствует порядку, указанному ключевым компаратором.

Охраняемые коллекции

Кроме того, C5 также предлагает "защищенные" коллекции, которые эффективно действуют как оболочка только для чтения, предотвращая изменение коллекции. Элементы в коллекции все еще могут быть изменены, но элементы не могут быть добавлены, удалены или вставлены в коллекцию.

Длинный ответ, но подробно о библиотеках C5 и различных коллекциях в вашем распоряжении. Я обнаружил, что библиотека C5 великолепна и часто использую ее в своем собственном коде, заменяя общий заголовок C# на:

using C5;
using SCG = System.Collections.Generic;

Answer 3

Вы должны взять книгу об основных структурах данных. Это одна и та же теория, независимо от языка.

Краткое объяснение:

• Array: (как например int[] myArray) - статический массив, который можно использовать, когда коллекция никогда не изменяется (вы не можете добавлять или удалять элементы в ней, но вы можете изменять значения отдельных элементов)
• ArrayList: массив / список общего назначения, который позволяет относительно быстрое перечисление, а также прямой доступ. Этот список может увеличиваться автоматически при добавлении элементов, но так как он хранит только ObjectВы должны редко использовать его из-за проблем с производительностью и безопасностью типов.
• List<T>: Универсальная версия вышеуказанного ArrayList. Он обеспечивает хороший баланс между производительностью и гибкостью и должен использоваться почти всегда, когда у вас есть динамический плоский список элементов. (Новое в.NET 2.0)
• Hashtable: Работает как плоский список, но вместо того, чтобы индексировать его целыми числами, он может быть проиндексирован с использованием любого объекта. Стоит отметить, что в хеш-таблице нет "порядка".
• Dictionary<T>: Универсальная версия Hashtable. Используйте это в.NET 2.0 и выше вместо Hashtable по тем же причинам, что и ArrayList против List выше.
• Stack<T>: Предоставляет список типа "первым пришел - последним вышел". Предмет, который вы добавили последним, будет тем, который вы получите первым, когда что-то выберете.
• Queue<T>: Предоставляет список "первым пришел - первым вышел". Думайте об этом как о трубе, где вы вставляете предметы на одном конце и выбираете их на другом конце. Обычно используется для передачи сообщений между потоками.

В общем, вы должны использовать универсальные коллекции почти для всего, что вы делаете в.NET 2.0 и выше. Вы получите полную безопасность типов (по сравнению, например, с ArrayList и HashTable), и они намного быстрее для типов значений (целые числа, структуры, числа с плавающей точкой и т. Д.) По сравнению с неуниверсальными единицами.

Если у вас есть список элементов, которые никогда не изменятся, или вам не нужна гибкость List<T> Вы, конечно, можете использовать массив, так как он имеет наименьшее количество служебных данных.

При возврате коллекции из открытого метода или свойства рекомендуется преобразовать ее в менее гибкий интерфейс. Так что если у вас есть список, который вы возвращаете, вы можете привести его к IEnumerable<int> это означает, что ваш потребитель не может добавлять элементы к нему (если, конечно, он не отбрасывает его назад, но это все еще указание для пользователей). Приведение его также даст вам возможность позже изменить базовую структуру данных, сохраняя стабильность API. Вы также можете выбрать ICollection<int> или же IList<int> чтобы раскрыть немного больше функциональности, но сохраняя фактическую структуру данных скрытой.

Answer 4

Хеш-карты

• толковый словарь
• Hashtable (не универсальный)

Это структура данных, которая позволяет вам хранить пары ключ-значение. Имея ключ, который можно упорядочить, вы можете вставить значение. Простым примером может быть список студентов, где ключ - это идентификатор студента, а значение - имя студента.

Списки произвольного доступа

• Список
• ArrayList (не универсальный)

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

Связанные списки и тому подобное

• LinkedList
• Очередь
• стек

Связанные списки хороши, если вы не хотите получать доступ к элементам посередине, так как это займет O(N) время. Замечательно, если вы хотите вставить / удалить элементы посередине, поскольку это требует только изменения нескольких указателей.

Очереди и стеки являются слегка специализированными, так как они оптимизированы для поведения FIFO и FILO ("первым пришел-первым вышел" и "первым пришел-первым вышел" соответственно).

Answer 5

Список можно сортировать, но не рекомендуется публиковать.

Коллекция является базовой, без излишеств.

Словарь - это набор пар ключ-значение (во многом как старая хеш-таблица, но теперь общая).

KeyedCollection - это словарь, в котором ключ можно определить по значению (это абстракция, поэтому вы должны наследовать его и поддерживать функцию GetKey).

ReadOnlyCollection - это специальная коллекция, содержимое которой не может быть изменено.

ArrayList и HashTable в основном устарели, начиная с.NET 2.0.

Answer 6

Если вы начнете с документа MSDN для System.Collections, вы можете перейти к отдельным типам коллекций, чтобы получить более подробную информацию об этих "списках" и о том, как их использовать. Например, документ для Hashtable говорит: "Представляет коллекцию пар ключ / значение, которые организованы на основе хэш-кода ключа".

Есть также хорошее обсуждение System.Collections.Generic в Понимании Общих понятий.

Answer 7

В дополнение к замечательным ответам на данный момент, есть еще несколько коллекций, доступных через C5 Generic Collection Library. Документация (также на их сайте) может помочь при принятии решения о том, что использовать в зависимости от ваших требований.

Answer 8

В MSDN есть статья " Выбор класса коллекции", которую я считаю очень полезной, когда пытаюсь выяснить, какую коллекцию использовать в данной ситуации.

Answer 9

Это примеры различных типов общих структур данных. Эти структуры данных используются повсеместно в разработке программного обеспечения.

Answer 10

Intellisense покажет вам краткое описание каждого, если вы просто наберете System.collections.Generic. в окно кода. Не забывайте завершающий период. О, и есть также System.Collections.ObjectModel., Оттуда вы сможете получить больше информации обо всем, что выглядит многообещающим из MSDN.