C++ STL源码剖析之双向环形链表list

0. 导语

源码对应的版本为gcc-4.9.1

1.list

list为双向环形链表，其结构为：

list - 图1

自己绘制的图如下：

list_all

双向环状链表从节点值为3开始插入，红色框表示最后一个节点(end()指向的节点)。黄色线条表示指向前驱节点，黑色线条表示指向后继节点。

1.1 list源码

1.1.1 类结构

  1.  template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
  2.  class list : protected _List_base<_Tp, _Alloc> 
  3.  {
  5.  }

list继承_List_base。

1.1.2 双向环形链表实现

【构造函数】

（1）不带任何元素的list

  1. explicit
  2. list(const allocator_type &__a) _GLIBCXX_NOEXCEPT: _Base(_Node_alloc_type(__a)) {}

（2）带n个元素且赋予初值的list

  1. explicit list(size_type __n, const value_type &__value = value_type(),const allocator_type &__a = allocator_type()) : _Base(_Node_alloc_type(__a)) 
  2. { _M_fill_initialize(__n, __value); }

（3）从一个范围中进行初始化list

  1. template<typename _InputIterator>
  2. list(_InputIterator __first, _InputIterator __last,
  3.      const allocator_type &__a = allocator_type())
  4.         : _Base(_Node_alloc_type(__a)) {
  5.     // Check whether it's an integral type.  If so, it's not an iterator.
  6.     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
  7.     _M_initialize_dispatch(__first, __last, _Integral());
  8. }

【创建节点】

做的事情：创建一个新的节点并动态分配内存，返回节点。

  1. _Node *_M_create_node(const value_type &__x) {
  2.     _Node *__p = this->_M_get_node();
  3.     __try
  4.     {
  5.         _M_get_Tp_allocator().construct
  6.                 (std::__addressof(__p->_M_data), __x);
  7.     }
  8.     __catch(...)
  9.     {
  10.         _M_put_node(__p);
  11.         __throw_exception_again;
  12.     }
  13.     return __p;
  14. }

注意到里面有两个重要的函数_M_get_node与_M_put_node，我们来查看后发现这些方法来自基类，源码为：

  1. _List_node<_Tp> * _M_get_node() { return _M_impl._Node_alloc_type::allocate(1); }
  3. void _M_put_node(_List_node<_Tp> *__p)   _GLIBCXX_NOEXCEPT
  4. { _M_impl._Node_alloc_type::deallocate(__p, 1); }

对应的就是创建节点动态分配内存，若创建过程中抛出异常，则释放内存。

【插入节点】

插入节点包括：

  • 尾部插入n个指定节点值的节点，对应的函数_M_fill_initialize

在list的构造函数中使用：

  1. explicit list(size_type __n, const value_type &__value = value_type(),const allocator_type &__a = allocator_type()) : _Base(_Node_alloc_type(__a)) 
  2. { _M_fill_initialize(__n, __value); }
  • 指定位置插入指定节点值的节点，对应的函数_M_insert

其中大家经常使用的push_back与push_front底层就是调用_M_insert函数。

两者函数区别是：

  1. this->_M_insert(end(), __x);  // push_back   尾部插入  
  2. this->_M_insert(begin(), __x); // push_front 头部插入
  • 双向环形链表插入函数_M_hook (最重要！！！)

像前面提到的push_back、push_front、_M_insert，还有insert都是使用最基础的双向链表插入函数_M_hook实现的。

下面来深入研究一下：

其中_M_fill_initialize源码如下：

  1. void _M_fill_initialize(size_type __n, const value_type &__x) {
  2.     for (; __n; --__n)
  3.         push_back(__x);
  4. }

其中push_back源码如下：

  1. void push_back(const value_type &__x) { this->_M_insert(end(), __x); }

其中_M_insert，在指定的位置插入初始值为x的节点。

  1. void _M_insert(iterator __position, const value_type &__x) {
  2.     _Node *__tmp = _M_create_node(__x);
  3.     __tmp->_M_hook(__position._M_node);
  4. }

其中_M_hook实现在gcc-4.9.1/libstdc++-v3/src/c++98/list.cc中,当然_List_node_base的其他函数，例如：_M_unhook也在这个文件中。

  1. // 在指定的位置前插入this指向的节点
  2. void_List_node_base::_M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT
  3. {
  4.   this->_M_next = __position;       
  5.   this->_M_prev = __position->_M_prev;
  6.   __position->_M_prev->_M_next = this;
  7.   __position->_M_prev = this;
  8. }

所以上述细分为两个函数：我们把上述代码进行总结：

（1）在指定的位置插入初始值为x的节点

  1. void _M_insert(iterator __position, const value_type &__x) {
  2.     _Node *__tmp = _M_create_node(__x);
  3.     __tmp->_M_next = __position;            // 第一步
  4.     __tmp->_M_prev = __position->_M_prev;   // 第二步
  5.     __position->_M_prev->_M_next = __tmp;   // 第三步
  6.     __position->_M_prev = __tmp;            // 第四步
  7. }

