Особенности реализации List в C#

List является одной из самых популярных коллекций в C#. Давайте разберёмся в некоторых особенностях работы с ним и посмотрим на внутреннюю реализацию его отдельных частей.

Введение

Данная статья будет посвящена полностью List<T> из пространства имён System.Collections.Generic, а если быть конкретнее, то его внутренней реализации и некоторым особенностям. Это самая часто используемая коллекция языка. И это не только моё мнение — так писали в своих книгах Эндрю Троелсен, Филипп Джепикс и Джон Скит. И это понятно – с List<T> легко работать. Он довольно гибкий и тем самым покрывает огромную часть повседневных задач программиста. С этим также помогает большое количество методов, идущих с ним в комплекте. А наличие LINQ ещё больше расширяет возможности данной коллекции.

Внутри List

Исходный код класса List<T> доступен на GitHub. Это значит, что мы можем взглянуть на его реализацию. Пройдёмся по важным аспектам.

Класс List<T> представляет последовательный список элементов с динамически изменяемым размером. Под капотом List<T> построен с использованием массива.

Класс List<T> содержит 3 основных поля:

• T[] _items – внутренний массив, на основе которого строится список;

• int _size – хранит информацию о количестве элементов в списке;

• int _version – содержит версию коллекции.

Добавление элемента в список

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

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:

• если внутренний массив пуст, то ёмкость списка будет равна 4, иначе удвоенной длине массива;

• если новое значение ёмкости получается больше максимально возможной длины массива, то данная ёмкость станет равна Array.MaxLength;

• если новое значение ёмкости коллекции получилось меньше текущего, то новая ёмкость станет равна текущей;

• в конце newcapacity записывается в свойство Capacity.

Зачем нужно поле _version?

Но зачем же всё-таки нужно поле _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 также приведёт к выбрасыванию исключения.

Capacity

У 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 действует по следующему алгоритму:

• если value меньше количества элементов в коллекции, то будет выброшено исключение;

• если value не равно длине внутреннего массива и value больше 0, то будет создан новый массив с ёмкостью, равной value;

• если количество элементов в списке больше 0, то будет выполнено копирование элементов из старого массива в новый;

• если value равно 0, то полю, которое представляет собой внутренний массив, будет присвоен пустой массив.

Прочие особенности методов List

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

Между двумя этими методами есть несколько различий:

• метод Sort принадлежит классу List<T>, а метод OrderBy является методом расширения из LINQ;

• метод Sort модифицирует исходную коллекцию, а OrderBy возвращает отсортированную копию с типом IOrderedEnumerable<TSource>;

• метод OrderBy производит устойчивую сортировку, а Sort – нет. Если вы используете метод Sort, то эквивалентные элементы могут быть переупорядочены.

Немного о производительности

List против ArrayList

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 производится множество операций упаковки, увеличивается и число сборок мусора. При этом получение элемента требует выполнения распаковки. Всё это приводит к снижению производительности.

Разница при использовании ссылочных типов несущественная, так как нет операций упаковки и распаковки, которые являются очень тяжёлыми. Судя по коду, небольшая разница в скорости появляется из-за операции преобразования типов.

Преимущества задания Capacity

Как уже было сказано ранее, если разработчик заранее знает размер списка, то он может указать его.

Проведём небольшой тест.

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 ненужных операций копирования на каждой итерации внешнего цикла.

Как быстрее всего определить, что в списке есть элементы?

Возьмём три варианта определения того, что список непустой:

• использовать метод Count из LINQ и сравнить результат с 0;

• использовать свойство Count и сравнить результат с 0;

• использовать метод расширения Any из LINQ.

Проведя тестирование, получаем следующие результаты для списка из 1 500 000 элементов:

Самым быстрым оказался доступ к свойству Count, так как оно просто возвращает значение поля _size.

Метод Count пытается преобразовать исходную коллекцию к ICollection. При успешном преобразовании метод вернёт значение свойства Count. В случае неудачи потребуется обойти всю коллекцию для высчитывания количества элементов. К счастью, List<T> реализует данный интерфейс.

Метод Any при обнаружении хотя бы одного элемента в коллекции вернёт true.

Заключение

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

C# содержит ещё множество коллекций, которые помогают в работе разработчикам. Какие-то из них более специфичные, а какие-то менее. Надеюсь, что данная статья поможет вам в работе и сделает ваше понимание списков чуть лучше :).

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Artem Rovenskii. List in C#: implementation and features.