前面學習了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;};