这种插入是在指定位置前插入，(对应到代码就是)例如实现在指定position节点为7前插入节点值9的节点(对应到代码就是tmp)，下面阐述了具体的插入流程。

list_insert

（2）在末尾依次插入n个节点值为x的节点

  1. void _M_fill_initialize(size_type __n, const value_type &__x) {
  2.     for (; __n; --__n)
  3.         _M_insert(end(), __x);
  4. }

对于上述的代码大家或许会联想到insert,它有三个。insert实现文件在libstdc++-v3/include/bits/list.tcc。

  • 第一：在指定迭代器之前插入指定元素值节点。

实现是调用前面的_M_hook函数。

  1. template<typename _Tp, typename _Alloc>
  2. typename list<_Tp, _Alloc>::iterator
  3. list<_Tp, _Alloc>::
  4. #if __cplusplus >= 201103L
  5. insert(const_iterator __position, const value_type& __x)
  6. #else
  7. insert(iterator __position, const value_type& __x)
  8. #endif
  9. {
  10.   _Node* __tmp = _M_create_node(__x);
  11.   __tmp->_M_hook(__position._M_const_cast()._M_node);
  12.   return iterator(__tmp);
  13. }
  • 第二：在指定迭代器之前插入n个指定节点值的节点。
  1. void insert(iterator __position, size_type __n, const value_type &__x) {
  2.     list __tmp(__n, __x, get_allocator());
  3.     splice(__position, __tmp);
  4. }

实现是先调用list构造函数，完成创建一个拥有n个指定节点值的list。

  1. explicit list(size_type __n, const value_type &__value = value_type(),const allocator_type &__a = allocator_type()) : _Base(_Node_alloc_type(__a)) 
  2. { _M_fill_initialize(__n, __value); }

然后使用splice函数完成从另一个list中来插入当前list。

  1. void splice(iterator __position, list &__x)
  2. {
  3.     if (!__x.empty()) {
  4.         _M_check_equal_allocators(__x);
  6.         this->_M_transfer(__position._M_const_cast(),
  7.                           __x.begin(), __x.end());
  8.     }
  9. }

其中_M_transfer追踪代码，可以知道：

  1. // Moves the elements from [first,last) before position.
  2. void
  3. _M_transfer(iterator __position, iterator __first, iterator __last) {
  4.     __position._M_node->_M_transfer(__first._M_node, __last._M_node);
  5. }

再次分析得到其来自list的基类_List_node_base，而_M_transfer实现文件在gcc-4.9.1/libstdc++-v3/src/c++98/list.cc中：

  1. void _List_node_base::
  2. _M_transfer(_List_node_base * const __first,
  3.     _List_node_base * const __last) _GLIBCXX_USE_NOEXCEPT
  4. {
  5.   if (this != __last)
  6.   {
  7.       // Remove [first, last) from its old position.
  8.       __last->_M_prev->_M_next  = this;
  9.       __first->_M_prev->_M_next = __last;
  10.       this->_M_prev->_M_next    = __first;
  12.       // Splice [first, last) into its new position.
  13.       _List_node_base* const __tmp = this->_M_prev;
  14.       this->_M_prev                = __last->_M_prev;
  15.       __last->_M_prev              = __first->_M_prev;
  16.       __first->_M_prev             = __tmp;
  17.   }
  18. }

仍然是上述的图：

list_all

经过前面分析，我们知道splice是将上述图的所代表的整个list插入指定迭代器前面，例如，我们想要在下面两个节点前面插入，具体图形步骤如下：

this代表的节点为值为8的节点，下图描述的就是在节点10与节点8中间插入整个list。

__last代表的是红色框节点，该节点为end()指向的节点，我们是不需要该节点的，所以在后面处理中，会把该节点从整个list中去除掉。

__first代表的是图中节点值为3的节点。

第一步：先将最后一个有效节点，也就是红色框的前一个节点的next指针指向指定的节点8。

list - 图5

对应代码为：

  1. __last->_M_prev->_M_next  = this;

第二步：_last的next指针指向自己。

list - 图6

对应的代码为：

  1. __first->_M_prev->_M_next = __last;

第三步：让指定迭代器之前的节点的nex指向原先list的第一个节点(__first)。

list - 图7

对应的代码为：

  1. this->_M_prev->_M_next    = __first;

第四步：保存指定迭代器的前驱节点(对应到哪图中的节点值为10的节点)。

  1. _List_node_base* const __tmp = this->_M_prev;

第五步：指定迭代器的前驱节点指向原list中实际最后一个节点(end()前一节点)。

list - 图8

对应的代码为：

  1. this->_M_prev                = __last->_M_prev;

第六步：让原list的最后一个节点(end()指向的节点)的prev指向自己。

list - 图9

