list 的核心成员函数及其模拟实现

        在模拟实现了vector以后，下一个我们应该学习的就是C++ 中自带的链表结构 list 了。在我们实现vector的时候，发现vector的实现和传统的顺序表还是有差别的。那么我们今天要实现的list也会和以前实现的链表有很大的差别吗？本篇博客将从头开始实现List 的核心成员函数。

        list 在STL库中实现的是一个双向带头循环链表，这样可以多提供很多操作。

1. 节点

        链表最基础的结构就是节点了，是先有的节点，然后才有的链表。所以首先，我们要先从节点入手。既然是双向带头循环链表，所以我们的节点应该是三个成员变量，两个指针指向前面和后面，还有一个存储数据的变量。

        同样，我们在自己实现 list 的时候也要记得把自己实现的list放在一个单独的命名空间内，防止和STL的 list 混淆。

        构建好节点类的时候不要忘记给节点类写一个构造函数。

namespace my_list{ templatestruct list_node{T _data;list_node* _next;list_node* _prev;list_node(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}};}

2. 迭代器

        在实现完节点类以后，还是先从迭代器开始实现。但是 list 的迭代器和其他类类型的迭代器不一样。其他类型的迭代器我们只需要对它进行 ++ / -- 就可以拿到下一个位置的值，但是 list 不可以。list 是链表结构，我们知道链表结构在内存空间里是不一定连续的，所以我们没办法通过类似于++ / -- 的这种方式获取到下一个位置的节点。所以这里我们要实现迭代器就不能只是一个单纯的指针，而要对这个迭代器进行封装，并且重载它的运算符。

        如果我们要封装一个迭代器，并且让自己实现的list类能够访问它，那么最好的方法就是创建一个结构体，因为结构体的成员默认都是公有的，这样实现起来很比较方便。当然，这里用类实现并且将成员设为公有也是可以的。

        在正式实现迭代器之前，我们要先思考一个问题。我们为了让类中对数据更好的进行读写，我们希望对迭代器解引用的时候可以对该节点进行读写，那么我们对运算符进行重载的时候就应该返回该节点的引用。但是由于我们要实现普通迭代器和 const 迭代器两种类型，我们在给运算符重载写返回值的时候就会出现冗余的代码。也就是除了这个重载以外，剩下的重载都是一模一样的。由此我们可以在类模板中多加入一个参数，用于表示函数的引用，在写返回值的时候用这个新的参数来写，就可以不用多写那么冗余的代码。下面看例子可以更好的理解这一点。

        我们写构造函数的时候

//这里我们对这个模板设置两个参数 并且设置一个重载//我们传const迭代器的时候就会返回const迭代器的版本//传普通迭代器的时候就会传普通的版本template struct list_iterator{typedef list_node Node;typedef list_iterator Self;Node* _node;list_iterator(Node* node):_node(node){} // Ref就是T类型的引用Ref operator*(){return _node->_data;} //迭代器++就是找下一个节点 Self& operator++(){_node = _node->_next;return *this;} //迭代器--就是找上一个节点 Self& operator--(){_node = _node->_prev;return *this;} //前置++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;} //前置--Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}//判断节点是否相等bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};}

3. list 类实现

3.1 默认成员函数

        在实现函数之前，先把前面写的迭代器和节点类 typedef 一下 ，方便后面写起来比较简单。

        成员变量只需要一个头节点的指针和一个长度就足够了。

templateclass list{typedef list_node Node;public:typedef list_iterator iterator;typedef list_iterator const_iterator; private: Node* _head;size_t _size;}

3.1.1 构造函数

        默认成员函数里我们就先来实现构造函数，由于 list 是一个带头双向循环链表，所以我们的构造函数肯定是要构造出一个头节点。不止是构造函数要用，后面的拷贝构造等都需要这个函数，所以我们单独把这个函数写出来。

void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}

3.1.2 析构函数

        析构函数就是需要我们把每一个节点都释放掉，最后再释放头节点。

~list(){auto it = begin(); // begin 和 end 后面实现while (it != end()){it = erase(it);//erase 也放到后面实现}delete _head;_head = nullptr;}

3.1.3 拷贝构造函数

        拷贝构造只需要先创建一个头节点，然后将节点依次遍历加进去就可以了。

list(const list& lt){empty_init();for (auto& e : lt){push_back(e); //后面实现push_back}}

3.1.4 赋值重载

         赋值重载依旧是用老方法，这里的swap我们只需要交换头节点和大小就可以了。

void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list& operator=(list lt){swap(lt);return *this;}

3.2 迭代器相关函数

        这里我们直接返回成员变量，通过隐式类型转换就会转成迭代器。

iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}

3.3 修改list的函数

3.3.1 insert

        在pos位置前插入一个新节点我们应该很熟悉了，先创建一个新节点，并且记录下当前节点和前一个节点。先把新节点的链接到两个节点上，再把两个节点的一前一后指针指向新的节点。先链接新节点是为了不会丢失以前的节点。

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

3.3.2 push_back 和 push_front

        这两个函数其实就是在头节点的一前一后插入数据，所以我们可以复用insert。

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

3.3.3 erase

        删除节点想必大家也不会陌生，就是先记录被删除节点的前后两个节点，然后让这两个节点连接上，最后再释放被删除的节点就好了。

iterator erase(iterator pos){Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;}

3.3.4 pop_back 和 pop_front

        头删和尾删也还是头节点的前后两个节点删除，所以我们可以复用erase

void pop_back(){erase(--end());}void pop_front(){erase(begin());}