Allocator example: A simple dynamic container
Part of the Visitor’s Guide to C++ Allocators
Overview
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.
- The container should be parametrised on a value type and an allocator.
- We represent the managed data by a pointer to the allocated memory and the
number of elements.
- Since we need to store the allocator object inside the container, we will
use nested auxiliary structures to take advantage of base layout optimisations,
particularly aimed at the case where the allocator is stateless (empty). (Our
solution is not the best possible, since a stateful allocator may mean that the
data pointer will not be stored at the beginning of the class and thus every
element access will require an offset computation. This can be avoided with more
elaborate class design.)
- We need a name:
vlarray, for "variable length array", seems apt.
Exceptions
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.
Implementation
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(*r.data); }
value_type const * data() const noexcept { return std::addressof(*r.data); }
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)
{ r.data = 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);
}
r.data = 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, r.data, size());
}
public:
~vlarray()
{
internal_clear();
}
void clear() noexcept
{
internal_clear();
r.data = 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)
{
r.data = internal_construct(r, rhs.data(), size());
}
vlarray(vlarray && rhs) noexcept
: r(rhs.r)
{
rhs.r.data = 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))
{
r.data = rhs.r.data;
rhs.r.data = pointer();
rhs.r.size = 0;
}
else
{
r.data = internal_construct(a, rhs.data(), 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.data(), rhs.size());
static_cast<allocator_type &>(r) = static_cast<allocator_type &>(rhs.r);
}
else
{
p = internal_construct(r, rhs.data(), rhs.size());
}
internal_clear();
r.data = 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.data = rhs.r.data;
r.size = rhs.r.size;
rhs.r.data = 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.data = rhs.r.data;
r.size = rhs.r.size;
rhs.r.data = pointer();
rhs.r.size = 0;
}
else
{
pointer p = internal_construct(r, rhs.data(), rhs.size());
internal_clear();
r.data = 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;
}
};