Understand the STL memory allocator in three pictures

This article analyzes the implementation principle and use of the memory allocator in the standard library based on the source code.

To clarify, I am using the GCC7.1.0 compiler, and the standard library source code is also in this version.

Let’s start with a mind map to see how this article covers the STL memory allocator and extractor, as follows:

In fact, the operation of memory allocation in STL contains two contents: memory allocator and memory extractor.

The use of memory allocators in vectors

As mentioned in the previous article, vector is essentially a dynamic array. It is implemented using the library’s memory allocator.

template<typename _Tp, typename _Alloc>
    struct _Vector_base
    {
      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
	rebind<_Tp>::other _Tp_alloc_type;
      typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
       	pointer;

      struct _Vector_impl
      : public_Tp_alloc_type { ... }; .public:
      _Vector_impl _M_impl;

      pointer
      _M_allocate(size_t __n)
      {
	typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
	return__n ! =0 ? _Tr::allocate(_M_impl, __n) : pointer();
      }
      ...
     };
class vector : protected_Vector_base<_Tp, _Alloc> {... };Copy the code

Vector inherits from _Vector_base, which allocates memory in the _Vector_impl structure, which inherits from _Tp_alloc_type, The full type for type _Tp_alloc_type is __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other, The _M_allocate function is used to allocate memory in the following way:

__gnu_cxx::__alloc_traits<_Tp_alloc_type>::allocate(_Tp_alloc_type, __n);
Copy the code

We don’t know how the memory is allocated until we know what’s going on in this line of code, and many other containers in the STL are implemented using this allocator, so we don’t know how to use containers until we know what’s going on in this allocator.

STL memory divider and extractor

1. Class relationship between distributor and extractor

To understand what they are, I need to understand the relationship between them, and I’ve traced the STL source code back to its roots.

To be honest, I wasted a lot of brain cells trying to figure out this relationship, because these types are really long and dizzy, so I drew a picture like this:

If so difficult to remember the type of description in words will go crazy, or a picture description is better, ha, ha, ha, this class inheritance should be be clear at a glance, including various types where the header files are marked clearly, naturally, for extractor and distributor exactly is what, we also have a preliminary concept, For example, in chapter 1, the __alloc_traits type is an extractor and the _Tp_alloc_type type is an allocator.

There is one thing we need to say about this file, allocator. H:

template<typename _Tp>
    class allocator: public __allocator_base<_Tp>
Copy the code

The new_allocator_base class is __allocator_base<_Tp>. The new_allocator_base class is __allocator_base.

template<typename _Tp>
    using __allocator_base = __gnu_cxx::new_allocator<_Tp>;
Copy the code

The __allocator_base type is an alias of the new_allocator class, so we have this inheritance relationship.

2. What are dispensers and extractors

We continue where we left off in chapter 1 by intercepting the following code from the stl_vector.h header:

template<typename _Tp, typename _Alloc>
struct _Vector_base
{
	typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
	struct _Vector_impl: public _Tp_alloc_type
	{
	...
	};
	_Vector_impl _M_impl;
    // Call _M_allocate to allocate __n
    pointer _M_allocate(size_t __n)
	{
		typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
		return__n ! =0 ? _Tr::allocate(_M_impl, __n) : pointer();
	}
    ...
};
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class vector : protected _Vector_base<_Tp, _Alloc>;
Copy the code

Obviously, the first thing we need to know is what the type _Tp_alloc_type is. This is another lengthy nesting process, as shown below:

So the other type is allocator<_Tp1>. Note that the allocator

is used first and then goes to the allocator with template. Vector

= allocator

vector

= allocator

So _Tp_alloc_type is actually an allocator

type. Some books refer to this nesting process as extraction, so I’ll call __alloc_traits an extractor that fetches an allocator.

Transpose the above call, and here it is:

allocator<int> _M_impl;
__gnu_cxx::__alloc_traits<allocator<int> > : :allocate(_M_impl, __n);
Copy the code

Take a look at the implementation of __gnu_cxx::__alloc_traits::allocate, as follows:

static pointer
    allocate(_Alloc& __a, size_type __n)
    { return __a.allocate(__n); }
Copy the code

Allocator

. Allocate. Class Allocator does not allocate memory. New_allocator does allocate memory.

pointer
      allocate(size_type __n, const void* = 0)
      {
	if (__n > this->max_size())
	  std::__throw_bad_alloc();

#if __cpp_aligned_new
	if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
	  {
	    std::align_val_t __al = std::align_val_t(alignof(_Tp));
	    return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp), __al));
	  }
#endif
	return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
      }
Copy the code

Finally, the ::operator new function is called to allocate memory, so an allocator is called a memory allocator.

Finally, the operation process of the dispenser and extractor is described, so the release of dynamic memory is the same process, not to say more here.

The use of memory allocator

1. Construct and destroy functions are described

In the case of memory allocator, allocate calls allocate, which ultimately calls operator new, and free memory which calls operator delete, so I won’t go into more detail here.

Let’s take a look at the operation of constructing and destructing data in the allocated dynamic memory. The interception code is as follows:

__p is a pointer to current memory, and __val is a value to be stored in memory
__p = new _Tp(__val);
void construct(pointer __p, const _Tp& __val)
      { ::new((void *)__p) _Tp(__val); }
// Destruction is easier to understand, calling the element destructor directly
void destroy(pointer __p) { __p->~_Tp(); }
Copy the code

How to use new:

#include <iostream>
using namespace std;

int main(a)
{
	int *p = new int;
	new (p) int(10);
	cout << "*p=" << *p << endl;
}
Copy the code

You can drop that, too.

2. Max_size function

Max_size = max_size (); max_size (); max_size (); max_size ();

size_type max_size(a) const _GLIBCXX_USE_NOEXCEPT
      { return size_t(- 1) / sizeof(_Tp); }
Copy the code

Okay, size_t, the reason we use size_t is to be cross-platform, so each platform may define a different type of size_t, but generally size_t is an unsigned integer, so if it’s an unsigned long, that’s 4294967295, divided by the size of that element, I’ve got the maximum number of elements that a container can hold

3. Use the Allocator class

Let’s use this class directly. The code is as follows:

#include <iostream>
#include <bits/allocator.h>
using namespace std;

int main(a)
{
	allocator<int> alloc;
	allocator<int>::size_type size = 5;
	allocator<int>::pointer ptr = alloc.allocate(size);
	for (int i = 0; i< size; i++)
	{
		alloc.construct(ptr+i, i+1);
	}

	for (int i = 0; i< size; i++)
	{
		cout << "alloc[" << i << "] =" << ptr[i] << endl;
	}
    // The destruction of memory must be done manually because the destructor of the Allocator class did nothing
	alloc.deallocate(ptr, size);

	return 0;
}
Copy the code

Why does the standard library use a memory allocator

I don’t know, I guess it’s to keep the containers assigned a unified interface, that is, standardization.