Чтобы пояснить более ранний ответ Тобсена, в 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 имеет значение true и 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;