STL 之 List简析

前言

记得我的一位老师说过，

好的结构一定会有好的结果。

C++的STL是数据结构与算法的集大成者，而其中的list就是典型代表。现在我手中有三种源码，分别是侯捷老师名著中用到的经典的SGI版本，VS下的版本，以及SGI的比较新的版本(实际上就是GCC编译器使用的新版本)。本人实力有限，只能解释一部分内容。

list介绍

list，也就是所谓的链表，是一个节点一个节点通过指连在一起的数据结构。而链式结构在生活中也很常见，比如项链，车链子。它的好处自然就是便于调整长短。比起vector对于调整size的硬伤，list完美的化解这一问题。

list的节点

list既然是通过指针链接在一起，它的每个节点自然应该封装指针。事实上，源码就是这样做的。

// SGI
struct _List_node_base { //我称之为节点的base类
  _List_node_base* _M_next; // 指向后一个节点 
  _List_node_base* _M_prev; // 指向前一个节点
};
template <class _Tp>
struct _List_node : public _List_node_base { // 真正的list节点类，继承节点的base类。
  _Tp _M_data; //数据域
};

SGI版本的节点设计，用一个节点base类封装前驱指针和后继指针，然后再用一个存储数据的类去继承节点的base类。后面你会看到，迭代器，list都是如此设计。而在新版本中SGI依旧使用这种继承的方式。而VS不太相同。

// VS
template <class _Value_type, class _Voidptr>
struct _List_node { // list node
    using value_type = _Value_type; //using的用法在这里等同typedef
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _List_node>;
    _Nodeptr _Next; // successor node, or first element if head
    _Nodeptr _Prev; // predecessor node, or last element if head
    _Value_type _Myval; // the stored value, unused if head
    ...};

英文注释来自VS源码自带。VS下的源码使用了C++11的using的新功能，这里不拓展。VS下的节点，将两个指针和数据域封装在了一起，没有使用继承的方式。

list的迭代器

SGI迭代器

// SGI
struct _List_iterator_base { //迭代器的base类
	//...
 _List_node_base* _M_node;
 	//...
 };
 
 template<class _Tp, class _Ref, class _Ptr>
struct _List_iterator : public _List_iterator_base { //继承base
  typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator; 
  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
  typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;
  // 构造函数
_List_iterator(_Node* __x) : _List_iterator_base(__x) {}
// operator*重载 和 operator->重载
  reference operator*() const { return ((_Node*) _M_node)->_M_data; }
  pointer operator->() const { return &(operator*()); } 
  _Self& operator++() {  // 前置++，返回reference
    this->_M_incr();
    return *this;
  }
  _Self operator++(int) {  //后置++，返回value
    _Self __tmp = *this;
    this->_M_incr();
    return __tmp;
    // ... 后面还有很多源码
  }
};

SGI版本的迭代器依旧是使用继承，而_List_iterator_base这个类里封装了_List_node_base的一个指针。这里我们可以大致看出，设计者想让迭代器的移动作为一个部分，迭代器的data作为一部分。而真正的迭代器设计的非常巧妙，因为迭代器有普通和const的，怎么区分呢？SGI在list的迭代器中增加了两个模板参数，分别代表引用和指针，传过来的是普通的Ref和Ptr就是iterator；传过来的是const的Ref和const的Ptr就是 const_iterator。

• 1

迭代器应该足够聪明，可以完成一个指针应该有的操作。所以重载了operator*和operator->。当对一个迭代器取星号，应该是拿到节点的值。
而operator->有一点意思。当我们在使用operator->时，编译器会做出一点特殊处理，它会再加上一个->,想象这样一个类，

class Data{
private:
	int _year = 0;
}

list<Data> ld;
ld.push_back(Data());

auto it = ld.begin();
cout << it->_year << endl; // 实际上是 it->->_year

• 2

而链表迭代器的++应该是到下一个节点，iterator应该足够聪明能做到这一点。
int类型的前置++可以加上两次，所以链表的迭代器返回reference。
int类型的后置++不能被加上两次，所以链表的迭代器返回value。

