一、list底層實(shí)現(xiàn)機(jī)制刨析
前面在講 STL list 容器時(shí)提到，該容器的底層是用雙向鏈表實(shí)現(xiàn)的，甚至一些 STL 版本中（比如 SGI STL），list 容器的底層實(shí)現(xiàn)使用的是雙向循環(huán)鏈表

圖 1 雙向鏈表（ a) ）和雙向循環(huán)鏈表（ b) ）
圖 1 中，node 表示鏈表的頭指針。
如圖 1 所示，使用鏈表存儲(chǔ)數(shù)據(jù)，并不會(huì)將它們存儲(chǔ)到一整塊連續(xù)的內(nèi)存空間中。恰恰相反，各元素占用的存儲(chǔ)空間（又稱(chēng)為節(jié)點(diǎn)）是獨(dú)立的、分散的，它們之間的線性關(guān)系通過(guò)指針（圖 1 以箭頭表示）來(lái)維持。
通過(guò)圖 1 可以看到，雙向鏈表的各個(gè)節(jié)點(diǎn)中存儲(chǔ)的不僅僅是元素的值，還應(yīng)包含 2 個(gè)指針，分別指向前一個(gè)元素和后一個(gè)元素。

通過(guò)查看 list 容器的源碼實(shí)現(xiàn)，其對(duì)節(jié)點(diǎn)的定義如下：

template<class T>struct list_node {	T data;	struct list_node<T>* next;//節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址	struct list_node<T>* prev;//節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的地址	list_node(const T date)		:		data(date),		next(nullptr)		, prev(nullptr)	{}	};

注意，為了方便讀者理解，此代碼以及本節(jié)后續(xù)代碼，都省略了和本節(jié)核心內(nèi)容不相關(guān)的內(nèi)容，如果讀者對(duì)此部分感興趣，可查看 list 容器實(shí)現(xiàn)源碼。

可以看到，list 容器定義的每個(gè)節(jié)點(diǎn)中，都包含 *prev、*next 和 data。其中，prev 指針用于指向前一個(gè)節(jié)點(diǎn)；next 指針用于指向后一個(gè)節(jié)點(diǎn)；data 用于存儲(chǔ)當(dāng)前元素的值
一、list的核心框架接口的模擬實(shí)現(xiàn)
1.list迭代器
STL容器迭代器有兩種實(shí)現(xiàn)方式，具體應(yīng)根據(jù)容器底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：
1）原生指針，比如：vector string
2）. 將原生態(tài)指針進(jìn)行封裝，因迭代器使用形式與指針完全相同，因此在自定義的類(lèi)中必須實(shí)現(xiàn)以下
方法：

1. 指針可以解引用，迭代器的類(lèi)中必須重載operator*()
2. 指針可以通過(guò)->訪問(wèn)其所指空間成員，迭代器類(lèi)中必須重載oprator->()
3. 指針可以++向后移動(dòng)，迭代器類(lèi)中必須重載operator++()與operator++(int)
   至于operator–()/operator–(int)釋放需要重載，根據(jù)具體的結(jié)構(gòu)來(lái)抉擇，雙向鏈表可以向前 移動(dòng)，所以需要重載，如果是forward_list就不需要重載–
4. 迭代器需要進(jìn)行是否相等的比較，因此還需要重載operator==()與operator!=()：

//迭代器結(jié)構(gòu)體	template<class T, class Ref, class Ptr>	struct list_Iterator {		typedef list_node<T> Node;		typedef list_Iterator<T, Ref, Ptr>  Self;		Node* node;	public:		bool operator!=(const Self& iter) {			return node != iter.node;		}		/*  list_Iterator& operator++(){			node =  node->next ;			  return *this;		  }*/		  //前置++		Self& operator ++()		{			node = node->next;			return *this;		}		//后置++和前置++構(gòu)成重載		Self& operator ++(int)		{			node = node->next;			return *this;		}		list_Iterator(Node* _node)			:node(_node)		{		}		Self& operator--() {			node = node->prev;			return *this;		}		Self& operator--(int) {			node = node->prev;			return *this;		}		Ptr operator*()const {			return node->data;		}		Ptr operator->() {			return &node->data;		}		bool operator	!=(const Self& it) const {			return node != it->node;		}		bool operator	==( const Self& it) const {			return node == it.node;		}	};

list迭代器分為ierator和const_iterator迭代器，本來(lái)分別實(shí)現(xiàn)他的iterator迭代器和const_iterator迭代器。但是c++中有模板作為支撐。對(duì)list類(lèi)采用三個(gè)模板來(lái)實(shí)現(xiàn)迭代器。

	typedef list_Iterator<T, T*, T&> iterator;		typedef list_Iterator<T, const T*, const T&> const_iterator;

list類(lèi)中iterator和const_iterator模板定義分別對(duì)應(yīng)迭代器中模板定義的：

	template<class T, class Ref, class Ptr>

采用向上傳值的方式，傳入不同值來(lái)采用不同迭代器。iterator傳入的對(duì)應(yīng)的是.
const_iterator傳入的是對(duì)應(yīng)的是,
迭代器根據(jù)傳入不同值來(lái)判斷采用的是那種迭代器。
首先是迭代器的++，分為前置++和后置++。兩種運(yùn)算符重載根據(jù)參數(shù)來(lái)構(gòu)成運(yùn)算符重載。

	  //前置++		Self& operator ++()		{			node = node->next;			return *this;		}		//后置++和前置++構(gòu)成重載		Self& operator ++(int)		{			node = node->next;			return *this;		

迭代器前置++和后置++都是將node->nex來(lái)賦給node來(lái)達(dá)到迭代器的移動(dòng)。
迭代器的operator*()和operator->()都是獲取迭代器所對(duì)應(yīng)的值。
但是operator*()返回的是模板的&可以都也可以寫(xiě)。
而operator->()返回的是模板對(duì)應(yīng)指針。

		Ptr operator*()const {			return node->data;		}		Ptr operator->() {			return &node->data;		}

list其他接口的實(shí)現(xiàn)：
list接口實(shí)現(xiàn)其實(shí)和鏈表基本差不了多少。唯一的差別就是list就是用到了迭代器。
2.1 list的insert()
數(shù)是一個(gè)迭代器和要插入的值X

iterator insert(iterator pos, const T& x) {			Node* cue = pos.node;			Node* prev = cue->prev;			Node* newnode = new Node(x);			prev->next = newnode;			newnode->prev = prev;			newnode->next = cue;			cue->prev = newnode;			return iterator(newnode);		}

先保存pos對(duì)應(yīng)的模板值接著參照鏈表的在pos的前一個(gè)節(jié)點(diǎn)和pos節(jié)點(diǎn)鏈接起來(lái)，返回pos’節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)的迭代器。

