STL？list！！！

一、引言

        之前我们一起完成了STL库中的vector，本期我们将一起完成list这一容器，在本期学习中，我们会更加加深对于模板的认识，让我们更加能感受到模板的魅力！

二、list的介绍与相关接口

        list是STL库中提供的一个链表容器，它是一个带头双向循环链表，事实上它的结构比较复杂，但是接口的实现相对简单，在实现该容器时，我们的重点将是如何正确、高效的使用模板的相关知识来简化代码、提升代码可读性

        在本文接下来的部分会介绍list的常用接口，事实上借助这些接口就可以解决平常所能遇到的大部分问题，如果还需要了解list提供的更多接口及使用方法的话，可以跳转到以下网页：

        list - C++ Reference

三、手撕一个list

        1、list的基本框架及其成员变量

        list是一个带头双向循环链表，对于list本身来讲我们只需要一个指向哨兵位的指针就可以管理整个链表，但是对于一个链表来说，我们还需要一个一个的节点来存储相关的数据，所以我们首先需要定义两个类，一个类用来管理链表的相关方法，另一个类用来管理一个一个的节点：
        

        在上面我已经完成了list_node的构造函数，在后面使用时我们只需要传给它一个T对象，它就可以帮助我们构造出一个节点

        2、构造函数

        库中的函数头：
        

        在这里说明一下，alloc是一个内存池，上面的缺省参数是STL库中提供的一个内存池，正常情况下是够用的，在以后的内容中我们会实现一个内存池，当下我们先忽略掉这个部分

        同时，构造函数还有其它重载，有的在这里不实现，在后面的插入函数实现之后我们通过复用来实现，有的不做实现

        对于一个带头双向循环链表来说，它天生一定不为空，在最开始的时候就一定、有一个哨兵位，同时该哨兵位的向前指针和向后指针都指向自己，天然的是一个双向循环链表：
        

        3、头插与尾插

                (1).头插函数：在链表的哨兵位之后插入一个节点

                库中的函数头：

                

                在实现插入相关函数的时候，一定要注意指针变向的顺序：
                

                (2).尾插函数：在链表的末尾，也就是哨兵位之前插入一个节点

                库中的函数头：
                

                实现：

                

        4、构造函数

        库中的函数头：
        

        在实现了插入函数之后，我们就可以实现上面使用n个T对象构造链表的构造函数了：
        

        5、拷贝构造函数

        库中的函数头：
        

        实现该函数，我们可以直接复用之前实现过的插入相关函数，直接对一个新对象不断尾插即可：
        

        6、交换函数

        库中的函数头：
        

        实现该函数可以借用一下算法库中实现的swap函数实现深层次的交换：
        

        7、赋值运算符重载

        库中的函数头：

        

        实现：
        

         对于赋值运算符重载，我们复用了上面的swap函数，同时我们的实现与库中的实现略有差异，在传参时我们采用了传值传参，这时候形参是实参的拷贝，调用我们刚才实现过的拷贝构造函数实现深拷贝，接着将*this与形参x交换，最后借助析构函数(后文会实现)对形参完成释放

        8、迭代器的实现及相关运算符重载和迭代器相关函数

                (1).迭代器类的定义

                list是一个带头双向循环链表，在物理结构上数据与数据之间并不是连续的，对于平常的指针来讲，我们不能通过++、--等运算符直接跳到下一个数据的位置，所以对于list来讲我们不能直接使用指针来充当迭代器，但是很显然Node*类型的指针是实现迭代器的最佳选择，所以我们要封装这个指针，从而让它来充当迭代器，由于C++中并不喜欢使用内部类来实现类内定义类型，所以我们采用封装一个迭代器类同时在list类中实现typedef，接下来我们一起完成这样一个迭代器类：

        

	template <class T>struct list_iterator{typedef list_node<T> Node;//成员变量Node* _node;//构造函数list_iterator(Node* node):_node(node){}//运算符重载//前置++list_iterator<T>& operator++(){_node = _node->_next;return *this;}//后置++list_iterator<T> operator++(int){list_iterator tmp = *this;_node = _node->_next;return tmp;}//前置--list_iterator<T>& operator--(){_node = _node->_front;return *this;}//后置--list_iterator<T> operator--(int){list_iterator tmp = *this;_node = _node->_front;return tmp;}//+操作符重载list_iterator<T> operator+(int x){list_iterator tmp = *this;while (x--){tmp++;}return tmp;}//-操作符重载size_t operator-(list_iterator<T> it){size_t ret = 0;while (it._node != _node){ret++;it._node = it._node->_next;}return ret;}

                对于正常的使用来说，上面的迭代器类已经可以正常的跑通范围for了，但是，接下来的问题是，我们怎么样定义出const_iterator呢？显然的方法是将上面的类复制以下，将‘*’操作符的重载返回值改变以下，再将‘->’操作符重载的返回值改变以下即可，但是对于两个如此相像的类，我们如果采用这样的方法代码复用率过低，这时候我们便可以想到使用模板的知识，在类模板参数部分多给几个参数：

        

template <class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;//成员变量Node* _node;//构造函数list_iterator(Node* node):_node(node){}//运算符重载//前置++list_iterator<T, Ref, Ptr>& operator++(){_node = _node->_next;return *this;}//后置++list_iterator<T, Ref, Ptr> operator++(int){list_iterator tmp = *this;_node = _node->_next;return tmp;}//前置--list_iterator<T, Ref, Ptr>& operator--(){_node = _node->_front;return *this;}//后置--list_iterator<T, Ref, Ptr> operator--(int){list_iterator tmp = *this;_node = _node->_front;return tmp;}//+操作符重载list_iterator<T, Ref, Ptr> operator+(int x){list_iterator tmp = *this;while (x--){tmp++;}return tmp;}//-操作符重载size_t operator-(list_iterator<T, Ref, Ptr> it){size_t ret = 0;while (it._node != _node){ret++;it._node = it._node->_next;}return ret;}//!=操作符重载bool operator!=(list_iterator<T, Ref, Ptr> it){return it._node != _node;}//==操作符重载bool operator==(list_iterator<T, Ref, Ptr> it){return it._node == _node;}//*操作符重载Ref operator*(){return _node->_val;}//->操作符重载Ptr operator->(){return &_node->_val;}
};

                在定义完成上面的迭代器类之后，我们只需要在list类中再将两种迭代器分别进行typedef即可：

        

