Что скрывают привычные коллекции .Net Core — List

Дмитрий Корабельников

Разработчик ГК Юзтех

Зачем вообще иметь представление о работе этих коллекций и их особенностях:

• знание нюансов позволит более осознанно выбирать ту или иную коллекцию, а при их использовании — понимать вычислительную сложность выполняемых операции и/или потребление памяти
• полезно понимать, какие решения принимали авторы оригинальных коллекций, изучение кода опытных коллег, позволяет местами оптимизировать собственные решения
• в конце концов, об этом, бывает, спрашивают на собеседованиях

Ниже рассмотрим коллекцию List, а в будущих статьях — и другие коллекции.

Disclaimer: далее исходные коды приводятся в объеме, необходимом для иллюстрации рассматриваемых нюансов работы коллекций. Комментарии, валидация значений, некоторые частные случаи и т.п. далее местами опущены. С исходниками в полном объеме любопытные читатели могут ознакомиться в публично доступном репозитории.

List

Пожалуй, эту коллекцию используют каждый раз, когда нужно работать с переменным числом однотипных объектов, раз уж старые добрые массивы не слишком-то для этого удобны.

Итак, что же находится внутри:

			public class List : IList, IList, IReadOnlyList
{
    internal T[] _items;
    internal int _size;
    private static readonly T[] s_emptyArray = new T[0];
    public List()
    {
      _items = s_emptyArray;
    }

    public List(int capacity)
    {
        if (capacity == 0)
            _items = s_emptyArray;
        else
            _items = new T[capacity];
    }
		

Мы видим, что внутри находится все тот же массив и отдельно ведется учет фактического количества элементов списка в переменной _size. При этом конструктор по умолчанию инициализирует внутренний массив нулевым количеством элементов, но есть и конструктор, позволяющий явно задать количество элементов, что приведет к созданию массива соответствующего размера.

В этом обзоре не буду приводить пример, но также существует и конструктор, принимающий на вход экземпляр IEnumerable, который осуществляет последовательное добавление элементов в коллекцию, при этом существует упрощенная ветка для случая, когда был передан экземпляр ICollection, т.к. свойство Count позволяет сразу создать массив нужного размера и скопировать в него элементы.

Что же произойдет при попытке добавления элемента?

			private const int DefaultCapacity = 4;
public void Add(T item)
{
    T[] array = _items;
    int size = _size;
    if (size < _items.Length)
    {
        _size = size + 1;
        array[size] = item;
    }
    else
    {
        AddWithResize(item);
    }
}

private void AddWithResize(T item)
{
    Grow(_size + 1);
    _size = _size + 1;
    _items[_size] = item;
}

private void Grow(int capacity)
{
    int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;
    if (newcapacity > Array.MaxLength)
        newcapacity = Array.MaxLength;
    if (newcapacity < capacity)
        newcapacity = capacity;
    Capacity = newcapacity;
}
		

Итак, в оптимистичном сценарии (текущий размер массива позволяет поместить в него еще один элемент), увеличивается счетчик количества элементов, а в массив добавляется еще одно значение.

В случае, когда массив полностью заполнен, он будет принудительно увеличен. При этом массив с 0 элементов будет увеличен до размера по умолчанию (в текущей версии — 4), а вот далее массив будет каждый раз увеличиваться вдвое относительно текущего размера. Но как именно это будет сделано? Рассмотрим подробнее свойство Capacity.

			public int Capacity

{
    get => _items.Length;
    set
    {
        if (value < _size)
        {
            // выбрасывается исключение
        }
        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;
            }
        }
    }
}
		

Работая со свойством Capacity, мы можем проверять и манипулировать размером массива, сокрытого внутри List (главное — не пытаться сделать его меньше текущего количества элементов). При увеличении размера внутреннего массива будет выделен новый массив заданного размера, куда методом Array.Copy (сложность которого, как подсказывает документация, O(n)) будет скопирован текущий массив.

Дополнительные методы:

Очистка массива

			public void Clear()
{
    if (RuntimeHelpers.IsReferenceOrContainsReferences())
    {
        int size = _size;
        _size = 0;
        if (size > 0)
        {
            Array.Clear(_items, 0, size);
        }
    }
    else
    {
        _size = 0;
    }
}
		

Здесь мы видим, что количество элементов списка становится нулем, а если в массиве или его элементах содержатся ссылочные типы, они очищаются для сборщика мусора. Заметим, что в противном случае принудительного «зануления» не происходит, логика класса не позволит обычным образом получить доступ к значениям массива вне текущего количества элементов.

Вставка элемента

			public void Insert(int index, T item)
{
    if (_size == _items.Length)
        Grow(_size + 1);
    if (index < _size)
        Array.Copy(_items, index, _items, index + 1, _size - index);
    _items[index] = item;
    _size++;
}
		

При попытке вставки, если есть такая необходимость, внутренний массив будет увеличен, затем будет осуществлено копирование элементов массива на одну позицию, начиная с индекса, куда предполагается вставить новый элемент, затем новый элемент будет помещен в массив.

Вставку набора элементов (InsertRange) приводить не буду, отмечу только, что логика в целом та же — массив будет по необходимости увеличен до необходимой величины, текущие элементы — перемещены, а новые — скопированы в увеличенный массив, начиная с целевой позиции.

Удаление элемента (RemoveAt) или набора элементов (RemoveRange) по позиции также приводить не будем, по сути своей они обратны вставке, только увеличения размера массива, естественно, не происходит.

Выводы

Вычислительная сложность

Ниже приведена сложность операций для List, внутри которого выделен массив размера N, заполненный на величину S. Сложность приведена, в том числе, для операций, которые не рассматривались выше, в связи с тем, что их реализация не отличается от уже рассмотренных методов или опирается на них. Методы поиска, проверок на наличие элементов и т.п. не приводятся за тривиальностью.

Какие практические выводы можно сделать из всего, изложенного выше:

1. Помните, что внутри List находится массив, а не связанный список. Достаточно представить, как могут выполняться те или иные операции над массивом, чтобы оценить сложность той или иной операции.

2. Если это уместно, инициализируйте List, задавая предполагаемый размер коллекции. Если вы заранее знаете порядок количества элементов, которые предполагается поместить в коллекцию, используйте это. Данное знание позволит существенно сэкономить на операциях, связанных с изменением размера массива.

3. Тип значений, хранимых в List, может повлиять на вычислительную сложность выполняемых операций. Для ссылочных типов местами имеет место дополнительная обработка.

4. Рассмотренные участки кода методов, изменяющих коллекцию, достаточно наглядно показывают отсутствие гарантий потокобезопасности. Доступ к переменной _size, определяющей размер массива, самому массиву и его элементам никаким образом не синхронизируется. Как следствие, попытка одновременного изменения коллекции из нескольких потоков может иметь побочные эффекты. Чтобы их исключить, можно использовать коллекции из пространства имен System.Collections.Concurrent или, для особых случаев, реализовать собственные потокобезопасные коллекции.