1、什么是list

list是一個帶頭結點的雙向循環鏈表模版容器，可以存放任意類型，需要顯式定義

2、list的使用

有了前面學習string和vector的基礎，學習和使用list會方便很多，因為大部分的內容依然是高度重合的。

與順序表不同，鏈表是以結點形式進行鏈接和存儲，其地址并不是連續的，因此進行插入和刪除操作不需要進行大量的數據挪動，只需要改變指針的指向即可，方便很多。

使用push_back()和push_front()可以分別實現尾插和頭插

    list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);for (auto e : lt){cout << e << " ";}cout << endl;

也可以使用insert實現在某一位置的插入，erase實現在某一位置的刪除

    lt.insert(lt.begin(), 9);for (auto e : lt){cout << e << " ";}cout << endl;lt.erase(lt.begin());for (auto e : lt){cout << e << " ";}cout << endl;

然而由于迭代器的失效問題，erase會返回被刪除元素的下一個位置，因此，當進行連續刪除時，我們可以使用迭代器來直接對此返回值進行接收來實現

	list<int>::iterator it = ++lt.begin();while (it != lt.end()){cout << (*it) << " ";it=lt.erase(it);}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;

同時，由于list底層結構的不同，不能像string和vector一樣去實現迭代器，因為string和vector在底層結構中是連續的，可以直接用指針去訪問得到相應位置的元素內容，對指針進行++或者--操作又可以直接到達下一位置或者前一位置，list中存放的是一個一個不連續的結點，對迭代器的實現時需要進行相應的重載，使用也會受限，比如在上述代碼中就無法使用lt.begin()+3等，更多內容在進行list的模擬實現中可以得到更多的體會

reverse()用于逆置，庫里有實現公用的reverse，不過list里面也有提供自己的逆置，如果使用公用的則需要使用兩個參數指定逆置的范圍，如果使用的是自己的逆置則不需要傳參

    reverse(lt.begin(), lt.end());lt.reverse();for (auto e : lt){cout << e << " ";}cout << endl;

對于排序，之前的vector可以直接調用庫中的sort()函數實現排序，實際sort()排序使用的是快排進行排序，而對于數組這種結構來說快排會很方便，而對于鏈表來說則比較困難，代價較高，因此庫中的排序函數并不能對list進行排序，list內部自己有實現一個排序，可以進行使用并完成排序。不過對于list來說，排序始終代價較大，如果需要頻繁使用排序應該使用其他的結構來存放數據，所以庫里的sort()函數實質上也是對程序員的一種約束。

	//sort(lt.begin(), lt.end());lt.sort();for (auto e : lt){cout << e << " ";}cout << endl;

find()函數是庫里實現的公用函數，list也可以使用，同時會返回尋找元素的位置

	auto it=find(lt.begin(), lt.end(), 3);cout << *it;

splice()可以用于將某一部分的內容轉移至其他list中，也可以轉移給自身的其他地方

	list<int> lt2 = { 10,20,30 };//全部轉移//lt2.splice(lt2.begin(), lt);//部分轉移//lt2.splice(lt2.begin(), lt, ++lt.begin());//轉移某一位置的內容lt2.splice(lt2.begin(), lt,++lt.begin(),--lt.end());//轉移某一段位置的內容//lt2.splice(++lt2.begin(), lt2, lt2.begin(), lt2.end());for (auto e : lt){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;lt2.splice(lt2.begin(), lt2, ++lt2.begin(), lt2.end());for (auto e : lt2){cout << e << " ";}cout << endl;

以上就是list的一些較常用的使用，那么在對list及其使用都有了解后就可以進行模擬實現

3、list的模擬實現

不得不說，我覺得list的實現比前面的string和vector的實現難很多，主要是迭代器的原因會上很大難度，很難以理解，所以直到勉強實現出來以后也還是處于一個似懂非懂的狀態里，希望后面能繼續加強自己的技術，實現輕松手撕

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;namespace bit
{template<class T>struct ListNode{ListNode(const T& val = T()):_prev(nullptr),_next(nullptr),_val(val){}ListNode* _prev;ListNode* _next;T _val;};template<class T,class Ref,class Ptr>struct List_iterator{typedef ListNode<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++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;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{public:typedef ListNode<T> Node;typedef List_iterator<T, T&, T*> iterator;typedef List_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const {return _head->_next;}const_iterator end() const{return _head;}List(){empty_init();}//list(const list<T>& lt)//{//	empty_init();//	for (auto& e : lt)//	{//		push_back(e);//		_size++;//	}//}size_t size(){return _size;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_head->_val = 0;_size = 0;}void push_back(const T& x){insert(end(), x);//Node* newnode = new Node;//_head->_prev->_next = newnode;//newnode->_prev = _head->_prev;//newnode->_next = _head;//_head->_prev = newnode;//newnode->_val = x;//_size++;}void push_front(const T& x){insert(++end(), x);//Node* newnode = new Node;//_head->_next->_prev = newnode;//newnode->_next = _head->_next;//_head->_next = newnode;//newnode->_prev = _head;//newnode->_val = x;//_size++;}void pop_back(){erase(--end());}void pop_front(){erase(++end());}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}iterator insert(iterator pos,const T& x){Node* newnode = new Node;Node* cur = pos._node;newnode->_prev = cur->_prev;cur->_prev->_next = newnode;cur->_prev = newnode;newnode->_next = cur;newnode->_val = x;_size++;return newnode;}iterator erase(iterator pos){Node* cur = pos._node;cur->_next->_prev = cur->_prev;cur->_prev->_next = cur->_next;pos._node = cur->_next;delete cur;_size--;return pos;}void swap(List<T> tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}List<T>& operator=(List<T> tmp){swap(tmp);return *this;}List(const List<T>& lt){empty_init();//const_iterator it = lt.begin();//while (it != lt.end())//{//	push_back(*(it));//	it++;//}//_size = lt._size;for (auto& e : lt){push_back(e);}}~List(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};
}