11.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 an extensible way. An allocator can allocate and deallocate memory for its elements and initialize and destroy element memory. And it can perform each of these actions as separate steps.

Why bother?

Allocators were originally conceived during the initial development of the standard library when library developers realized that some classes that took a template parameter of type T could break if T did not have a default constructor. An allocator can create default values for types that don’t have their own default values. Similarly, an allocator can ensure memory is destroyed when we are finished with it. In short, the original new and delete operators did not handle all the cases required for advanced memory management.

We can handle types without a default value by giving users the option to specify the value to be used when we need a default:

void resize(size_t new_capacity, T default_value = T())
{
  reserve(new_capacity);
  std::fill(begin()+size_, begin()+capacity_, default_value);
  size_ = new_capacity;
}

This form of resize() will use T(), unless the user provides an alternative. For example:

bag<double> stuff;
stuff.resize(100);        // add 100 doubles all == 0.0
stuff.resize(200, 3.14);  // add 200 copies of 3.14
stuff.resize(300, 0.0);   // add 200 copies of 0.0 (redundant)

The destructor 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 an manipulate uninitialized storage. This is where allocator comes in. A simplified allocator looks like this:

template<class T>
  class allocator {

    using value_type    = T;
    // other types and constructors omitted

    T*   allocate  (size_t n);        // allocate space to n objects of T
    void deallocate(T* p, size_t n);  // deallocate n objects of T
                                           // starting at location p

    void construct(T* p, const T& value);  // construct a value of T in p
    void destroy  (T* p);                  // destroy the T in p

  };

These 4 functions provide the core capabilities of an allocator:

11.5.1. Using std::allocator_traits

An allocator is exactly what a container 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 a allocator type parameter and a local variable to store an instance of the allocator. Although you can use an allocator directly, the allocator interfaces are deprecated, and 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(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.

void reserve(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 (size_t i = 0; i < new_capacity; ++i) {
    memory::construct(allocator_, &new_data[i], data_[i]);
  }

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

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

More to Explore

You have attempted of activities on this page