STL——list用法

一、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的区别

	vector	list
底层结构	动态顺序表，一段连续的空间	带头双向循环链表
随机访问	支持随机访问，访问某个元素效率为O(1)	不支持随机访问，访问某个元素效率为O(N)
插入和删除	在尾部删除和插入效率高，其余地方插入和删除效率低。	任意位置插入和删除的效率都高
空间利用率	空间利用率高，底层为连续空间，不容易造成内存碎片	底层节点动态开辟，空间利用率低
迭代器	原生态指针	对原生指针（节点指针）进行封装
迭代器失效	在插入数据时可能会扩容，导致迭代器失效；删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时只会导致当前迭代器失效，其它不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量的插入和删除操作，不关心随机访问