Date: 2014-07-19

Thomas Köppe <>

Allocator example: A simple dynamic container

Part of the Visitor’s Guide to C++ Allocators


We design a simple dynamic array that obtains storage from an allocator. We keep the container’s interface simple, and instead focus on the important allocator operations. The container is essentially a dynamic array whose size is fixed at construction. We only allow either value-initialising each element, or copy-initialising each element from a prototype. The interesting aspects for the purpose of this example lie in copying, moving, assigning and swapping the container, as well as in choosing its internal representation.

We summarise the design decisions so far.


Allocator support adds another level of subtlety to exception correctness. We would like to provide the strong exception guarantee everywhere (i.e. either an operation completes or has no effect).

The naive assumption is that swaps and moves should be exception-free, and that move-assignment and default construction should have the same exception specification. However, stateful allocators complicate the picture: move operations may turn into copy operations if the allocators are not equal.

In the sequel, we invite the reader to consider carefully for each function why and how the exception specification was chosen.


We start with a number of type aliases. Note in particular that the allocator_type type member is used by the uses-allocator construction.

#include <memory> #include <type_traits> #include <utility> template <typename T, typename Alloc = std::allocator<T>> class vlarray { public: using value_type = T; using allocator_type = Alloc; private: using traits = std::allocator_traits<allocator_type>; using pointer = typename traits::pointer; public: using size_type = typename traits::size_type; private: struct representation : allocator_type { pointer data; size_type size; explicit representation(allocator_type const & a, size_type n) : allocator_type(a), size(n) {} }; representation r;

Next, we build the accessor interface. Note that we need to convert from the allocator’s pointer type to the native pointer type.

