Date: 2016-09-06

Thomas Köppe <tkoeppe@google.com>

“Under Construction”
A visitor’s guide to C++ allocators

Contributors and collaborators welcome!

Contents

  1. Introduction
  2. Background
  3. Allocators
  4. Pointers
  5. From allocation to construction
  6. Requirements for allocators and pointers
  7. Allocator identity
  8. Standard library container requirements
  9. Propagating allocators
  10. Examples
  11. Open issues
  12. Acknowledgements

Introduction

Allocators are perhaps one of the most pervasive, yet least loved parts of the C++ standard library. This guide attempts to explain what allocators are and how library authors are supposed to use them. On this brief journey through one of the wilder realms of C++ we will meet allocator traits, pointer traits, fancy pointers and cast operations that will shake even the strongest minds.

Background

C++ classes often manage dynamic resources as part of their implementation. Typical examples of such classes are dynamic containers, strings, function wrappers, file handles, mutexes, etc. There is one distinguished resource which is needed to create new C++ objects: memory. Given appropriate memory (i.e. of the right size and alignment) at some address p, we can bring to life a new C++ object of type T by saying ::new (p) T. This is the fundamental idea underpinning all dynamic containers.

However, the mechanism by which suitable memory is obtained is system-specific and essentially opaque to the user. C++ offers a default mechanism, ::operator new(sizeof(T)), but there is little to no control over what this does. Since the logic of a dynamic container does not depend on the specifics of how memory is obtained, general wisdom dictates that the design of container classes should be decoupled from the memory allocation policy. Enter allocators.

For the remainder of this guide, it will be useful to have a few concrete and representative examples in mind. We pick two, which are ubiquitous and well-known. Note that the dynamic resource allocation and deallocation is entirely opaque to the user, who only ever observes the contained element values. The container owns the elements and is responsible for their storage and lifetime.

Allocators

The C++ standard library defines the notion of an allocator, which is an object used to parametrise memory allocation and object construction. The point that an allocator has two separate responsibilities is worth repeating: an allocator knows how to obtain memory, and it knows how to construct objects.

To understand why allocators are useful, let us step back into a world without allocators. Creating a dynamic object can be broken down into separate steps, which are typically hidden behind the convenience expressions new and delete:

Broken down operations
void * addr = ::operator new(sizeof(T)); // allocation T * p = ::new (addr) T(1, 'x', true); // construction p->~T(); // destruction // (no placement-delete in normal execution flow) ::operator delete(addr); // deallocation
Convenient use
T * p = ::new T(1, 'x', true); // allocation and construction ::delete p; // destruction and deallocation

The broken-down operations show the mental model that allocators are intended to parametrise. To achieve this, an allocator defines four fundamental operations: allocate, deallocate, construct, and destroy, which generalise, respectively, to the allocation function (::operator new), the deallocation function (::operator delete), placement-new, and the explicit destructor call.

To go into further detail, we need to establish some terminology. The standard reference is section [allocator.requirements].

The standard header <memory> defines a trait class template allocator_traits, which provides a uniform interface to allocators. The allocator traits reflect certain members of the actual allocator type, but they also provide defaults, so that a custom allocator only needs to provide a minimal set of information that differs from the defaults. (The traits template may be specialised for user-defined types, and different defaults may be provided in a specialisation.)

Suppose a is an allocator of type Alloc. Let us write AllocTraits = std::allocator_traits<Alloc>. We say that “a is an allocator for T”, where T = AllocTraits::value_type. This means that a knows how to obtain and release memory to store objects of type T. To do so, we call AllocTraits::allocate(a, n), and we obtain storage for n objects of type T.

So far so good. However, we can also use a to construct objects, either explicitly or via a default mechanism. But not just objects of type T, but any type of object! This is very much intentional. Recall our example of a linked list. We would like to be able to allocate memory for an entire list node, but we only need to construct objects of list element type. So it is convenient if a single allocator knows how to construct objects of different types.

