This is the fifth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

This article introduces the new sequential container forward_list in c++11, based on STL source analysis of the container’s overall implementation and data structure.

Note that I am using the GCC7.1.0 compiler, which is also the version of the standard library source code.

As usual, take a look at the outline of the article, as follows:

1. What is forward_list

Forward_list is a new sequential container for STL in c++11. The actual class declaration is in the bits/forward_list.h header file. The forward_list class is a class template based on a single linked list structure. Let’s take a look at its implementation based on the source code forward_list.

2. Introduction to the forward_list peripheral class

Before we get into the formal introduction to the class template forward_list, let’s take a look at the other types it uses, which are preconditions for understanding the source implementation of forward_list.

2.1 class template_Fwd_list_nodeAnd its base class_Fwd_list_node_base

The class template _Fwd_list_node declaration is also in the bits/forward_list.h header.

template<typename _Tp>
    struct _Fwd_list_node
    : public _Fwd_list_node_base
    {
      _Fwd_list_node() = default;

      __gnu_cxx::__aligned_buffer<_Tp> _M_storage;

      _Tp*
      _M_valptr() noexcept
      { return _M_storage._M_ptr(); }

      const _Tp*
      _M_valptr() const noexcept
      { return_M_storage._M_ptr(); }};Copy the code

__gnu_cxx::__aligned_buffer<_Tp>;

template<typename _Tp>
    struct __aligned_buffer
    : std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value>
    {
      typename
	std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value>::type _M_storage; . };Copy the code

Aligned_storage (); aligneD_storage (); aligneD_storage ();

template<std::size_t _Len, std::size_t _Align =
	   __alignof__(typename __aligned_storage_msa<_Len>::__type)>
    struct aligned_storage
    {
      union type
      {
	unsigned char __data[_Len];
	struct __attribute__(((aligned__((_Align)))) { } __align;
      };
    };
Copy the code

Aligned_storage ::type: aligned_storage::type ::type aligned_storage::type ::type aligneD_storage ::type ::type aligneD_storage ::type Struct __attribute__((__aligned__((_Align)))) {})) struct __attribute__((__aligned__((_Align)))) {})) struct __attribute__((__aligned__((_Align)))) {}));

In this case, __aligned__((_Align)) specifies how many bytes are aligned, where _Align is the number of aligned bytes passed in through the non-type template parameter.

Aligned_storage: sizeof(_Tp); STD ::alignment_of<_Tp>::value; The second argument is based on alignment_of, which tells the compiler to align according to the bytes-alignment rules of the template type _Tp.

So basically, _Fwd_list_node::_M_storage is just a struct variable with the size of the template type _Tp.

Next, let’s look at the implementation of the base class _Fwd_list_node_base. Its source code is as follows:

struct _Fwd_list_node_base
  {
    _Fwd_list_node_base() = default;

    _Fwd_list_node_base* _M_next = nullptr; . };Copy the code

This class is simple. It just defines a pointer to a member, so I won’t say more about that.

2.2 Forward_list base class _Fwd_list_base

The forward_list base class _Fwd_list_base declaration is also in the bits/forward_list.h header file. Once again, let’s take a look at its member variables

  template<typename _Tp, typename _Alloc>
    struct _Fwd_list_base
    {
    protected:
	typedef __alloc_rebind<_Alloc, _Tp> 		  _Tp_alloc_type;
      typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
      typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
      struct _Fwd_list_impl 
      : public_Node_alloc_type { _Fwd_list_node_base _M_head; . }; _Fwd_list_impl _M_impl; . };Copy the code

Class _Fwd_list_base is also a class template. It has only one member variable, _M_impl, of the struct type, _Fwd_list_impl, defined in the class template. Its base class is _Node_alloc_type. However, the actual type of the base class is allocator<_Fwd_list_node<_Tp>>, which is a memory allocator. So _Fwd_list_impl is actually a memory extractor defined in the class template _Fwd_list_base, and it gets a memory allocator based on the template type, but it has one more member variable, _M_head, which we talked about in the last section, No more here.

