Imagine tracking orders as they arrive and are fulfilled. A fixed-size array might run out of room during a rush, then leave most of its space unused afterward. A vector, or dynamic array, keeps array-style access by position while adjusting its storage as the number of elements changes. section 5.11 section 5.19
The trick is that the underlying array is still fixed-size. When it must grow or shrink, the vector allocates another array and moves its elements. You can add to a full vector without choosing a new capacity yourself, but resizing takes time and may temporarily require substantial extra memory. section 5.3 section 8.7
One practical resizing strategy is:
- Start with capacity one, unless an initial capacity is specified. section 5.14
- When adding an element to a full array, double its capacity. section 5.14
- After a removal leaves only one-quarter of capacity in use, halve the capacity. Waiting this long leaves room for new additions without immediately growing again. section 5.14 section 5.13
After the holiday rush
Suppose open orders peak at 10,000 but normally number about 100. Keeping the peak-sized array indefinitely would waste most of its space. Shrinking after many orders close lets the storage follow demand; shrinking after every small decrease would be less useful. section 5.11 section 5.13
Choose a vector when the collection’s size grows or varies substantially. If its size is known or changes only slightly, a static array may avoid resizing costs. Individual insertions or deletions can take O(n) time when resizing is needed, although a sequence of n additions takes O(n) total amortized time. A linked list offers another resizing tradeoff, but cannot access an element directly by position. section 5.3 section 5.19
Operations on a stack implemented with a dynamic array. When push(1) is called, there is no unused array cell, so the array doubles its size.
A stack backed by a dynamic array doubles its capacity when a push finds no unused cell. section 8.7