Here is how this works. For any pointer C * c, and any list of arguments args..., we can say AllocTraits::construct(a, c, args...). This either invokes ::new (static_cast<void *>(c)) C(std::forward<Args>(args)...), or, if Alloc defines a suitable member function, a.construct(c, std::forward<Args>(args)...). In either case, the result is than an object of type C is constructed from the arguments at location c, and that afterwards *c is that object. In other words, a new object is constructed in a given piece of raw memory. Similarly, we can call AllocTraits::destroy(a, c) to destroy the object. This defaults to c->~C(), or calls a.destroy(c) if that expression is well-formed.

Pointers

So far we have dived right into object construction, but skirted the more fundamental question of how to allocate memory. Our allocator a for T can only allocate memory for a contiguous sequence of objects of type T. To allocate memory for n such objects, we say:

AllocTraits::pointer p = AllocTraits::allocate(a, n);

The allocator communicates memory in terms of customisable type AllocTraits::pointer. This defaults to the unsurprising T *, but it may be any user-defined type. When AllocTraits::pointer is not the same as T *, we say that the allocator uses a fancy pointer. Whatever the type is, it must satisfy the concept of a NullablePointer, which we describe below. The allocator also defines a corresponding “const pointer” via AllocTraits::const_pointer and “void pointers” via AllocTraits::void_pointer and AllocTraits::const_void_pointer. Pointers are implicitly convertible to const pointers. Pointers and void pointers are mutually convertible in the usual way, that is, a pointer is implicitly convertible to a void pointer, and a void pointer can be converted explicitly to any non-void pointer (all subject to not discarding qualifiers). However, there is no analogue for const_cast, that is, it is not generally possible to convert a fancy pointer to a less qualified version.

(The typical example of a fancy pointer is an “offset pointer” into shared memory that allows separate processes to access the same object in shared memory; the offset pointer stores only an offset, relative to the pointer object’s own address. This example demonstrates the complexity of the problem: The vector’s own memory must be in shared memory; each member list must allocate from the same shared memory; each string in the list must allocate from the shared memory, and all references are expressed in terms of relative offsets. However, each process must be able to obtain a proper, “normal” address for each object, even if the object is stored in shared memory, by virtue of the dereference operation.)

Now that we have convinced ourselves that pointers are not an altogether trivial matter, it is time to introduce the final level of abstraction that the standard library has to offer: pointer traits. This is a class template, called std::pointer_traits, also defined in <memory>, and among other things it allows us to obtain pointers to objects (including fancy pointers). Let us write AllocPtrTraits = std::pointer_traits<AllocTraits::pointer>. The pointer traits define an element type via AllocPtrTraits::element_type, which is either just the allocator’s value type T if AllocTraits::pointer == T *, or otherwise it is reflected out of the fancy pointer type. The important operation provided by pointer traits is obtaining a pointer to an element: AllocPtrTraits::pointer_to(r) produces a pointer, either by computing std::addressof(r) if AllocTraits::pointer == T *, or otherwise by a mechanism specified by the fancy pointer class. See below for details. Finally, it is a requirement that AllocTraits::pointer must be dereferenceable (producing a value of type AllocTraits::value_type) by providing operator* and operator->.

The NullablePointer requirements

The type AllocTraits::pointer may not be arbitrary, but rather it must satisfy a set of requirements called NullablePointer which capture the semi-regular features of the built-in pointer types (default-constructible, copyable, copy-assignable, destructible, all without throwing exceptions; and copying and assigning have the usual semantics), as well as the existence of a special null value. Specifically, if a type T satisfies the NullablePointer requirements, then it must have a distinguished null value, which compares equal only to itself, can be tested for by Boolean conversion, and value-initialisation of T (i.e. T()) produces the null value. (Therefore, the following holds: assert(!T()).)

The fact that AllocTraits::pointer can be any type that satisfies these requirements has consequences for library authors: It is not generally permissible to attempt to produce a null pointer from an initialiser such as NULL or a literal 0. The pointer type may not have appropriate constructors, or the constructor overload may be ambiguous, or it may not have the desired effect. The only way to produce a null value of type AllocTraits::pointer is to value-initialise it or to initialize it with a value of type std::nullptr_t.

