模拟实现STL中的list

1.设计list的结点

STL中的list采用的底层数据结构是带头双向循环链表，我们也采用这种方式，因此，结点可以这样来设计。

代码如下：为了满足容器中可以存放各种类型的数据这一需求，我们使用模板元编程的思想，将结点设计为模板类型。

    /* 定义节点 */
    template<class T>       // T表示存储的数据的类型 
    struct ListNode
    {
        ListNode<T>* _prev; // 指向前一个结点
        ListNode<T>* _next; // 指向后一个结点
        T _data;            // 存储数据

        ListNode(const T& x = T()) // 构造函数
            :_next(nullptr)
            , _prev(nullptr)
            , _data(x)
        {}
    };

2.设计list的迭代器

list的底层空间不像string和vector那样是连续的，因此，list的迭代器需要对结点的指针进行封装，来模拟指针的行为。比如：连续空间上的指针进行++操作，直接就能到达后一个数据的位置，但是不连续空间上的指针进行++操作不能到达后一个数据的位置。

同样，我们需要将迭代器设计为模板类型，我们设计三个模板参数，分别是：

• T：存储的数据的类型。
• Ref：存储的数据的引用类型，相当于T&。
• Ptr：存储的数据的指针类型，相当于T*。

template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef ListNode<T> Node;
    typedef __list_iterator<T, Ref, Ptr> self;
        
    // 成员变量
    Node* _node; // 对结点的指针进行封装
};

之所以遮掩设计是为了同时满足const对象和非const对象的需求，const对象需要调用const版本的迭代器，非const兑现需要调用非const版本的迭代器。

代码如下：迭代器模仿的是原生指针的行为，因此，我们实现迭代器的时候，至少需要实现以下操作。

• 前置++和后置++
• 前置--和后置--
• 指针的解引用（*）操作
• 指针的箭头（->）操作
• 判断 相等 和 不相等 操作

/* 
    * 迭代器
    * T：存储的元素类型
    * Ref：该类型的引用T&
    * Ptr：该类型的指针T*
*/
template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef ListNode<T> Node;
    typedef __list_iterator<T, Ref, Ptr> self;
        
    /* 成员变量 */
    Node* _node; // 对结点的指针进行封装即可

    /* 成员函数 */
    __list_iterator(Node* x)
        :_node(x)
    {}

    // ++it
    self& operator++()        // 前置++，让当前迭代器指向下一个节点
    {
        _node = _node->_next;
        return *this;         // 返回++以后的值
    }

    // it++
    self operator++(int)      // 后置++，让当前迭代器指向下一个节点
    {
        //__list_iterator<T> tmp(*this);
        self tmp(*this);

        _node = _node->_next;

        return tmp;           // 返回++之前的值
    }

    // --it
    self& operator--()        // 前置--，让当前迭代器指向上一个节点
    {
        _node = _node->_prev;
        return *this;         // 返回--之后的值
    }

    // it--
    self operator--(int)      // 后置--，让当前迭代器指向上一个节点
    {
        self tmp(*this);

        _node = _node->_prev; // 返回--之前的值

        return tmp;
    }

    Ref operator*()           // 返回当前结点的数据域的引用
    {
        return _node->_data;
    }

    Ptr operator->()          // 返回当前结点中数据域的指针
    {
        return &(_node->_data);
    }

    bool operator!=(const self& s) // 判断两个迭代器是否不相等
    {
        return _node != s._node;
    }

    bool operator==(const self& s) // 判断两个迭代器是否相等
    {
        return _node == s._node;
    }
};

3.list类的设计总览

我们的list类设计如下：

• 成员变量只有一个头结点的指针。
• 成员函数涉及迭代器的相关操作，四个特殊的成员函数，插入和删除操作。

template<class T> // T表示存储的数据的类型
class list
{
private:
    typedef ListNode<T> Node; // 对结点类型重命名
    Node* _head;              // 定义一个头结点
public:
    /* 迭代器的声明 */
    typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
    typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器

    /* 迭代器的相关操作 */
    iterator begin();             // 返回第一个元素的迭代器
    iterator end();               // 返回最后一个元素的后一个位置的迭代器
    const_iterator begin() const; // 提供给const对象的begin
    const_iterator end() const;   // 提供给const对象的end

    /* 四个特殊的成员函数 */
    list();                                // 无参的默认构造函数
    ~list();                               // 析构函数
    list(const list<T>& lt);               // 拷贝构造
    list<T>& operator=(const list<T>& lt); // 赋值运算符重载函数

    /* 插入操作 */
    iterator insert(iterator pos, const T& x); // 在指定位置之前插入指定元素
    void push_back(const T& x);                 // 尾插
    void push_front(const T& x);               // 头插

    /* 删除操作 */
    iterator erase(iterator pos); // 删除指定位置的元素           
    void pop_back();              // 尾删
    void pop_front();              // 头删
};

4.list类的迭代器操作

begin()系列接口用于获取第一个元素的迭代器，也就是头结点后面那个元素的迭代器。

