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

Артём Ровенский
Статей: 24

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

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

Введение

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

Внутри List<T>

Исходный код класса 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<T>

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