Re: [boost] Interest in StaticVector - fixed capacity vector

Subject: Re: [boost] Interest in StaticVector - fixed capacity vector
From: Stephan T. Lavavej (stl_at_[hidden])
Date: 2011-10-12 19:26:26

[Howard Hinnant]
> Fwiw, one can create allocators that allocate off the stack and then turn any container into a static_container.
> Here's an example vector, list and set:  http://home.roadrunner.com/~hinnant/stack_alloc.html

> This particular implementation will spill to heap if the static buffer is overrun.  But you could easily build
> another allocator that had another behavior.  Just doing an allocator and res-using existing allocator-aware
> containers (e.g. std::vector) seems like a win to me.

C++03 forbids "internal storage" allocators (when an allocator returns memory from "inside itself").

C++03 20.1.5 [lib.allocator.requirements]'s tables say (they don't copy/paste well, so I have to type them in by hand - these are only the relevant portions):

Variable  # Definition
T, U      # any type
X         # an Allocator class for type T
Y         # the corresponding Allocator class for type U
a, a1, a2 # values of type X&
b         # a value of type Y

expression # return type # assertion/note pre/post-condition
a1 == a2   # bool        # returns true iff storage allocated from each can be deallocated via the other
X a(b);    #             # post: Y(a) == b

Here's why this rules out "internal storage" allocators.

1. I start with Y b; which is MyAlloc<U> b;
2. I construct X a(b); which is MyAlloc<T> a(b);
3. I construct Y c(a), giving it a name for clarity.  That's MyAlloc<U> c(a).

b is the original MyAlloc<U>.  c is the doubly-rebound MyAlloc<U>.  They're required to compare equal, which means that storage allocated from one can be deallocated from the other and vice versa.

This is possible for stateless allocators (e.g. if you just call malloc/free), or stateful allocators that store things like heap handles (the heap handle is passed along by the rebinding constructor).  It is impossible for "internal storage" allocators, because b and c will have separate internal storage.

Also, consider how "internal storage" allocators affect moving and swapping containers.

Taking advantage of C++03's requirements, VC11 contains optimizations that will break "internal storage" allocators, even in the absence of moving/swapping. It avoids storing stateless allocators completely, and stores only one copy of a stateful allocator - rebinding it on the fly whenever it needs to allocate a secret node type, a super secret proxy type, etc. C++03's requirements guarantee that as long as the container keeps at least one copy of a stateful allocator around, regardless of the type that it's for, it can be rebound to any other type and service allocations for that type (i.e. keeping one copy around will keep all allocations around, regardless of their type).

C++03 has no objection to allocators returning memory that happens to live on the stack, as long as it is "separate" from the allocator itself and its lifetime is sufficient.

STL