C++ STL 容器设计与实现分析 -- list
3、list
list 是双向链表实现。双向链表结点在堆上动态申请，插入和删除操作不存在移动元素的操作。
3.1、_List_node
list 中每个结点都用 _List_node 表示，继承于 _List_node_base。_List_node 成员 _M_storage，用于保存数据。
/// stl_list.h
/// An actual node in the %list.
template<typename _Tp>
struct _List_node : public __detail::_List_node_base
{
#if __cplusplus >= 201103L
__gnu_cxx::__aligned_membuf<_Tp> _M_storage;
_Tp* _M_valptr() { return _M_storage._M_ptr(); }
_Tp const* _M_valptr() const { return _M_storage._M_ptr(); }
#else
// ...
#endif
};
_List_node_base 只有两个指针成员 next 和 prev，分别指向 list 中前一个和后一个成员。_List_node_base 定义了一组函数接口，用于将本 node 链接或者移除 list。
/// stl_list.h
struct _List_node_base
{
_List_node_base* _M_next;
_List_node_base* _M_prev;
static void
swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
void
_M_transfer(_List_node_base* const __first,
_List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
void
_M_reverse() _GLIBCXX_USE_NOEXCEPT;
void
_M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
void
_M_unhook() _GLIBCXX_USE_NOEXCEPT;
};
接下来分析 _List_node_base 定义的函数接口。首先是 swap 函数。用于将两个 x 和 y 交换。
/// c++98/list.cc
void
_List_node_base::swap(_List_node_base& __x,
_List_node_base& __y) _GLIBCXX_USE_NOEXCEPT
{
if ( __x._M_next != &__x ) // x 不为空
{
if ( __y._M_next != &__y ) // y 不为空
{ // x 和 y 都不为空，交换 x 和 y 的内容
// Both __x and __y are not empty.
std::swap(__x._M_next,__y._M_next);
std::swap(__x._M_prev,__y._M_prev);
__x._M_next->_M_prev = __x._M_prev->_M_next = &__x;
__y._M_next->_M_prev = __y._M_prev->_M_next = &__y;
}
else
{ // x 不为空，y 为空
// __x is not empty, __y is empty.
__y._M_next = __x._M_next;
__y._M_prev = __x._M_prev;
__y._M_next->_M_prev = __y._M_prev->_M_next = &__y;
__x._M_next = __x._M_prev = &__x;
}
}
else if ( __y._M_next != &__y )
{ // x 为 空，y 不为空
// __x is empty, __y is not empty.
__x._M_next = __y._M_next;
__x._M_prev = __y._M_prev;
__x._M_next->_M_prev = __x._M_prev->_M_next = &__x;
__y._M_next = __y._M_prev = &__y;
}
}
_M_transfer() 函数 [first, last) 的元素全部转移到 *this 所在的 list。
/// c++98/list.cc
void
_List_node_base::
_M_transfer(_List_node_base * const __first,
_List_node_base * const __last) _GLIBCXX_USE_NOEXCEPT
{
__glibcxx_assert(__first != __last);
if (this != __last)
{
// Remove [first, last) from its old position.
__last->_M_prev->_M_next = this;
__first->_M_prev->_M_next = __last;
this->_M_prev->_M_next = __first;
// Splice [first, last) into its new position.
_List_node_base* const __tmp = this->_M_prev;
this->_M_prev = __last->_M_prev;
__last->_M_prev = __first->_M_prev;
__first->_M_prev = __tmp;
}
}
_M_reverse() 函数用于将所有 node 的 next 和 prev 交换，改变 list 的指向。
/// c++98/list.cc
void
_List_node_base::_M_reverse() _GLIBCXX_USE_NOEXCEPT
{
_List_node_base* __tmp = this;
do
{
std::swap(__tmp->_M_next, __tmp->_M_prev);
// Old next node is now prev.
__tmp = __tmp->_M_prev;
}
while (__tmp != this);
}
_M_hook() 和 _M_unhook() 两个函数用户将 *this 插入和删除。
/// c++98/list.cc
void
_List_node_base::
_M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT
{
this->_M_next = __position;
this->_M_prev = __position->_M_prev;
__position->_M_prev->_M_next = this;
__position->_M_prev = this;
}
void
_List_node_base::_M_unhook() _GLIBCXX_USE_NOEXCEPT
{
_List_node_base* const __next_node = this->_M_next;
_List_node_base* const __prev_node = this->_M_prev;
__prev_node->_M_next = __next_node;
__next_node->_M_prev = __prev_node;
}
3.2、_List_iterator
list 的迭代器区分 const 和 非 const 类型。两者保存的都是 _List_node_base 类型的指针，指向对应的 node。当向 list 插入和删除元素后，其他迭代器不会失效。
值得注意的是，list 的迭代器数据成员 _M_node 是 public 成员，可以直接访问。
/// stl_list.h
template<typename _Tp>
struct _List_iterator
{
typedef _List_iterator<_Tp> _Self;
typedef _List_node<_Tp> _Node;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Tp* pointer;
typedef _Tp& reference;
// ...
// The only member points to the %list element.
__detail::_List_node_base* _M_node;
};
template<typename _Tp>
struct _List_const_iterator
{
typedef _List_const_iterator<_Tp> _Self;
typedef const _List_node<_Tp> _Node;
typedef _List_iterator<_Tp> iterator;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
// ...
// The only member points to the %list element.
const __detail::_List_node_base* _M_node;
};
3.3、_List_node_header
链表头节点使用 _List_node_header 表示。头结点保存有 size，表示 list 中有多少个元素。构造时，头节点 next 和 prev 都指向头节点自己。
/// stl_list.h
struct _List_node_header : public _List_node_base
{
#if _GLIBCXX_USE_CXX11_ABI
std::size_t _M_size;
#endif
_List_node_header() _GLIBCXX_NOEXCEPT
{ _M_init(); }
#if __cplusplus >= 201103L
_List_node_header(_List_node_header&& __x) noexcept
: _List_node_base{ __x._M_next, __x._M_prev }
# if _GLIBCXX_USE_CXX11_ABI
, _M_size(__x._M_size)
# endif
{
if (__x._M_base()->_M_next == __x._M_base())
this->_M_next = this->_M_prev = this;
else
{
this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base();
__x._M_init();
}
}
void
_M_move_nodes(_List_node_header&& __x)
{
_List_node_base* const __xnode = __x._M_base();
if (__xnode->_M_next == __xnode)
_M_init();
else
{
_List_node_base* const __node = this->_M_base();
__node->_M_next = __xnode->_M_next;
__node->_M_prev = __xnode->_M_prev;
__node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
# if _GLIBCXX_USE_CXX11_ABI
_M_size = __x._M_size;
# endif
__x._M_init();
}
}
#endif
void
_M_init() _GLIBCXX_NOEXCEPT
{
this->_M_next = this->_M_prev = this;
#if _GLIBCXX_USE_CXX11_ABI
this->_M_size = 0;
#endif
}
private:
_List_node_base* _M_base() { return this; }
};
3.4、std::list
首先分析 _List_base。_List_base 是 list 的基类，定义了链表基本的操作。
首先 _List_base 内部定义了一个数据据结构 _List_impl，继承于 _Node_alloc_type，有一个 _List_node_header 数据成员，也就是 _List_impl 保存有链表头节点。
然后 _List_base 定义了一个 _List_impl 类型的成员。整个结构比较清晰，_List_base 定义了链表的结构，其头节点保存在 _M_impl 数据成员中。
/// stl_list.h
template<typename _Tp, typename _Alloc>
class _List_base
{
protected:
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<_Tp>::other _Tp_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tp_alloc_traits;
typedef typename _Tp_alloc_traits::template
rebind<_List_node<_Tp> >::other _Node_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
struct _List_impl
: public _Node_alloc_type
{
__detail::_List_node_header _M_node;
// ...
};
_List_impl _M_impl;
// ...
void
_M_init() _GLIBCXX_NOEXCEPT
{ this->_M_impl._M_node._M_init(); }
};
list 继承于 _List_base，没有其他的数据成员。
/// stl_list.h
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class list : protected _List_base<_Tp, _Alloc>
{
typedef _List_base<_Tp, _Alloc> _Base;
typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
typedef typename _Base::_Tp_alloc_traits _Tp_alloc_traits;
typedef typename _Base::_Node_alloc_type _Node_alloc_type;
typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
public:
typedef _Tp value_type;
typedef typename _Tp_alloc_traits::pointer pointer;
typedef typename _Tp_alloc_traits::const_pointer const_pointer;
typedef typename _Tp_alloc_traits::reference reference;
typedef typename _Tp_alloc_traits::const_reference const_reference;
typedef _List_iterator<_Tp> iterator;
typedef _List_const_iterator<_Tp> const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Alloc allocator_type;
protected:
// Note that pointers-to-_Node's can be ctor-converted to
// iterator types.
typedef _List_node<_Tp> _Node;
using _Base::_M_impl;
using _Base::_M_put_node;
using _Base::_M_get_node;
using _Base::_M_get_Node_allocator;
// ...
begin() 返回头节点 next 指向的结点，而 end() 返回头结点。头节点 next 指向的是 list 第一个结点，而 prev 指向的是 list 最后一个结点。
/// stl_list.h
_GLIBCXX_NODISCARD
iterator
begin() _GLIBCXX_NOEXCEPT
{ return iterator(this->_M_impl._M_node._M_next); }
iterator
end() _GLIBCXX_NOEXCEPT
{ return iterator(&this->_M_impl._M_node); }
当向 list 插入一个元素时，首先会调用 _M_create_node() 函数申请和构造一个结点。_M_get_node() 在堆上申请一块内存，然后在这块内存上构造一个结点。
/// stl_list.h
template<typename... _Args>
_Node*
_M_create_node(_Args&&... __args)
{
auto __p = this->_M_get_node();
auto& __alloc = _M_get_Node_allocator();
__allocated_ptr<_Node_alloc_type> __guard{__alloc, __p};
_Node_alloc_traits::construct(__alloc, __p->_M_valptr(),
std::forward<_Args>(__args)...);
__guard = nullptr;
return __p;
}
插入和删除结点分别调用 _M_insert() 和 _M_erase() 函数。
_M_insert() 函数首先调用 _M_create_node() 构造一个结点，然后调用 _M_hook() 函数将其插入到 position 结点前面。
_M_erase() 函数和 _M_insert() 函数类似，执行相反的操作删除一个结点。首先调用 _M_unhook() 函数将结点从 list 删除，然后调用 destroy 函数析构内存，最后调用 _M_put_node() 释放内存。
/// stl_list.h
template<typename... _Args>
void
_M_insert(iterator __position, _Args&&... __args)
{
_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
__tmp->_M_hook(__position._M_node);
this->_M_inc_size(1);
}
void
_M_erase(iterator __position) _GLIBCXX_NOEXCEPT
{
this->_M_dec_size(1);
__position._M_node->_M_unhook();
_Node* __n = static_cast<_Node*>(__position._M_node);
_Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());
_M_put_node(__n);
}
merge() 用于合并两 list 并且保证合并后保持递增顺序。
/// list.tcc
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
merge(list&& __x)
#else
merge(list& __x)
#endif
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 300. list::merge() specification incomplete
if (this != std::__addressof(__x))
{
_M_check_equal_allocators(__x);
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
const _Finalize_merge __fin(*this, __x, __first2);
while (__first1 != __last1 && __first2 != __last2)
if (*__first2 < *__first1) // first2 小于 first1
{
iterator __next = __first2; // 将 frist2 转移到 first1 前面
_M_transfer(__first1, __first2, ++__next);
__first2 = __next;
}
else
++__first1;
if (__first2 != __last2)
{ // 将 [first2, last2) 元素转移到 last1 前面
_M_transfer(__last1, __first2, __last2);
__first2 = __last2;
}
}
}
merge() 函数主要调用 _M_transfer() 函数，其直接调用 node 的 _M_transfer() 函数。
/// stl_list.h
void
_M_transfer(iterator __position, iterator __first, iterator __last)
{ __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
sort() 函数将 list 排序，需要使用 _Scratch_list 数据结构。
首先分析 _Scratch_list 数据结构。_Scratch_list 用于部分排序的链表。
/// stl_list.h
// Used by list::sort to hold nodes being sorted.
struct _Scratch_list : _List_node_base
{
_Scratch_list() { _M_next = _M_prev = this; }
bool empty() const { return _M_next == this; }
void swap(_List_node_base& __l) { _List_node_base::swap(*this, __l); }
template<typename _Iter, typename _Cmp>
struct _Ptr_cmp
{
_Cmp _M_cmp;
bool
operator()(__detail::_List_node_base* __lhs,
__detail::_List_node_base* __rhs) /* not const */
{ return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); }
};
template<typename _Iter>
struct _Ptr_cmp<_Iter, void>
{
bool
operator()(__detail::_List_node_base* __lhs,
__detail::_List_node_base* __rhs) const
{ return *_Iter(__lhs) < *_Iter(__rhs); }
};
// Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp.
template<typename _Cmp>
void
merge(_List_node_base& __x, _Cmp __comp)
{ // 归并排序
_List_node_base* __first1 = _M_next;
_List_node_base* const __last1 = this;
_List_node_base* __first2 = __x._M_next;
_List_node_base* const __last2 = std::__addressof(__x);
while (__first1 != __last1 && __first2 != __last2)
{
if (__comp(__first2, __first1)) // first2 小于 first1
{
_List_node_base* __next = __first2->_M_next;
__first1->_M_transfer(__first2, __next); // first2 <--> first1
__first2 = __next;
}
else
__first1 = __first1->_M_next;
}
if (__first2 != __last2) // [first2, last2) <--> this
this->_M_transfer(__first2, __last2);
}
// Splice the node at __i into *this.
void _M_take_one(_List_node_base* __i) // 拿取一个结点
{ this->_M_transfer(__i, __i->_M_next); } // i <--> this
// Splice all nodes from *this after __i.
void _M_put_all(_List_node_base* __i)
{
if (!empty())
__i->_M_transfer(_M_next, this); // [next, last) <--> i
}
};
sort() 使用的归并排序，逐步将 list 拆解成多个有序链表，最后再归并成一个有序 list。
根据上面的算法，list 被拆解成两个有序的链表，最后将多个链表合并成一个有序链表。
下面是 sort() 函数的实现，结合上面两幅图，比较容易看懂原理。
/// list.tcc
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
sort()
{
// Do nothing if the list has length 0 or 1.
if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
&& this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
{
using __detail::_Scratch_list;
// The algorithm used here is largely unchanged from the SGI STL
// and is described in The C++ Standard Template Library by Plauger,
// Stepanov, Lee, Musser.
// Each element of *this is spliced out and merged into one of the
// sorted lists in __tmp, then all the lists in __tmp are merged
// together and then swapped back into *this.
// Because all nodes end up back in *this we do not need to update
// this->size() while nodes are temporarily moved out.
_Scratch_list __carry;
_Scratch_list __tmp[64];
_Scratch_list* __fill = __tmp;
_Scratch_list* __counter;
_Scratch_list::_Ptr_cmp<iterator, void> __ptr_comp;
__try
{
do
{
__carry._M_take_one(begin()._M_node);
for(__counter = __tmp;
__counter != __fill && !__counter->empty();
++__counter)
{
__counter->merge(__carry, __ptr_comp);
__carry.swap(*__counter);
}
__carry.swap(*__counter);
if (__counter == __fill)
++__fill;
}
while ( !empty() );
for (__counter = __tmp + 1; __counter != __fill; ++__counter)
__counter->merge(__counter[-1], __ptr_comp);
__fill[-1].swap(this->_M_impl._M_node);
}
__catch(...)
{
// Move all nodes back into *this.
__carry._M_put_all(end()._M_node);
for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
__tmp[__i]._M_put_all(end()._M_node);
__throw_exception_again;
}
}
}
欢迎关注公众号“源知源为”，阅读更多技术干货
#STL#C/C++基础 文章被收录于专栏
C/C++ 语言基础