typedef list_iterator<T,T*,T&> iterator;
typedef list_iterator<T, const T*,const T&> const_iterator;

                (2).迭代器相关函数

                

//迭代器相关函数
iterator begin()
{return head->_next;
}
iterator end()
{return head;
}
const_iterator begin() const
{return head->_next;
}
const_iterator end() const
{return head;
}

        9、在指定位置插入函数--insert

        库中的函数头：
        

        insert函数可以在pos之前位置插入val：
        

        10、将指定位置的元素删除--erase

        库中的函数头：
        

        erase函数可以将pos位置的元素删除：
        

        11、将链表中的元素清空--clear

        库中的函数头：
        

        clear函数可以将链表中的元素清空：
        

        12、析构函数

        由于析构函数的特殊性，在这里就不再展示库中的函数头：
        

四、list

        下面就是我们今天实现的list了：
        

namespace bea
{template <class T>struct list_node{//成员函数//构造函数list_node(const T& val = T()):_val(val),_front(nullptr),_next(nullptr){}//成员变量list_node* _front;list_node* _next;T _val;};template <class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;//成员变量Node* _node;//构造函数list_iterator(Node* node):_node(node){}//运算符重载//前置++list_iterator<T, Ref, Ptr>& operator++(){_node = _node->_next;return *this;}//后置++list_iterator<T, Ref, Ptr> operator++(int){list_iterator tmp = *this;_node = _node->_next;return tmp;}//前置--list_iterator<T, Ref, Ptr>& operator--(){_node = _node->_front;return *this;}//后置--list_iterator<T, Ref, Ptr> operator--(int){list_iterator tmp = *this;_node = _node->_front;return tmp;}//+操作符重载list_iterator<T, Ref, Ptr> operator+(int x){list_iterator tmp = *this;while (x--){tmp++;}return tmp;}//-操作符重载size_t operator-(list_iterator<T, Ref, Ptr> it){size_t ret = 0;while (it._node != _node){ret++;it._node = it._node->_next;}return ret;}//!=操作符重载bool operator!=(list_iterator<T, Ref, Ptr> it){return it._node != _node;}//==操作符重载bool operator==(list_iterator<T, Ref, Ptr> it){return it._node == _node;}//*操作符重载Ref operator*(){return _node->_val;}//->操作符重载Ptr operator->(){return &_node->_val;}};template <class T>class list{typedef list_node<T> Node;//成员函数public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T, const T&,const T*> const_iterator;//迭代器相关函数iterator begin(){return head->_next;}iterator end(){return head;}const_iterator begin() const{return head->_next;}const_iterator end() const{return head;}//构造函数//空构造explicit list(){head = new Node;head->_front = head;head->_next = head;}//用n个对象构造explicit list(size_t n, const T& val = T()){if (head == nullptr){head = new Node;head->_front = head;head->_next = head;}int ntmp = n;while (ntmp--){push_back(val);}}//拷贝构造函数list(const list& x){Node* cur = x.head->_next;while (cur != x.head){if (head == nullptr){head = new Node;head->_front = head;head->_next = head;}push_back(cur->_val);cur = cur->_next;}}//头插函数void push_front(const T& val){Node* newnode = new Node(val);newnode->_front = head;newnode->_next = head->_next;head->_next = newnode;newnode->_next->_front = newnode;}//尾插函数void push_back(const T& val){Node* newnode = new Node(val);newnode->_next = head;newnode->_front = head->_front;head->_front = newnode;newnode->_front->_next = newnode;}//insert函数iterator insert(iterator pos, const T& val){Node* x = pos._node;Node* newnode = new Node(val);newnode->_front = x->_front;newnode->_next = x;x->_front = newnode;newnode->_front->_next = newnode;return (iterator)newnode;}//erase函数iterator erase(iterator pos){Node* eaim = pos._node;Node* ret = eaim->_next;eaim->_next->_front = eaim->_front;eaim->_front->_next = eaim->_next;delete eaim;return ret;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}//交换函数void swap(list& x){std::swap(x.head, head);}//赋值运算符重载list& operator=(const list x){swap(x);return *this;}//打印函数void Print(){Node* cur = head->_next;cout << "head->";while (cur != head){cout << cur->_val << "->";cur = cur->_next;}cout << "head" << endl;}//析构函数~list(){clear();delete head;}//成员变量private:Node* head;};
}

五、结语

        这就是我们所实现的list的全部内容了，我们的目的是了解list的用法、加深类和对象和模板等知识点的理解，感谢大家的阅读，欢迎各位于晏、亦菲和我一起交流、学习、进步！