12.5. Allocators

Those of you who have been paying attention may have noticed most containers in the standard library have declarations like:

template< class T,
          class Allocator = std::allocator<T>>
class vector;

What is the second template type parameter for?

An allocator manages the memory of each element stored in the container. The job of an allocator is similar to what the operators new and delete do, but in a more generic and extensible way. An allocator can allocate and deallocate memory for its elements and containers can separately initialize and destroy objects in that memory. The important point is that allocation and construction are separate steps, and destruction and deallocation are also separate steps.

Why bother?

Allocators were originally conceived during the initial development of the standard library to allow containers to be independent of a single hard-coded memory allocation strategy. They also support the way containers work internally: a container may allocate storage now, but construct objects in that storage later. In short, a container needs more control than a simple use of new[] and delete[] provides.

  • Designers realized a container should not be tied to exactly one allocation strategy. Allocators allow specialized code to choose a memory allocation scheme appropriate for its runtime environment.

  • Containers separate the memory allocation and deallocation from the initialization and destruction of their elements.

    A call to vector::reserve(n) allocates memory for at least n elements. The constructor for each element will not be called.

For example, a container can reserve space without constructing any values. When it later needs to create new elements, it can require the caller to provide the values to construct. This avoids requiring T to be default-constructible:

void resize(std::size_t new_size, const T& value)
{
  reserve(new_size);
  while (size_ < new_size) {
    push_back(value);
  }
}

This form of resize does not need to use T(). The caller supplies the value used to initialize new elements. For example:

bag<double> stuff;
stuff.resize(200, 3.14);  // add copies of 3.14 until size is 200
stuff.resize(300, 0.0);   // add copies of 0.0 until size is 300

The destruction problem is harder to address. We need to deal with a data structure that may contain a mix of some initialized data and some uninitialized data. Typically, we are very careful to avoid uninitialized data and the associated programming errors. Now as the developers of generic containers we have to handle this problem so that users of these containers don't have to.

First we need a way to get and manipulate uninitialized storage. This is where allocator comes in. A simplified modern allocator interface looks like this:

template<class T>
class allocator {
public:
  using value_type = T;

  // other types and constructors omitted

  T* allocate(std::size_t n);
  void deallocate(T* p, std::size_t n);
};

The allocator itself allocates and deallocates raw storage. Containers should use allocator_traits to construct and destroy objects in that storage.

C++20 Feature

Older allocator examples often show direct allocator member functions named construct and destroy. Those direct members of allocator were deprecated in C++17 and removed in C++20. Use allocator_traits instead.

These operations provide the core capabilities containers need:

  • Allocate memory of a size suitable to hold an object of type T without initializing it.

  • Construct an object of type T in uninitialized space using allocator_traits.

  • Destroy an object of type T using allocator_traits, returning the memory space to the uninitialized state.

  • Deallocate uninitialized memory of size suitable for an object of type T.

12.5.1. Using std::allocator_traits

An allocator is what a container uses to separate memory allocation from object construction, and memory deallocation from object destruction.

How does a container use an allocator? First, as in the standard library, we need an allocator type parameter and a local variable to store an instance of the allocator. Although you can use an allocator directly, some old direct allocator member functions are no longer part of C++20. We are going to use the allocator_traits interface. The allocator_traits class template provides the standardized way to access various properties of allocators. The standard containers and other standard library components access allocators through this template, which makes it possible to use any class type as an allocator.

template<class T, class Allocator = std::allocator<T>>
class bag {

  Allocator allocator_;

  // . . .
};

The allocator_traits interface consists entirely of static members - no object instance exists and it is completely stateless, however the syntax is a bit verbose, which is why I frequently alias it in a class:

template<class T, class Allocator = std::allocator<T>>
class bag {

  Allocator allocator_;
  using memory = std::allocator_traits<Allocator>;

  // . . .
};

Now except for using our allocator object, the class is unchanged. Container users can ignore the allocator unless they need a bag that manages memory for its elements in some unusual way.

The only class functions that require modification are those that deal directly with memory:

  • object construction and destruction

  • memory allocation and deallocation

void reserve(std::size_t new_capacity)
{
  // never decrease allocation
  if (new_capacity <= capacity_) {
    return;
  }
  // allocate new space
  T* new_data = new T[new_capacity];

  // copy into new space
  std::copy(begin(), end(), new_data);

  // delete old memory
  delete[] data_;

  // point to the new data
  data_ = new_data;
  capacity_ = new_capacity;
}

Refactoring the original version of reserve to use an allocator involves several steps. This sketch shows the main idea, but it omits the exception-safety details required in a production container.

void reserve(std::size_t new_capacity)
{
  // never decrease allocation
  if (new_capacity <= capacity_) {
    return;
  }

  // allocate new space
  T* new_data = memory::allocate(allocator_, new_capacity);

  // copy into new space
  for (std::size_t i = 0; i < size_; ++i) {
    memory::construct(allocator_, &new_data[i], data_[i]);
  }

  // destroy old elements
  for (std::size_t i = 0; i < size_; ++i) {
    memory::destroy(allocator_, &data_[i]);
  }

  // deallocate old space
  if (capacity_ != 0) {
    memory::deallocate(allocator_, data_, capacity_);
  }
  data_ = new_data;
  capacity_ = new_capacity;
}

For real container code, if construction of one of the new elements throws, the already-constructed new elements must be destroyed and the newly allocated memory must be deallocated before the exception continues. That is one reason writing standard-library-quality containers is difficult.

For most programs, do not write your own allocator or container. Use the standard containers and RAII types first. If a program needs to choose a memory allocation strategy at runtime, the C++17 pmr library provides polymorphic allocators and memory resources designed for that purpose.

More to Explore