目录
前言
list概述
list的节点
list的迭代器
list的结构
构造与析构
拷贝构造与赋值
list的元素操作
insert()
push_back()
push_front()
erase()
pop_back()
pop_front()
clear()
swap()
size()
完整代码链接
前言
如果你对链表还不熟悉或者忘了的话，建议你可以回去复习一下或者看一下这篇文章：双向链表
如果你没看过前几篇vector的模拟实现和string的模拟实现也建议可以去看看，因为这里有些内容在前面讲过了，所以解释的篇幅就比较少了。
如果内容有错，还望指出
希望本篇文章能对你学习STL有所帮助。
list概述
相较于vector，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。list的底层其实是一个双向链表的结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素，所以list是可以在常数范围内的任意位置进行插入和删除的序列式容器，并且可以前后迭代。但是list的最大的缺陷是不支持任意位置的随机访问。
list的节点
list本身和list节点的结构是不同的，所以我们需要分开写，下面是list的节点结构，很明显它是个双向链表。
template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}};list的迭代器
可以说list的精华就在这迭代器上。list的迭代器的设计不能再向vector一样用个普通指针作为迭代器，因为对于链表来每个节点之间空间是不连续的，并且我们必须要让list的迭代器正确的指向list的节点，并且能够完成迭代器的一系列操作（取值、++、--等）。
所以我们的list迭代器初步设计如下
template <class T>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T> iterator;Node* _node;//初始化__list_iterator(Node* node):_node(node){}bool operator!=(const iterator& it)const{return _node != it._node;}bool operator==(const iterator& it)const{return _node == it._node;}//*itT& operator*(){return _node->_data;}//it->T* operator->(){return &(operator*());}//++ititerator& operator++(){_node = _node->_next;return *this;}//it++iterator& operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}//--ititerator& operator--(){_node = _node->_prev;return *this;}//it--iterator& operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}};为了前置++和后置++、前置--和后置--之间能构成函数重载，所以我们需要在参数上动手脚，我这里在参数上就加了个int，包括源码中也是这样实现的。
对于->访问，源码里的实现并结合对应的场景来看，就有点让人难以看懂了
struct Coord
{Coord(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}int _a1;int _a2;
};int main()
{hjx::list<Coord> lt;lt.push_back(Coord(10, 20));//匿名对象lt.push_back(Coord(21, 11));//匿名对象auto it = lt.begin();while (it != lt.end()){cout << it->_a1 << ":" << it->_a2 << endl;it++;}return 0;
}其实这里为了语言的可读性，编译器做了特殊处理，省略了一个->，所以没做特殊处理前应该是这样写的：it->->_a1，前一个->是调用了it.operator->()。
基于上面的迭代器的设计，对于const迭代器我们需要在operator*()和operator->()返回值加上const，但是这样写的话只有返回值不同不构成重载，当然你可以为const迭代器重新弄一个类出来。我们可以看看源码中是怎样设计的
源码中把T&和T*单领出来进行模板的实例化，如果模板实例化出const类型那这个迭代器就是const迭代器。
所以我们将迭代器重新设计如下
template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> iterator;Node* _node;__list_iterator(Node* node):_node(node){}bool operator!=(const iterator& it)const{return _node != it._node;}bool operator==(const iterator& it)const{return _node == it._node;}//*itRef operator*(){return _node->_data;}//it->Ptr operator->(){return &(operator*());}//++ititerator& operator++(){_node = _node->_next;return *this;}//it++iterator& operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}//--ititerator& operator--(){_node = _node->_prev;return *this;}//it--iterator& operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}};
list的结构
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 iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const {return const_iterator(_head);}private:Node* _head;};list在源码中的实现其实就是带头节点的双向循环链表
构造与析构
构造函数
对于只有一个哨兵位来说的话只要让next和prev都指向自己就好了。
//对哨兵位的头结点进行初始化void empty_Init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_Init();}//迭代器区间构造template<class Inputiterator>list(Inputiterator first, Inputiterator last){empty_Init();while (first != last){push_back(*first);first++;}}析构函数
调用clear函数就行，最后不要忘记哨兵位也要释放掉。
~list(){clear();delete _head;_head = nullptr;}拷贝构造与赋值
这里就提供现代的写法啦，毕竟现代写法更简单。
有些细心的同学可能在C++文档中看到拷贝构造的接口时会省略掉模板参数，这是被C++所允许的，在类里面可以这样，但在类外可不能省略。建议初学者还是不要去省略这里的模板参数了。
list(const list<T>& lt){empty_Init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}list<T>& operator=(list<T> lt){swap(lt);return *this;}list的元素操作
如果你数据结构学的非常扎实的话，这部分内容对你来说应该是小菜一碟。
insert()
iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}push_back()
void push_back(const T& x){insert(end(), x);}push_front()
void push_front(const T& x){insert(begin(), x);}erase()
iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}pop_back()
void pop_back(){erase(--end());}pop_front()
void pop_front(){erase(begin());}clear()
void clear(){//写法一//Node* cur = _head->_next;头删//while (cur != _head)//{// _head->_next = cur->_next;// delete cur;// cur = _head->_next;//}//_head->_next = _head->_prev = nullptr;//写法二iterator it = begin();while (it != end()){it = erase(it);//erase返回的是下一个位置的迭代器}}swap()
void swap(list& x){std::swap(_head, x._head);}size()
size_t size()const{Node* cur = _head->_next;size_t count = 0;while (cur != _head){count++;cur = cur->_next;}return count;}关于其它函数有兴趣可以自己动手去实现一下，这里就不在展示了。
完整代码链接
代码链接：list
源码链接：STL源码
