C++----剖析list

前面学习了vector和string，接下来剖析stl中的list，在数据库中学习过，list逻辑上是连续的，但是存储中是分散的，这是与vector这种数组类型不同的地方。所以list中的元素设置为一个结构体，将list设计成双向的：

	template <class T>struct list_node{list_node<T>* _next;list_node<T>* _pre;T _data;list_node(const T& val=T()):_next(nullptr),_pre(nullptr),_data(val){}};

接下来是stl中的迭代器部分，list的迭代器还可以像vector这种原生指针是的使用方式使用吗？答案是否定的，因为vector的底层存储是连续的，并且迭代器就是vector内部元素指针的简单封装。所以底层自然实现起来比较简单，但是list的底层不可以，比如迭代器++，vector本来就是连续的，所以直接就能用，但是struct不是连续的，所以要自己实现，否则谁知道会++到哪里造成访问未知空间。所以既然它不支持我们直接使用，那我们就造一个迭代器出来，这个迭代器的核心就是node：

	template <class T, class PTR, class PEF>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T,PTR,PEF> self;Node* _node;//核心_list_iterator(Node* node):_node(node){}PEF operator*(){return _node->_data;}//要可以返回值、还能修改！PTR operator->(){return &(operator*());}self& operator++(){_node = _node->_next;return *this;}//后置++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_pre;return *this;}//后置--self operator--(int){self tmp(*this);_node = _node->_pre;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};

这里其他的地方没有太大的疑问，就是operator->发现了，返回的是nodedata的地址，首先咱们来看，当T是内置类型int时，是没有必要用这个的吧？直接*就可以得到，但是如果T时自定义类型的呢？比如：

	struct A{int _a;int _b;A(int a = 1,int b=1):_a(a),_b(b){}};void test2(){list<A> l;l.push_back(A(1,1));l.push_back(A(2, 2));l.push_back(A(3, 3));l.push_back(A(4, 4));std::cout << it->_a << " " << it->_b << " ";list<A>::iterator it = l.begin();}

此时我想访问A中的数据，我当然可以重载<<这个运算符了，但是在stl中我们不知道自定义类型中会有什么数据，所以stl中是不会预先，也不能写出来<<运算符。所以就有了->符，我们可以自己访问struct中的数据，但是还有一个问题，->返回struct的地址，还应该再来一个->吧，就是it->->_a，这里编译器做了优化，所以只需要一个->就可以。

看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);}list(){_head = new Node;_head->_next = _head;_head->_pre = _head;}//void push_back(Node newnode)//{//	Node* tail = _head->_pre;//	tail->_next = newnode;//	newnode->_pre = tail;//	newnode->_next = _head;//	_head->_pre = newnode;//}void push_back(const T& val){Node* newnode = new Node(val);Node* tail = _head->_pre;tail->_next = newnode;newnode->_pre = tail;newnode->_next = _head;_head->_pre = newnode;}private:Node* _head;};

list的形式：带哨兵位的双向列表

解释模板在const迭代器和普通迭代器中的巧妙使用，通过模板避免多写代码：

 巧妙使用模板参数。

list迭代器失效的场景只存在于删除结点时，他不像vector这种连续的，插入了会导致其中大部分元素发生移动，所以只会在删除结点时，如何解决？返回删除结点的下一个节点的迭代器。

附全部代码：

	template <class T>struct list_node{list_node<T>* _next;list_node<T>* _pre;T _data;list_node(const T& val=T()):_next(nullptr),_pre(nullptr),_data(val){}};template <class T, class PTR, class PEF>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T,PTR,PEF> self;Node* _node;//核心_list_iterator(Node* node):_node(node){}PEF operator*(){return _node->_data;}//要可以返回值、还能修改！PTR operator->(){return &(operator*());}self& operator++(){_node = _node->_next;return *this;}//后置++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_pre;return *this;}//后置--self operator--(int){self tmp(*this);_node = _node->_pre;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){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;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);}list(){_head = new Node;_head->_next = _head;_head->_pre = _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_pre = _head;}template<class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}~list(){clear();delete _head;_head = nullptr;} void swap(list<T>& l){std::swap(_head, l._head);}list(const list<T>& l){ empty_init();list<T> tmp(l.begin(), l.end());swap(tmp);}//l2=l1 list<T>& operator=(list<T> l){swap(l);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}//void push_back(Node newnode)//{//	Node* tail = _head->_pre;//	tail->_next = newnode;//	newnode->_pre = tail;//	newnode->_next = _head;//	_head->_pre = newnode;//}void insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur = pos._node;Node* pre = cur->_pre;cur->_pre = newnode;newnode->_next = cur;pre->_next = newnode;newnode->_pre = pre;}void push_front(const T& val){insert(begin(),val);}void push_back(const T& val){Node* newnode = new Node(val);Node* tail = _head->_pre;tail->_next = newnode;newnode->_pre = tail;newnode->_next = _head;_head->_pre = newnode;}//返回值是删去节点的下一个节点的迭代器，避免迭代器失效，//因为释放了当前迭代器的结点，再次访问会出现错误iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* pre = cur->_pre;Node* next = cur->_next;next->_pre = pre;pre->_next = next;delete cur;return iterator(next);}void pop_front(){iterator it = erase(begin());}void pop_back(){iterator it = erase(--end());}private:Node* _head;};