public: value_type * data() noexcept { return std::addressof(*; } value_type const * data() const noexcept { return std::addressof(*; } value_type & operator[](size_type i) noexcept { return data()[i]; } value_type const & operator[](size_type i) const noexcept { return data()[i]; } size_type size() const noexcept { return r.size; } bool empty() const noexcept { return r.size == 0; } allocator_type get_allocator() const noexcept { return r; }

We could also offer an interface to obtain an element’s fancy address, which can be computed as std::pointer_traits<pointer>::pointer_to(operator[](i)). We have omitted this somewhat obscure feature here for brevity, and in any case we have not exposed the allocator’s pointer type to the user directly.

Now we get to the constructors and the destructor. We will use the modern signature for allocator-extended operations, which take two initial arguments, std::allocator_arg, alloc. The older convention of adding a single allocator argument as the last argument is arguably less readable and prone to ambiguities.

We have to allow our container to exist in an empty state, which is the state it should have after it has been moved from. We will also allow the container to be default-constructed to be in the empty state, and we provide a clear() function to put a container into the empty state.

Note that the default constructor may not be available if the allocator does not have an accessible default constructor. If it is available, its exception specification depends on the exception specification of the allocator’s default constructor.

// Construct new container from scratch constexpr vlarray() noexcept(std::is_nothrow_default_constructible<allocator_type>::value) : vlarray(std::allocator_arg, allocator_type()) {} constexpr vlarray(std::allocator_arg_t, allocator_type const & alloc) noexcept : r(alloc, 0) { = pointer(); } explicit vlarray(size_type n) : vlarray(n, value_type()) {} explicit vlarray(size_type n, value_type const & x) : vlarray(std::allocator_arg, allocator_type(), n, x) {} vlarray(std::allocator_arg_t, allocator_type const & alloc, size_type n) : vlarray(std::allocator_arg, alloc, n, value_type()) {} vlarray(std::allocator_arg_t, allocator_type const & alloc, size_type n, value_type const & x) : r(alloc, n) { allocator_type & a = r; pointer p = traits::allocate(a, size()); for (size_type i = 0; i != size(); ++i) { traits::construct(a, std::addressof(*p) + i, x); } = p; } // Destructor private: void internal_clear() noexcept { if (empty()) { return; } allocator_type & a = r; for (size_type i = 0; i != size(); ++i) { size_type k = size() - i - 1; traits::destroy(a, data() + k); } traits::deallocate(a,, size()); } public: ~vlarray() { internal_clear(); } void clear() noexcept { internal_clear(); = pointer(); r.size = 0; } // Construct container from existing container private: pointer internal_construct(allocator_type & a, value_type const * src, size_type n) { pointer p = traits::allocate(a, n); size_type current = 0; try { for (size_type i = 0; i != n; ++i, ++current) { traits::construct(a, std::addressof(*p) + i, src[i]); } return p; } catch (...) { do { traits::destroy(a, std::addressof(*p) + current); } while (current --> 0); traits::deallocate(a, p, n); throw; } } public: vlarray(vlarray const & rhs) : vlarray(std::allocator_arg, traits::select_on_container_copy_construction(rhs.r), rhs) {} vlarray(std::allocator_arg_t, allocator_type const & alloc, vlarray const & rhs) : r(alloc, rhs.r.size) { = internal_construct(r,, size()); } vlarray(vlarray && rhs) noexcept : r(rhs.r) { = pointer(); rhs.r.size = 0; } vlarray(std::allocator_arg_t, allocator_type const & alloc, vlarray && rhs) : r(alloc, rhs.r.size) { allocator_type & a = r; if (a == static_cast<allocator_type &>(rhs.r)) { =; = pointer(); rhs.r.size = 0; } else { = internal_construct(a,, size()); } }

We have introduced private helper functions internal_clear() and internal_construct, which will be used repeatedly. The latter function in particular encapsulates the strong exception guarantee nicely, since it will either return a pointer to a fully populated storage, or exit with an exception.

Finally we get to the most involved parts of the container design: assignment and swap. The details of these operations depend on the allocator POCCA, POCMA and POCS properties (“propagate on container {copy assignment, move assignment, swap}”).

Swapping is the easiest. Either the allocator has POCS, in which case it we swap the two allocator objects, or otherwise we may simply demand that the allocators compare equal, or the behaviour is undefined. With this precondition, we require no further branching.

void swap(vlarray & rhs) noexcept { std::swap(r, rhs.r); }

Assignment is trickier. We first need to deallocate the existing storage and then reallocate new storage with the appropriate allocator. For copy-assignment, the POCCA condition is relatively unobtrusive.

vlarray & operator=(vlarray const & rhs) { if (this == &rhs) { return *this; } pointer p; if (traits::propagate_on_container_copy_assignment::value) { allocator_type ra = rhs.r; p = internal_construct(ra,, rhs.size()); static_cast<allocator_type &>(r) = static_cast<allocator_type &>(rhs.r); } else { p = internal_construct(r,, rhs.size()); } internal_clear(); = p; r.size = rhs.size(); return *this; }

The most subtle part is move-assignment. If the allocator has POCMA, then we move-assign the allocator and take over the assigned resources, and no exceptions can arise in this case. If the allocator does not have POCMA, we can check dynamically whether the two allocators happen to be equal and then take over the assigned resources. Failing that, we have to make a copy of the data. Since this decision is a dynamic one, we cannot give a nothrowing exception specification. (This is bad: other containers, such as std::vector, can only move data efficiently if it can be moved without throwing. Otherwise, those containers have to fall back on copying. The moral is that allocators without POCMA are to be considered with great care.)

private: void internal_move_assign(vlarray && rhs, std::true_type) noexcept { internal_clear(); static_cast<allocator_type &>(r) = std::move(rhs.r); =; r.size = rhs.r.size; = pointer(); rhs.r.size = 0; } void internal_move_assign(vlarray && rhs, std::false_type) { if (static_cast<allocator_type &>(r) == static_cast<allocator_type &>(rhs.r)) { internal_clear(); =; r.size = rhs.r.size; = pointer(); rhs.r.size = 0; } else { pointer p = internal_construct(r,, rhs.size()); internal_clear(); = p; r.size = rhs.size(); } } public: vlarray & operator=(vlarray && rhs) noexcept(traits::propagate_on_container_move_assignment::value) { if (this != &rhs) { internal_move_assign(std::move(rhs), typename traits::propagate_on_container_move_assignment()); } return *this; } };