Basic implementations of dynamic arrays are size 2n, where half of the space is populated by existing elements, and the other half is reserved at the end for appending new elements in O(1) time.
Inserting new elements anywhere other than at the end of the array requires reallocation of the array, which is an expensive operation.
Are there any C++ implementations of resizable arrays, where space is also reserved at the beginning of the array, for prepending elements efficiently? If so, how much space is reserved compared to the space reserved at the end for appending? I would imagine prepending is a much less common operation, but if it is happening often enough in a program, it could be devastating to reallocate upon each prepending operation.
Deques allow for prepending and appending in amortized constant time.
Unlike vectors, where the array is stored contiguously and reallocated if capacity is reached, deque elements are not guaranteed to be stored contiguously. Instead, deques store elements in chunks. If more space is needed as a result of a push_back() or push_front() call, a new chunk of space is allocated and linked to.
Thank you to Mark Ransom for posting about deques in the comments.