一、list介绍

1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2、list就是一个带头双向循环链表，list通常在任意位置进行插入、移除元素的执行效率更好。

3、list最大的缺陷是不支持任意位置的随机访问。

二、list的使用

有了前面使用string和vector的经验后，list的使用也跟它们如出一辙，看一下文档介绍就可以使用了。这里就不演示使用了。文档链接list - C++ Reference (cplusplus.com)

要注意的点就是迭代器失效问题：迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

三、list模拟实现

template<class T>//节点类型struct _list_node{_list_node* _next;_list_node* _prev;T _val;_list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};//迭代器可以理解成指针，指向节点，用类封装原生指针控制迭代器行为，通过运算符重载来控制template<class T, class Ref, class Ptr>struct __list_iterator{typedef _list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;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--(){_node = _node->_prev;return *this;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._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;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return reverse_iterator(end());}const_reverse_iterator rend() const{return reverse_iterator(begin());}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;}list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto& e : lt){push_back(e);}}/*list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);++it;}}*/void swap(list<T>& tl){std::swap(_head, tl._head);std::swap(_size, tl._size);}list<T>& operator=(list<T> tmp){swap(tmp);return *this;}void push_back(const T& x){insert(end(), x);/*Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;}iterator erase(iterator pos){assert(pos._node != _head);Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;}size_t size(){return _size;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};

后面再总结反向迭代器的实现。

四、vector和list的区别