Moreover, note that if the pointer type is a class type, then it may not be trivially constructible, since the default constructor may be required to initialise its state to the null value. Therefore, common “small-container” optimisations that represent the container class members as a union of a set of pointers and raw storage need be careful to provide the union with appropriate constructors.

In summary, it is tempting to write container code as though the pointer type were T *, but in order to make a container work with arbitrary standard conforming allocators, care must be taken to talk about pointers only in the language of the NullablePointer requirements.

Fancy pointer summary

We write T = AllocTraits::value_type for brevity, and we assume that T is an unqualified object type.

Putting it all together, we arrive at a self-consistency identity for dereferenceable pointers:

ptr == std::pointer_traits<AllocTraits::pointer>::pointer_to(*trueaddress(ptr))

From allocation to construction

Suppose now we have an allocator Alloc a; for a type T and we would like to allocate memory and construct the object from some given arguments. We continue writing AllocTraits for std::allocator_traits<Alloc>. We need the following sequence of operations.

Alloc a; // given T-allocator AllocTraits::pointer ptr = AllocTraits::allocate(a, 1); // space for one element AllocTraits::construct(a, trueaddress(ptr), x, y, z); // constructs a T(x, y, z) AllocTraits::destroy(a, trueaddress(ptr)); // ~T() AllocTraits::deallocate(a, ptr, 1); // deallocate element space

Requirements for allocators and pointers

The full set of requirements is spread out in the C++ standard across the sections [allocator.requirements], [allocator.traits] and [pointer.traits]. We collect a few of the essential requirements here. We continue writing Alloc for some, generic allocator type, and AllocTraits and AllocPtrTraits for its related allocator traits and pointer traits type.

In all of the above we ignored the alternative possibility of specialising std::allocator_traits directly for the desired allocator type. So rather than defining Alloc::pointer, it is also permissible to specialise std::allocator_traits<Alloc> and define its member pointer. In that fashion, it is possible for an allocator to have fancy pointers even it if does not define a pointer member. (Such a design would be obscure and cumbersome, though, since the Alloc::allocate member function still needs to have a return type that matches AllocTraits::pointer.) The above requirements are to be understood with this concession in mind.

Allocator identity

Allocators are strange animals in the C++ bestiary. The operational identity of an allocator object is not really connected with the object itself, but rather, the identity is spread out over a whole family of related allocators. Given an allocator a of type Alloc for a type T, we can always obtain an allocator for a different type U like this:

std::allocator_traits<Alloc>::rebind_alloc<U> b(a); assert(a == b);

We call b a rebound copy of a for U.

In this construction, all that matters is that we construct one allocator from another one. This allows allocators to pass on some internal state. (However, if the allocator is empty and DefaultConstructible, then there is no distinction between constructing a rebound allocator from an original allocator and just default-constructing the rebound allocator.) The upshot is that we can obtain allocators for any type from any one given allocator, and all the allocators thus obtained are compatible in the sense that memory that was obtained with any one allocator in the family can always be deallocated with a new allocator built from any one allocator in the family.

In fact, it is required that for any two allocators a1, a2 of the same type, a1 == a2 holds whenever memory allocated with one can be deallocated with the other. This must be true when we have Alloc a1, a2(a1);, but it may also be true in other cases. And there is more: For any two allocators Alloc a and AllocTraits::rebind_alloc<U> b, the comparison a == b is defined as a == AllocTraits::rebind_alloc<Alloc::value_type>(b).

So we can say that the identity of an allocator family lies in the shared state much more than in any one object, and if there is no shared state (as is the case with std::allocator<T>), then all allocators obtained by rebinding one allocator are in the same, compatible family. Let us summarise:

We can apply rebound copies repeatedly to arrive at a self-consistency identity for allocators. For any Alloc a and any type U:

