一、list类
1、 list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2、 list的底层是带头双向循环链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3、 list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4、 与其他的序列式容器相比(array，vector，deque)，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) {} };
链表的定义：
template<class T> class list { typedef list_node<T> Node; private: Node* _head;//哨兵位头节点 }；
二、迭代器
1、说明
迭代器的价值在于封装底层的实现，不暴露底层的实现细节，又提供统一的访问方式，这样几乎所有的容器都可以用相似的方法来访问。对于vector和string类而言，物理空间是连续的，通过++或者--，我们就可以访问一个位置的前一个位置或者后一个位置，所以我们可以用原生的指针来实现迭代器。
但是对于list而言，它的空间是不连续的，我们无法直接通过++或者--来直接访问一个位置的前一个位置或者后一个位置，所以使用指针来实现list的迭代器是不可能的了。我们需要进行一些特殊处理。怎么处理呢？
C++作为一种优秀的编程语言，它的一个非常牛逼的功能之一就是可以对运算符进行重载和三大特性之一的封装，使其有特殊的功能，来帮助我们满足一些特殊的需求。list 无法直接通过++或者--来直接访问一个位置的前一个位置或者后一个位置，那么我们可以通过运算符重载来帮助我们来找到一个结点的前一个位置或者下一个位置。
2、迭代器模板实现
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; } //const T& operator*() // T& operator*() //通过模板参数来控制是const还是非const Ref operator*() { return _node->_data; } //T* operator->() Ptr operator->() //p->_data p.operator->() { return &(operator*()); } //++it iterator& operator++() { _node = _node->_next; return *this; } //it++ iterator operator++(int) { iterator tmp(*this); _node = _node->_next; return tmp; } //--it iterator& operator--() { _node = _node->_prev; return *this; } //it-- iterator operator--(int) { iterator tmp(*this); _node = _node->_prev; return tmp; } };
3、迭代器实现
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); }
实现了迭代器后我们就可以直接使用范围for了。
那么为什么需要重载 -> 呢？请看下图：
从上图我们可以看出如果只重载了 * 的话，我们解引用只能拿到Pos（自定义类型），而不能拿到Pos里的数据， 所以我们就可以重载一下 -> 来帮助我们直接访问 _a1 和 _a2。
第二个重载函数的调用结果是 &(_node->_data) ，括号里面我们取到了 Pos，然后取到Pos的地址，这样我们就可以通过 -> 来访问 _a1 和 _a2，即：it->->_a1。但是为了可读性，编译器将它简化为了 it->_a1来使用。
说明：前面的 it-> 是重载的运算符部分，返回的是T*，而我们知道指针可以使用 -> 符号来访问成员，因此就可以直接访问 _a1 和 _a2。
三、增删查改
1、insert
iterator insert(iterator pos, const T& x) { Node* newnode = new Node(x); Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return iterator(newnode);//返回新插入位置的迭代器 }
2、erase
iterator erase(iterator pos)//返回删除位置下一个位置的迭代器 { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return iterator(next); }
3、push_back
void push_back(const T& x) { /*Node* tail = _head->_prev; Node* newnode = new Node(x); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;*/ insert(end(), x); }
4、push_front
void push_front(const T& x) { insert(begin(), x); }
5、pop_back
void pop_back() { erase(--end()); }
6、pop_front
void pop_front() { erase(begin()); }
7、clear
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
四、list的各种构造函数和析构函数
1、构造函数
我们可以用empty_init()来封装初始化，方便复用。
void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list() { empty_init(); }
2、区间构造
template<class InputIterator> //区间构造 list(InputIterator first, InputIterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } }
3、拷贝构造函数
void swap(list<T>& x) { std::swap(_head, x._head); } //拷贝构造函数 lt2(lt1) list(const list<T>& lt) { empty_init(); list<T> tmp(lt.begin(), lt.end()); swap(tmp); }
4、 赋值重载
// lt1 = lt3 list<T>& operator=(list<T> lt) { swap(lt); return *this; }
5、析构函数
~list() { clear(); delete _head; _head = nullptr; }
五、反向迭代器
在lis的STL的源码中，我们发现还提供了一种十分好的遍历方式，那就是反向遍历。对于vector和string，我们可以直接通过下标的++或者--来反向遍历，而在list中，我们则需要进行一些特殊的处理。
通过前面例子知道，反向迭代器的++就是正向迭代器的 - -，反向迭代器的 - - 就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。
template<class Iterator, class Ref, class Ptr> struct _reverse_iterator { Iterator _cur; typedef _reverse_iterator<Iterator, Ref, Ptr> RIterator; _reverse_iterator(Iterator it) :_cur(it) {} RIterator operator++() { --_cur; return *this; } RIterator operator--() { ++_cur; return *this; } Ref operator*() { //return *_cur; auto tmp = _cur; --tmp; return *tmp; } Ptr operator->() { //return &(*_cur); return &(operator*()); } bool operator!=(const RIterator& it) { return _cur != it._cur; } };
六、总代码
namespace zdl { 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) {} }; //迭代器模板 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; } //const T& operator*() // T& operator*() //通过模板参数来控制是const还是非const Ref operator*() { return _node->_data; } //T* operator->() Ptr operator->() //p->_data p.operator->() { return &(operator*()); } //++it iterator& operator++() { _node = _node->_next; return *this; } //it++ iterator operator++(int) { iterator tmp(*this); _node = _node->_next; return tmp; } //--it iterator& operator--() { _node = _node->_prev; return *this; } //it-- iterator operator--(int) { iterator tmp(*this); _node = _node->_prev; return tmp; } }; 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 _reverse_iterator<iterator, T&, T*> reverse_iterator; typedef _reverse_iterator<iterator, const T&, const T*> const_reverse_iterator; iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_iterator begin()const { return const_iterator(_head->_next); } const_iterator end()const { return const_iterator(_head); } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } template<class InputIterator> //区间构造 list(InputIterator first, InputIterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } list() { empty_init(); } void swap(list<T>& x) { std::swap(_head, x._head); } //拷贝构造函数 lt2(lt1) list(const list<T>& lt) { empty_init(); list<T> tmp(lt.begin(), lt.end()); swap(tmp); } // lt1 = lt3 list<T>& operator=(list<T> lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } void push_back(const T& x) { /*Node* tail = _head->_prev; Node* newnode = new Node(x); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;*/ insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator insert(iterator pos, const T& x) { Node* newnode = new Node(x); Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return iterator(newnode);//返回新插入位置的迭代器 } iterator erase(iterator pos)//返回删除位置下一个位置的迭代器 { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return iterator(next); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } private: Node* _head;//哨兵位头节点 };
