There is a template parameter for STL containers to chose a custom allocator. It took a while, but I think I understand how it works. Somehow it isn't really nice because the given allocator type isn't used directly but it is rebound to the allocator of another type. Finally I can work with it.
After reading the API I recognized that there is also the possibility to give allocators as constructor parameter. But how do I know which kind of allocator the container uses, if it internally rebinds the given allocator from the template parameter?
Additionally I read that C++11 now uses scoped allocators which allow to reuse the allocator of a container for its containing containers. How does the implementation of a scoped allocator enabled container roughly differs from one that is not aware of scoped containers?
Unfortunately I wasn't able to find anything that could explain this. Thanks for answers!
The type of the allocator used by a container is defined by its constructor argument: it is exactly this type which is expected in the container's constructors. However, any allocator needs to be able to serve different types than the one it is defined for. For example, for a
std::list<T, A>
the allocator expected is capable to allocateT
object but it will never be used to allocate these object because thestd::list<T, A>
actually needs to allocate nodes. That is, the allocator will be rebound to allocate a different type. Unfortunately, this makes it hard to use an allocator to serve a specific type: You don't know the type the allocator will actually serve.With respect to scoped allocators it works quite straight forward: The container determines if it has any member with a constructor taking a matching allocator. If this is the case, it will rebind the allocator it used and passes this allocator to the member. What isn't that straight forward is the logic determining whether an allocator is being used. To determine if a member uses an allocator, the traits
std::uses_allocator<T, A>
is used: It determines ifT
has a nestedtypedef allocator_type
which and ifA
can be converted to this type. The rules for how member objects are constructed are described in 20.6.7.2 [allocator.uses.construction].In practice this means that allocators are useful for dealing with a pool used for a container and its members. In some contexts it may also work reasonable when similar sized objects are allocated, e.g. for any of the node based containers, to keep a pool of equal sized objects. However, it isn't necessary clear from the pattern used with allocator if they are, e.g., for the nodes or some strings contained with. Also, since the use of different allocation policies would change the type, it seems most reasonable to either stick with the default allocation or to use an allocator type which is a proxy for a polymorphic allocator actually defining the allocation policy. Of course, the moment you have stateful allocators, you may have objects with different allocators and e.g.
swap()
ing them might not work.Always supply an
Allocator<T>
to the constructor (whereT
is thevalue_type
of the container). The container will convert it to anAllocator<U>
is necessary whereU
is some internal data structure of the container. TheAllocator
is required to supply such converting constructors, e.g.:Well, to be more precise, C++11 has an allocator adaptor called
scoped_allocator_adaptor
:From C++11:
So you only get the scoped allocators behavior if you specify a
scoped_allocator_adaptor
as the allocator for your container.The key is that the container now deals with its allocator via a new class called
allocator_traits
instead of dealing with the allocator directly. And the container must useallocator_traits
for certain operations such as constructing and destructingvalue_type
s in the container. The container must not talk to the allocator directly.For example, allocators may provide a member called
construct
that will construct a type at a certain address using the given arguments:If an allocator does not provide this member,
allocator_traits
will provide a default implementation. In any event, the container must construct allvalue_type
s using thisconstruct
function, but using it throughallocator_traits
, and not using theallocator
directly:The
scoped_allocator_adaptor
provides customconstruct
functions whichallocator_traits
will forward to which take advantage of theuses_allocator
traits and passes the correct allocator along to thevalue_type
constructor. The container remains blissfully ignorant of these details. The container only has to know that it must construct thevalue_type
using theallocator_traits construct
function.There are more details the container must have to deal with to correctly handle stateful allocators. Though these details too are dealt with by having the container not make any assumptions but get all properties and behaviors via
allocator_traits
. The container can not even assume thatpointer
isT*
. Rather this type is found by askingallocator_traits
what it is.In short, to build a C++11 container, study up on
allocator_traits
. And then you get scoped allocator behavior for free when your clients use thescoped_allocator_adaptor
.