List<> Capacity returns more items than added

There are several properties on List<T> that seem to be related to number of items in the list - Capacity, Count (which is present as a property and a method). This is quite confusing especially compared with Array that has just Length.

I'm using List.Capacity but it gives unexpected result:

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);

when I run this the Console displays:

the List has 4 items in it.

I don't understand why its showing a Capacity of 8, when I only added 5 items.

Answers


The Capacity of the list represents how much memory the list currently has set aside for the current objects and objects to be added to it. The Count of the list is how many items have actually been added to the list.


Here's the full explanation for the Capacity property from MSDN:


Capacity is the number of elements that the List<T> can store before resizing is required, while Count is the number of elements that are actually in the List<T>.

Capacity is always greater than or equal to Count. If Count exceeds Capacity while adding elements, the capacity is increased by automatically reallocating the internal array before copying the old elements and adding the new elements.

The capacity can be decreased by calling the TrimExcess() method or by setting the Capacity property explicitly. When the value of Capacity is set explicitly, the internal array is also reallocated to accommodate the specified capacity, and all the elements are copied.

Retrieving the value of this property is an O(1) operation; setting the property is an O(n) operation, where n is the new capacity.


To add to the other answers, the default behaviour of List when adding items one by one is to start with a capacity of 4 and double it whenever the list becomes full. This explains the capacity of 8.


In order to understand why it is bigger, you need to understand how List<T> works internally. Internally, a List<T> uses an array (so T[]) to store its contents.

This array starts off with a size of 4 elements, so equivalent to saying T[] array = new T[4]. When you add an item to a List<T>, it is stored in the array: the first item in array[0], the second in array[1], etc. The fifth item, however, can't fit into this array, as it's only four elements long. And because the length of an array can't be changed after it has been created, the only option is to take the contents of the array and move it to a new array that is large enough to hold that fifth item as well. The implementation of List<T> chooses to double the size of the array buffer each time it runs out of space, so to fit the fifth item, it doubles the array capacity to 8. Then 16, and so on.

There is probably good mathematical backing on why it chooses to double, it's probably a good compromise between the expensive copy operations (don't want to allocate a new buffer too often) and wasted space. By doubling, the memory waste is never over 50% and the amount of times a new array needs to be allocated decreases logarithmically, I believe.


Capacity is not the same as the item count of the list. Well implemented list containers in all languages by default allocate more memory than they need to save the current number of entries. This is because it is more efficient to allocate a bigger chunk of memory some of the time than to allocate memory for one more item every time you add one.


Need Your Help

PHP How To Know When To Put A Space Between A Word And Parentheses

php naming-conventions

I have been recommended to put a space between foreach and (, among other things. My understanding is that it helps to differentiate between functions and everything else.

variable not set during before_create callback

ruby-on-rails ruby ruby-on-rails-3.2

I have a problem understand the order of events that are causing my value selectedplan to not be set in my set_expiration_date in my model.