Bounded-size Dynamic Arrays and Capacity
The simplest dynamic array is constructed by allocating a fixed-size array and then dividing it into two parts: the first stores the elements of the dynamic array and the second is reserved, or unused. We can then add or remove elements at the end of the dynamic array in constant time by using the reserved space, until this space is completely consumed. The number of elements used by the dynamic array contents is its logical size or size, while the size of the underlying array is called the dynamic array's capacity, which is the maximum possible size without relocating data.
In applications where the logical size is bounded, the fixed-size data structure suffices. This may be short-sighted, when problems with the array filling up turn up later. It is best to put resize code into any array, to respond to new conditions. Then choosing initial capacity is optimization, not getting the program to run. Resizing the underlying array is an expensive task, typically involving copying the entire contents of the array.
Read more about this topic: Dynamic Array
Famous quotes containing the words dynamic and/or capacity:
“The nearer a conception comes towards finality, the nearer does the dynamic relation, out of which this concept has arisen, draw to a close. To know is to lose.”
—D.H. (David Herbert)
“Lords and Commoners of England, consider what nation it is whereof ye are, and whereof ye are the governors; a nation not slow and dull, but of a quick, ingenious and piercing spirit, acute to invent, subtle and sinewy to discourse, not beneath the reach of any point the highest that human capacity can soar to.”
—John Milton (1608–1674)