对应的代码为：

  1. __last->_M_prev              = __first->_M_prev;

第七步：让原list第一个节点的prev指向第四步保存的节点。

list - 图10

对应的代码为：

  1. __first->_M_prev             = __tmp;

这样经过以上七步操作，完成了在节点8与节点10之前插入一个list。

  • 第三：从一个list范围把数据插入到指定迭代器前面。
  1. template<typename _InputIterator>
  2. void
  3. insert(iterator __position, _InputIterator __first,
  4.        _InputIterator __last) {
  5.     list __tmp(__first, __last, get_allocator());
  6.     splice(__position, __tmp);
  7. }

原理同上，只不过这个__tmp是调用另外一个构造函数。

【删除节点】

  • 删除指定节点

删除指定节点分为两个，第一个通过迭代器删除，第二个是通过元素值删除。

（1）通过迭代器删除，对应函数为erase

其中pop_front与pop_back、erase、remove底层实现基于_M_erase函数。

  1. this->_M_erase(begin());    // pop_front 不断删除起点的元素
  2. this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); // pop_back移除最后一个元素

在libstdc++-v3/include/bits/list.tcc中：

  1. erase(iterator __position)
  2. #endif
  3. {
  4.   iterator __ret = iterator(__position._M_node->_M_next);
  5.   _M_erase(__position._M_const_cast());
  6.   return __ret;
  7. }

（2）通过元素值删除，对应函数为remove

特殊情况处理，当删除元素的地址与迭代器的地址一样的时候，先保存起来，最后判断保存的迭代器是不是end()，如果不是，就删除掉。底层仍旧是通过_M_erase删除。

  1. template<typename _Tp, typename _Alloc>
  2. void list<_Tp, _Alloc>::remove(const value_type& __value)
  3. {
  4.   iterator __first = begin();
  5.   iterator __last = end();
  6.   iterator __extra = __last;
  7.   while (__first != __last)
  8.   {
  9.       iterator __next = __first;
  10.       ++__next;
  11.       if (*__first == __value)
  12.         {
  13.           // _GLIBCXX_RESOLVE_LIB_DEFECTS
  14.           // 526. Is it undefined if a function in the standard changes
  15.           // in parameters?
  16.           if (std::__addressof(*__first) != std::__addressof(__value))
  17.         _M_erase(__first);
  18.           else
  19.         __extra = __first;
  20.         }
  21.       __first = __next;
  22.   }
  23.   if (__extra != __last)
  24.     _M_erase(__extra);
  25. }

除了这个remove外，还有一个是remove_if，根据条件来删除。

  1. template<typename _Tp, typename _Alloc>
  2. template <typename _Predicate>
  3. void list<_Tp, _Alloc>::
  4. remove_if(_Predicate __pred)
  5. {
  6.     iterator __first = begin();
  7.     iterator __last = end();
  8.     while (__first != __last)
  9.     {
  10.         iterator __next = __first;
  11.         ++__next;
  12.         if (__pred(*__first))
  13.           _M_erase(__first);
  14.         __first = __next;
  15.     }
  16. }

对上述的remove的if去掉，在里面添加一个判断即可。

使用如下：

  1. bool isone(int one) {
  2.     return one==2;
  3. }
  4. int main() {
  5.     list<int> t;
  6.     t={3,4,0,2,0,10,10};
  7.     for(auto i:t) cout<<i<<" ";  // 3 4 0 2 0 10 10 
  8.     cout<<endl;
  9.     t.remove_if(isone);
  10.     for(auto i:t) cout<<i<<" ";  // 3 4 0 0 10 10 
  11.     cout<<endl;
  12. }
  • 删除一系列节点
  • 删除所有节点，对应的函数clear

（1）删除指定节点详细分析

  1. _M_erase(iterator __position)
  2. _GLIBCXX_NOEXCEPT
  3. {
  4.     __position._M_node->_M_unhook();
  5.     _Node *__n = static_cast<_Node *>(__position._M_node);
  6. #if __cplusplus >= 201103L
  7.     _M_get_Node_allocator().destroy(__n);
  8. #else
  9.     _M_get_Tp_allocator().destroy(std::__addressof(__n->_M_data));
  10. #endif
  11.     _M_put_node(__n);       // 释放内存
  12. }

其中_M_unhook实现在gcc-4.9.1/libstdc++-v3/src/c++98/list.cc，实现如下：

  1. void _List_node_base::_M_unhook() _GLIBCXX_USE_NOEXCEPT
  2. {
  3.   _List_node_base* const __next_node = this->_M_next;   // 第一步：保存后继节点
  4.   _List_node_base* const __prev_node = this->_M_prev;   // 第二步：保存前驱节点
  5.   __prev_node->_M_next = __next_node;                   // 第三步：前驱节点的next指向后继节点
  6.   __next_node->_M_prev = __prev_node;                   // 第四步：后继节点的prev指向前驱节点
  7. }

