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)
“Mankind’s common instinct for reality ... has always held the world to be essentially a theatre for heroism. In heroism, we feel, life’s supreme mystery is hidden. We tolerate no one who has no capacity whatever for it in any direction. On the other hand, no matter what a man’s frailties otherwise may be, if he be willing to risk death, and still more if he suffer it heroically, in the service he has chosen, the fact consecrates him forever.”
—William James (1842–1910)