end()系列接口用于获取最后一个元素后面那个元素的迭代器，也就是头结点的迭代器。

为了满足const对象和非const对象的不同需求，我们提供const版本和非const版本。

/* 迭代器的声明 */
typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器

iterator begin()         // 返回第一个元素的迭代器
{
    return _head->_next; // 利用单参数的构造函数进行隐式的类型转换
}

iterator end()    // 返回最后一个元素的后一个位置的迭代器
{
    return _head; // 利用单参数的构造函数进行隐式的类型转换
}

const_iterator begin() const // 提供给const对象的begin
{
    return _head->_next;
}

const_iterator end() const   // 提供给const对象的end
{
    return _head;
}

5.list类的四个特殊的默认成员函数

无参的默认构造函数

• 只需要构造出一个起哨兵作用的头结点即可

// 无参的默认构造函数
list()   
    : _head(new Node)
    , _head->_next(_head)
    , _head->_prev(_head);
{}

拷贝构造函数

• list的拷贝构造函数可以复用尾插实现。（尾插在后面会讲解，先用起来）

// 拷贝构造
list(const list<T>& lt)
    : _head(new Node)
    , _head->_next(_head)
    , _head->_prev(_head);
{
    for (const auto& e : lt)
    {
        push_back(e); // 复用尾插实现
    }
}

赋值运算符重载函数

传统写法：释放赋值list的所有结点，然后复用尾插接口将被赋值list的所有结点尾插进来。

// 传统写法的赋值运算符重载函数
list<T>& operator=(const list<T>& lt)
{
    if (this != &lt)
    {
        // 释放之前的所有结点
        iterator it = begin();
        while (it != end())
        {
            it = erase(it);
        }

        // 复用push_back尾插所有结点
        for (const auto& e : lt)
        {
            push_back(e);
        }
    }

    return *this;
}

现代写法：

• 现代写法依赖于交换函数，所以我们先实现交换两个list的函数，交换两个list只需要交换list中的 _head 指针即可。
• 在现代写法中，我们以传值传参的方式传递参数，此时的参数就相当于被赋值对象的一份临时拷贝，也就是复用拷贝构造函数，然后将当前对象与这个临时拷贝的对象进行交换。并且这个临时对象析构的时候，自动调用析构函数，析构的是赋值对象之前的值，避免了手动释放结点。

void swap(list<T>& tmp)
{
    std::swap(_head, tmp._head);
}
        
// 现代写法的赋值运算符重载函数
list<T>& operator=(const list<T> lt)
{
    swap(lt);
    return *this;
}

析构函数

list类涉及到资源的管理，析构函数需要显示给出，在析构的时候，需要逐个释放结点。

// 析构函数
~list()
{
    // 逐个释放节点
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);
    }
    
    // 释放哨兵位的头结点
    delete _head;
    _head = nullptr;
}

6.list类的插入操作

在指定位置之前插入：

// 在指定位置之前插入指定元素

iterator insert(iterator pos, const T& x)
{
    // prev newnode cur
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);

    // 连接prev和newnode
    prev->_next = newnode;
    newnode->_prev = prev;

    // 连接newnode和cur
    newnode->_next = cur;
    cur->_prev = newnode;

    return newnode;
}

尾插：在最后一个结点之后插入

// 尾插
void push_back(const T& x)
{
    // head -> …… -> tail -> newnode ->head
    Node* newnode = new Node(x);
    Node* tail = _head->_prev;

    // 连接tail和newnode
    tail->_next = newnode;
    newnode->_prev = tail;

    // 连接newnode和head
    newnode->_next = _head;
    _head->_prev = newnode;
}

// 复用insert实现尾插
void push_back(const T& x)
{
    insert(end(), x);
}

头插：复用insert在begin()之前插入。

// 头插
void push_front(const T& x)
{
    insert(begin(), x);
}

7.list类的删除操作

删除指定位置的元素：

// 删除指定位置的元素
iterator erase(iterator pos)
{
    assert(pos != end());

    // prev cur next
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;

    // 断开要删除结点和前后结点的连接
    prev->_next = next;
    next->_prev = prev;

    // 释放要删除的结点
    delete cur;

    // 返回指向被删除结点的后一个结点的迭代器
    return next;
}

复用erase实现尾删和头删：

• 尾删：end()的上一个位置就是尾结点。
• 头删：begin()就是第一个结点的位置。

// 尾删
void pop_back()
{
    erase(--end());
}

// 头删
void pop_front()
{
    erase(begin());
}

8.list.hpp源代码

#include <assert.h>

namespace xy
{
    /* 定义节点 */
    template<class T>       // T表示存储的数据的类型 
    struct ListNode
    {
        ListNode<T>* _prev; // 指向前一个结点
        ListNode<T>* _next; // 指向后一个结点
        T _data;            // 存储数据

        ListNode(const T& x = T()) // 构造函数
            :_next(nullptr)
            , _prev(nullptr)
            , _data(x)
        {}
    };

