《数据结构与STL》笔记和习题（3）

chapter6

这一章主要讲的是链表，基于list实现。

deque、vector较list的主要优势是随机访问是常数级别的，但是频繁的随机位置插入，复杂度是线性的，同时，插入、删除会带来大面积的迭代器失效。

list的主要优势是随机插入是常数的，但是要求传入插入位置，除了erase会使当前位置迭代器失效外，基本不失效。

课后有两个pj，一个是行编辑器，另一个是实现一个简单的list。

我选择了后一个，前一个感觉没什么意思。

释放空间和申请空间，我用的是delete和new，偷懒了。

list类定义：

template <class T>
class list {
protected:
    struct Node {
        T data;
        Node* prev;
        Node* next;

        Node(const T &x): data(x), prev(NULL), next(NULL) {}
        Node(): prev(NULL), next(NULL) {}
    };

    Node* head_ptr; // point to the list head
    size_t length;

public:
    class iterator {
    protected:
        // important: otherwise couldn't call iterator(Node*)
        friend class list;
        Node* cur_ptr;
        iterator(Node* ptr): cur_ptr(ptr) {}

    public:
        iterator() {}
        T& operator*() const { return cur_ptr->data; }
        inline bool operator==(const iterator &itr) const;
        inline bool operator!=(const iterator &itr) const;
        inline iterator& operator++(); // ++cur_ptr
        inline iterator operator++(int); // cur_ptr++
        inline iterator& operator--(); // --cur_ptr
        inline iterator operator--(int); // cur_ptr--
    };

    list();
    list(const list<T> &another);
    ~list();
    void push_front(const T &x);
    void push_back(const T &x);
    iterator insert(iterator pos, const T &x); // return the insert position
    void pop_front();
    void pop_back();
    void erase(iterator pos);
    void erase(iterator first, iterator last); // do not include *(last)
    inline size_t size() const;
    inline bool empty() const;
    iterator begin() const;
    iterator end() const;
};

因为外部不需要知道list是以struct Node存储的，所以iterator（Node*）是一个私有构造器，但是要声明list是iterator的友元类，不然list就无法访问这个构造器（函数传参和返回时，用于类型隐式自动转换）。

遇到的问题：

list的两个构造器，有相近的代码，为了方便，我就这么写了，结果悲剧：

template <class T>
list<T>::list(): length(0) {
    head_ptr = new Node();
    head_ptr->next = head_ptr;
    head_ptr->prev = head_ptr;
}

template <class T>
list<T>::list(const list<T> &another): length(0) {
    list();
    for (list<T>::iterator itr = another.begin();
            itr != another.end(); itr++)
        push_back(*itr);
}

后来仔细一想，这个错误真是太可笑了。list()只不过构造了一个temp类，想当然了（貌似，java这样是可以的）。不过我也不太确信这样解释对不对，先搁在这里吧。

后来就改成，过了：

template <class T>
list<T>::list(): length(0) {
    head_ptr = new Node();
    head_ptr->next = head_ptr;
    head_ptr->prev = head_ptr;
}

template <class T>
list<T>::list(const list<T> &another): length(0) {
    head_ptr = new Node();
    head_ptr->next = head_ptr;
    head_ptr->prev = head_ptr;
    for (list<T>::iterator itr = another.begin();
            itr != another.end(); itr++)
        push_back(*itr);
}

源代码：

 list.zip