目录
前言
一、list的结构
二、默认成员函数
构造函数
析构函数
clear
拷贝构造
赋值重载
swap
三、容量相关
empty
size
四、数据访问
front/back
五、普通迭代器
begin/end
六、const迭代器
begin/end
七、插入数据
insert
push_back
push_front
八、删除数据
erase
pop_back
pop_front
九、代码
总结
前言
我们之前讲解了string和vector的模拟实现，它们都是类似于顺序表的结构，string的底层是一个指针，一个元素的数量，一个空间总容量，而vector的底层是三个指针，这是它们结构上不一样的地方，但是实现的方法和原理还是大差不差的，那本篇我们来谈谈list，list的迭代器和之前的容器是不一样的，而且是一个双向带头循环链表，任意位置的插入删除效率都是O(1)，那我们开始正题
一、list的结构
list的结构是一个一个的节点，所以我们在定义的时候就要去定义一个节点
template<class T>
struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _val;
};_prev指向前一个节点
_next指向下一个节点
_val表示节点中存储的值
list_node这个类可以写成class，然后放成公有，也可以直接定义成struct的，因为这个类中的成员在list这个类中会用到，所以像这种节点类就直接放成公有就好
template<class T>
class list
{typedef list_node<T> Node;
private:Node* _head;size_t _size;
};对于list这个类，我们需要先把list_node这个类给typedef，否则一直用他太长了，而且要带上模版参数，要注意的是，typedef也会受到访问限定符的限制，所以在外面是看不到Node的，然后我们用这个Node来定义一个头结点，也就是指向头节点的指针_head，然后还有一个成员函数是_size，_size是用来返回链表内的数据个数的，如果没有_size的话就只能遍历求一遍，这样增加一个成员变量代价反而小了
二、默认成员函数
构造函数
构造函数要来初始化成员变量，所以就需要先去给_head去new一个节点，然后它的前驱和后继都指向自己，_size初始化成0就好了，因为头节点不存储有效数据，所以也就不算做元素个数了
list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}对于Node这个类在new的时候会去调用它的构造函数，所以我们要给Node类补上一个构造，用匿名对象做这里的缺省参数
template<class T>
struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}
};析构函数
析构函数需要把所有的节点都释放了，因为所有节点都是new出来的，那就先来实现一个clear函数
clear
clear是要清空除头节点外链表中所有的节点，就要从头节点的下一个节点开始，去删除每一个节点，但是删除了当前节点就会找不到下一个节点，所以要先保存一下下一个节点
void clear()
{Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}
}cur表示的是当前节点，next记录下一个节点的位置，循环判断的条件就是不等于头结点就继续删，删到最后一个节点，那它的next就是头结点了，也就证明删完了，循环结束
那在析构函数中就先去调用clear先把后面链接的节点全部删掉，然后再把头节点删掉并置空就好了
~list()
{clear();delete _head;_head = nullptr;
}拷贝构造
这里就不能再去用memcpy或者赋值来写了，因为list在物理上并不是连续的空间，不可以用下标来访问，所以采用的方法是遍历有数据的这个容器，然后依次尾插进被拷贝的容器中
//l2(l1)
list(const list<T>& l)
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto e : l){push_back(e);}
}然后这里的l2在插入数据前一定要去初始化，要把头节点new出来再把前后都指向自己，否则在访问时会出问题，这里用的是范围for，那就需要支持迭代器才可以，并且push_back也还没有实现，所以暂时这个拷贝构造是不能跑的，大家可以等下面的实现完再回来看
赋值重载
赋值就写一个现代写法去调用拷贝构造就可以，这个我们很详细的说过了，在这里就不再多赘述了
swap
void swap(list<T>& l)
{std::swap(_head, l._head);std::swap(_size, l._size);
}//l2 = l1
list<T>& operator=(list<T> l)
{swap(l);return *this;
}三、容量相关
empty
判空的逻辑是判断头节点的前驱和后继是不是指向自己，且元素个数是否为0
bool empty() const
{return _head->_next == _head&& _head->_prev == _head&& _size == 0;
}size
size函数只需要返回_size的值就可以
size_t size() const
{return _size;
}四、数据访问
front/back
front就是返回第一个节点里存储的值，back返回最后一个节点里的值，一定要注意是第一个存储有效数据的节点，所以是头结点的下一个节点，而不是头节点中存储的值
front和back各自分别有两个版本，一个普通版本，一个const版本，跟我们之前讲的一样，普通对象优先调用普通版本，如果没有普通版本再去调用const版本，const对象只能调用const版本
T& front()
{return _head->_next->_val;
}const T& front() const
{return _head->_next->_val;
}T& back()
{return _head->_prev->_val;
}const T& back() const
{return _head->_prev->_val;
}五、普通迭代器
我们在最开始的时候说过，list的迭代器与前面的有些不一样，我们就来看看list的迭代器有哪些不一样，可以说list最重要的部分就是迭代器，大家先来看可不可以这么写我们的迭代器呢？
typedef Node* iterator答案显而易见，肯定是不可以的，因为迭代器我们解引用是要拿到数据，但是现在解引用拿到的是一个节点，而且++要向下一个位置走，--要向前一个位置走，现在这个迭代器++走到哪去谁能知道呢？所以我们要用运算符重载来控制这里的逻辑，也就要再封装一个迭代器的类来控制
template<class T>
struct __list_iterator
{typedef list_node<T> Node;Node* _node;
};在外面需要去访问这个类中的成员函数，所以我们把这个迭代器类定义成struct的，里面有一个节点的指针_node，我们先来实现下*和->，*就是返回数据的引用，->是返回数据的地址
T& operator*()
{return _node->_val;
}T* operator->()
{return &(_node->_val);
}然后是++和--，++就是向下一个节点走，--就是向前一个节点走，而++和--呢又分为前置和后置，我们先实现前置，前置的话就是_node走完返回迭代器的本身，那这个迭代器类的名字太长了，我们也同样来typedef一下
typedef __list_iterator<T> Self;这个typedef就和Node的typedef放在一起就行
Self& operator++()
{_node = _node->_next;return *this;
} Self& operator--()
{_node = _node->_prev;return *this;
}前置++返回的是迭代器走完的结果，所以就可以用引用返回
后置是返回++或者--之前的值，那就需要先保存一份才可以，然后返回保存的这一份，区分前置和后置，就是给后置加上一个int类型的参数
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)
{return _node != s._node;
}bool operator==(const Self& s)
{return _node == s._node;
}begin/end
begin就是返回头节点的下一个位置，因为迭代器是左闭右开，所以end应该返回的是最后一个有效数据的下一个位置，也就是头节点_head
iterator begin()
{return _head->_next;
}iterator end()
{return _head;
}那在list这个类中需要用到iterator，我们就把这个类给嵌到list这个类里，这个要放成公有的，外面要用迭代器
public:typedef __list_iterator<T> iterator;而且还要给迭代器类实现一个构造函数，用节点指针去构造迭代器，现在的begin和end是隐式类型转换，构造加拷贝构造，拷贝构造我们不需要实现，迭代器去浅拷贝就可以了，也可以返回匿名对象或者是先构造出来对象再返回这个对象，这三种都可以，我们这种是最简单的，直接隐式类型的转换
__list_iterator(Node* node):_node(node)
{}我们再结合迭代器的使用来看
int main()
{hx::list<int> l;hx::list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;return 0;
}需要什么我们就写什么就可以了，迭代器也就是需要这几个函数，不需要实现其他功能了，那我们的普通迭代器就实现好了
六、const迭代器
下面我们来看一下const迭代器，有了刚才的封装，那const迭代器可不可以直接套上一个const呢？
typedef __list_iterator<T> iterator;
typedef const __list_iterator<T> const_iterator;这样写也是不行的，因为这样写就是修饰迭代器本身不能修改了，那迭代器本身都不能修改了还怎么++/--呢？所以const迭代器也是需要我们自己去封装一个自定义类型来控制，那我们就照葫芦画瓢来实现一个
template<class T>
struct __list_const_iterator
{typedef __list_const_iterator<T> Self;typedef list_node<T> Node;Node* _node;__list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_val;}const T* operator->(){return &(_node->_val);}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};
那大家有没有发现，普通迭代器和const迭代器不一样的地方就在于*和->的返回值，其他的地方全都一样，那这样设计就太冗余了，我们有没有办法可以就用一个类来控制一下*和->的返回值呢？其实很好办，只需要增加模版参数就可以
template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_iterator<T, Ref, Ptr> Self;typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};Ref是引用，也就是operator*的返回值，Ptr是指针，也就是operator->的返回值，然后不要忘记在typedef Self的时候把这两个模版参数给加上，然后在list类中我们把后面的两个模版参数写死就可以了
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;begin/end
const_iterator begin() const
{return _head->_next;
}const_iterator end() const
{return _head;
}begin和end还是一样的实现逻辑，返回值变一样，再设计成const成员函数就可以
那迭代器部分我们就说到这里，因为这里可能会比较复杂，三个类互相缠绕，所以在文章的最后会把所有的代码给贴出来，如果大家对这里还有不太懂的地方可以去参考
七、插入数据
insert
insert是在某个迭代器插入一个val，那就是把这个迭代器里存的节点指针定义出来，然后找到前一个，再新创建一个节点，把他们之间互相链接起来就行了，最后返回新插入的这个节点的迭代器
iterator insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;
}push_back
push_back是尾插，直接去复用insert，给一个迭代器位置
void push_back(const T& val)
{insert(end(), val);
}end就是头结点，那在头节点的前面插入也就是尾插
push_front
push_back是头插，直接去复用insert，给一个迭代器位置
void push_front(const T& val)
{insert(begin(), val);
}begin就是头结点的下一个位置，在begin之前插入，也就是在头结点和第一个节点之间插入，就是头插
八、删除数据
erase
erase是要删除某个迭代器位置，那也是把迭代器里存的节点指针定义出来，然后找到前后节点，把前后节点互相连起来就好了，最后再删除，然后要返回删除的这个位置的下一个节点的迭代器
iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;
}pop_back
pop_back是尾删，直接去复用erase，给一个迭代器位置
void pop_back()
{erase(--end());
}end是头节点的位置，那--end就是头结点的前一个，也就是最后一个节点
pop_front
pop_front是头删，直接去复用erase，给一个迭代器位置
void pop_front(){erase(begin());}begin是头结点的下一个位置，也就是第一个存放有效数据的节点
九、代码
namespace hx
{template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef __list_iterator<T, Ref, Ptr> Self;typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};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;}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}//l2(l1)list(const list<T>& l){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto e : l){push_back(e);}}//l2 = l1list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = nullptr;}void swap(list<T>& l){std::swap(_head, l._head);std::swap(_size, l._size);}bool empty() const{return _head->_next == _head&& _head->_prev == _head&& _size == 0;}size_t size() const{return _size;}void clear(){Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}}T& front(){return _head->_next->_val;}const T& front() const{return _head->_next->_val;}T& back(){return _head->_prev->_val;}const T& back() const{return _head->_prev->_val;}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;}void push_back(const T& val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}private:Node* _head;size_t _size;};
}总结
本篇文章我们讲了list，以及关于迭代器部分，list的迭代器类型是一个自定义类型，跟以前不太一样，但是这种方式在以前也还是很常见的，比如map/set，unordered map/unordered set，还是要这么用，迭代器部分都要去这样封装，大家还是要习惯这种方式，那本篇文章就到这里啦，如果觉得下篇写的不错的小伙伴，可以给小编一个一键三连表示支持，感谢大家！！！