例如：删除节点值为9的节点，第三与第四步图解：

list_erase

（2）删除一系列元素详细分析

  1. iterator
  2. #if __cplusplus >= 201103L
  3. erase(const_iterator __first, const_iterator __last) noexcept
  4. #else
  5. erase(iterator __first, iterator __last)
  6. #endif
  7. {
  8.     while (__first != __last)
  9.         __first = erase(__first);
  10.     return __last._M_const_cast();
  11. }

使用erase，删除给定迭代器范围内的数据。

（3）删除所有元素详细分析

清空元素，并初始化，回到list默认状态。

  1. void clear()
  2. _GLIBCXX_NOEXCEPT
  3. {
  4.     _Base::_M_clear();
  5.     _Base::_M_init();
  6. }

其中_M_clear实现在：libstdc++-v3/include/bits/list.tcc中：

  1. _List_base<_Tp, _Alloc>::
  2. _M_clear() _GLIBCXX_NOEXCEPT
  3. {
  4.   typedef _List_node<_Tp>  _Node;
  5.   _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
  6.   while (__cur != &_M_impl._M_node)
  7.     {
  8.       _Node* __tmp = __cur;         // 保存节点
  9.       __cur = static_cast<_Node*>(__cur->_M_next);  // 往后遍历
  10.     #if __cplusplus >= 201103L
  11.       _M_get_Node_allocator().destroy(__tmp);
  12.     #else
  13.       _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
  14.     #endif
  15.       _M_put_node(__tmp);   // 释放内存
  16.     }
  17. }

_M_init实现，全部指向自己即可。

  1. void _M_init()
  2. _GLIBCXX_NOEXCEPT
  3. {
  4.     this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
  5.     this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
  6. }

【元素访问】

每个都实现了两个版本：引用与常引用。

  • front 返回第一个元素
  1. reference front()
  2. _GLIBCXX_NOEXCEPT
  3. { return *begin(); }
  4. const_reference
  5. front() const
  6. _GLIBCXX_NOEXCEPT
  7. { return *begin(); }
  • 返回最后一个元素
  1. reference
  2. back()
  3. _GLIBCXX_NOEXCEPT
  4. {
  5.     iterator __tmp = end();
  6.     --__tmp;
  7.     return *__tmp;
  8. }
  9. const_reference
  10. back() const
  11. _GLIBCXX_NOEXCEPT
  12. {
  13.     const_iterator __tmp = end();
  14.     --__tmp;
  15.     return *__tmp;
  16. }

【算法】

  • unique

从容器中的每个连续的相等元素组中除去除第一个元素外的所有元素。

请注意，只有与列表容器紧邻的元素相比，该元素才从列表容器中删除。因此，此功能对于排序列表特别有用。

  1. template<typename _Tp, typename _Alloc>
  2. template <typename _BinaryPredicate>
  3.   void
  4.   list<_Tp, _Alloc>::
  5.   unique(_BinaryPredicate __binary_pred)
  6.   {
  7.     iterator __first = begin();
  8.     iterator __last = end();
  9.     if (__first == __last)
  10.   return;
  11.     iterator __next = __first;
  12.     while (++__next != __last)
  13.   {
  14.     // 满足条件就删除
  15.     if (__binary_pred(*__first, *__next))
  16.        // 删除
  17.       _M_erase(__next);
  18.     else
  19.       __first = __next;
  20.     __next = __first;
  21.   }
  22.   }