a == std::allocator_traits<AllocTraits::rebind_alloc<U>>::rebind_alloc<Alloc::value_type>(AllocTraits::rebind_alloc<U>(a))

Standard library container requirements

The standard library container requirements (cf. [container.requirements.general]) mandate that the construct and destroy functions of the allocator of a container only be used to construct and destroy container elements, but not any internal data structures. In our linked list example, this means that in order to comply with the container requirements, the list nodes themselves may not be constructed with the allocator, only the actual data elements must be so constructed. This may be implemented by designing the list node type so that it has a trivial constructor and destructor, so that allocated memory may be treated directly as a list node as soon as storage for it has been obtained.

An example: the linked list

This example is worth spelling out in detail. Suppose we have elements of type T, list nodes of type Node<T>, and an allocator a for T of type Alloc. For example:

template <typename T> struct Node {   using NodeTraits = std::allocator_traits<Alloc>::rebind_traits<Node>;   NodeTraits::pointer prev;   NodeTraits::pointer next;   typename std::aligned_storage<sizeof(T), alignof(T)>::type storage; };

We need a helper function to access the storage as though it were a T:

T * storage(Node<T> * n) { return reinterpret_cast<T *>(&n->storage); }

Now we create a new node with a value constructed from some arguments, and then destroy it right away:

Alloc a; // given T-allocator using NodeTraits = std::allocator_traits<Alloc>::rebind_traits<Node<T>>; // node allocator traits type NodeTraits::allocator_type n_a(a); // node allocator NodeTraits::pointer ptr = NodeTraits::allocate(n_a, 1); // space for one node NodeTraits::construct(n_a, storage(trueaddress(ptr)), x, y, z); // constructs a T(x, y, z) NodeTraits::destroy(n_a, storage(trueaddress(ptr))); // ~T() NodeTraits::deallocate(n_a, ptr, 1); // deallocate node space

(We have assumed here for simplicity that Node<T> is trivially constructible, so that a node’s lifetime begins as soon as storage for it is allocated.)

Note that n_a is a rebound copy for Node<T> of the original allocator a. Moreover, we use n_a and not a to construct elements, even though the elements are actually of type T, which is the value type of a and not of n_a. Allocators are designed to be able to construct arbitrary objects, not just objects of their own value type. Practically, this allows us to only keep a copy of the node allocator around, and never store a copy of the original allocator.

Another example: vector

Let us also study how a contiguous storage container like std::vector should use allocators. The situation is rather simpler than for the linked list. A vector of T only needs one allocator a for T, which we continue to call Alloc. To obtain storage of capacity n, we only need to call AllocTraits::allocate(a, n) and convert the result into a true pointer, say p, of type T *, to the first available slot.

Given this pointer to the start of the sequence, we can start constructing elements. Very crudely, we can default-construct k elements with no-throwing constructors like this:

for (T * x = p; x != p + k; ++x) { AllocTraits::construct(a, x); }

If exceptions may occur, we also need to track our progress, catch exceptions, and in the event of an exception destroy the already constructed elements before rethrowing the caught exception.

The contiguous array is an example where the allocator fits most naturally. There is no need to rebind or to construct elements of different types. The allocator neatly separates the allocation of memory from the construction of objects.

Propagating allocators

A single dynamic container with an allocator is a fine thing, but it is only the first step. Two separate sets of questions arise naturally.

  1. What happens when you copy the container? What kind of allocator does the copy get? What happens when you assign to a container or swap to containers? Are the allocators swapped, too, or is only the data swapped?
  2. If the container contains types which themselves require an allocator, how can the contained elements be made aware of the container’s allocator so that they may use compatible allocators?

The two problems are orthogonal to one another. Both require a fair amount of machinery.

Lateral allocator propagation: copy, assign, swap

If an allocator is stateless, then all container objects that use the same allocator type have compatible allocators, and there is no problem. For example, swapping two containers can be achieved by simply exchanging internal memory handles; either container’s allocator knows how to deallocate the memory.

