Linear memory: vectors, stacks, and queues
Vectors are just the prototypical example of a data structure that holds a dynamic linear memory. They grow by means of reallocating and moving/copying data when the old buffer runs out of memory. We actually discussed the algorithm for vector growth back in Chapter 2. Each time the vector grows, the size of the allocation grows by a multiple of the existing allocation; in practice, this almost always means the size of the allocation doubles each time. This means that most insertions do not require an allocation, and the cost of reallocating is amortized. This means that a vector has very fast push operations (on average) at the back (as in, the end where push_back operates). However, inserting elsewhere in the vector is very expensive since this requires moving all the elements from the insertion point forward one position toward the back.
Structure of array versus array of structures
Linear memory is great. It provides fast access...
