List является одной из самых популярных коллекций в C#. Давайте разберёмся в некоторых особенностях работы с ним и посмотрим на внутреннюю реализацию его отдельных частей.
Данная статья будет посвящена полностью List<T> из пространства имён System.Collections.Generic, а если быть конкретнее, то его внутренней реализации и некоторым особенностям. Это самая часто используемая коллекция языка. И это не только моё мнение — так писали в своих книгах Эндрю Троелсен, Филипп Джепикс и Джон Скит. И это понятно – с List<T> легко работать. Он довольно гибкий и тем самым покрывает огромную часть повседневных задач программиста. С этим также помогает большое количество методов, идущих с ним в комплекте. А наличие LINQ ещё больше расширяет возможности данной коллекции.
Исходный код класса List<T> доступен на GitHub. Это значит, что мы можем взглянуть на его реализацию. Пройдёмся по важным аспектам.
Класс List<T> представляет последовательный список элементов с динамически изменяемым размером. Под капотом List<T> построен с использованием массива.
Класс List<T> содержит 3 основных поля:
Как уже было сказано, размер списка динамически изменяется. Взглянем поподробнее, что же происходит при добавлении элемента в список.
public void Add(T item)
{
_version++;
T[] array = _items;
int size = _size;
if ((uint)size < (uint)array.Length)
{
_size = size + 1;
array[size] = item;
}
else
{
AddWithResize(item);
}
}В первую очередь значение поля _version увеличивается на 1 (смысл данного действия мы разберём чуть позже). После этого происходит создание двух локальных переменных – массива array с элементами типа T и size типа int. Им присваиваются соответствующие поля. Далее если в массиве ещё есть место для одного элемента, то происходит изменение элемента массива по индексу size + 1. Если же размер массива не позволяет добавить ещё один элемент, то вызывается метод AddWithResize.
private void AddWithResize(T item)
{
Debug.Assert(_size == _items.Length);
int size = _size;
Grow(size + 1);
_size = size + 1;
_items[size] = item;
}Здесь вызывается метод Grow для увеличения текущего размера внутреннего массива. Далее производятся те же действия, что и в методе Add, для добавления при доступном месте.
Рассмотрим метод Grow подробнее:
private void Grow(int capacity)
{
....
int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;
if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;
if (newcapacity < capacity) newcapacity = capacity;
Capacity = newcapacity;
}Алгоритм работы метода Grow:
Но зачем же всё-таки нужно поле _version, значение которого менялось в методе Add? Как уже было написано ранее, это поле, которое позволяет отслеживать версию списка. Его значение проверяется при обходе списка. К примеру, рассмотрим метод ForEach:
public void ForEach(Action<T> action)
{
....
int version = _version;
for (int i = 0; i < _size; i++)
{
if (version != _version)
{
break;
}
action(_items[i]);
}
if (version != _version)
ThrowHelper
.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}Перед началом обхода значение поля _version сохраняется в переменную. Если во время обхода список будет изменён, то обход прекращается и выбрасывается исключение типа System.InvalidOperationException. Похожим образом _version отслеживается и в List<T>.Enumerator. Поэтому изменение списка при его обходе в foreach также приведёт к выбрасыванию исключения.
У List<T> есть конструктор, который первым аргументом принимает число – начальную ёмкость.
List<int> list = new List<int>(8);Если разработчик заранее знает нужный размер списка, то он может задать его. Это избавляет от ненужных операций копирования и выделения памяти под новый массив при добавлении новых элементов.
Кстати, размером внутреннего массива можно управлять, ещё и используя свойство Capacity:
list.Capacity = 8;Рассмотрим код данного свойства:
public int Capacity
{
get => _items.Length;
set
{
if (value < _size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(....);
}
if (value != _items.Length)
{
if (value > 0)
{
T[] newItems = new T[value];
if (_size > 0)
{
Array.Copy(_items, newItems, _size);
}
_items = newItems;
}
else
{
_items = s_emptyArray;
}
}
}
}Аксессор get возвращает значение _items.Length, то есть длину внутреннего массива.
Аксессор set действует по следующему алгоритму:
Insert
Метод Insert позволяет вставить элемент в коллекцию только в рамках начала и конца этой коллекции. Если количество элементов в коллекции будет равно размерности внутреннего массива, то произойдёт увеличение ёмкости массива с помощью метода Grow(_size + 1). При попытке вставить элемент на индекс, который больше list.Count, будет выброшено исключение System.ArgumentOutOfRangeException.
List<string> list = new List<string>() { "1", "2"};
list.Insert(1, "10"); // OK
list.Insert(2, "15"); // OK
list.Insert(10, 12); // throw exceptionПодобное поведение останется даже при явном управлении размером внутреннего массива.
Рассмотрим пример:
List<string> list = new List<string>() { "1", "2"};
list.Capacity = 8;
list.Insert(3, "3");В свойство Capacity присваивается 8, что приводит к изменению размера внутреннего массива. Однако это не даёт возможности вставить элемент на позицию, превышающую list.Count. Результатом выполнения приведённого кода будет выбрасывание исключения.
Clear
Данный метод производит очистку коллекции. В результате этой операции свойство Count будет иметь значение 0. Элементы коллекции ссылочного типа получают значение по умолчанию. Если элементы коллекции являются структурами и имеют поля ссылочного типа, то данные поля тоже получат значение по умолчанию. Стоит заметить, что размер внутреннего массива остаётся неизменным. Если до вызова Clear свойство Capacity было равно 8, то и после Clear размер массива останется равным 8. Для освобождения памяти, выделяемой под сам массив, необходимо после Clear вызвать метод TrimExcess.
TrimExcess
Данный метод делает размер внутреннего массива равным количеству элементов в списке. Его стоит использовать, например, когда вы знаете, что в коллекцию больше не будут добавлены новые элементы.
list.Clear();
list.TrimExcess();Sort и OrderBy
Между двумя этими методами есть несколько различий:
List<T> является обобщённым, а это значит, что мы должны при создании списка указать, с объектами какого типа он работает.
List<string> list = new List<string>();Джеффри Рихтер в своей книге "CLR via C#" приводит следующие преимущества обобщений:
В той же книге в начале 12-ой главы про обобщения имеется хороший пример сравнения List<T> и его необобщённого аналога ArrayList. Суть теста заключается в добавлении элемента в список и присваивании этого же элемента из списка в переменную 10 миллионов раз.
Пример кода для тестирования ArrayList со значимым типом:
public void ValueTypeArrayList()
{
ArrayList a = new ArrayList();
for (Int32 n = 0; n < _count; n++)
{
a.Add(n);
Int32 x = (Int32)a[n];
}
}Тестирование производилось с объектами значимых (Int32) и ссылочных (String) типов.
Переписав приведённый в книге код и протестировав его с помощью BenchmarkDotNet, я получил следующие результаты:
Из результатов видно, что c Int32 алгоритм List<T> работает гораздо быстрее, чем ArrayList. В целых 13 раз! Плюс с List<T> в 4 раза меньше выделяется память.
Из-за того что при работе ArrayList производится множество операций упаковки, увеличивается и число сборок мусора. При этом получение элемента требует выполнения распаковки. Всё это приводит к снижению производительности.
Разница при использовании ссылочных типов несущественная, так как нет операций упаковки и распаковки, которые являются очень тяжёлыми. Судя по коду, небольшая разница в скорости появляется из-за операции преобразования типов.
Как уже было сказано ранее, если разработчик заранее знает размер списка, то он может указать его.
Проведём небольшой тест.
public void ListWithoutCapacity()
{
for (int i = 0; i < Count; i++)
{
List<int> list = new List<int>();
for (int j = 0; j < Length; j++)
{
list.Add(j);
}
}
}В данном случае происходит добавление в list 150 000 элементов. Для наглядности проведём эту операцию 1000 раз. И сравним производительность с таким же методом, но с указанным capacity, который равен количеству операций добавления.
Из результатов видно, что затраченное время на выполнение метода без capacity в 2 раза больше, чем с заранее установленным. Также памяти выделяется почти в 4 раза больше. Подобные действия убирают 17 ненужных операций копирования на каждой итерации внешнего цикла.
Возьмём три варианта определения того, что список непустой:
Проведя тестирование, получаем следующие результаты для списка из 1 500 000 элементов:
Самым быстрым оказался доступ к свойству Count, так как оно просто возвращает значение поля _size.
Метод Count пытается преобразовать исходную коллекцию к ICollection. При успешном преобразовании метод вернёт значение свойства Count. В случае неудачи потребуется обойти всю коллекцию для высчитывания количества элементов. К счастью, List<T> реализует данный интерфейс.
Метод Any при обнаружении хотя бы одного элемента в коллекции вернёт true.
Можно сказать, что List<T> является более удобной для работы версией массива. Например, со списком удобнее работать, когда заранее неизвестно количество элементов последовательности.
C# содержит ещё множество коллекций, которые помогают в работе разработчикам. Какие-то из них более специфичные, а какие-то менее. Надеюсь, что данная статья поможет вам в работе и сделает ваше понимание списков чуть лучше :).