C# Особенности работы List

Котодомик

2 месяца назад

Исходный код: https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,d2ac2c19c9cf1d44

Конструктор

У класса List есть 3 конструктора:

Без аргументов;
С числовым аргументом int capacity;
С перечислением IEnumerable collection;

Первые два работают схоже — создается внутренний массив _items типа T с нужным размером (0, либо capacity).

private T[] _items;

1	private T[] _items;

Третий (IEnumerable collection) работает немного сложнее.

Алгоритм можно посмотреть ниже:

 public List(IEnumerable<T> collection) { 
            ICollection<T> c = collection as ICollection<T>;
            if( c != null) {
                int count = c.Count;
                if (count == 0)
                {
                    _items = _emptyArray;
                }
                else {
                    _items = new T[count];
                    c.CopyTo(_items, 0);
                    _size = count;
                }
            }    
            else {                
                _size = 0;
                _items = _emptyArray;

                using(IEnumerator<T> en = collection.GetEnumerator()) {
                    while(en.MoveNext()) {
                        Add(en.Current);                                    
                    }
                }
            }
        }

public List(IEnumerable<T> collection) {

ICollection<T> c = collection as ICollection<T>;

if( c != null) {

int count = c.Count;

if (count == 0)

{

_items = _emptyArray;

}

else {

_items = new T[count];

c.CopyTo(_items, 0);

_size = count;

}

else {

_size = 0;

_items = _emptyArray;

using(IEnumerator<T> en = collection.GetEnumerator()) {

while(en.MoveNext()) {

Add(en.Current);

}

Вначале IEnumerable<T> collection преобразуется к ICollection<T>;
Далее логика зависит от того — удалось ли преобразование:
1. Удалось — значит используем метод CopyTo из одного массива в другой (всё тот же _items);
2. Не удалось — получаем энумератор и итерируя его и заполняем _items;

Работа с данными

Работа через индекс

Чтение — возвращает просто данные из _items по индексу:

return _items[index];

1	return _items[index];

Запись — записывает данные в массив _items по индексу и увеличивает версию :

_items[index] = value;
_version++

1 2	_items[index] = value; _version++

Метод Add

Тут сложнее логика.

Идёт вызов метода EnsureCapacity(_size + 1);
Идёт присвоение в массив items по индексу _size + 1: _items[_size++] = item;

Далее не получится продолжить не рассмотря метод EnsureCapacity.

EnsureCapacity

На вход данный метод получает аргумент int min.

Стоит уточнить, что логика данного метода работает исключительно в случае, когда количество элементов в массиве _items меньше, чем указано в аргументе min.

Новая размерность рассчитывается по следующему алгоритму:

Если в массиве _items отсутствуют элементы — устанавливается стандартная размерность: private const int _defaultCapacity = 4;
Если нет — текущая размерность массива _items умножается на два;
Если полученное число больше 2146435071 (Array.MaxArrayLength), то оно заменяется этим числом;
Если полученное число меньше, чем требуемое в аргументе (int min), то оно заменяется этим числом;
Полученное число устанавливается в свойство this.Capacity.

Вышел интересный алгоритм, с ним поиграемся далее, пока нужно посмотреть логику setter’а у свойства this.Capacity.

Capacity (get; set;)

Getter у данного свойства простой — он возвращает _items.Length. Вот с Setter'ом всё сложнее.

Если новое значение менее _size (фактическое количество элементов), то будет ошибка.

Если новое значение равно _size, то на этом логика работы setter’а завершается.

Остается последний путь — когда новое значение более того, что указано в _size.

Создается новый массив с размерностью, которую мы пытаемся присвоить в Setter у свойства Capacity. В новый массив копируются все элементы из _items, а затем в это же поле _items присваевается этот новый массив. Таким образом расширяется внутренний массив в классе List.

Insert

При добавлении идёт вызов EnsureCapacity, на случай, если количество элементов внутри массива равна _size.

Далее, если аргумент index, меньше _size (то есть мы хотим добавить элемент в середину массива), вызывается следующая логика:

Array.Copy(_items, index, _items, index + 1, _size - index);

1	Array.Copy(_items, index, _items, index + 1, _size - index);

Напомню — как выглядит сигнатура данного метода:

void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)

1	void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)

То есть из внутреннего массива List’а, начиная с индекса, куда мы хотим записать новый элемент, мы копируем в этот же массив, но со следующего за индексом элемента. А количество элементов — количество элементов за вычетом данного index’а. То есть фактически — мы просто сдвигаем все элементы на единицу вправо. Для того, чтобы в освободившуюся ячейку записать новый элемент.

InsertRange (он же AddRange, который является частным случаем InsertRange )

На вход идёт два аргумента — int index и IEnumerable collection.

Далее идёт уже известная нам логика из третьего конструктора — приведения энумератора к ICollection.

Если это невозможно, то идёт итеративный вызов Insert.

Если возможно, то происходит опять логика, похожая на логику Insert со сдвигами и Array.CopyTo.

В List ещё много интересных методов, но основные описаны в статье. По сути — это обёртка над массивом с кучей удобств.

Немного экспериментов

Конструкторы:

var list1 = new List<int>();
PrintListInfo(list1); // 0 / 0

var list2 = new List<int>(0);
PrintListInfo(list2); // 0 / 0

var list3 = new List<int>(new int[] {1, 2, 3});
PrintListInfo(list3); // 3 / 3

static void PrintListInfo(List<int> list)
{
    Console.WriteLine($"{list.Count} / {list.Capacity}");
}

var list1 = new List<int>();

PrintListInfo(list1); // 0 / 0

var list2 = new List<int>(0);

PrintListInfo(list2); // 0 / 0

var list3 = new List<int>(new int[] {1, 2, 3});

PrintListInfo(list3); // 3 / 3

static void PrintListInfo(List<int> list)

{

Console.WriteLine($"{list.Count} / {list.Capacity}");

}

Первый конструктор без аргументов — выставил capacity 0. Элементов внутри массива и не было. Поэтому вывод: 0 / 0.

Второй конструктор с аргументом 0. Это эквивалентно первому примеру. Вывод: 0 / 0. Если бы мы указали в конструкторе 1, то вывод был бы 0 / 1.

Третий конструктор с массивом на входе — подстроил List под массив, поэтому вывод: 3 / 3.

Дальше посмотрим как работает расширение..

var list1 = new List<int>();
for (int i = 0; i < 50; i++)
{
    list1.Add(i);
    PrintListInfo(list1);
}

static void PrintListInfo(List<int> list)
{
    Console.WriteLine($"{list.Count} / {list.Capacity}");
}

var list1 = new List<int>();

for (int i = 0; i < 50; i++)

{

list1.Add(i);

PrintListInfo(list1);

}

static void PrintListInfo(List<int> list)

{

Console.WriteLine($"{list.Count} / {list.Capacity}");

}

Вывод будет следующим:

1 / 4

2 / 4

3 / 4

4 / 4

5 / 8

6 / 8

7 / 8

8 / 8

9 / 16

10 / 16

11 / 16

12 / 16

13 / 16

14 / 16

15 / 16

16 / 16

17 / 32

18 / 32

19 / 32

20 / 32

21 / 32

22 / 32

23 / 32

24 / 32

25 / 32

26 / 32

27 / 32

28 / 32

29 / 32

30 / 32

31 / 32

32 / 32

33 / 64

34 / 64

35 / 64

36 / 64

37 / 64

38 / 64

39 / 64

40 / 64

41 / 64

42 / 64

43 / 64

44 / 64

45 / 64

46 / 64

47 / 64

48 / 64

49 / 64

50 / 64

То есть вначале Capacity был равен 0, однако после первого вызова Add — внутренний массив _items увеличился до 4. При добавлении пятого элемента — он увеличился в два раза до 8.. И так далее при попытках добавить новый элемент при заполненном внутреннем массиве. Если мы бы добавили 65 элементов, то Capacity стало бы 128.

Capacity

var list = new List<int>();
PrintListInfo(list); // 0 / 0

list.Add(1);
PrintListInfo(list); // 1 / 4

list.Add(2);
PrintListInfo(list); // 2 / 4

list.Add(3);
PrintListInfo(list); // 3 / 4

list.Add(4);
PrintListInfo(list); // 4 / 4

list.Add(5);
PrintListInfo(list); // 5 / 8

list.Capacity = 5;
PrintListInfo(list); // 5 / 5

try
{			
	list.Capacity = 4; 
}
catch(System.ArgumentOutOfRangeException e)
{
	Console.WriteLine(e.Message); // capacity was less than the current size. (Parameter 'value')
}

list.Capacity = 1000;
PrintListInfo(list); // 5 / 1000


static void PrintListInfo(List<int> list)
{
	Console.WriteLine($"{list.Count} / {list.Capacity}");
}

var list = new List<int>();

PrintListInfo(list); // 0 / 0

list.Add(1);

PrintListInfo(list); // 1 / 4

list.Add(2);

PrintListInfo(list); // 2 / 4

list.Add(3);

PrintListInfo(list); // 3 / 4

list.Add(4);

PrintListInfo(list); // 4 / 4

list.Add(5);

PrintListInfo(list); // 5 / 8

list.Capacity = 5;

PrintListInfo(list); // 5 / 5

try

{

list.Capacity = 4;

}

catch(System.ArgumentOutOfRangeException e)

{

Console.WriteLine(e.Message); // capacity was less than the current size. (Parameter 'value')

}

list.Capacity = 1000;

PrintListInfo(list); // 5 / 1000

static void PrintListInfo(List<int> list)

{

Console.WriteLine($"{list.Count} / {list.Capacity}");

}

Думаю тут всё и так понятно. Добавляем элементы, пока не получим размерность 5/8 (5 элементов в листе, 8 размерность листа).

Затем выставляем Capacity = 5. Так как в листе элементов как раз 5 — это разрешается и мы получаем 5/5.

При попытке установить размерность меньше, чем элементов в листе — мы получаем ошибку ArgumentOutOfRangeException

EnsureCapacity

По сути — это метод-хелпер над Setter‘ом у Capacity.

Он выставляет размерность внутреннего массива исходя из логики:

Если элементов 0, то стандартная стартовая размерность, равная 4;
Если больше, то размерность увеличивается в 2 раза;
Если полученная размерность меньше, чем пришло в аргументе, то используется число из аргумента;

Давайте проведем эксперимент:

var list = new List<int>();
PrintListInfo(list); // 0 / 0

list.EnsureCapacity(1);
PrintListInfo(list); // 0 / 4

list.EnsureCapacity(4);
PrintListInfo(list); // 0 / 4

list.EnsureCapacity(5);
PrintListInfo(list); // 0 / 8

list.EnsureCapacity(8);
PrintListInfo(list); // 0 / 8

list.EnsureCapacity(17);
PrintListInfo(list); // 0 / 17

static void PrintListInfo(List<int> list)
{
	Console.WriteLine($"{list.Count} / {list.Capacity}");
}

var list = new List<int>();

PrintListInfo(list); // 0 / 0

list.EnsureCapacity(1);

PrintListInfo(list); // 0 / 4

list.EnsureCapacity(4);

PrintListInfo(list); // 0 / 4

list.EnsureCapacity(5);

PrintListInfo(list); // 0 / 8

list.EnsureCapacity(8);

PrintListInfo(list); // 0 / 8

list.EnsureCapacity(17);

PrintListInfo(list); // 0 / 17

static void PrintListInfo(List<int> list)

{

Console.WriteLine($"{list.Count} / {list.Capacity}");

}

Если бы в последнем расширении массива мы бы использовали любое значение от 9 до 16, то размерность бы получилась 16. Но так как мы поставили размерность больше, чем автовычисленные по логике «умножить прошлую размерность на 2», то алгоритм взял то число, которое мы передали аргументом.

Выводы

Ну в первую очередь — лист это удобный и гибкий инструмент, который решает многие проблемы за вас. Его логика работы простая и понятная, а значит понимая, как он работает — можно использовать его на полную. А именно — учитывать определенные нюансы при построении вашего приложения, когда работаете с List.

Основная проблема List‘а — это периодическое расширение массива, который используется у него под капотом, во время заполнения List‘а. А значит — зная хотя бы приблизительно порядок элементов, которые мы планируем добавить в List — мы можем избежать данных накладных расходов с помощью:

Конструктора с аргументом int capacity на входе (var list = new List(1000));
Выставление capacity через setter свойства Capacity (list.Capacity = 1000);
Либо используя метод EnsureCapacity (list.EnsureCapacity(1000)).