STL的list实现

最近在学习Mark Weiss的《数据结构与算法分析（C++描述）》一书，里面介绍了list的实现，非常值得学习（在这里顺便也推荐一下这本书 ，Mark Weiss的另一本数据结构与算法分析C语言描述是我大学时候数据结构课的教材，该书是我大学课本中个人认为最为出色的一本教材，《数据结构与算法分析（C++描述）》是他关于数据结构与算法分析的另一本著作，我认为这本书同样非常的棒，值得一读）。list其实就是链表，链表算是数据结构中最常见的一种了，不过由于不能随机存取元素，因此用的场合并不是很多。不过作为一个C++程序员，了解一下它的实现无论如何都是非常必要的，对于深入理解C++的模板，STL设计思想以及迭代器模式都是很有好处的。
老规矩，先上代码

#include "stdafx.h"
#include <iostream>

using namespace std;

template<class T>
class LinkedList
{
public:
    struct Node
    {
        T t;
        Node * next;
        Node * prev;
        Node() : next(NULL), prev(NULL) {}
    };

    void init()
    {
        tail = head = new Node;
        head->next = new Node;
        head->next->prev = head;
    }

    LinkedList() : head(NULL), tail(NULL), Size(0)
    {
        init();
    }

    LinkedList(LinkedList &aList) : head(NULL), tail(NULL), Size(0)
    {
        init();
        for (LinkedList<T>::iterator iter = aList.begin();
            iter != aList.end();
            iter++)
        {
            push_back(*iter);
        }
    }

    const LinkedList & operator=(LinkedList<T> &aList)
    {
        if (&aList != this)
        {
            clear();
            for (LinkedList<T>::iterator iter = aList.begin();
                iter != aList.end();
                iter++)
            {
                push_back(*iter);
            }
        }
        return *this;
    }


    void push_back(T t)
    {
        Node * endNode = tail->next;
        tail->next = new Node;
        tail->next->prev = tail;
        tail = tail->next;
        tail->t = t;
        tail->next = endNode;
        endNode->prev = tail;
        Size++;
    }
    void pop_back()
    {
        if (empty())
            return;
        Node * newTail = tail->prev;
        Node * endNode = tail->next;
        newTail->next = endNode;
        endNode->prev = newTail;
        delete tail;
        tail = newTail;
        Size--;
    }
    bool empty() {return size() == 0;}
    int size() {return Size;}

    // inner class iterator
    class iterator
    {
    public:
        iterator() {}
        iterator & operator++()
        {
            current = current->next;
            return *this;
        }
        iterator operator++(int)
        {
            iterator oldIter = *this;
            ++(*this);
            return oldIter;
        }
        const T & operator*() const
        {
            return retrieve();
        }
        bool operator!=(iterator& rhs) const
        {
            return this->current != rhs.current;
        }
    protected:
        LinkedList<T> *theList;
        Node *current;

        iterator(LinkedList<T> & lst, Node * p) : theList(&lst), current(p) {}
        T &retrieve() const
        {
            return current->t;
        }
        friend class LinkedList<T>;
    };

    iterator begin()
    {
        iterator iter(*this, head->next);
        return iter;
    }
    iterator end()
    {
        iterator iter(*this, tail->next);
        return iter;
    }

    void clear()
    {
        while (!empty())
            pop_back();
    }

    virtual ~LinkedList()
    {
        while (!empty())
            pop_back();
    }
private:
    Node * head;
    Node * tail;
    int Size;
};

template <typename Iterator, typename Object>
Iterator find(Iterator start, Iterator end, const Object & x)
{
    Iterator iter = start;
    for (; iter != end; ++iter)
    {
        if (*iter == x)
            break;
    }
    return iter;
}

int _tmain(int argc, _TCHAR* argv[])
{
    // initialize two linkedlist L
    LinkedList<int> L;
    for (int i = 1; i <= 30; i++)
        L.push_back(i);

     LinkedList<int>::iterator iter = find(L.begin(), L.end(), 30);
    if (iter != L.end())
        cout << "Iterator found, the value is " << *iter << endl;
    else
        cout << "Iterator not found" << endl;

    return 0;
}

//eof

      不到两百行的代码，基本涵盖了一个简易的list（为避免和stl标准库的混淆，我们将链表定义为LinkedList）的基本操作，麻雀虽小，五脏俱全，尤其是里面对迭代器的定义，了解它是非常有好处的。初看这些代码有些头大，不过我保证比你看微软标准库的STL中list的实现要舒服多了。分析代码要一步一步来，先看第10行Node的定义，这里使用了struct关键字而非class，struct和class的区别是C++面试常考的一道问题，它们的区别是什么？区别是class默认成员是私有的，struct默认成员是公有的，除此之外没有任何区别！OK，我们看这个Node是一个双向链表的结点，其中定义了next和prev指针，分别指向后继结点和前驱结点。接下来我们来看LinkedList的构造函数，默认构造函数调用init()成员函数，init函数里面new了两个node，这两个node叫做哨兵，本身是不存储任何信息的，但是定义他们对于简化链表的一系列操作的代码是极其有好处的，不信你可以写一个初始化head和tail为空的链表，再实现push_back，pop_back等操作看看，哈哈。我们的链表同样支持拷贝构造函数，细节请看30-39行，实现了拷贝构造函数请同时实现赋值操作符，代码43行判断了传入对象是否为this，不是的话才进行赋值操作，记得操作之前clear()一下，清空链表元素，同时释放内存，clear()代码简洁明了，参见130行。同时我们定义size函数，该函数返回Size，Size是私有成员变量，在push_back时自增，在pop_back时自减。push_back和pop_back就是一些指针交换操作，但很容易写错，这里要注意操作顺序和正确性。
      OK，现在基本的函数和功能介绍好了，下面介绍迭代器的实现，这块我个人认为是STL的精髓，你随便叫一个C++的programmer写一个list的iterator，他还真不一定能写出来，一般人也就停留在会用，不过真正了解其中含义的还真不多。首先请注意的是，iterator在LinkedList内部是一个inner class，也就是子LinkedList内部定义的类，在116行还声明了friend class LinkedList; 即LinkedList是iterator的友元，不光可以操作器公有成员，也可以操作其保护成员。接下来请看iterator的构造函数即代码第111行，这里它保存了LinkedList的指针，和一个Node结点，retrieve函数负责iterator当前指向的Node的内容。iterator不难理解，它的行为和C的指针极其相似，既然像指针，那就少不了自增，自减，取内容*操作符。第88行的自增操作（前缀形式++iter），就是把current->next赋给current自己，93行的自增操作为自增的后缀形式，也就是iter++的形式，C++为了区分自增的前缀和后缀，规定在后缀形式的自增操作符重载中加入一个int型参数，这个参数没有实际用处，仅为区分后缀操作而已。这里我们看到，后缀操作要定义一个iterator，所以相对 操作要慢于前缀形式的自增操作符，所以平时使用时尽量使用前缀形式的，像这样"for (list::iterator iter = List.begin(); iter != List.end(); ++iter)". 取地址操作符的实现是直接调用retrieve函数并返回。

      测试程序比较简单，我们定义一个查找函数find，输入参数是start, end的迭代器，同时输入一个待查找的对象Object，然后我们用1到30初始化一个LinkedList，然后查找30是否在这个表里，输出为
Iterator found, the value is 30