举例如下：

  1. // list::unique
  2. #include <iostream>
  3. #include <cmath>
  4. #include <list>
  6. // a binary predicate implemented as a function:
  7. bool same_integral_part (double first, double second)
  8. { return ( int(first)==int(second) ); }
  10. // a binary predicate implemented as a class:
  11. struct is_near {
  12.   bool operator() (double first, double second)
  13.   { return (fabs(first-second)<5.0); }
  14. };
  16. int main ()
  17. {
  18.   double mydoubles[]={ 12.15,  2.72, 73.0,  12.77,  3.14,
  19.                        12.77, 73.35, 72.25, 15.3,  72.25 };
  20.   std::list<double> mylist (mydoubles,mydoubles+10);
  22.   mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,
  23.                              // 15.3,  72.25, 72.25, 73.0,  73.35
  25.   mylist.unique();           //  2.72,  3.14, 12.15, 12.77
  26.                              // 15.3,  72.25, 73.0,  73.35
  28.   mylist.unique (same_integral_part);  //  2.72,  3.14, 12.15
  29.                                        // 15.3,  72.25, 73.0
  31.   mylist.unique (is_near());           //  2.72, 12.15, 72.25
  33.   std::cout << "mylist contains:";
  34.   for (std::list<double>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
  35.     std::cout << ' ' << *it;
  36.   std::cout << '\n';
  38.   return 0;
  39. }

上述排序后会删除所有的重复元素，只剩下一个，而不排序只会删除重复且连续的元素。

  • merge

merge源码实现采用前面_M_transfer函数，假设现在有两个list，分别是list1与list2。list1中的元素与list2中的元素进行比较，如果list1中元素值小于list2中元素值，则对list1迭代器++，不进行任何操作，而如果list1中的元素值大于list2中的元素值，那么每次将list2这个小的元素对应的迭代器塞入_M_transfer函数中，通过这个函数完成向list1中刚才比较的迭代器前面插入list2较小的元素，那么最后所有元素都会被插入到list1中。

当list1已经遍历完毕，而list2还没有遍历完毕，那么只需要执行一次_M_transfer，将list2链表从当前迭代器开始到最后的end插入到list1的末尾即可。

  1. template<typename _Tp, typename _Alloc>
  2. void
  3. list<_Tp, _Alloc>::
  4. #if __cplusplus >= 201103L
  5. merge(list&& __x)
  6. #else
  7. merge(list& __x)
  8. #endif
  9. {
  10.   // _GLIBCXX_RESOLVE_LIB_DEFECTS
  11.   // 300. list::merge() specification incomplete
  12.   if (this != &__x)
  13.   {
  14.       _M_check_equal_allocators(__x);
  16.       iterator __first1 = begin();
  17.       iterator __last1 = end();
  18.       iterator __first2 = __x.begin();
  19.       iterator __last2 = __x.end();
  20.       while (__first1 != __last1 && __first2 != __last2)
  21.         if (*__first2 < *__first1)
  22.          {
  23.             iterator __next = __first2;
  24.             _M_transfer(__first1, __first2, ++__next);
  25.             __first2 = __next;
  26.          }
  27.         else
  28.           ++__first1;
  29.       if (__first2 != __last2)
  30.         _M_transfer(__last1, __first2, __last2);
  31.    }
  32. }

使用：

  1. int main() {
  2.     list<int> l1 = {2,3,5,7};
  3.     list<int> l2 = {1,10,9,5};
  4.     l1.sort();
  5.     l2.sort();
  6.     l1.merge(l2);
  7.     for(auto i:l1) cout<<i<<" ";    // 1 2 3 5 5 7 9 10
  8.     return 0;
  9. }
  • sort

由于STL本身的排序算法sort接受的输入迭代器是随机访问迭代器，但是双向list链表容器的访问方式是双向迭代器，因此，不能使用STL本身的排序算法sort，必须自己定义属于自己访问的排序算法。我们从源码的剖析中，可以看到该排序算法思想类似于归并排序。

sort中splice调用的是：

  1. void splice(const_iterator __position, list& __x, const_iterator __i) noexcept
  2. { splice(__position, std::move(__x), __i); }

进一步分析：

  1. void
  2. splice(iterator __position, list &__x, iterator __i)
  3. {
  4.     iterator __j = __i._M_const_cast();
  5.     ++__j;
  6.     if (__position == __i || __position == __j)
  7.         return;
  9.     if (this != &__x)
  10.         _M_check_equal_allocators(__x);
  12.     this->(__position._M_const_cast(),
  13.                       __i._M_const_cast(), __j);
  14. }

最后调用的是_M_transfer。

在sort中还有一个函数swap，完成两个链表交换，实现代码在gcc-4.9.1/libstdc++-v3/src/c++98/list.cc中：

  1. void
  2. _List_node_base::swap(_List_node_base& __x,
  3.           _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT
  4. {
  5.       if ( __x._M_next != &__x )
  6.     {
  7.       if ( __y._M_next != &__y )
  8.         {
  9.           // Both __x and __y are not empty.
  10.           std::swap(__x._M_next,__y._M_next);
  11.           std::swap(__x._M_prev,__y._M_prev);
  12.           __x._M_next->_M_prev = __x._M_prev->_M_next = &__x;
  13.           __y._M_next->_M_prev = __y._M_prev->_M_next = &__y;
  14.         }
  15.       else
  16.         {
  17.               // __x is not empty, __y is empty.
  18.               __y._M_next = __x._M_next;
  19.               __y._M_prev = __x._M_prev;
  20.               __y._M_next->_M_prev = __y._M_prev->_M_next = &__y;
  21.               __x._M_next = __x._M_prev = &__x;
  22.             }
  23.         }
  24.       else if ( __y._M_next != &__y )
  25.         {
  26.           // __x is empty, __y is not empty.
  27.           __x._M_next = __y._M_next;
  28.           __x._M_prev = __y._M_prev;
  29.           __x._M_next->_M_prev = __x._M_prev->_M_next = &__x;
  30.           __y._M_next = __y._M_prev = &__y;
  31.         }
  32. }

具体的实现思路是，判断两个链表为空还是不为空，然后修改next指针与prev指针。

下面来看看强大的sort：

  1. template<typename _Tp, typename _Alloc>
  2. void
  3. list<_Tp, _Alloc>::
  4. sort() {
  5.     // Do nothing if the list has length 0 or 1.
  6.     if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
  7.         && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) {
  8.         list __carry; // 辅助链表，用于从a中提取元素以及临时保存两个链表的合并结果
  9.         list __tmp[64]; // 保存着当前每一个归并层次的结果, i号链表保存的元素个数为2的i次方或者0
  10.         list *__fill = &__tmp[0]; // 表示当前最大归并排序的层次，while循环之后__fill变成log2(list.size())
  11.         list *__counter;
  13.         do {
  14.             __carry.splice(__carry.begin(), *this, begin()); //把当前链表的第一个节点放在carry链表头
  16.             for (__counter = &__tmp[0];
  17.                  __counter != __fill && !__counter->empty();
  18.                  ++__counter) {
  19.                 __counter->merge(__carry);  // 两个有序链表合并
  20.                 __carry.swap(*__counter); // 类似于交换链表carry和counter[i]内容  
  21.             }
  22.             __carry.swap(*__counter); // 类似于交换链表carry和counter[i]内容  
  23.             if (__counter == __fill)
  24.                 ++__fill;
  25.         } while (!empty());
  26.         // 每两个进行归并，依次网上，直到最后*(__fill-1)保存最后的排序结果。然后交换到当前list中。
  27.         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
  28.             __counter->merge(*(__counter - 1));
  29.         swap(*(__fill - 1)); 
  30.     }
  31. }

上述代码看起来比较难懂，在网上查找后发现，G2.9中：

  1. template <class T, class Alloc>
  2. void list<T, Alloc> :: sort(){
  3.     // 判断链表是否为空或者只有一个元素
  4.     if(node->next == node || link_type(node->next)->next == node){
  5.         return;
  6.     }
  8.     list<T, Alloc> carry;
  9.     list<T, alloc> counter[64];
  10.     int fill = 0;
  11.     while(!empty()){
  12.         carry.splice(carry.begin(), *this, begin());
  13.         int i = 0;
  14.         while(i < fill && !counter[i].empty()){
  15.             counter[i].merge(carry);
  16.             carry.swap(counter[i++]);
  17.         }
  18.         carry.swap(counter[i]);
  19.         if(i == fill){
  20.             ++fill;
  21.         } 
  22.     }
  24.     for(int i = 1; i < fill; ++i){
  25.         counter[i].merge(counter[i-1]);
  26.     }
  27.     swap(counter[fill-1]);
  28. }

对应的外部实现是：

  1. void sortList(list<int> &l) {
  2.     if (l.size() <= 1) {
  3.         return;
  4.     }
  5.     list<int> carry;       // 辅助链表，用于从a中提取元素以及临时保存两个链表的合并结果
  6.     list<int> counter[64]; // 保存着当前每一个归并层次的结果, i号链表保存的元素个数为2的i次方或者0
  7.     int fill = 0;          // 表示当前最大归并排序的层次，while循环之后fill变成log2(a.size())
  9.     while (!l.empty()) {
  10.         carry.splice(carry.begin(), l, l.begin()); // 将链表a中的第一个元素移动至carry开头
  11.         int i = 0;
  12.         // 从小往大不断合并非空归并层次直至遇到空层或者到达当前最大归并层次
  13.         while (i < fill && !counter[i].empty()) {
  14.             counter[i].merge(carry);    // 链表合并，结果链表是有序的，必须保证合并前两个链表是有序的
  15.             carry.swap(counter[i++]);   // 链表元素互换
  16.         }
  17.         carry.swap(counter[i]);
  18.         if (i == fill) {       // i到达当前最大归并层次，说明得增加一层
  19.             ++fill;
  20.         }
  21.     }
  23.     for (int i = 1; i < fill; ++i) {  // 将所有归并层次的结果合并得到最终结果counter[fill - 1]
  24.         counter[i].merge(counter[i - 1]);
  25.     }
  26.     l.swap(counter[fill - 1]);
  27. }

这一块可以参考

https://blog.csdn.net/chenhanzhun/article/details/39337331

上面给出了详细的过程图解。

我们再次将G4.9转换对应的外部实现：

  1. void sortList1(list<int> &l) {
  2.     typedef list<int> list;
  3.     if (l.size() <= 1) {
  4.         return;
  5.     }
  6.     list __carry;
  7.     list __tmp[64];
  8.     list *__fill = &__tmp[0];
  9.     list *__counter;
  10.     do {
  11.         __carry.splice(__carry.begin(), l, l.begin());
  12.         for (__counter = &__tmp[0];
  13.              __counter != __fill && !__counter->empty();
  14.              ++__counter) {
  15.             __counter->merge(__carry);
  16.             __carry.swap(*__counter);
  17.         }
  18.         __carry.swap(*__counter);
  19.         if (__counter == __fill) ++__fill;
  20.     } while (!l.empty());
  22.     for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
  23.         __counter->merge(*(__counter - 1));
  25.     l.swap(*(__fill - 1));
  26. }

使用：

  1. int main() {
  2.     list<int> l = {7, 5, 8, 1};
  3.     cout << "===============排序前==============" << endl;
  4.     for (auto i:l) cout << i << " ";
  5.     cout << endl;
  6.     sortList1(l);
  7.     cout << "===============排序后==============" << endl;
  8.     for (auto i:l) cout << i << " ";
  9.     cout << endl;
  11.     return 0;
  12. }

【操作符重载】

  1. template<typename _Tp, typename _Alloc>
  2. inline bool
  3. operator==(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) {
  4.     typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
  5.     const_iterator __end1 = __x.end();
  6.     const_iterator __end2 = __y.end();
  8.     const_iterator __i1 = __x.begin();
  9.     const_iterator __i2 = __y.begin();
  10.     while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
  11.         ++__i1;
  12.         ++__i2;
  13.     }
  14.     return __i1 == __end1 && __i2 == __end2;
  15. }

