C++ STL容器(二) —— list 底层剖析

计划写几篇关于C++ STL容器底层剖析的文章，主要基于的是MSVC的实现，本篇先从比较简单的 list 入手，个人感觉文章更偏于代码的具体实现，而不是原理的讲解，所以前置需要你了解链表的相关算法，如果有问题欢迎评论区指出。

文章目录

数据结构
UML 类图
代码解析
- 默认构造函数
- 插入节点
- 删除节点
- 清空容器
- 析构函数
小结

数据结构

之前知道的C++ STL容器里的 list 是双向链表，看完 MSVC 里的实现，更准确地说其 list 是一个双向循环的链表，并且有一个哨兵节点。

UML 类图

MSVC 内部的实现还是比较复杂的，所以在深入代码实现之前，先梳理下 list 相关的 UML 类图，这里 list 封装了操作这个双向链表的方法，且可以看作是双向链表+分配器的组合，而实际的双向链表结构其实本体是 _List_val 其保存了链表的哨兵节点和链表的实际长度。而每个链表上的节点信息由 _List_node 类定义。

对于 list 中节点的插入也封装成了一个操作类 _List_node_emplace_op2

代码解析

由于相关的操作和代码很多，所以这里只挑一些我觉得比较常用的操作进行分析，管中窥豹一下了。

默认构造函数

先从默认构造函数入手，下面是源码：

    list() : _Mypair(_Zero_then_variadic_args_t{}) {_Alloc_sentinel_and_proxy();}

下面是 _MyPair 里的构造函数，首先匹配上的是 _Zero_then_variadic_args_t 为首参数的构造函数，其分别调用了 _Ty1 的无参构造函数，和 _Myval2 的有参构造函数，这里的 _Ty1 就是我们的分配器，我们不关注，_Myval2 就是保存了我们的双向链表 _List_val。

    template <class... _Other2>constexpr explicit _Compressed_pair(_Zero_then_variadic_args_t, _Other2&&... _Val2) noexcept(conjunction_v<is_nothrow_default_constructible<_Ty1>, is_nothrow_constructible<_Ty2, _Other2...>>): _Ty1(), _Myval2(_STD forward<_Other2>(_Val2)...) {}

而这里 _List_val 其实是没传参数的构造函数，具体代码如下，就是初始化链表长度为0，_Myhead 是哨兵节点指针，初始为NULL：

_List_val() noexcept : _Myhead(), _Mysize(0) {} // initialize data

回到 list()，后续调用 _Alloc_sentinel_and_proxy()，这里翻译就是分配哨兵和代理，本质上就是给哨兵节点分配内存，然后将其的 _Next 和 _Prev 都指向自身，_Construct_in_place 具体实现是 ::new (static_cast<void*>(_STD addressof(_Obj))) _Ty(_STD forward<_Types>(_Args)...); 就是个 placement new 在已分配好的内存上构建对象，最后将 _Myhead 指向 _Newhead 我们就保存了哨兵节点的指针。这里还有一部分代码是关于容器代理的(和迭代器有关)，博主还没有完全弄懂，等后续全部理解了，再出相关文章讲解，本篇只关注于 list 本身。

    void _Alloc_sentinel_and_proxy() {auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());_Container_proxy_ptr<_Alty> _Proxy(_Alproxy, _Mypair._Myval2);auto& _Al     = _Getal();auto _Newhead = _Al.allocate(1);_Construct_in_place(_Newhead->_Next, _Newhead);_Construct_in_place(_Newhead->_Prev, _Newhead);_Mypair._Myval2._Myhead = _Newhead;_Proxy._Release();}

以 list<int> 为例看看 _Mypair 具体保存了什么。

插入节点

