STL Container: Constructor's Allocator parameter and scoped allocators

Question

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!

Answer 1

But how do I know which kind of allocator the container uses, if it internally rebinds the given allocator from the template parameter?

Always supply an Allocator<T> to the constructor (where T is the value_type of the container). The container will convert it to an Allocator<U> is necessary where U is some internal data structure of the container. The Allocator is required to supply such converting constructors, e.g.:

template <class T> class allocator {
    ...
    template <class U> allocator(const allocator<U>&);

Additionally I read that C++11 now uses scoped allocators which allow to reuse the allocator of a container for its containing containers.

Well, to be more precise, C++11 has an allocator adaptor called scoped_allocator_adaptor:

template <class OuterAlloc, class... InnerAllocs>
class scoped_allocator_adaptor : public OuterAlloc
{
    ...
};

From C++11:

The class template scoped_allocator_adaptor is an allocator template that specifies the memory resource (the outer allocator) to be used by a container (as any other allocator does) and also specifies an inner allocator resource to be passed to the constructor of every element within the container. This adaptor is instantiated with one outer and zero or more inner allocator types. If instantiated with only one alloca- tor type, the inner allocator becomes the scoped_allocator_adaptor itself, thus using the same allocator resource for the container and every element within the container and, if the elements themselves are con- tainers, each of their elements recursively. If instantiated with more than one allocator, the first allocator is the outer allocator for use by the container, the second allocator is passed to the constructors of the container’s elements, and, if the elements themselves are containers, the third allocator is passed to the elements’ elements, and so on. If containers are nested to a depth greater than the number of allocators, the last allocator is used repeatedly, as in the single-allocator case, for any remaining recursions. [Note: The scoped_allocator_adaptor is derived from the outer allocator type so it can be substituted for the outer allocator type in most expressions. — end note ]

So you only get the scoped allocators behavior if you specify a scoped_allocator_adaptor as the allocator for your container.

How does the implementation of a scoped allocator enabled container roughly differs from one that is not aware of scoped containers?

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 use allocator_traits for certain operations such as constructing and destructing value_types 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:

template <class T> class Allocator {
     ...
    template<class U, class... Args>
        void construct(U* p, Args&&... args);
};

If an allocator does not provide this member, allocator_traits will provide a default implementation. In any event, the container must construct all value_types using this construct function, but using it through allocator_traits, and not using the allocator directly:

allocator_traits<allocator_type>::construct(the_allocator, *ugly details*);

The scoped_allocator_adaptor provides custom construct functions which allocator_traits will forward to which take advantage of the uses_allocator traits and passes the correct allocator along to the value_type constructor. The container remains blissfully ignorant of these details. The container only has to know that it must construct the value_type using the allocator_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 that pointer is T*. Rather this type is found by asking allocator_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 the scoped_allocator_adaptor.

Answer 2

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 allocate T object but it will never be used to allocate these object because the std::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 if T has a nested typedef allocator_type which and if A 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.