List <> Capacity возвращает больше элементов, чем добавлено

Question

В 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 пунктов.

Answer 1

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

Answer 2

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

---

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

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

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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