list類的基本結(jié)構(gòu)

xxxxSTL中l(wèi)ist是一個(gè)雙向帶頭循環(huán)鏈表。除了頭結(jié)點(diǎn)不存儲(chǔ)有效信息外，其余node結(jié)點(diǎn)存儲(chǔ)有效信息。同時(shí)，為了防止代碼冗余，對(duì)于存儲(chǔ)信息類型不同的問題，將采用模板的方式解決。
xxxxlist需要?jiǎng)?chuàng)建3個(gè)類：結(jié)點(diǎn)類、迭代器類和鏈表類。

結(jié)點(diǎn)類

成員變量

xxxx就像C語言中鏈表的創(chuàng)建，C++的鏈表也需要構(gòu)建一個(gè)類（類似于C的結(jié)構(gòu)體）包含節(jié)點(diǎn)中數(shù)據(jù)信息、下一節(jié)點(diǎn)地址和上一節(jié)點(diǎn)的地址三部分信息。
結(jié)點(diǎn)類成員變量如下：

template<class T>struct _list_node_{	T _val;					//存儲(chǔ)數(shù)據(jù)	_list_node_<T>* _next;	_list_node_<T>* _prev;};

成員函數(shù)

xxxx分析我們需要寫的成員函數(shù)：發(fā)現(xiàn)只有構(gòu)造函數(shù)需要寫，因?yàn)樵趎ew新的結(jié)點(diǎn)時(shí)，會(huì)自動(dòng)調(diào)用它的構(gòu)造函數(shù)，如果不寫就會(huì)產(chǎn)生隨機(jī)值。但是結(jié)點(diǎn)不會(huì)拷貝構(gòu)造，不會(huì)賦值。并且節(jié)點(diǎn)的釋放是list控制。所以不需要寫拷貝構(gòu)造、賦值運(yùn)算法重載和析構(gòu)函數(shù)。
結(jié)點(diǎn)類完整代碼如下：

解釋:由于結(jié)點(diǎn)類的成員變量需要被其他類直接訪問，所以要將成員變量設(shè)置成公有，所以直接用struct（默認(rèn)內(nèi)容為公有public）。下面迭代器類同理

迭代器類

xxxx不同于string、vector兩種容器，list的迭代器并不是原生的指針，而是封裝結(jié)點(diǎn)指針成了一個(gè)類。
迭代器類代碼如下：

	template<class T, class Ref, class Ptr>	struct _list_iterator_					//迭代器就是需要淺拷貝，不需要重新寫拷貝構(gòu)造或者復(fù)制	{										//析構(gòu)函數(shù)：迭代器只是存一下指針，指針指向的結(jié)點(diǎn)由鏈表管理，不需要迭代器去釋放空間		typedef _list_node_<T> node;		typedef _list_iterator_<T, Ref, Ptr> self;		_list_iterator_(node* pnode = nullptr)			:_pnode(pnode)		{}		Ref operator*()				//不加引用就是返回一個(gè)臨時(shí)變量，不可更改具有常屬性		{			return _pnode->_val;		}		Ptr operator->()		{			return &_pnode->_val;				//it->->_year   it->獲得T*，T*->獲得T類中的內(nèi)容		}		bool operator==(const self& s) const		{			return _pnode == s._pnode;		}		bool operator!=(const self& s) const		{			return _pnode != s._pnode;			}		self& operator++()		{			_pnode = _pnode->_next;			return *this;		}		self operator++(int)			//返回的是臨時(shí)對(duì)象，所以不返回引用		{			self tmp(*this);			_pnode = _pnode->_next;			return tmp;		}		self& operator--()		{			_pnode = _pnode->_prev;			return *this;		}		self operator--(int)			//返回的是臨時(shí)對(duì)象，所以不返回引用		{			self tmp(*this);			_pnode = _pnode->_prev;			return tmp;		}		//成員變量		node* _pnode;	};