实现思路是，迭代判断两个迭代器是否都抵达末尾。

剩下就是其他的操作符重载，比较简单，就不阐述了。其中lexicographical_compare实现在c++-v3/src/c++98/stl_algobase.h中，该函数是按照字典序测试[frist1,last1)是否小于[first2,last2)。该函数使用opeartor<或者是comp进行比较。其行为类似于：如果两个序列长度不同，并且短序列和长序列头部完全一样，例如example和examplee.那么，长度大的字典序比短序的大。

  1. template <class InputIterator1, class InputIterator2>
  2. bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
  3. InputIterator2 first2, InputIterator2 last2)
  4. {
  5.     while (first1!=last1)
  6.     {
  7.         if (first2==last2 || *first2<*first1) return false;
  8.         else if (*first1<*first2) return true;
  9.         ++first1; ++first2;
  10.     }
  11.     return (first2!=last2);
  12. }

使用：

  1. int main() {
  2.      vector<char> v1{'h','e','l','l','o'};
  3.     vector<char> v2{'h','e','l','l','o','o'};
  4.     vector<char> v3{'h','e','l','m','o'};
  5.     cout<<"v1=";
  6.     for(char i:v1)
  7.         cout<<i<<" ";
  8.     cout<<endl;
  9.     cout<<"v2=";
  10.     for(char i:v2)
  11.         cout<<i<<" ";
  12.     cout<<endl;
  13.     cout<<"v3=";
  14.     for(char i:v3)
  15.         cout<<i<<" ";
  16.     cout<<endl;
  18.     if(lexicographical_compare(v1.begin(),v1.end(),v2.begin(),v2.end()))
  19.         cout<<"v1 is less than v2 "<<endl;
  20.     else
  21.         cout<<"v2 is less than v1 "<<endl;
  23.     if(lexicographical_compare(v1.begin(),v1.end(),v3.begin(),v3.end()))
  24.         cout<<"v1 is less than v3 "<<endl;
  25.     else
  26.         cout<<"v3 is less than v1 "<<endl;
  27. }

