C++: Optimized list

Question

Some intensive profiling of my code revealed that a it spends a lot of time allocating space for vectors.
For Most of these vectors the size is known in advance so I call reserve() to pre-allocate the space.
For most of these vectors, the size is almost always very small - like 4 or 5 elements but on rare occasions it can be pretty large.
One additional optimization I thought about is to create my own container OptimizedList<T,N> . An instance of this object contains in itself N instances of T as a plain array and if the user tries to add more than N items, it starts using dynamic allocation for the extra items.

Is there a known implementation of this?

Answer 1

How about Qt's stack based variable length array?

Looks like the perfect match for your use case, mostly small arrays, which will be allocated on the stack (the fastest allocation, just a pair of add / sub instructions on a pointer) for small arrays, and on the heap for large ones.

It does however waste space.