xxxx問題一：為什么要這樣做呢？因?yàn)橛捎趌ist并不是序列型容器，而是一個(gè)一個(gè)結(jié)點(diǎn)通過地址連接起來的。而為了保證所有容器迭代器使用方法的統(tǒng)一性，都要有對(duì)迭代器++/–/*等操作。++/–會(huì)直接訪問上一個(gè)結(jié)點(diǎn)或者下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)；解引用操作則會(huì)直接訪問當(dāng)前結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)。如果我們使用原生指針（結(jié)點(diǎn)的指針），則無法達(dá)到迭代器所要求的結(jié)果。因此，我們需要將結(jié)點(diǎn)的指針包裝成類，通過運(yùn)算符重載改變它的行為。達(dá)到這樣的目的。
xxxx問題二：為什么迭代器類不寫拷貝構(gòu)造、賦值重載和析構(gòu)函數(shù)呢？因?yàn)榈髟诳截悩?gòu)造和賦值的時(shí)候，就是希望做到淺拷貝，就是將值進(jìn)行拷貝，讓他們指向同一塊空間，而不是將指向的內(nèi)容進(jìn)行深拷貝。因此編譯器自動(dòng)生成的淺拷貝就夠了。其次，由于迭代器并沒有自己開辟空間，因此無空間的釋放，所以不需要析構(gòu)函數(shù)。結(jié)點(diǎn)的釋放是鏈表的任務(wù)
xxxx問題三:迭代器的模板中，為何需要三個(gè)模板參數(shù)？三個(gè)模板參數(shù)分別代表什么意思？。我們都知道，list的迭代器不同于string和vector的原生指針類型的迭代器，他是一個(gè)類。對(duì)于原生指針來說。被const修飾和不被const修飾的兩種指針就是兩種類型。因此對(duì)于正常的思維來說，迭代器就應(yīng)該實(shí)現(xiàn)成兩種類，一個(gè)是iterator，一個(gè)是const_iterator，兩種分開寫。因?yàn)槿绻€是想string、vector一樣單純把const和非const兩種迭代器看作一種，在list類里typedef成const和非const類型的迭代器。這樣就會(huì)導(dǎo)致const無效，還是可以更改內(nèi)容。因?yàn)?，迭代器仍然是非const，你只是把迭代器的類型名改成了const_iterator，并沒有改變迭代器的實(shí)質(zhì)。所以當(dāng)調(diào)用解引用的操作符重載時(shí)，還是會(huì)返回T&，還是可以更改。所以第一種解決方法就是將iterator和const_iterator兩種迭代器類型分成兩個(gè)類來寫，這樣const修飾的鏈表就會(huì)去調(diào)用const_iterator的類，非const鏈表就會(huì)調(diào)用iterator的類。但是這樣就會(huì)造成大量代碼的冗余。
xxxx于是，就出現(xiàn)了利用模板的方法，來區(qū)分兩種迭代器。
xxxx第一個(gè)參數(shù)模板class T：代表的是數(shù)據(jù)的類型。
xxxx第二個(gè)參數(shù)模板class Ref：代表的是結(jié)點(diǎn)中數(shù)據(jù)的引用。
xxxx第三個(gè)參數(shù)模板class Ptr：代表的是結(jié)點(diǎn)中數(shù)據(jù)的指針。
具體如下圖：

如果還是有不理解可以通過下面成員函數(shù)的解析再次加深理解。

成員函數(shù)

1、解引用運(yùn)算符重載

Ref operator*()				//不加引用就是返回一個(gè)臨時(shí)變量，不可更改具有常屬性{	return _pnode->_val;}

xxxx對(duì)于string、vector迭代器是原生指針的容器來說。他們的迭代器就是數(shù)據(jù)的地址，因此解引用可以直接拿到數(shù)據(jù)。而list并不是，所以需要運(yùn)算符重載來改變它的行為?？梢酝ㄟ^對(duì)迭代器解引用直接獲取數(shù)據(jù)。所以return _pnode->val
xxxx同時(shí)，對(duì)于返回值，我們需要返回的是一個(gè)引用，否則，返回的就是一個(gè)臨時(shí)變量，具有常屬性，不可改變。并且，如果迭代器是const_iterator所以它的Ref就是const T&就不能對(duì)數(shù)據(jù)進(jìn)行寫，只能讀。const類型迭代器返回的是T&，就可讀可寫了。

2、箭頭運(yùn)算符重載

Ptr operator->(){	return &_pnode->val;}

xxxx若迭代器為原生指針，則it->就可以直接獲取it的內(nèi)容，但是list的迭代器不可以，所以就需要運(yùn)算符重載改變行為。
xxxx值得注意的是

3、迭代器前置++

typedef _list_iterator_<class T, class Ref, class Ptr> selfself& operator++(){	_pnode = _pnode->_next;	return *this;}

xxxxself是一個(gè)類型，返回的就是迭代器自己。self是typedef出來的。前置–類似就是將_next換成_prev。

4、迭代器后置++

self operator++(int){	self tmp(*this);	_pnode = _pnode->_next;	return tmp;}

xxxx因?yàn)榉祷氐氖莟mp，是臨時(shí)變量，所以不能返回引用。因?yàn)榉祷氐闹凳歉淖冎暗闹?，所以要?bào)錯(cuò)原來的值，返回再將*this改變。后置–類似，就是將_next換成_prev。

5、迭代器的比較

xxxx迭代器的比較比較簡(jiǎn)單，所以就不細(xì)說了。

鏈表類

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;	list()	{		_head = (node*)malloc(sizeof(node));		_head->_next = _head;		_head->_prev = _head;	}	list(const list<T>& lt)	{		_head = new node;		_head->_next = _head;		_head->_prev = _head;		for (const T& e:lt)		{			push_back(e);		}	}			list<T>& operator=(list<T> lt)		//現(xiàn)代寫法	{		swap(_head, lt._head);		return *this;	}	~list()	{		clear();		delete _head;		_head = nullptr;	}				void clear()	{		iterator it = begin();		while (it != end())		{			it = erase(it);		}	}	iterator begin()	{		return _head->_next;	}	const_iterator begin() const	{		return _head->_next;	}	iterator end()	{		return _head;	}	const_iterator end() const	{		return _head;	}	void push_back(const T& x)	{		node* tail = _head->_prev;		node* newnode = new node(x);		//調(diào)用node的構(gòu)造函數(shù)		tail->_next = newnode;		newnode->_next = _head;		_head->_prev = newnode;		newnode->_prev = tail;	}	void insert(iterator pos, const T& x)	{		assert(pos._pnode);		node* cur = pos._pnode;		node* prev = cur->_prev;		node* newnode = new node(x);		prev->_next = newnode;		newnode->_next = cur;		cur->_prev = newnode;		newnode->_prev = prev;	}	iterator erase(iterator pos)	{		assert(pos._pnode);		assert(pos != end());		node* prev = pos._pnode->_prev;		node* next = pos._pnode->_next;		delete pos._pnode;				prev->_next = next;		next->_prev = prev;		return iterator(next);	}	size_t size()	{		size_t sz = 0;		iterator it = begin();		while (it != end())		{			it++;			sz++;		}		return sz;	}	bool empty()	{		return begin() == end();	}private:	node* _head;};

成員變量

xxxx成員變量就是一個(gè)頭結(jié)點(diǎn)。同時(shí)還需要typedef出結(jié)點(diǎn)、const_iterator和iterator

成員函數(shù)

1、構(gòu)造函數(shù)

list(){	_head = (node*)malloc(sizeof(node));	_head->_next = _head;	_head->_prev = _head;}

xxxx注意_head需要使用malloc來開辟空間，因?yàn)轭^結(jié)點(diǎn)不需要存儲(chǔ)數(shù)據(jù)，所以不需要初始化。如果用new的話存在一個(gè)問題，就是如果出現(xiàn)數(shù)據(jù)類型T也是list，那么用new開辟頭結(jié)點(diǎn)空間時(shí)，就會(huì)自動(dòng)迪調(diào)用構(gòu)造函數(shù)初始化，初始化就要調(diào)用構(gòu)造函數(shù)，調(diào)用構(gòu)造函數(shù)就要new并且初始化，就會(huì)出現(xiàn)一個(gè)無限循環(huán)。所以就需要malloc來開辟空間。
xxxx對(duì)于空鏈表來說，應(yīng)該是頭結(jié)點(diǎn)的next和prev都指向自己。

2、拷貝構(gòu)造

list(const list<T>& lt){	_head = (node*)malloc(sizeof(node));	_head->_next = _head;	_head->_prev = _head;	for(const auto& e : lt)	{		push_back(e);	}}

xxxx可以復(fù)用代碼，使用push_back。但是push_back之前，必須是規(guī)范的空鏈表，必須初始化。

3、賦值重載

list<T>& operator=(const list<T> lt){	swap(_head, lt._head);	return *this;}

xxxx這是一種現(xiàn)代寫法，很簡(jiǎn)單，先利用拷貝構(gòu)造，構(gòu)造出一個(gè)完全相同的，這樣把*this的_head與拷貝構(gòu)造出來的_head一換，這樣就直接把拷貝構(gòu)造出來的內(nèi)容的給了this

4、析構(gòu)函數(shù)

~list(){	clear();	delete _head;	_head = nullptr;}

xxxx同樣的道理，也是復(fù)用，先用clear，將鏈表置空（所有的結(jié)點(diǎn)都被釋放掉），然后再釋放掉頭結(jié)點(diǎn)。

5、clear

void clear(){	iterator it = begin();	while(it != end())	{		it = erase(it);	}}

xxxx挨個(gè)釋放所有結(jié)點(diǎn)就是復(fù)用erase，同時(shí)，因?yàn)獒尫沤Y(jié)點(diǎn)后，就無法找到該結(jié)點(diǎn)后的結(jié)點(diǎn)，所以it要接受erase的返回值（即：被釋放結(jié)點(diǎn)后結(jié)點(diǎn)的迭代器）

6、begin（）、end（）

iterator begin(){	return _head->_next;}const_iterator begin() const{	return _head->_next;}iterator end(){	return _head->_prev;}const_iterator end() const{	return _head->_prev;}

7、insert

void insert(iterator pos, const T&x){	assert(pos._pnode);	node* cur = pos._pnode;	node* prev = cur->_prev;	node* newnode = new node(x);	prev->_next = newnode;	newnode->_next = cur;	cur->_prev = newnode;	newnode->_prev = prev;}

xxxxprev、cur、next三個(gè)結(jié)點(diǎn)的鏈接關(guān)系搞清楚即可，由于是帶頭雙向循環(huán)，所以，不需要考慮結(jié)點(diǎn)之間連接的順序，也不需要考慮多種情況。需要考慮的就是pos除是否為空，空的位置不能操作，斷言一下。提高安全性。

8、erase

iterator erase(iterator pos){	assert(pos._pnode);	assert(pos != end());	node* prev = pos._pnode->_prev;	node* next = pos._pnode->_next;	delete pos._pnode;	prev->_next = next;	next->_prev = prev;	return iterator(next);}

xxxx刪除后，為了防止迭代器失效，所以要把下一位置的的迭代器當(dāng)做返回值返回。這是STL中容器的普遍做法。

其他小型接口

xxxx其余的接口都比較比較簡(jiǎn)單，直接看代碼就能明白，代碼在上面的list類完整版部分。

xxxx
xxxx
xxxx
xxxx
xxxx如果讀者還有任何疑問，可以評(píng)論留言，或者私信我，我們一起探討，一起進(jìn)步