int i = 0;
++++i; // right
i++++; // wrong

list<int>::iterator it = l.begin();
++++it; //right
it++++; //wrong

根据effectiveC++中提到的，链表的迭代器的前置++和后置++应该与内置类型高度一致。

VS下的迭代器的不同之处

SGI版本的迭代器设计已经是巧妙无比，但也有些许的问题，就是太多模板参数不好理解。而VS版本将list迭代器的模板参数降低为一个。

// VS  
template <class _Mylist>
class _List_const_iterator { //const迭代器实现
 _NODISCARD reference operator*() const noexcept; //这些成员方法我只保留了声明
  _NODISCARD pointer operator->() const noexcept; //因为实现与SGI版本的大抵相同
    _List_const_iterator& operator++() noexcept;  //主要剖析实现的思想
   _List_const_iterator operator++(int) noexcept;
 // ...
 };
 template <class _Mylist>
class _List_iterator : public _List_const_iterator<_Mylist> { // 普通迭代器，继承了const迭代器
 using _Mybase           = _List_const_iterator<_Mylist>; // typedef一下，_Mybase就是const迭代器

 _NODISCARD reference operator*() const noexcept {
        return const_cast<reference>(_Mybase::operator*()); //复用const迭代器的operator*
    }														// + 转型去掉返回值的const
    _NODISCARD pointer operator->() const noexcept {
        return pointer_traits<pointer>::pointer_to(**this); //这个没有复用，但是我认为可以复用
    }														//也有可能是代码比较短，没有必要。
    _List_iterator& operator++() noexcept {
        _Mybase::operator++(); //复用const迭代器的前置++
        return *this;
    }
    _List_iterator operator++(int) noexcept {
        _List_iterator _Tmp = *this;
        _Mybase::operator++(); //复用const迭代器的后置++
        return _Tmp;
    }

我们可以看到VS下的迭代器也是很巧妙！vs版为list的iterator和const_iterator分别写了一个类，这样就只需要传一个模板参数，然后在类里面定义出reference和pointer，这样就搞定了迭代器。

但是，有一个很大的问题，iterator和const_iterator两个类的成员方法是几乎一样的，除了参数和返回值。这有大量重复，所以更巧秒的地方就是vs版用普通迭代器去继承了const迭代器的类，然后复用const类中所有的成员方法。这实际上是const的复用问题，用非const成员去调用const成员。实际上在最新版本的GCC源码中，list的迭代器也被分成了普通和const，但是没有复用。

list整体结构

STL中的list是一个双向循环的链表，实际上，为了区分begin和end，专门加入了一个所谓的哨兵节点，这个手法也在红黑树中使用。而SGI和VS都还专门区分了头节点和一般节点，我觉得实在没有必要。

list的成员方法

template <class _Tp, class _Alloc>
class _List_base 
{
public:
 // ...
protected:
  _List_node<_Tp>* _M_node;
};

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> { // 继承list的base类
public:
  typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator; //普通迭代器
  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; //const迭代器
public:
  explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
  
  iterator begin()             { return (_Node*)(_M_node->_M_next); } //返回iterator 
  const_iterator begin() const { return (_Node*)(_M_node->_M_next); } //返回const_iterator

  iterator end()             { return _M_node; } //返回iterator
  const_iterator end() const { return _M_node; } //返回const_iterator
  iterator insert(iterator __position, const _Tp& __x); //insert，这里我只给出了声明
  iterator insert(iterator __position) { return insert(__position, _Tp()); } //insert的重载，调用上面一个insert
   void push_front(const _Tp& __x) { insert(begin(), __x); } //复用insert
  void push_back(const _Tp& __x) { insert(end(), __x); } //复用insert
  // ...
  };

以上就是SGI版本list的大概实现，可以看到其中也有大量复用，而在VS下的list让我难以下咽，能力不足，不做讲解。
(全文完)