无论是 push_front、push_back、insert 最后调用的都是 _Emplace 方法：

    void push_front(const _Ty& _Val) {_Emplace(_Mypair._Myval2._Myhead->_Next, _Val);}void push_back(const _Ty& _Val) {_Emplace(_Mypair._Myval2._Myhead, _Val);}iterator insert(const_iterator _Where, const _Ty& _Val) { // insert _Val at _Where
#if _ITERATOR_DEBUG_LEVEL == 2_STL_VERIFY(_Where._Getcont() == _STD addressof(_Mypair._Myval2), "list insert iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2return _Make_iter(_Emplace(_Where._Ptr, _Val));}

那么我们深入看下 _Emplace 方法。

    template <class... _Valty>_Nodeptr _Emplace(const _Nodeptr _Where, _Valty&&... _Val) { // insert element at _Wheresize_type& _Mysize = _Mypair._Myval2._Mysize;if (_Mysize == max_size()) {_Xlength_error("list too long");}_List_node_emplace_op2<_Alnode> _Op{_Getal(), _STD forward<_Valty>(_Val)...};++_Mysize;return _Op._Transfer_before(_Where);}

首先是获取到链表的长度，看看是否超过了最大长度的限制，一般是 $2^{64} - 1$ 。
构造了一个操作类的对象。
++_Mysize 增加链表的长度。
调用 _Transfer_before 插入节点。

那么看下这个操作类的构造函数：

    template <class... _Valtys>explicit _List_node_emplace_op2(_Alnode& _Al_, _Valtys&&... _Vals) : _Alloc_construct_ptr<_Alnode>(_Al_) {this->_Allocate();_Alnode_traits::construct(this->_Al, _STD addressof(this->_Ptr->_Myval), _STD forward<_Valtys>(_Vals)...);}

this->_Allocate() 就是用分配器分配一块_List_node大小的内存。
然后 construct 在这块内存上构造，就是把 _List_node._Myval 给设置好，但它的 _Prev 和 _Next 都还未设置。

最后就是通过 _Op._Transfer_before(_Where) 设置好 _Prev 和 _Next，本质就是一个简单的链表插入节点，在 _Insert_next 前插入节点，对于一开始无节点的链表(只有一个哨兵节点)，就是插入到哨兵节点的前面。

    pointer _Transfer_before(const pointer _Insert_before) noexcept {const pointer _Insert_after = _Insert_before->_Prev;_Construct_in_place(this->_Ptr->_Next, _Insert_before);_Construct_in_place(this->_Ptr->_Prev, _Insert_after);const auto _Result    = this->_Ptr;this->_Ptr            = pointer{};_Insert_before->_Prev = _Result;_Insert_after->_Next  = _Result;return _Result;}

删除节点

对于 pop_front 和 pop_back 内部调用的是 _Unchecked_erase，这里哨兵节点的前驱节点是链表的最后一个节点，哨兵节点的后继节点是链表的第一个节点：

void pop_front() noexcept /* strengthened */ {
#if _CONTAINER_DEBUG_LEVEL > 0_STL_VERIFY(_Mypair._Myval2._Mysize != 0, "pop_front called on empty list");
#endif // _CONTAINER_DEBUG_LEVEL > 0_Unchecked_erase(_Mypair._Myval2._Myhead->_Next);}void pop_back() noexcept /* strengthened */ {
#if _CONTAINER_DEBUG_LEVEL > 0_STL_VERIFY(_Mypair._Myval2._Mysize != 0, "pop_back called on empty list");
#endif // _CONTAINER_DEBUG_LEVEL > 0_Unchecked_erase(_Mypair._Myval2._Myhead->_Prev);}

继续看下 _Unchecked_erase ，这里的 _Pnode 就是要删除的节点。

    _Nodeptr _Unchecked_erase(const _Nodeptr _Pnode) noexcept { // erase element at _Pnodeconst auto _Result = _Pnode->_Next;_Mypair._Myval2._Orphan_ptr2(_Pnode);--_Mypair._Myval2._Mysize;_Pnode->_Prev->_Next = _Result;_Result->_Prev       = _Pnode->_Prev;_Node::_Freenode(_Getal(), _Pnode);return _Result;}

首先获取到要删除节点的后继节点给 _Result。
_Orphan_ptr2 主要是在 Debug 下和迭代器有关的操作，后续出文章细说。
链表大小减 1。
经典的删除节点操作，让删除节点的前驱节点的后继指向 _Result，然后把 _Result 节点的前驱节点指向要删除节点的前驱节点
_Node::_Freenode(_Getal(), _Pnode) 分配器回收内存

其中 _Node::_Freenode 具体代码如下：

    template <class _Alnode>static void _Freenode(_Alnode& _Al, _Nodeptr _Ptr) noexcept { // destroy all members in _Ptr and deallocate with _Alallocator_traits<_Alnode>::destroy(_Al, _STD addressof(_Ptr->_Myval));_Freenode0(_Al, _Ptr);}

destroy 就是调用 _List_node 的 _Myval 的析构函数：

    template <class _Uty>static _CONSTEXPR20 void destroy(_Alloc&, _Uty* const _Ptr) {
#if _HAS_CXX20_STD destroy_at(_Ptr);
#else // ^^^ _HAS_CXX20 / !_HAS_CXX20 vvv_Ptr->~_Uty();
#endif // ^^^ !_HAS_CXX20 ^^^}

_Freenode0 一个是调用要删除节点 _Prev 和 _Next 的析构函数(这里可能是封装成指针的类)，然后分配器回收内存：

    template <class _Alnode>static void _Freenode0(_Alnode& _Al, _Nodeptr _Ptr) noexcept {// destroy pointer members in _Ptr and deallocate with _Alstatic_assert(is_same_v<typename _Alnode::value_type, _List_node>, "Bad _Freenode0 call");_Destroy_in_place(_Ptr->_Next);_Destroy_in_place(_Ptr->_Prev);allocator_traits<_Alnode>::deallocate(_Al, _Ptr, 1);}

对于另一个删除节点的方法 erase 本质也是调用了 _Freenode：

    iterator erase(const const_iterator _Where) noexcept /* strengthened */ {
#if _ITERATOR_DEBUG_LEVEL == 2_STL_VERIFY(_Where._Getcont() == _STD addressof(_Mypair._Myval2), "list erase iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2const auto _Result = _Where._Ptr->_Next;_Node::_Freenode(_Getal(), _Mypair._Myval2._Unlinknode(_Where._Ptr));return _Make_iter(_Result);}

_Freenode 前面已经分析过了，下面看下这里的 _Unlinknode，其实就是之前提到的删除节点的经典方式，不知道为啥前面的那部分代码不直接用 _Unlinknode 这个封装好的方法：

    _Nodeptr _Unlinknode(_Nodeptr _Pnode) noexcept { // unlink node at _Where from the list_Orphan_ptr2(_Pnode);_Pnode->_Prev->_Next = _Pnode->_Next;_Pnode->_Next->_Prev = _Pnode->_Prev;--_Mysize;return _Pnode;}

清空容器

下面再聊下也是常使用的一个操作 clear 清空容器：

    void clear() noexcept { // erase allauto& _My_data = _Mypair._Myval2;_My_data._Orphan_non_end();_Node::_Free_non_head(_Getal(), _My_data._Myhead);_My_data._Myhead->_Next = _My_data._Myhead;_My_data._Myhead->_Prev = _My_data._Myhead;_My_data._Mysize        = 0;}

_Node::_Free_non_head 回收除了哨兵节点之外其他节点的内存。
将哨兵节点复原到初始状态，即它的 _Next 和 _Prev 都指向自身。
链表长度归 0。

这里主要再看下 _Free_non_head 的内部实现：

    template <class _Alnode>static void _Free_non_head(_Alnode& _Al, _Nodeptr _Head) noexcept { // free a list starting at _First and terminated at nullptr_Head->_Prev->_Next = nullptr;auto _Pnode = _Head->_Next;for (_Nodeptr _Pnext; _Pnode; _Pnode = _Pnext) {_Pnext = _Pnode->_Next;_Freenode(_Al, _Pnode);}}

把哨兵节点的前驱节点的后继设为 nullptr。
找到哨兵节点的后继节点，也就是链表的第一个节点。
然后开始释放链表中的每一个节点。

析构函数

最后看下 list 的析构函数：

    ~list() noexcept {_Tidy();
#if _ITERATOR_DEBUG_LEVEL != 0 // TRANSITION, ABIauto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());_Delete_plain_internal(_Alproxy, _Mypair._Myval2._Myproxy);
#endif // _ITERATOR_DEBUG_LEVEL != 0}

_Tidy() 其实内部就和之前 clear 差不多，只不过这里还需要把哨兵节点也释放掉：

    void _Tidy() noexcept {auto& _Al      = _Getal();auto& _My_data = _Mypair._Myval2;_My_data._Orphan_all();_Node::_Free_non_head(_Al, _My_data._Myhead);_Node::_Freenode0(_Al, _My_data._Myhead);}

小结

本篇文章大致地讲解了下 list 的内部结构和一些基础操作的具体实现，但是代码框架还挺庞大的，尤其还会涉及到辅助 Debug 信息的代码。然后博主对迭代器失效的问题(MSVC的内部实现)还没有完全搞明白，所以后续想着还是把 MSVC 的迭代器的部分给搞清楚，更篇迭代器的文章，之后再继续更一些 vector、unordered_map、priority_queue 等MSVC的底层实现解析。