上篇文章我们介绍了forward_list的整体类实现和构造的实现,知道它其实就是个单链表,本篇文章接着介绍它的插入、删除、去重、反转等操作的实现以及相应的时间复杂度。
说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。
按照惯例,还是先看一下本文大纲,如下:
插入操作一般来讲,都是分为头部插入、尾部插入和中间插入,对于forward_list
来讲,因为它没有办法直接操作尾部,如要操作尾部,要从头结点一个结点一个结点的推过去,效率会很差,所以根据标准库的性能优先原则,forward_list
是不提供尾部插入函数的,所以它只有头部插入和根据位置插入两种,下面我们一一的看看他们都是怎么实现的。
先看一下函数原型,如下:
//在链表头部插入数据
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)。
从中间插入,其实就是在指定位置插入结点,还是先看看函数原型,如下:
iterator insert_after(const_iterator __pos, const _Tp& __val)
{ return iterator(this->_M_insert_after(__pos, __val)); }
可以看到调用的函数跟头部插入一样,只不过push_front
是直接指定了头结点,但是insert_after
没有指定结点而已,从这个操作本身来看,它的时间复杂度也是O(1)。
删除与插入比较类似,对于forward_list
而言,也是只有头部删除和中间删除两种情况,下面具体看看实现。
先看下函数原型,如下:
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
删除指定结点所指向的下一个结点,并销毁该结点所占用的内存。
结合整个调用来看,从头部删除,其实就是删除头结点指向的结点,并让头结点指向第二个链表结点。
删除还有一种情况,从某个指定的位置进行删除,函数原型如下:
iterator
erase_after(const_iterator __pos)
{ return iterator(this->_M_erase_after(const_cast<_Node_base*>
(__pos._M_node))); }
可以看到,这里也是调用的_M_erase_after
函数,只不过给了一个结点位置的入参,所以说白了,这个函数就是删除指定结点所指向的下一个结点。
我们之前也多次说过了,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
将入参所指向的一段链表插入到当前结点之后,并从原有链表脱离。
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;
}
}
根据代码,其实叫做去重并不完全准确,它是根据传入的特定函数,满足条件的就删掉,不满足条件的就继续往后,且该函数只能针对两个相邻的结点进行操作,不支持对不相邻的结点操作。
所谓结点内容重置,是说对链表的每个结点进行重新赋值,先看下函数原型,如下:
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
,则把多余的删掉。
除了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
不会修改原有结点的值。
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;
}
}
所谓反转,其实就是链表的方向发生了变化,每一个结点都由指向它的后一个结点变为指向前一个结点,但头结点不变。