Across languages, vector is the #1 most common and useful container. Hashtable might be #2.
I used to feel that a vector (and hashtable) can grow its “backing array” without heap. There’s global memory and stack memory and perhaps more. Now I think that’s naive.
- Global area is allocated at compile time. The array would be fixed in size.
- For an array to be allocated on stack, the runtime must know its size. Once it’s allocated on that stack frame, it can’t grow beyond that stack frame.
- In fact, any array can’t grow at all.
The vector grows its backing array by allocating a bigger array and copying the payload. That bigger array can’t be in global area because this type on-demand reallocation is not compile-time.
Anything on heap is accessed by pointer. Vector owns this hidden pointer. It has to delete the array on heap as in RAII. No choice.
Now the painful part — heap allocation is much slower than stack allocation. Static allocation has no runtime cost at all after program starts.
