This article has participated in the call for good writing activities, click to view: back end, big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!

This article introduces the overall implementation of the DEQUE container and its memory structure based on the source code of STL in GCC.

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

First, take a look at the mind map, as follows:

1. Deque container overall source code implementation introduction

A deque is a class template. Its declaration is in bits/stl_deque.h, and its implementation is in bits/deque.tcc. Let’s take a look at the implementation of the DeQUE around these two files.

Let’s take a look at the overall class diagram for deques:

Here’s a quick interpretation of the class diagram:

  • Deque container protection inherits from class templates_Deque_base, that is,_Deque_baseIs the base class of the deque, and memory allocation and freeing are done through the base class.
  • Container headers and iterators are stored in structure member variables_M_implIt inherits from the alias type_Tp_alloc_typeThe final memory allocation is actually done through it;
  • The deque uses its own iterator_Deque_iterator, does not directly use the public iterator in the STL, and the iterator stores the current address, the first address, the last address, and the current node.

There are a few types that are hard to understand. The first is _Tp_alloc_type, which is an alias. I’ve written a previous article about this type: Three diagrams that take you through the MEMORY allocator in the STL

Then there are the _Elt_pointer and _Map_pointer types, whose archetypes are as follows:

// where _Tp is the template type
#if __cplusplus < 201103L
      typedef _Deque_iterator<_Tp, _Tp&, _Tp*>	     iterator;
      typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
      typedef _Tp*					 _Elt_pointer;
      typedef _Tp**					_Map_pointer;
#else
    private:
      template<typename _Up>
	using __ptr_to = typename pointer_traits<_Ptr>::template rebind<_Up>;
      template<typename _CvTp>
	using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_to<_CvTp>>;
    public:
      typedef __iter<_Tp>		iterator;
      typedef __iter<const _Tp>		const_iterator;
      typedef __ptr_to<_Tp>		_Elt_pointer;
      typedef __ptr_to<_Elt_pointer>	_Map_pointer;
#endif
Copy the code

Before c++11, they were directly pointer types. After c++11, we used the rebind attribute for class templates called pointer_traits. For a full explanation of pointer_traits, see the following article:

Traits from the c++ library pointer extractor

If you look closely, the rebind of POinter_traits results in the same type as a pointer, but it’s probably a little cleaner because template types are a little more formal.

2. What is the memory structure of the deque

In the source code, the deque container constructor is overloaded. Let’s take a look at one of the typical types. The constructor prototype is as follows:

// Construct a deque of size n, where all elements are values and __a is the default allocator
deque(size_type __n, const value_type& __value, const allocator_type& __a = allocator_type())
      : _Base(__a, __n)
      { _M_fill_initialize(__value); }
Copy the code

For the whole construction call process, let’s look at the following figure:

We can see that the three constructors only initialize the allocator and other member variables. The real memory allocation is the template function _M_initialize_map, and then the template function _M_fill_initialize, which fills the container with data.

Take a look at the template function _M_initialize_map, the source code is as follows:

//deque initializes the number of elements
template<typename _Tp, typename _Alloc>
    void _Deque_base<_Tp, _Alloc>::_M_initialize_map(size_t __num_elements)
    {
     // If sizeof(_Tp)<512, __deque_buf_size returns 512/sizeof(_Tp), otherwise returns 1. _Tp is the element type of the container, so this returns the default number of elements in a block memory. A subsequent buffer refers to a block of memory
     //__num_nodes = number of elements/number of memory elements + 1 to obtain the total number of buffers
      const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
				  + 1);
     //_S_initial_map_size Defaults to 8, depending on the Max call to get the final block memory number
      this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
					   size_t(__num_nodes + 2));
     // We apply dynamic memory for nodes based on the type and number of buffers. We do not apply dynamic memory for blocks that actually store elements
      this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
     // According to the following two lines, the first and last nodes of _M_map are actually reserved and will not be used for now
      _Map_pointer __nstart = (this->_M_impl._M_map
			       + (this->_M_impl._M_map_size - __num_nodes) / 2);
      _Map_pointer __nfinish = __nstart + __num_nodes;
      __try
	{ 
        // This function applies dynamic space to each buffer based on a node loop, with one node pointing to one buffer
          _M_create_nodes(__nstart, __nfinish); }
      __catch(...)
	{
	  _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
	  this->_M_impl._M_map = _Map_pointer();
	  this->_M_impl._M_map_size = 0;
	  __throw_exception_again;
	}
    //_M_set_node initializes the corresponding position and iterator position of the node, and holds the start and end positions of the node using member variables
      this->_M_impl._M_start._M_set_node(__nstart);
      this->_M_impl._M_finish._M_set_node(__nfinish - 1);
      this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
      this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
					+ __num_elements
					% __deque_buf_size(sizeof(_Tp)));
    }
Copy the code

According to the above code and comments, we can draw a conclusion that the deque first applies for a segment of contiguous memory, and then each node in the contiguous memory points to a buffer, as shown in the figure below:

In the figure above, node represents nodes, which are a segment of continuous memory, and each node points to an independent buffer. From the perspective of data structure, a Deque container is actually a double-ended queue.

Let’s look at another template function, _M_fill_initialize, which has the following source code:

template <typename _Tp, typename _Alloc>
    void
    deque<_Tp, _Alloc>::
    _M_fill_initialize(const value_type& __value)
    {
      _Map_pointer __cur;
      __try
        {
          // The loop fills the container with the value __value for each element
          for (__cur = this->_M_impl._M_start._M_node;
	       __cur < this->_M_impl._M_finish._M_node;
	       ++__cur)
           // The __uninitialized_fill_A function constructs each element based on its value and acts as a placement new
            std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
					__value, _M_get_Tp_allocator());
          std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
				      this->_M_impl._M_finish._M_cur,
				      __value, _M_get_Tp_allocator());
        }
      __catch(...)
        {
          std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), _M_get_Tp_allocator()); __throw_exception_again; }}Copy the code

This function is relatively simple, and the comments make it clear, so I won’t go into more details here.

Let’s give a use case that looks like this:

#include <deque>

int main(a)
{
	std::deque<int> deq(1024.100);
	return 0;
}
Copy the code

A deque is simply defined with 1024 elements and 100 for each element.

Well, this article is for you to introduce here, if you think the content is useful, remember to click a like oh ~