其它重载操作符如下：

  1. template<typename _Tp, typename _Alloc>
  2. inline bool
  3. operator<(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) {
  4.     return std::lexicographical_compare(__x.begin(), __x.end(),
  5.                                         __y.begin(), __y.end());
  6. }
  8. /// Based on operator==
  9. template<typename _Tp, typename _Alloc>
  10. inline bool
  11. operator!=(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) { return !(__x == __y); }
  13. /// Based on operator<
  14. template<typename _Tp, typename _Alloc>
  15. inline bool
  16. operator>(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) { return __y < __x; }
  18. /// Based on operator<
  19. template<typename _Tp, typename _Alloc>
  20. inline bool
  21. operator<=(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) { return !(__y < __x); }
  23. /// Based on operator<
  24. template<typename _Tp, typename _Alloc>
  25. inline bool
  26. operator>=(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) { return !(__x < __y); }

1.2 list基类源码

_list_base中有一个结构体:_List_impl,而_List_impl中有一个List_node_base。

  1. class _List_base
  2. {
  3. protected:
  4.   typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
  5.     _Node_alloc_type;
  7.   typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
  9.   struct _List_impl
  10.   : public _Node_alloc_type
  11.   {
  12.     __detail::_List_node_base _M_node;
  14.     _List_impl()
  15.     : _Node_alloc_type(), _M_node()
  16.     { }
  18.     _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
  19.     : _Node_alloc_type(__a), _M_node()
  20.     { }
  22.     #if __cplusplus >= 201103L
  23.     _List_impl(_Node_alloc_type&& __a) _GLIBCXX_NOEXCEPT
  24.     : _Node_alloc_type(std::move(__a)), _M_node()
  25.     { }
  26.     #endif
  27.   };
  29.   _List_impl _M_impl;
  30. };

