简介

最近在看侯捷老师的STL剖析课程。边看课顺便记下笔记，算是对自己的监督吧。侯捷老师的课程选用的是cygnus C++ 2.91.57 for windows 版本，虽然年代久远但是看起来要容易很多，而我看的是SGI的STL版本，内容上应该差不多，主要是阅读起来方便。最近在看书，我很喜欢侯捷老师书中的一句话，“天下大事必作于细”，与君共勉。

List内容介绍

List 在标准库中指的是双向链表，而我们在数据结构中自己定义的可能是单向链表，基本原理差不多。另外，要注意的是标准库的双向链表其实是环状链表，示意图如下：
list2
注意图中有一个灰色的节点，该节点就是我们常用的list.end()尾后迭代器所指向的地方。但是要注意该节点不属于我们定义的list内容，因此对它解引用会出现越界的错误。

List代码简析

下面的代码是对list_node的定义，从类模板的定义中可以知道，一个节点包括两个空指针和一个T类型的data。空指针其实可以换为list_node类型指针，后面的标准库中进行了更换。空指针是无类型指针，任何指针都可以直接赋值给它。

template <class T>
struct __list_node 
{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

接下来看下运算符重载，这主要是针对list中iterator的运算符。iterator其实也是一个类模板。下面看看主要代码，代码中的类型定义不要太过于纠结，主要看其实现原理。

template <class T, class Alloc=alloc>
class list{
protected:
    typedef __list_node<T> list_node;
public:
    typedef list_node* link_type;
    typedef __list_iterator<T, T&, T*> iterator;
protected:
    link_type node;
};
template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node<T>* link_type;
    typedef ptrdiff_t difference_type;
    link_type node;
    reference operator*() const {return (*node).data;}
    pointer operator->() const {return &(operator*());}
    self & operator++()
    {node = (link_type)((*node).next); return *this;}
    self operator++(int)
    {self tmp = *this; ++*this; return tmp;}
}

其中，我觉得首先要注意的是运算符重载的顺序，我们可以发现iterator的解引用重载发生在(->)操作符重载之前，而后置递增运算符在前置运算符之后，其中的目的很明显，主要是后一个要用到前一个，所以我们在用到运算符重载的时候也应该注意这样的顺序，减少代码量。

递增运算符重载肯定返回的是调用者本身的类型即iterator类型。所以是返回*this。而前置递增运算符返回的是+1之后的iterator，而这里的+1其实就是让原先的指针node变成下一个node。注意前置运算符返回的是引用，而后置运算符不是。后置运算符多加了一个函数参数int，加上该参数的目的是为了区分前置与后置运算符，理由是当我们在调用这两种运算符时，只有一个函数参数即iterator的对象，所以无法区分，因此加上了一个函数参数int。而我们在调用时却不用写成i++5，理由是编译器会给我们加上，然后就可以区分了。后置递增运算符需要先保存以前的对象，然后再利用前置运算符进行递增，饭后旧的iterator。

解引用和(->)运算符返回的类型有一定差别，分别是引用和指针。这两者最终还是调用的built-in type的操作。举个例子：

list<Foo>::iterator ite;
ite->method();
//相当于(*ite).method, *ite获得一个 Foo object;最后就是 object.method()
//相当于(&(*ite))->method(); &(*ite)得到一个对象指针，然后就相当于指针调用一个method;

另外需要注意的是在后置运算符重载的定义中 self tmp = *this 调用的是复制构造函数而不是*重载运算符。++*this 调用的是前置运算符重载，因为这是存在的运算符优先级关系。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。