However, when allocators are stateful, the situation is more complicated. We distinguish three situations which require a policy decision:

The allocator propagation operations are generally not allowed to throw exceptions. Specifically, if POC{CA, MA, S} is true, then {copy-assignment, move-assignment, swap} must not throw exceptions.

When an allocator is stateless, that is, when any two instances always compare equal, then it should have POCMA be true. Otherwise, containers must perform a dynamic equality check and cannot promise non-throwing moves. (The original std::allocator got this wrong; see the issues list below.)

Deep allocator propagation: the uses_allocator construction

Suppose we have a vector of linked lists, and the vector uses some allocator of our choice. Even if we used a list type that would also be configured to use an allocator of the same type as our vector’s allocator, we still need a mechanism for ensuring that the vector elements (which themselves are lists) are constructed with the correct allocator (namely with a suitably rebound copy of the vector allocator).

To tackle this problem, we need a standard convention how allocators are passed to class constructors. The standard library provides the following machinery.

  1. There is yet another trait class template, std::uses_allocator<X, A>, which contains a Boolean member constant std::uses_allocator<X, A>::value. For brevity, let us write UsesAlloc<X> = std::uses_allocator<X, Alloc>::value for the value of this trait for our allocator class Alloc. Then UsesAlloc<X> is true if either the trait has been thus specialised, or otherwise if X defines a member type X::allocator_type = Alloc. In other words, UsesAlloc<X> tells us whether the class X uses the allocator Alloc.
  2. If UsesAlloc<X> is true, then we assume that either The second form is the “legacy form” employed by the traditional standard library containers; the first form is the recommended, new style, which is unambiguous. Classes whose constructors accept allocators in this fashion are sometimes called “allocator-extended”. (Not every class that has allocator-extended constructors actually consumes an allocator. An example is std::tuple, for which the uses_allocator trait is specialised to true, so that allocators may be propagated through tuples of types which themselves require an allocator.)
  3. Now it gets complicated. We will present only the simplest case, but the standard library provides far more advanced machinery. Suppose both our out vector and our inner linked list type should use an allocator of type Alloc, and they should use compatible allocators (i.e. their all their allocators should compare equal). Suppose further we already have an allocator Alloc a, and that both our vector and our list class take the new form of constructor. Then we use a new allocator:

    ScopedAlloc = std::scoped_allocator_adaptor<Alloc> ScopedAllocTraits = std::allocator_traits<ScopedAlloc>

    We construct our vector like this:

    using ListType = List<T, ScopedAllocTraits::rebind_alloc<T>>; using VecType = Vector<ListType, ScopedAllocTraits::rebind_alloc<ListType>>; VecType v(std::allocator_arg, a);

    When the vector calls std::allocator_traits<...>::construct(get_allocator(), p, arg1, arg2, arg2), this calls get_allocator().construct(p, arg1, arg2, arg2) on the scoped allocator adaptor. The adaptor in turn recognises that *p has the uses_allocator trait, and thus it forwards the call to std::allocator_traits<AllocTraits::rebind_alloc<ListType>>::construct(outer_allocator(), std::allocator_arg, *this, arg1, arg2, arg3). In this fashion, the allocator is always rebound-copied into the constructors of the element values, as long as those have the uses_allocator trait set.

Examples

A few complete end-to-end examples are available on separate pages:

The complete code from the examples is available in the example_code subdirectory in the GitHub repository.

Open issues

The specification of allocators in the C++ standard underwent significant changes from C++03 to C++11. As result, the wording that is included in C++11 contains a few points that are vague, unclear or outright impossible to implement. These issues are being addressed by the standardisation committee in library defect reports. Once a defect report is accepted, we consider it part of the language.

Here follows a partial list of issues that affect allocators.

Acknowledgements

This guide has benefited greatly from feedback, suggestions and corrections from the C++ community. In particular, Jonathan Wakely has repeatedly provided valuable insights, and Jens Maurer helped getting the offset pointer example right.