3. Implementation of forward_list framework

Now that we’ve seen some of the class implementations around forward_list, let’s look at how to associate these classes with forward_list.

First, let’s look at the overall class diagram for forward_list.

Based on the above class diagram and the introduction of forward_list peripheral classes in the previous chapter, we summarize the overall class framework of the class template forward_list as follows:

  • classforward_listItself does not save data, only to achieve the insertion, deletion, query, construction and other interfaces, for programmers to use;
  • classforward_listIs the base class_Fwd_list_baseMember variables that hold data_M_implDeclared in the base class, the real operation of data is also completed based on the base class;
  • Member variables_M_implThe header node is saved in_M_head, the head node is the entry of the linked list;
  • The first node_M_headType is_Fwd_list_node_base, which contains only one member variable_M_next._M_nextIs a base class pointer that points to the next linked list node of type_Fwd_list_node<_Tp>, which contains two member variables, one that inherits from the base class_M_head, and a member variable defined by the class itself_M_storage.

At this point, we have some general knowledge of forward_list, but at this point we still don’t have a very clear memory implementation, so let’s take a look at what the memory structure of forward_list looks like as a line.

4. Forward_list construct implementation and memory structure

Forward_list has a variety of constructors, including the copy constructor, the default no-argument constructor, the parameter constructor, the move constructor, and so on. Here we take one of the parameters as an example. The constructor is declared as follows:

// The first argument is the number of elements the container needs to construct, the second argument is the value of each element, and the third argument is the allocator. The allocator is the template parameter specified by the class
forward_list(size_type __n, const _Tp& __value,
                   const _Alloc& __al = _Alloc())
      : _Base(_Node_alloc_type(__al))
      { _M_fill_initialize(__n, __value); }
Copy the code

This function first calls the base class constructor to specify the memory allocator. We’ll use the default for this, but I won’t go into more detail here.

Then call the function _M_fill_initialize for dynamic memory application and element assignment operations, the function source code implementation is as follows:

template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    _M_fill_initialize(size_type __n, const value_type& __value)
    {
        // The head node is a class object with a fixed address. Here we take the address of the head node and assign it to the temporary pointer __to
      _Node_base* __to = &this->_M_impl._M_head;
      for (; __n; --__n)
        {
          // Create a node and assign the node address to the _M_next of the previous node
          __to->_M_next = this->_M_create_node(__value);
          //__to refers to the node newly created in the previous line of code__to = __to->_M_next; }}Copy the code

To create a node, use the _M_create_node function. This function is implemented in the forward_list base class. The source code is as follows:

_Node* _M_get_node()
{
    // Here we use the specified memory allocator to request a space of _Fwd_list_node size and return the address pointing to that space to __ptr
	auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
    // Get the address of __ptr and return it
	return std::__addressof(*__ptr);
}
// The variable parameter template is used here. The detailed description of the variable parameter template is described in the last article. I won't say more about it here
template<typename. _Args> _Node* _M_create_node(_Args&&... __args) { _Node* __node =this->_M_get_node();
    __try
      {
    _Tp_alloc_type __a(_M_get_Node_allocator());
    typedef allocator_traits<_Tp_alloc_type> _Alloc_traits;
        // This is where the placement new is: :new ((void*)__node) _Node;
        // The constructor of the element type is called and assigned according to the function input
    _Alloc_traits::construct(__a, __node->_M_valptr(), std::forward<_Args>(__args)...) ; } __catch(...) {this->_M_put_node(__node);
        __throw_exception_again;
      }
    return __node;
}
Copy the code

In detail, as indicated in the above code comment, we can draw the forward_list memory structure according to the constructor invocation route as follows:

This is a typical single linked list structure with no data stored at the head node, so I won’t say more about it here.

Well, this article for you to introduce here, feel content useful to you, remember to click a like and follow oh ~