最后形成的图就是:

list's iterator_design

所以如果求:

  1. sizeof(list<int>)=16

原因是:

list的sizeof为1,所以sizeof来源于基类_list_base,而_list_base中有一个结构体:_List_impl,而_List_impl中有一个_List_node_base.

我们知道_List_node_base,里面有两个指针,在64位上,每个为8字节,共16字节。

2.list's Iterator剖析

2.1 iterator

list的iterator定义

  1. template<typename _Tp>
  2. struct _List_iterator
  3. {
  4.   typedef _List_iterator<_Tp>                _Self;
  5.   typedef _List_node<_Tp>                    _Node;
  7.   typedef ptrdiff_t                          difference_type;
  8.   typedef std::bidirectional_iterator_tag    iterator_category;
  9.   typedef _Tp                                value_type;
  10.   typedef _Tp*                               pointer;
  11.   typedef _Tp&                               reference;
  13.    // The only member points to the %list element.
  14.    __detail::_List_node_base* _M_node;         
  15.    //  _List_node(节点的数据部分) -> _List_node_base(前指针与后指针)
  17.   _List_iterator() _GLIBCXX_NOEXCEPT
  18.   : _M_node() { }
  20.   explicit
  21.   _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
  22.   : _M_node(__x) { }
  24.   _Self
  25.   _M_const_cast() const _GLIBCXX_NOEXCEPT
  26.   { return *this; }
  28.   // The only member points to the %list element.
  29.   __detail::_List_node_base* _M_node;
  30. };

内部重载函数:

  1. // Must downcast from _List_node_base to _List_node to get to _M_data.
  2. // 重载*操作符
  3. reference operator*() const _GLIBCXX_NOEXCEPT
  4. { 
  5.     return static_cast<_Node*>(_M_node)->_M_data; 
  6. }
  8. // 重载->操作符
  9. pointer operator->() const _GLIBCXX_NOEXCEPT
  10. { 
  11.     return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); 
  12. }
  14. // 重载前置++操作符  ++i
  15. _Self& operator++() _GLIBCXX_NOEXCEPT   
  16. { 
  17.     _M_node = _M_node->_M_next;
  18.     return *this;
  19. }
  21. // 重载后置++操作符 i++
  22. _Self operator++(int) _GLIBCXX_NOEXCEPT
  23. {
  24.     _Self __tmp = *this;             // 记录原值  *调用的是拷贝构造函数
  25.     _M_node = _M_node->_M_next;      // 进行操作
  26.     return __tmp;                    // 返回原值
  27. }
  29. // 重载前置--操作符  --i
  30. _Self& operator--() _GLIBCXX_NOEXCEPT
  31. {
  32.     _M_node = _M_node->_M_prev;
  33.     return *this;
  34. }
  35. // 重载后置--操作符  --i
  36. _Self operator--(int) _GLIBCXX_NOEXCEPT
  37. {
  38.     _Self __tmp = *this;
  39.     _M_node = _M_node->_M_prev;
  40.     return __tmp;
  41. }
  42. // 重载++操作符
  43. bool operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
  44. { 
  45.     return _M_node == __x._M_node; 
  46. }
  47. // 重载!=操作符
  48. bool operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
  49. { 
  50.     return _M_node != __x._M_node; 
  51. }

2.2 结点设计

iterator内部的_List_node,这里可以得到继承自_List_node_base.

_List_node放数据部分

_List_node_base放前后指针

  1. /// An actual node in the %list.
  2. template<typename _Tp>
  3. struct _List_node : public __detail::_List_node_base
  4. {
  5.   ///< User's data.
  6.   _Tp _M_data;
  8. #if __cplusplus >= 201103L
  9.   template<typename... _Args>
  10.     _List_node(_Args&&... __args)
  11. : __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...) 
  12.     { }
  13. #endif
  14. };

_List_node_base代码:

  1. namespace __detail
  2. {
  3.     _GLIBCXX_BEGIN_NAMESPACE_VERSION
  4.     /// Common part of a node in the %list. 
  5.     struct _List_node_base
  6.     {
  7.       _List_node_base* _M_next;
  8.       _List_node_base* _M_prev;
  10.       static void
  11.       swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
  13.       void
  14.       _M_transfer(_List_node_base* const __first,
  15.           _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
  17.       void
  18.       _M_reverse() _GLIBCXX_USE_NOEXCEPT;
  20.       void
  21.       _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
  23.       void
  24.       _M_unhook() _GLIBCXX_USE_NOEXCEPT;
  25.     };
  27.     _GLIBCXX_END_NAMESPACE_VERSION
  28. } // namespace detail

迭代器在设计的时候,总是保持前闭后开原则,例如iter->begin()指向第一个元素,iter->end()指向实际最后一个元素的下一个元素,故最后的设计刻意在环形list尾部加一个空白结点,用以符合STL前闭后开原则.