Array capacity and granularity

Describes the granularity and capacity of a dynamic array.

The capacity of an array is the number of elements which the array can hold or represent within the space currently allocated to its array buffer.

For a flat array buffer, the increase in capacity of a buffer, when the insertion of an additional element causes the buffer to be re-allocated, is termed the granularity of the array. For example, adding a fifth element to a fixed flat array constructed with a granularity of four, causes the array buffer to be re-allocated so that its capacity increases from four to eight elements.

For a segmented array buffer, the granularity defines the capacity of a single segment. A segmented array buffer is always expanded by allocating additional segments.

The granularity of an array is defined at construction time. The choice of value depends on the use to be made of the array and needs careful consideration. Too small a value for an array with a high turnover of elements can incur considerable overhead from the process of allocating memory. Too large a value can result in wasted space if insufficient new elements are subsequently added.