    /* 
        * 迭代器
        * T：存储的元素类型
        * Ref：该类型的引用T&
        * Ptr：该类型的指针T*
    */
    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef ListNode<T> Node;
        typedef __list_iterator<T, Ref, Ptr> self;
        
        /* 成员变量 */
        Node* _node; // 对结点的指针进行封装即可

        /* 成员函数 */
        __list_iterator(Node* x)
            :_node(x)
        {}

        // ++it
        self& operator++()        // 前置++，让当前迭代器指向下一个节点
        {
            _node = _node->_next;
            return *this;         // 返回++以后的值
        }

        // it++
        self operator++(int)      // 后置++，让当前迭代器指向下一个节点
        {
            //__list_iterator<T> tmp(*this);
            self tmp(*this);

            _node = _node->_next;

            return tmp;           // 返回++之前的值
        }

        // --it
        self& operator--()        // 前置--，让当前迭代器指向上一个节点
        {
            _node = _node->_prev;
            return *this;         // 返回--之后的值
        }

        // it--
        self operator--(int)      // 后置--，让当前迭代器指向上一个节点
        {
            self tmp(*this);

            _node = _node->_prev; // 返回--之前的值

            return tmp;
        }

        Ref operator*()           // 返回当前结点的数据域的引用
        {
            return _node->_data;
        }

        Ptr operator->()          // 返回当前结点中数据域的指针
        {
            return &(_node->_data);
        }

        bool operator!=(const self& s) // 判断两个迭代器是否不相等
        {
            return _node != s._node;
        }

        bool operator==(const self& s) // 判断两个迭代器是否相等
        {
            return _node == s._node;
        }
    };

    template<class T> // T表示存储的数据的类型
    class list
    {
    private:
        typedef ListNode<T> Node; // 对结点类型重命名
        Node* _head;              // 定义一个头结点
    public:
        /* 迭代器的声明 */
        typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
        typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器

        iterator begin()         // 返回第一个元素的迭代器
        {
            return _head->_next; // 利用单参数的构造函数进行隐式的类型转换
        }

        iterator end()    // 返回最后一个元素的后一个位置的迭代器
        {
            return _head; // 利用单参数的构造函数进行隐式的类型转换
        }

        const_iterator begin() const // 提供给const对象的begin
        {
            return _head->_next;
        }

        const_iterator end() const   // 提供给const对象的end
        {
            return _head;
        }

        /* 四个特殊的成员函数 */

        // 无参的默认构造函数
        list()   
            : _head(new Node)
            , _head->_next(_head)
            , _head->_prev(_head);
        {}

        // 拷贝构造
        list(const list<T>& lt)
            : _head(new Node)
            , _head->_next(_head)
            , _head->_prev(_head);
        {
            for (const auto& e : lt)
            {
                push_back(e);
            }
        }

        // 传统写法的赋值运算符重载函数
        list<T>& operator=(const list<T>& lt)
        {
            if (this != &lt)
            {
                // 释放之前的所有结点
                iterator it = begin();
                while (it != end())
                {
                    it = erase(it);
                }

                // 复用push_back尾插所有结点
                for (const auto& e : lt)
                {
                    push_back(e);
                }
            }

            return *this;
        }

        void swap(list<T>& tmp)
        {
            std::swap(_head, tmp._head);
        }
        
        // 现代写法的赋值运算符重载函数
        list<T>& operator=(const list<T> lt)
        {
            swap(lt);
            return *this;
        }

        // 析构函数
        ~list()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }

            delete _head;
            _head = nullptr;
        }

        /* 插入操作 */

        // 在指定位置之前插入指定元素
        iterator insert(iterator pos, const T& x)
        {
            // prev newnode cur
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(x);

            // 连接prev和newnode
            prev->_next = newnode;
            newnode->_prev = prev;

            // 连接newnode和cur
            newnode->_next = cur;
            cur->_prev = newnode;

            return newnode;
        }

        // 尾插
        void push_back(const T& x)
        {
            // head -> …… -> tail -> newnode ->head
            Node* newnode = new Node(x);
            Node* tail = _head->_prev;

            // 连接tail和newnode
            tail->_next = newnode;
            newnode->_prev = tail;

            // 连接newnode和head
            newnode->_next = _head;
            _head->_prev = newnode;
        }

        //void push_back(const T& x)
        //{
        //    insert(end(), x);
        //}

        // 头插
        void push_front(const T& x)
        {
            insert(begin(), x);
        }

        /* 删除操作 */

        // 删除指定位置的元素
        iterator erase(iterator pos)
        {
            assert(pos != end());

            // prev cur next
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            // 断开要删除结点和前后结点的连接
            prev->_next = next;
            next->_prev = prev;

            // 释放要删除的结点
            delete cur;

            // 返回指向被删除结点的后一个结点的迭代器
            return next;
        }

        // 尾删
        void pop_back()
        {
            erase(--end());
        }

        // 头删
        void pop_front()
        {
            erase(begin());
        }
    };
}