本篇文章介绍一下c++11中新增的顺序容器forward_list，基于stl的源码分析一下该容器的整体实现及数据结构。
说明一下，我用的是gcc7.1.0编译器，标准库源代码也是这个版本的。
按照惯例，还是先看一下本文大纲，如下：
1. forward_list是什么
forward_list是c++11为STL新增加的一种顺序容器，使用的时候包含头文件forward_list即可，真实的类声明位于头文件bits/forward_list.h中，类forward_list是一个类模板，基于单链表结构实现，下面我们就来基于forward_list的源码来看下它的具体实现。
2. forward_list周边类介绍
在正式开始介绍类模板forward_list之前，我们先了解下它所使用到的其他类型的介绍，这些类型是理解forward_list源码实现的前置条件。
2.1 类模板_Fwd_list_node和它的基类_Fwd_list_node_base
类模板_Fwd_list_node声明同样位于头文件bits/forward_list.h中，先看下类声明，如下：
1template<typename _Tp> 2 struct _Fwd_list_node 3 : public _Fwd_list_node_base 4 { 5 _Fwd_list_node() = default; 6 7 __gnu_cxx::__aligned_buffer<_Tp> _M_storage; 8 9 _Tp* 10 _M_valptr() noexcept 11 { return _M_storage._M_ptr(); } 12 13 const _Tp* 14 _M_valptr() const noexcept 15 { return _M_storage._M_ptr(); } 16 };
该类定义了一个成员变量_M_storage，这个成员变量类型是__gnu_cxx::__aligned_buffer<_Tp>，同样是一个类模板，看看类模板__aligned_buffer的类声明，如下：
1template<typename _Tp> 2 struct __aligned_buffer 3 : std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value> 4 { 5 typename 6 std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value>::type _M_storage; 7 ...... 8 };
可以看到其实它是基于另外一个类aligned_storage实现的，且以这个基类中声明的类型type定义了一个同样的成员变量_M_storage，接着看类aligned_storage实现：
1template<std::size_t _Len, std::size_t _Align = 2 __alignof__(typename __aligned_storage_msa<_Len>::__type)> 3 struct aligned_storage 4 { 5 union type 6 { 7 unsigned char __data[_Len]; 8 struct __attribute__((__aligned__((_Align)))) { } __align; 9 }; 10 };
基于以上代码，可以看出类型aligned_storage::type其实是一个联合体类型，该联合体的第一个字段很明朗，就是以模板类型_Tp的长度定义了一个无符号字符数组，但第二个字段__align就比较奇怪了，他的类型是struct __attribute__((__aligned__((_Align)))) { }，整体而言这是一个结构体，但大括号里面为空，说明该结构体是没有字段的，那么它到底是什么呢？
其实__attribute__是gcc的一个扩展用法，它允许在该关键字后面的双括号里面指定某些特殊属性，这里的__aligned__((_Align))就是指定了按多少个字节对齐，其中的_Align是通过非类型模板形参传入的对齐字节数。
我们在看下，这里的使用场景下类模板aligned_storage的实参是sizeof(_Tp), std::alignment_of<_Tp>::value，第一个实参就是模板类型_Tp的长度，第二个实参是基于alignment_of实现的，其实就是告诉编译器，根据模板类型_Tp的字节对齐规则去对齐。
所以简单来说，其实_Fwd_list_node::_M_storage就是一个结构体变量而已，它的大小是模板类型_Tp的大小。
接下来我们再看看基类_Fwd_list_node_base的实现，它的源码如下：
1struct _Fwd_list_node_base 2 { 3 _Fwd_list_node_base() = default; 4 5 _Fwd_list_node_base* _M_next = nullptr; 6 ...... 7 8 };
这个类就比较简单哈，就是定义了一个成员指针而已，这里不再多说。
2.2 forward_list的基类_Fwd_list_base
forward_list的基类_Fwd_list_base声明同样位于头文件bits/forward_list.h中，同样的，先看看它有哪些成员变量，我们截取一段源码，如下
1 template<typename _Tp, typename _Alloc> 2 struct _Fwd_list_base 3 { 4 protected: 5 typedef __alloc_rebind<_Alloc, _Tp> _Tp_alloc_type; 6 typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type; 7 typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; 8 struct _Fwd_list_impl 9 : public _Node_alloc_type 10 { 11 _Fwd_list_node_base _M_head; 12 ...... 13 }; 14 _Fwd_list_impl _M_impl; 15 ...... 16 };
类_Fwd_list_base也是一个类模板，它只有一个成员变量_M_impl，该成员变量类型也是在这个类模板中定义的结构体类型_Fwd_list_impl，它的基类是_Node_alloc_type，这个类型比较复杂，但结合我们之前写的内存萃取器和内存分配器的说明，经过一番推导，可知这个基类真正的类型是allocator<_Fwd_list_node<_Tp>>，这是一个内存分配器，所以实际上_Fwd_list_impl它可以说是类模板_Fwd_list_base里面定义的一个内存萃取器，它根据模板类型取得一个内存分配器，只不过它多保存了一个成员变量_M_head而已，_M_head的类型我们在上一小节里面说了，这里不再多说。
3. forward_list框架实现
前面介绍了forward_list周边的一些类实现，接下来我们看看怎么把这些类与forward_list关联起来。
首先呢，我们还是来看一下forward_list的整体类图，如下：
基于以上类图以及上一章对于forward_list周边类的介绍，我们对类模板forward_list的整体类框架实现总结如下：
- 类
forward_list本身不保存数据，只实现了插入、删除、查询、构造等接口，供程序员们使用； - 类
forward_list的基类是_Fwd_list_base，保存数据的成员变量_M_impl声明于该基类中，真正对数据的操作也都是基于该基类完成的； - 成员变量
_M_impl中保存了头结点_M_head，头结点是链表的入口； - 头结点
_M_head类型是_Fwd_list_node_base，该类型只包含一个成员变量_M_next，_M_next是一个基类指针，它指向下一个链表节点，每个节点类型是_Fwd_list_node<_Tp>，该类型含两个成员变量，一个是继承于基类的_M_head，还有一个是该类本身定义的成员变量_M_storage。
到这里，对forward_list我们就有了一些整体的认知了，但此时我们还是对于它的内存结构实现不是特别清晰，接下来就以forward_list的构造为一条线来详细看下最后它的内存结构是怎样的。
4. forward_list构造实现及内存结构
forward_list有很多种构造函数，包括拷贝构造、默认无参构造、有参构造、移动构造等，这里我们以其中一种有参构造为例，该构造函数声明如下：
1//第一个参数为容器需构造的元素数量，第二个参数为每个元素的值，第三个参数是分配器，其中分配器是类的模板参数指定，这里我们使用默认的即可 2forward_list(size_type __n, const _Tp& __value, 3 const _Alloc& __al = _Alloc()) 4 : _Base(_Node_alloc_type(__al)) 5 { _M_fill_initialize(__n, __value); }
该函数首先调用基类构造函数指定内存分配器，关于这一点我们使用默认的即可，这里不再多说。
然后调用了函数_M_fill_initialize进行动态内存申请及元素赋值等操作，该函数源码实现如下：
1template<typename _Tp, typename _Alloc> 2 void 3 forward_list<_Tp, _Alloc>:: 4 _M_fill_initialize(size_type __n, const value_type& __value) 5 { 6 //头节点是类对象，地址固定，这里取头节点地址赋给临时指针__to 7 _Node_base* __to = &this->_M_impl._M_head; 8 for (; __n; --__n) 9 { 10 //创建一个节点，且将节点地址赋给上一节点的_M_next 11 __to->_M_next = this->_M_create_node(__value); 12 //__to指向上一行代码新创建的节点 13 __to = __to->_M_next; 14 } 15 }
该函数就比较简单了，具体作用注释也写明了，我们接下来看看具体创建节点是怎么样的，节点创建使用函数_M_create_node，该函数实现在forward_list基类中，源码如下：
1_Node* _M_get_node() 2{ 3 //这里使用指定内存分配器申请一个_Fwd_list_node大小的空间，并返回指向该空间的地址给__ptr 4 auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); 5 //获取__ptr的地址并返回 6 return std::__addressof(*__ptr); 7} 8//这里使用了变参数模板，关于变参数模板的详细说明，我在上一篇文章中详细说明了，这里不再多说 9template<typename... _Args> 10_Node* _M_create_node(_Args&&... __args) 11{ 12 _Node* __node = this->_M_get_node(); 13 __try 14 { 15 _Tp_alloc_type __a(_M_get_Node_allocator()); 16 typedef allocator_traits<_Tp_alloc_type> _Alloc_traits; 17 //这里是placement new的用法，做了二次分配 18 ::new ((void*)__node) _Node; 19 //这里会根据函数入参调用元素类型的构造函数并进行赋值 20 _Alloc_traits::construct(__a, __node->_M_valptr(), 21 std::forward<_Args>(__args)...); 22 } 23 __catch(...) 24 { 25 this->_M_put_node(__node); 26 __throw_exception_again; 27 } 28 return __node; 29}
详细的说明，在上面代码的注释中都写明了，那么根据构造函数的调用路线，我们可以画出forward_list内存结构如下：
这是一个典型的头节点不存储数据的单链表结构，这里就不再多说啦。 好了，本篇文章就为大家介绍到这里，觉得内容对你有用的话，记得顺手点个赞和关注哦~