The C++ standard provides the guarantee that the content of a std::vector is stored contiguously. But does it states that the total occupied memory is:
S = C+N*sizeof(T)
- S is the total size on the stack AND on the heap
- C is the total size on the stack: C = sizeof(std::vector)
- N is the capacity of the vector
- T is the type stored
In other words, do I have the guarantee that there is no overhead per element ? And if I have no such guarantee is there any reason ?
EDIT: to be clear, if I take the example of a
std::list, it generally stores 2 extra pointers per element. So my question is: would a such implementation of a
std::vector be standard-compliant ?
Best How To :
For there to be any such guarantee, the standard would have to pass the requirement on to the interface of the allocator. It doesn't, so there isn't.
In practice though, as a quality of implementation issue, you expect that memory allocators probably have a constant overhead per allocation but no overhead proportional to the size of the allocation. A counter-example to this would be a memory allocator that always uses a power-of-two-sized block regardless of the size requested. This would be pretty wasteful for large allocations, but not forbidden either as a user-defined allocator or even as the system allocator used by
::operator new. It would create an overhead proportional to
N on average, assuming that the vector capacities don't happen to fit nicely.
Leaving aside the allocator, I don't believe there's anything in the standard to say that the vector can't allocate (for example) an extra byte per element and use it to store some flags for who-knows-what purpose. As others have remarked, the contiguousness requirement means that those extra bytes cannot lie between the vector elements. They would have to be in a separate allocation or all together at one end of the allocation.
There's at least one good reason that the standard doesn't forbid implementations from "wasting" space by using it to store data used for operations not required by the standard -- doing so would rule out many debugging techniques!