C++ STL 容器设计实现 -- forward_list
4、forward_list (C++11)
forward_list 是 C++11 引入的单链表数据结构。
4.1、_Fwd_list_node
首先是 forward_list 链表结点。_Fwd_list_node 继承于 _Fwd_list_node_base，成员 _M_storage 保存用户数据，_M_valptr() 函数返回 _M_storage 的地址。
/// forward_list.h
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(); }
};
foward_list 链表结点主要操作在基类 _Fwd_list_node_base 中定义。_Fwd_list_node_base 只有一个指针成员 next，初始化为 nullptr。
/// forward_list.h
struct _Fwd_list_node_base
{
_Fwd_list_node_base() = default;
_Fwd_list_node_base(_Fwd_list_node_base&& __x) noexcept
: _M_next(__x._M_next)
{ __x._M_next = nullptr; }
_Fwd_list_node_base(const _Fwd_list_node_base&) = delete;
_Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete;
_Fwd_list_node_base&
operator=(_Fwd_list_node_base&& __x) noexcept
{
_M_next = __x._M_next;
__x._M_next = nullptr;
return *this;
}
_Fwd_list_node_base* _M_next = nullptr; // next 指针，初始化为空
// ...
};
_Fwd_list_node_base 有两个重要的成员函数：_M_transfer_after() 和 _M_reverse_after() 函数。
_M_transfer_after() 函数用于将 (begin, end] 转移到 *this 后面。如下图，_M_transfer_after() 函数返回后，this->next 指向值为 2 的结点。
/// forward_list.h
_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 = nullptr;
_M_next = __keep;
return __end;
}
_M_reverse_after() 用于将链表反转。
4.2、_Fwd_list_iterator
forward_list 的迭代器区分 const 和 非 const 类型。两者保存的都是 \Fwd_list_node_base 类型的指针，指向对应的 node。当向 forward_list 插入和删除元素后，其他迭代器不会失效。
值得注意的是，forward_list 的迭代器数据成员 _M_node 是 public 成员，可以直接访问。
/// forward_list.h
template<typename _Tp>
struct _Fwd_list_iterator
{
typedef _Fwd_list_iterator<_Tp> _Self;
typedef _Fwd_list_node<_Tp> _Node;
typedef _Tp value_type;
typedef _Tp* pointer;
typedef _Tp& reference;
typedef ptrdiff_t difference_type;
typedef std::forward_iterator_tag iterator_category;
// ...
_Fwd_list_node_base* _M_node; // public
};
template<typename _Tp>
struct _Fwd_list_const_iterator
{
typedef _Fwd_list_const_iterator<_Tp> _Self;
typedef const _Fwd_list_node<_Tp> _Node;
typedef _Fwd_list_iterator<_Tp> iterator;
typedef _Tp value_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
typedef ptrdiff_t difference_type;
typedef std::forward_iterator_tag iterator_category;
// ....
const _Fwd_list_node_base* _M_node;
};
4.3、_Fwd_list_base
_Fwd_list_base 是 forward_list 的基类，定义了单链表 forward_list 头结点。
/// forward_list.h
template<typename _Tp, typename _Alloc>
struct _Fwd_list_base
{
protected:
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;
public:
typedef _Fwd_list_iterator<_Tp> iterator;
typedef _Fwd_list_const_iterator<_Tp> const_iterator;
typedef _Fwd_list_node<_Tp> _Node;
// ...
};
_M_get_node() 和 _M_put_node() 函数分别用于申请和释放一个结点，而 _M_create_node() 用于构造一个结点。注意到，_M_put_node() 并不负责析构一个结点，某个结点的析构显示调用 destroy() 执行，在 _M_erase_after() 函数中可以看到。
/// forward_list.h
_Node*
_M_get_node()
{
auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
return std::__to_address(__ptr);
}
template<typename... _Args>
_Node*
_M_create_node(_Args&&... __args)
{
_Node* __node = this->_M_get_node();
__try
{
::new ((void*)__node) _Node; // 构造指针
_Node_alloc_traits::construct(_M_get_Node_allocator(),
__node->_M_valptr(),
std::forward<_Args>(__args)...); // 构造数据
}
__catch(...)
{
this->_M_put_node(__node);
__throw_exception_again;
}
return __node;
}
void
_M_put_node(_Node* __p)
{
typedef typename _Node_alloc_traits::pointer _Ptr;
auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__p);
_Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ptr, 1);
}
_M_insert_after() 函数负责在 pos 后插入一个元素。
/// forward_list.tcc
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_erase_after() 函数负责将 pos 后的元素删除。
/// forward_list.tcc
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;
_Node_alloc_traits::destroy(_M_get_Node_allocator(),
__curr->_M_valptr()); // 析构数据
__curr->~_Node(); // 析构结点
_M_put_node(__curr); // 释放结点内存
return __pos->_M_next;
}
template<typename _Tp, typename _Alloc>
_Fwd_list_node_base*
_Fwd_list_base<_Tp, _Alloc>::
_M_erase_after(_Fwd_list_node_base* __pos,
_Fwd_list_node_base* __last)
{
_Node* __curr = static_cast<_Node*>(__pos->_M_next);
while (__curr != __last)
{
_Node* __temp = __curr;
__curr = static_cast<_Node*>(__curr->_M_next);
_Node_alloc_traits::destroy(_M_get_Node_allocator(),
__temp->_M_valptr());
__temp->~_Node();
_M_put_node(__temp);
}
__pos->_M_next = __last;
return __last;
}
4.4、std::forward_list
forward_list 继承于 _Fwd_list_base 类，没有定义其他成员变量，使用 \Fwd_list_base 中对单向链表的定义。
template<typename _Tp, typename _Alloc = allocator<_Tp>>
class forward_list : private _Fwd_list_base<_Tp, _Alloc>
{
private:
typedef _Fwd_list_base<_Tp, _Alloc> _Base;
typedef _Fwd_list_node_base _Node_base;
typedef typename _Base::_Node _Node;
typedef typename _Base::_Node_alloc_type _Node_alloc_type;
typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
typedef allocator_traits<__alloc_rebind<_Alloc, _Tp>> _Alloc_traits;
public:
// types:
typedef _Tp value_type;
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef typename _Base::iterator iterator;
typedef typename _Base::const_iterator const_iterator;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef _Alloc allocator_type;
/// ....
forward_list 的 begin() 函数返回的迭代器指向链表第一个结点，end() 返回 nullptr。除此之外，还提供 before_begin() 函数，返回头结点，方便单向链表在插入。
/// forward_list.h
iterator
before_begin() noexcept
{ return iterator(&this->_M_impl._M_head); }
iterator
begin() noexcept
{ return iterator(this->_M_impl._M_head._M_next); }
iterator
end() noexcept
{ return iterator(nullptr); }
forward_list 有一个比较重要的私有成员函数是 _M_splice_after()，该函数将 (before last) 区间内的结点，插入到 pos 指向的结点后面，其实现如下。
/// forward_list.tcc
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;
if (__b != __end)
return iterator(__tmp->_M_transfer_after(__b, __end));
else
return iterator(__tmp);
}
比如 insert_after() 成员函数就是调用 _M_splice_after() 函数向 forward_list 中插入元素。
/// forward_list.tcc
template<typename _Tp, typename _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::
insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
{
if (__n)
{
forward_list __tmp(__n, __val, get_allocator());
return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
}
else
return iterator(const_cast<_Node_base*>(__pos._M_node));
}
template<typename _Tp, typename _Alloc>
template<typename _InputIterator, typename>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::
insert_after(const_iterator __pos,
_InputIterator __first, _InputIterator __last)
{
forward_list __tmp(__first, __last, get_allocator());
if (!__tmp.empty())
return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
else
return iterator(const_cast<_Node_base*>(__pos._M_node));
}
merge() 也是 调用 _M_splice_after() 函数。
/// forward_list.tcc
template<typename _Tp, typename _Alloc>
template<typename _Comp>
void
forward_list<_Tp, _Alloc>::
merge(forward_list&& __list, _Comp __comp)
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 3088. forward_list::merge behavior unclear when passed *this
if (std::__addressof(__list) == this)
return;
_Node_base* __node = &this->_M_impl._M_head;
while (__node->_M_next && __list._M_impl._M_head._M_next)
{
if (__comp(*static_cast<_Node*>
(__list._M_impl._M_head._M_next)->_M_valptr(),
*static_cast<_Node*>
(__node->_M_next)->_M_valptr()))
__node->_M_transfer_after(&__list._M_impl._M_head,
__list._M_impl._M_head._M_next);
__node = __node->_M_next;
}
if (__list._M_impl._M_head._M_next)
*__node = std::move(__list._M_impl._M_head);
}
forward_list::sort() 使用归并排序，评价时间复杂度 O(NlgN)。
每轮归并的两个链表，最大长度为 insize，下一轮归并，insize *= 2，两倍增长（应为 insize 的两个链表已经合并了）。
/// forward_list.tcc
template<typename _Tp, class _Alloc>
template<typename _Comp>
void
forward_list<_Tp, _Alloc>::
sort(_Comp __comp)
{
// If `next' is nullptr, return immediately.
_Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
if (!__list)
return;
unsigned long __insize = 1;
while (1)
{
_Node* __p = __list;
__list = nullptr;
_Node* __tail = nullptr;
// Count number of merges we do in this pass.
unsigned long __nmerges = 0; // 本轮归并合并的次数
// 归并 p 和 q 指向的两个链表，长度分别为 psize 和 qsize
while (__p)
{
++__nmerges;
// There exists a merge to be done.
// Step `insize' places along from p.
_Node* __q = __p;
unsigned long __psize = 0; // for 循环为了确定 qsize 大小
for (unsigned long __i = 0; __i < __insize; ++__i)
{ // 最大为 insize，可能小于 insize，应为 q 到链表末尾了
++__psize;
__q = static_cast<_Node*>(__q->_M_next);
if (!__q)
break;
}
// If q hasn't fallen off end, we have two lists to merge.
unsigned long __qsize = __insize;
// qsize 默认为 insize，需要结合 q 判断释放不为空
// Now we have two lists; merge them.
while (__psize > 0 || (__qsize > 0 && __q))
{ // p 链表或者 q 链表不为空
// Decide whether next node of merge comes from p or q.
_Node* __e;
if (__psize == 0)
{
// p is empty; e must come from q.
__e = __q;
__q = static_cast<_Node*>(__q->_M_next);
--__qsize;
}
else if (__qsize == 0 || !__q)
{
// q is empty; e must come from p.
__e = __p;
__p = static_cast<_Node*>(__p->_M_next);
--__psize;
}
else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr()))
{
// First node of q is not lower; e must come from p.
__e = __p;
__p = static_cast<_Node*>(__p->_M_next);
--__psize;
}
else
{
// First node of q is lower; e must come from q.
__e = __q;
__q = static_cast<_Node*>(__q->_M_next);
--__qsize;
}
// Add the next node to the merged list.
if (__tail)
__tail->_M_next = __e;
else
__list = __e;
__tail = __e;
} // while (p || q)
// Now p has stepped `insize' places along, and q has too.
__p = __q; // 合并完成，从 q 开始再拆分出两个链表用于合并
} // while (p)
__tail->_M_next = nullptr;
// If we have done only one merge, we're finished.
// Allow for nmerges == 0, the empty list case.
if (__nmerges <= 1)
{
this->_M_impl._M_head._M_next = __list;
return;
}
// Otherwise repeat, merging lists twice the size.
__insize *= 2; // 扩大 insize
}
}
欢迎关注公众号“源知源为”，阅读更多技术干货
#STL#C/C++基础 文章被收录于专栏
C/C++ 语言基础
