Memory Management with std::allocator

What is common between all containers of the Standard Template Library? They have a type parameter Allocator that is by default std::allocator. The job of the allocator is to manage the lifetime of its elements. That means allocating and deallocating memory for its elements and initializing and destroying them.

I write in this post about the containers of the Standard Template Library, but this includes std::string. For simplicity reasons, I will use the term container for both.

What is special about std::allocator?

On the one hand, it makes a difference if std::allocator allocates elements for a std::vector or pairs of std::map. 

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


template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

On the other hand, an allocator needs a bunch of attributes, methods, and functions to do its job.

The interface

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Attributes
value_type                               T
pointer                                  T*
const_pointer                            const T*
reference                                T&
const_reference                          const T&
size_type                                std::size_t
difference_type                          std::ptrdiff_t
propagate_on_container_move_assignment   std::true_ty
rebind                                   template< class U > struct rebind { typedef allocator<U> other; };
is_always_equal                          std::true_type

// Methods
constructor
destructor
address
allocate
deallocate
max_size
construct
destroy

// Functions
operator==
operator!=

In short, here are the essential members of std::allocator<T>.

The inner class template rebind (line 10) is one of these important members. Thanks to the class template, you can rebind a std::allocator of type T to a type U. The heart of std::allocate are the two methods allocate (line 17) and deallocate (line 18). Both methods manage the memory in which the object is initialized with construct (line 20) and destroyed with destroy (line 21). The method max_size (line 19) returns the maximum number of objects of type T for which std::allocate can allocate memory. 

Of course, you can directly use std::allocator.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// allocate.cpp

#include <memory>
#include <iostream>
#include <string>
 
int main(){
  
  std::cout << std::endl;

  std::allocator<int> intAlloc; 

  std::cout << "intAlloc.max_size(): " << intAlloc.max_size() << std::endl;
  int* intArray = intAlloc.allocate(100);

  std::cout << "intArray[4]: " << intArray[4] << std::endl;
 
  intArray[4] = 2011;

  std::cout << "intArray[4]: " << intArray[4] << std::endl;
 
  intAlloc.deallocate(intArray, 100);

  std::cout << std::endl;
 
  std::allocator<double> doubleAlloc;
  std::cout << "doubleAlloc.max_size(): " << doubleAlloc.max_size() << std::endl;
  
  std::cout << std::endl;

  std::allocator<std::string> stringAlloc;
  std::cout << "stringAlloc.max_size(): " << stringAlloc.max_size() << std::endl;
 
  std::string* myString = stringAlloc.allocate(3); 
 
  stringAlloc.construct(myString, "Hello");
  stringAlloc.construct(myString + 1, "World");
  stringAlloc.construct(myString + 2, "!");
 
  std::cout << myString[0] << " " << myString[1] << " " << myString[2] << std::endl;
 
  stringAlloc.destroy(myString);
  stringAlloc.destroy(myString + 1);
  stringAlloc.destroy(myString + 2);
  stringAlloc.deallocate(myString, 3);
  
  std::cout << std::endl;
  
}

I used in the program three allocators. One for an int (line 11), one for a double (line 26), and one for a std::string (line 31). Each allocator knows the maximum number of elements it can allocate (lines 14, 27, and 32).

Now to the allocator for int: std::allocator<int> intAlloc (line 11). With intAlloc you can allocate an int array of 100 elements (line 14). The access to the 5th element is not defined because, firstly, it has to be initialized. That changes in line 20. Thanks to the call intAlloc.deallocate(intArray, 100) (line 22)  I deallocate the memory.  

The handling of the std::string allocator is more complex. The stringAlloc.construct calls in den lines 36 - 38 trigger three constructor calls for std::string. The three stringAlloc.destroy calls (lines 42 - 44) do the opposite. At the end (line 34), the memory of myString is released.

And now the output of the program.

C++17

With C++17, the interface of std::allocator becomes a lot easier to handle. A lot of its members are deprecated.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// Attributes
value_type                               T
propagate_on_container_move_assignment   std::true_ty
is_always_equal                          std::true_type

// Methods
constructor
destructor
allocate
deallocate

// Functions
operator==
operator!=

But the key answer is this post is still missing.

Why does a container need an allocator?

I have three answers.

1. The container should be independent of the underlying memory model. For example, the  Intel Memory Model on x86 architectures uses six variants:tiny, small, medium, compact, large, and huge. I want to stress the point explicitly. I speak from the Intel Memory Model, not the memory model as the base of multithreading.
2. The container can separate the memory allocation and deallocation from initializing and destroying their elements. Therefore, a call of vec.reserve(n) of a  std::vector vec allocates only memory for at least n elements. The constructor for each element will not be executed. (Sven Johannsen)
3. You can adjust the allocator of the container precisely to your needs. Therefore, the default allocators are optimized for not-so-frequent memory calls and big memory areas. Under the hood, the C function std::malloc will typically be used. Therefore, an allocator using preallocated memory can significantly boost performance. An adjusted allocator also makes a lot of sense if you need a deterministic timing behavior for your program. With the default allocator of a container, you have no guarantee of how long a memory allocation will take. Of course, you can use an adjusted allocator to give you enriched debugging information.  

What's next?

Which strategies for requesting memory exist? That's the question I want to answer in the next post.