2.2 list的push_back()

	void push_back(const T& t) {			/*	  Node* l = head->prev;				  Node* newnode = new Node(t);				  newnode->prev = l;				  l->next = newnode;				  head->prev = newnode;				  newnode->next = head;*/			insert(end(), t);		}

list的push_back()只需調(diào)用insert()但是參數(shù)迭代器是end().
2.3 list的erase()

		iterator erase(iterator iter) {			assert(iter != end());			Node* cur = iter.node;			Node* prev = cur->prev;			Node* Next = cur->next;			prev->next = Next;			Next->prev = prev;			delete cur;			return iterator(Next);		}

list的erase()傳入要?jiǎng)h所對(duì)應(yīng)的迭代器。然后保存迭代器所對(duì)應(yīng)的模板值找到前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)將錢(qián)一個(gè)節(jié)點(diǎn)后一個(gè)節(jié)點(diǎn)連接起來(lái)。釋放pos對(duì)應(yīng)的節(jié)點(diǎn)。返回pos下一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的指針。
2.4 list構(gòu)造
在list無(wú)參構(gòu)造將head的next和prev都指向自己，早就循環(huán)鏈表。

list() {			head = new Node(T());			head->next = head;			head->prev = head;					}

		list(IteraterFirst first,IteraterFirstEnd en) {			head = new Node(T());			head->next = head;			head->prev = head;					while (first!=en) {				push_back(*first);				first++;			}				}

傳統(tǒng)寫(xiě)法	list(const list<T>& x) {			head = new Node(T());			head->next = head;			head->prev = head;			const_iterator i = x.begin();			while (i != x.end()) {				push_back(*i);				i++;			}					}現(xiàn)代寫(xiě)法	list(const list<T>& t) {			head = new Node(T());				head->next = head;			head->prev = head;			list<T> temp(t.begin(),t.end());			swap(head, temp.head);		}		list<T> operator=(const list<T> lt) {					swap(head, lt.head);			return *this;		}

2.5 其他接口大多都是參照inser()和erase()實(shí)現(xiàn)的