В C# для хранения набора однотипных данных можно использовать массивы. Но с ними не всегда удобно работать потому, что они имеют фиксированный размер и часто бывает сложно угадать, какого размера нужен массив.
Для решения этих задач в C# есть коллекции. Они позволяют динамически изменять свой размер. Также они удобны тем что некоторые из них представляют из себя готовые реализации стандартных структур данных, таких как список, хеш таблица, стек, очередь.
Все коллекции лежат в нескольких пространствах имен:
- System.Collections — простые необобщенные коллекции.
- System.Collections.Generic — обобщенные коллекции.
- System.Collections.Specialized — специальные коллекции.
- System.Collections.Concurrent — коллекции для работы в многопоточной среде.
Устройство коллекций
Все коллекции, так или иначе, реализую интерфейс ICollection, некоторые реализуют интерфейсы IList и IDictionary (которые внутри наследуют ICollection). Этот интерфейс предоставляет минимальный набор методов, которые позволяют реализовать коллекцию.
В свою очередь, ICollection расширяет интерфейс IEnumerable. Он предоставляет нумератор, который позволяет обходить коллекции элемент за элементом. Именно этот интерфейс позволяет использовать коллекции в цикле foreach.
Вместительность коллекций
Одна из ключевых особенностей коллекций это изменяемый размер. Когда создается экземпляр коллекции она внутри себя инициализирует какую-то структуру данных, зачастую это массив. По умолчанию этот массив имеет определённую вместительность, которую можно просмотреть с помощью свойства Capacity.
После активного наполнения коллекции наступает момент, когда внутренний массив заполнен и мы не можем добавить новый элемент. В таком случае коллекция создаёт новый массив с большей вместительностью (обычно в два раза больше) и копирует туда данные со старого массива.
Поэтому коллекции, которые основаны на массивах имеют сложность вставки:
- O(1) — когда вместительности достаточно.
- O(n) — когда вместительности недостаточно и нужно копировать данные в массив побольше.
Чтобы избежать уменьшения производительности нужно при создании коллекции указать необходимую нам вместительности. Это позволит уменьшить количество копирований.
Сравнивание и сортировка элементов коллекций
Сравнение
Такие методы как Contains, IndexOf, LastIndexOf, and Remove используют сравнение элементов для свое работы. Если коллекция является обобщенной, то используются два механизма сравнения:
- Если тип реализует интерфейс IEquatable тогда механизм сравнения использует метод Equals этого интерфейса.
- Если тип не реализует интерфейс IEquatable тогда для сравнения используется Object.Equals
Некоторые коллекции имеют конструктор, который принимает имплементацию IEqualityComparer который используется для сравнения.
Сортировка
Сортировка работает похожим образом, как и сравнение, но делиться на два вида: явную сортировку и сортировка по умолчанию.
Сортировка по умолчанию подразумевает, что типы хранящиеся в коллекции реализуют интерфейс IComparable, чьи методы под капотом используют коллекции для сравнения.
Явная сортировка подразумевает, что наши элементы не реализуют интерфейс IComparable, поэтому в качестве параметра метода сортировки нужно передать объект, который реализует интерфейс IComparer.
Если тип не реализует интерфейс IComparable и мы не передали явно тип, который реализует IComparer, то при вызове метода сортировки вылетит исключение.
System.InvalidOperationException: Failed to compare two elements in the array.
System.ArgumentException: At least one object must implement IComparable.
Алгоритмическая сложность коллекций
Список List
Класс List представляет из себя простейший список однотипных элементов, которые можно получить по индексу. Предоставляет методы для поиска, сортировки и изменения списка.
var linkedList = new List<string>();
linkedList.Add("A");
linkedList.Add("B");
linkedList.Add("C");
Для своей работы списки используют обычные массивы. Это значит что могут быть проблемы с производительностью из-за частого создания нового массива. Также у списков есть еще два нюанса:
- Вставка элемента в середину списка приведет к созданию нового массива и копирование данных, что негативно влияет на производительность.
- Списки не могут хранить экстремально огромное количество элементов из-за фрагментации адресного пространства.
Если эти проблемы существенны для вас, то стоит присмотреться к LinkedList или ImmutableList
Связанный список LinkedList
Класс LinkedList реализует простой двухсвязный список, каждый элемент которого имеет ссылка на предыдущий и следующий элемент.
Каждый элемент списка оборачивается в специальный класс LinkedListNode, который имеет ссылку на следующий элемент (Next), на предыдущий элемент (Previous) и само значение (Value).
var linkedList = new LinkedList<string>();
linkedList.AddFirst("A");
linkedList.AddLast("B");
linkedList.AddLast("C");
Console.WriteLine(linkedList.First.Previous == null); // True
Console.WriteLine(linkedList.Last.Next == null); // True
Связанный список позволяет вставлять и удалять элементы со сложностью O (1). Также мы можем удалить элемент и заново вставить в тот же или другой список без дополнительного выделения памяти.
Словарь Dictionary
Словари хранят данные в виде ключ-значение. Каждый элемент словаря представляет из себя объект структуры KeyValuePair.
В качестве ключа можно использовать любой объект. Ключи должны быть уникальными в рамках коллекции.
var linkedList = new Dictionary<string, string>();
linkedList.Add("key1", "A");
linkedList.Add("key2", "B");
linkedList.Add("key3", "C");
Внутри словари построены на базе хеш-таблицы, что позволяет очень быстро вставлять элементы и получать по ключу (сложность O (1)). Сами же хеш-таблицы, в свою очередь, реализованы с помощью массивов.
Для адресации значений внутри коллекции используются хеш коды ключей. Это значит что объект ключа не должен изменяться, потому что это приведет к изменению хеш кода, что в свою очередь приведет к потере данных.
Исходники Dictionary
Стек Stack и Очередь Queue
Очереди и стеки полезны, когда нужно временно хранить какие-то элементы, то есть удалять элемент после его извлечения. Также они позволяют определить строгую очередность записи и извлечения элементов.
Стеки Stack — реализуют подход LIFO (last in — first out).
var stack = new Stack<int>();
stack.Push(1); // stack = [1]
stack.Push(2); // stack = [1,2]
var item = stack.Pop(); // stack = [1], item = 2
Очереди Queue — реализуют подход (first in — first out).
var queue = new Queue<int>();
queue.Enqueue(1); // queue = [1]
queue.Enqueue(2); // queue = [1,2]
item = queue.Dequeue(); // queue = [2], item = 1
Внутри они реализованы с помощью обычных массивов.
Множества HashSet и SortedSet
Эти классы реализуют математические множества. По своей природе множество — набор уникальных элементов с общими характеристиками, в нашем случае одного типа.
Также множества отличаются от обычных списков тем что они предоставляют набор методов, которые реализуют операции с теории множеств.
Внутренняя реализация этих классов отличается:
- HashSet — множество, построенное на базе хеш-таблицы.
- SortedSet — отсортированное множество, построенное на базе красно-черного дерева.
ISet<int> set = new HashSet<int> { 1, 2, 3, 4, 5 };
set.UnionWith(new[] { 5, 6 }); // set = { 1, 2, 3, 4, 5, 6 }
set.IntersectWith(new[] { 3, 4, 5, 6, 7 }); // set = { 3, 4, 5, 6 }
set.ExceptWith(new[] { 6, 7 }); // set = { 3, 4, 5 }
set.SymmetricExceptWith(new[] { 4, 5, 6 }); // set = { 3, 6 }
Можно заметить что LINQ предоставляет несколько похожих операций (Distinct, Union, Intersect, Except), которые можно выполнить с любой коллекцией. Но HastSet предоставляет намного больший набор операций с множествами.
Основная разница в том что методы множеств изменяют текущую коллекцию, в то время как LINQ методы всегда создают новый экземпляр коллекции.
KeyedCollection
KeyedCollection это абстрактный класс, который позволяет построить собственную коллекцию.
Эта коллекция является гибридом между списками (IList) и словарями (IDictionary). От списков ей досталась возможность получать элементы по индексу, а от словарей возможность получать элемент по ключу.
В отличие от словарей, элемент KeyedCollection коллекции не является парой ключ-значение, вместо этого весь элемент является значением, а в качестве ключа используется его поле, свойство или любое другое значение. Для получения ключа используется абстрактный метод, который является обязательным для реализации. GetKeyForItem
var keyedCollection = new UserCollection();
keyedCollection.Add(new User {
Id = 1,
Name = "A"
});
keyedCollection.Add(new User {
Id = 2,
Name = "B"
});
Console.WriteLine(keyedCollection[2].Name); // B
public class UserCollection: KeyedCollection<int, User>
{
protected override int GetKeyForItem(User user) => user.Id;
}
public class User
{
public int Id {get;set;}
public string Name {get;set;}
}
Внутри KeyedCollection построен на базе двух структур данных. Для быстрого получения данных по ключу используется словарь, а для получение элемента по индексу используется массив.
NameValueCollection
Представляет из себя коллекцию, которая похожа на словарь но в качестве ключей и значений используются строки. Элементы можно получить как по индексу так и по ключу.
Особенной эту коллекцию делает то что однин ключ может содержать несколько эллементов.
var namedCollection = new NameValueCollection();
namedCollection.Add("key1", "value1");
namedCollection.Add("key2", "value2");
namedCollection.Add("key1", "value3");
Console.WriteLine(namedCollection.Count); // 2
Console.WriteLine(namedCollection["key1"]); // value1,value3
Иммутабельные коллекции
Иммутабельные коллекции не входят в стандартную библиотеку классов (BCL). Для их использования нужно установить System.Collections.Immutable NuGet пакет.
Они позволяют безопасно работать в многопоточной среде. Вместо того чтобы использовать блокировки синхронизации, как это делают многопоточные коллекции, неизменяемые коллекции не могут быть изменены после создания. Это автоматически делает их безопасными для использования в многопоточных сценариях, так как нет возможности другому потоку изменить коллекцию.
Сами же коллекции можно поделить на несколько видов:
- Mutable — обычные коллекции которые поддерживают изменения.
- Immutable — коллекции, которые полностью запрещают изменения. Хотя на самом деле любое изменение иммутабельной коллекции приводит к созданию новой.
- ReadOnly — обертки над стандартными коллекциями, которые не дают поменять данные. Из-за того что это всего лишь обертка мы можем поменять данные в оригинальной коллекции и ead only коллекция подтянет изменения.
Детальнее можно ознакомиться в статье: Read only, frozen, and immutable collections.
Иммутабельные стеки ImmutableStack и очереди ImmutableQueue
Ничем не отличаются от обычных стеков и очередей, кроме того, что являются не изменяемыми.
Для реализации иммутабельных стеков/очередей массивы не подойдут. Причина заключается в том, что на каждое изменение придётся делать полную копию массива что очень неэффективно.
Поэтому для работы иммутабельных стеков/очередей используется связанный список. При изменении коллекции нужно всего лишь создать новый элемент, который ссылается на предыдущее значение. В итоге не происходит никакого копирования и экономится память.
Иммутабельные списки ImmutableList
Под капотом используют сбалансированное бинарное дерево вместо массива или связанного списка.
Массивы не подходят из-за накладных расходов на их использование. Связанный список тоже не подойдет, потому что ImmutableList поддерживает обращение по индексу из-за чего нужно долго перебирать связанные элементы. Поэтому для нормальной работы иммутабельных списков используют сбалансированное бинарное дерево.
Иммутабельные массивы ImmutableArray
По сути, это небольшая прослойка над обычными массивами и все. Любые мутабельные операции приводят к копированию массива. Из-за этого скорость добавления элементов равна O (n), но в то же время получение элемента по индексу занимает O (1).
Итерация по массиву работает в несколько раз быстрее чем у других неизменяемых коллекциях.
Иммутабельные словари ImmutableDictionary
Неизменяемые словари внутри работают на базе сбалансированного дерева, но с одной особенностью. Каждый элемент внутри коллекции представлен в виде отдельного дерева (ImmutableList>). Так что по своей сути иммутабельные словари — это деревья деревьев.
Из-за своей особенности иммутабельные словари потребляют очень много памяти и долго работают. Поэтому стоит аккуратно их использовать.
Особенности использования
Как было выше сказано все операции изменения коллекций приводят к созданию новой коллекции. Нужно помнить, что необходимо использовать новый экземпляр вместо старого.
var immutableList = new[] { 1, 2, 3 }.ToImmutableList();
immutableList = immutableList.Add(4);
По идее чтобы было проще, мы можем объединить все изменения в цепочку:
immutableList = immutableList
.Add(5)
.Add(6)
.Add(7);
Однако такого способа стоит избегать, потому что каждый вызов метода создает новый экземпляр коллекции. Хотя неизменяемые коллекции реализованы таким образом, чтобы повторно использовать как можно большую часть оригинальной коллекции при создании нового экземпляра, некоторые выделения памяти все же необходимы. Это означает больше работы для сборщика мусора.
Чтобы минимизировать проблему стоит использовать методы, которые могут выполнить нужные изменения за один вызов. Например:
immutableList = immutableList.AddRange(new[] { 5, 6, 7 });
Но такие методы позволяют сделать только один вид изменения. Например у нас нет единого метода, который позволяет добавить и удалить одну запись:
immutableList = immutableList
.Add(6)
.Remove(2);
Для решения этой проблемы иммутабельные коллекции предоставляют билдеры (builders).
var builder = immutableList.ToBuilder();
builder.Add(6);
builder.Remove(2);
immutableList = builder.ToImmutable();
Внутри себя билдеры используют соответствующую мутабельную коллекцию, что позволяет выполнить все операции над одним экземпляром коллекции. Только после вызова метода ToImmutable экземпляр снова будет неизменяемым. Таким образом можно сократить объем работы уборщика мусора.
Источники и доп. материалы
