Список <> Емкость возвращает больше элементов, чем добавлено

В List<T> есть несколько свойств, которые, как представляется, связаны с количеством элементов в списке - Capacity, Count (который присутствует как свойство и метод). Это довольно запутанно, особенно по сравнению с Array, имеющим только Length.

Я использую List.Capacity, но это дает неожиданный результат:

List <string> fruits = new List<string>();
fruits.Add("apple");
fruits.Add("orange");
fruits.Add("banana");
fruits.Add("cherry");
fruits.Add("mango");
Console.WriteLine("the List has {0} items in it.", fruits.Capacity);

когда я запускаю это, отображается Консоль:

the List has 4 items in it.

Я не понимаю, почему он показывает Capacity из 8, когда я добавил только 5 элементов.

Ответ 1

Capacity списка представляет собой объем памяти, который в настоящее время список зарезервирован для текущих объектов и объектов, которые будут добавлены к нему. Список Count списка состоит в том, сколько элементов фактически добавлено в список.

Ответ 2

Здесь полное объяснение свойства Capacity из MSDN:

Емкость - количество элементов, которое может хранить List<T> до изменения размера, тогда как Подсчет - это количество элементов, которые фактически находятся в List<T>.

Емкость всегда больше или равна Count. Если Count превышает Capacity при добавлении элементов, емкость увеличивается за счет автоматического перераспределения внутреннего массива перед копированием старых элементов и добавления новых элементов.

Емкость можно уменьшить, вызвав метод TrimExcess() или установив свойство Capacity явно. Когда значение Capacity задано явно, внутренний массив также перераспределяется для размещения указанной емкости, и все элементы копируются.

Получение значения этого свойства является операцией O (1); установка свойства - это операция O (n), где n - новая емкость.

Ответ 3

Чтобы добавить к другим ответам, поведение List по умолчанию при добавлении элементов один за другим начинается с емкости 4 и удваивает его, когда список заполняется. Это объясняет емкость 8.

Ответ 4

Чтобы понять, почему он больше, вам нужно понять, как List<T> работает внутри. Внутри a List<T> использует массив (so T[]) для хранения его содержимого.

Этот массив начинается с размера 4 элемента, что эквивалентно выражению T[] array = new T[4]. Когда вы добавляете элемент в List<T>, он сохраняется в массиве: первый элемент в array[0], второй в array[1] и т.д. Однако пятый элемент не может вписаться в этот массив, поскольку это всего лишь четыре элемента. И поскольку длина массива не может быть изменена после его создания, единственная опция - взять содержимое массива и перенести его в новый массив, который достаточно велик, чтобы удерживать этот пятый элемент. Реализация List<T> позволяет удвоить размер буфера массива каждый раз, когда он заканчивается, поэтому, чтобы соответствовать пятому элементу, он удваивает емкость массива до 8. Затем 16 и т.д.

Существует, вероятно, хорошая математическая поддержка того, почему он выбирает удвоение, это, вероятно, хороший компромисс между дорогостоящими операциями копирования (не нужно слишком часто выделять новый буфер) и потерянным пространством. По удвоению, потери памяти никогда не превышают 50%, и количество раз, которое нужно выделить новому массиву, уменьшается логарифмически, я считаю.

Ответ 5

Емкость не совпадает с количеством элементов списка. Хорошо реализованные контейнеры списка на всех языках по умолчанию выделяют больше памяти, чем нужно, чтобы сохранить текущее количество записей. Это связано с тем, что более эффективно выделять большую часть памяти в определенное время, чем выделять память для еще одного элемента каждый раз, когда вы добавляете его.