【STL源码拆解】forward_list容器插入、删除等是怎么实现的
【STL源码拆解】forward_list容器插入、删除等是怎么实现的
上篇文章我们介绍了forward_list的整体类实现和构造的实现，知道它其实就是个单链表，本篇文章接着介绍它的插入、删除、去重、反转等操作的实现以及相应的时间复杂度。
说明一下，我用的是gcc7.1.0编译器，标准库源代码也是这个版本的。
按照惯例，还是先看一下本文大纲，如下：
1. forward_list插入操作
插入操作一般来讲，都是分为头部插入、尾部插入和中间插入，对于forward_list来讲，因为它没有办法直接操作尾部，如要操作尾部，要从头结点一个结点一个结点的推过去，效率会很差，所以根据标准库的性能优先原则，forward_list是不提供尾部插入函数的，所以它只有头部插入和根据位置插入两种，下面我们一一的看看他们都是怎么实现的。
1.1 头部插入
先看一下函数原型，如下：
//在链表头部插入数据
void push_front(const _Tp& __val)
{ this->_M_insert_after(cbefore_begin(), __val); }
这里的cbefore_begin返回的是头结点的位置，接下来我们看看函数_M_insert_after的实现，如下：
template<typename _Tp, typename _Alloc>
template<typename... _Args>
_Fwd_list_node_base*
_Fwd_list_base<_Tp, _Alloc>::
_M_insert_after(const_iterator __pos, _Args&&... __args)
{
//获取指定结点
_Fwd_list_node_base* __to
= const_cast<_Fwd_list_node_base*>(__pos._M_node);
_Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
__thing->_M_next = __to->_M_next;
__to->_M_next = __thing;
return __to->_M_next;
}
这个实现就比较简单啦，新的结点指向当前结点的下一个结点，然后当前结点又指向新的结点，所以_M_insert_after其实就是在指定结点后面插入一个新的结点，结合整体调用过程来看，就是在头结点后面插入一个新的结点，也就是所谓的从头部插入。
从整个调用过程来看，头部插入的时间复杂度为O(1)。
1.2 中间插入
从中间插入，其实就是在指定位置插入结点，还是先看看函数原型，如下：
iterator insert_after(const_iterator __pos, const _Tp& __val)
{ return iterator(this->_M_insert_after(__pos, __val)); }
可以看到调用的函数跟头部插入一样，只不过push_front是直接指定了头结点，但是insert_after没有指定结点而已，从这个操作本身来看，它的时间复杂度也是O(1)。
2. forward_list删除操作
删除与插入比较类似，对于forward_list而言，也是只有头部删除和中间删除两种情况，下面具体看看实现。
2.1 从头部删除
先看下函数原型，如下：
void pop_front()
{ this->_M_erase_after(&this->_M_impl._M_head); }
接着看下函数_M_erase_after的实现，如下：
template<typename _Tp, typename _Alloc>
_Fwd_list_node_base*
_Fwd_list_base<_Tp, _Alloc>::
_M_erase_after(_Fwd_list_node_base* __pos)
{
_Node* __curr = static_cast<_Node*>(__pos->_M_next);
__pos->_M_next = __curr->_M_next;
_Tp_alloc_type __a(_M_get_Node_allocator());
allocator_traits<_Tp_alloc_type>::destroy(__a, __curr->_M_valptr());
__curr->~_Node();
_M_put_node(__curr);
return __pos->_M_next;
}
函数_M_erase_after删除指定结点所指向的下一个结点，并销毁该结点所占用的内存。
结合整个调用来看，从头部删除，其实就是删除头结点指向的结点，并让头结点指向第二个链表结点。
2.2 根据指定位置删除
删除还有一种情况，从某个指定的位置进行删除，函数原型如下：
iterator
erase_after(const_iterator __pos)
{ return iterator(this->_M_erase_after(const_cast<_Node_base*>
(__pos._M_node))); }
可以看到，这里也是调用的_M_erase_after函数，只不过给了一个结点位置的入参，所以说白了，这个函数就是删除指定结点所指向的下一个结点。
3. forward_list中插入另外一个forward_list
我们之前也多次说过了，forward_list其实就是一个单链表结构，所以它也支持在当前的forward_list的某个位置插入另外一个forward_list，提供该功能函数名为splice_after
先看一下该函数的原型，如下：
void splice_after(const_iterator __pos, forward_list&& __list) noexcept
{
if (!__list.empty())
_M_splice_after(__pos, __list.before_begin(), __list.end());
}
调用了函数_M_splice_after，该函数实现如下：
template<typename _Tp, typename _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::
_M_splice_after(const_iterator __pos,
const_iterator __before, const_iterator __last)
{
_Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
_Node_base* __b = const_cast<_Node_base*>(__before._M_node);
_Node_base* __end = __b;
//这里检查链表是否存在有效结点
while (__end && __end->_M_next != __last._M_node)
__end = __end->_M_next;
//如果__before和__last所代表的链表存在有效结点，则调用函数_M_transfer_after
if (__b != __end)
return iterator(__tmp->_M_transfer_after(__b, __end));
else
return iterator(__tmp);
}
根据代码和注释可知，函数_M_splice_after实际上只是做了一个校验，真正的操作是_Fwd_list_node_base::_M_transfer_after完成的，下面我们看看该函数的实现，如下：
_Fwd_list_node_base*
_M_transfer_after(_Fwd_list_node_base* __begin,
_Fwd_list_node_base* __end) noexcept
{
//记录待插入链表的起点
_Fwd_list_node_base* __keep = __begin->_M_next;
if (__end)
{
//待插入链表从原有的链表里面脱离
__begin->_M_next = __end->_M_next;
__end->_M_next = _M_next;
}
else
{
__begin->_M_next = 0;
}
_M_next = __keep;
return __end;
}
函数_M_transfer_after将入参所指向的一段链表插入到当前结点之后，并从原有链表脱离。
4. forward_list去重
forward_list也有去重的功能，我们看下去重的一种重载函数，原型如下：
template<typename _Tp, typename _Alloc>
template<typename _BinPred>
void
forward_list<_Tp, _Alloc>::
unique(_BinPred __binary_pred)
{
iterator __first = begin();
iterator __last = end();
if (__first == __last)
return;
iterator __next = __first;
while (++__next != __last)
{
if (__binary_pred(*__first, *__next))
erase_after(__first);
else
__first = __next;
__next = __first;
}
}
根据代码，其实叫做去重并不完全准确，它是根据传入的特定函数，满足条件的就删掉，不满足条件的就继续往后，且该函数只能针对两个相邻的结点进行操作，不支持对不相邻的结点操作。
5. 重置forward_list
5.1结点内容重置
所谓结点内容重置，是说对链表的每个结点进行重新赋值，先看下函数原型，如下：
void assign(size_type __n, const _Tp& __val)
{ _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); }
调用了函数_M_assign_n，我们看下该函数的实现，如下：
void
_M_assign_n(size_type __n, const _Tp& __val, true_type)
{
auto __prev = before_begin();
auto __curr = begin();
auto __end = end();
while (__curr != __end && __n > 0)
{
*__curr = __val;
++__prev;
++__curr;
--__n;
}
if (__n > 0)
insert_after(__prev, __n, __val);
else if (__curr != __end)
erase_after(__prev, __end);
}
该函数根据指定大小和值对forward_list进行大小和内容的重置，如果原链表大小不够__n，则补足，如果超过__n，则把多余的删掉。
5.2 resize重置
除了assign重置以外，forward_list还提供了resize重置，我们先看下它的其中一种重载，如下：
template<typename _Tp, typename _Alloc>
void
forward_list<_Tp, _Alloc>::
resize(size_type __sz, const value_type& __val)
{
iterator __k = before_begin();
size_type __len = 0;
while (__k._M_next() != end() && __len < __sz)
{
++__k;
++__len;
}
if (__len == __sz)
erase_after(__k, end());
else
insert_after(__k, __sz - __len, __val);
}
从代码可知，resize函数入参也是指定结点数量和值，但是如果当前forward_list的结点数量大于__sz，则直接把多余的删掉，但并不会修改原有结点的值，如果当前forward_list的结点数量小于__sz，则根据__sz补充不够的结点，新的结点的值是指定入参，但是原有结点的值不会被修改。
根据上述分析可知，assign和resize都有对forward_list进行重置的功能，都是结点数不够就补充，够的就删掉多余结点，不同之处是assign会把原有结点的值也修改掉，而resize不会修改原有结点的值。
6. forward_list反转
forward_list是单链表，单链表反转相对而言就比较简单了，我们先看看源码，如下：
void reverse() noexcept
{ this->_M_impl._M_head._M_reverse_after(); }
调用了函数_Fwd_list_node_base::_M_reverse_after，这里看看该函数的源码，如下：
void _M_reverse_after() noexcept
{
_Fwd_list_node_base* __tail = _M_next;
//如果链表为空，则直接返回
if (!__tail)
return;
//一个结点一个结点的循环，并保存下指向当前结点的指针
while (_Fwd_list_node_base* __temp = __tail->_M_next)
{
//保存头结点指向的结点
_Fwd_list_node_base* __keep = _M_next;
//头结点指向当前结点
_M_next = __temp;
//当前结点的上一个结点指向当前结点的下一个结点
__tail->_M_next = __temp->_M_next;
//当前结点指向之前的第一个结点
_M_next->_M_next = __keep;
}
}
所谓反转，其实就是链表的方向发生了变化，每一个结点都由指向它的后一个结点变为指向前一个结点，但头结点不变。