本次所需實作的三個類及其成員函式介面總覽

namespace cl
{
	//模擬實作list當中的結點類
	template<class T>
	struct _list_node
	{
		//成員函式
		_list_node(const T& val = T()); //建構式

		//成員變數
		T _val;                 //資料域
		_list_node<T>* _next;   //后繼指標
		_list_node<T>* _prev;   //前驅指標
	};

	//模擬實作list迭代器
	template<class T, class Ref, class Ptr>
	struct _list_iterator
	{
		typedef _list_node<T> node;
		typedef _list_iterator<T, Ref, Ptr> self;

		_list_iterator(node* pnode);  //建構式

		//各種運算子多載函式
		self operator++();
		self operator--();
		self operator++(int);
		self operator--(int);
		bool operator==(const self& s) const;
		bool operator!=(const self& s) const;
		Ref operator*();
		Ptr operator->();

		//成員變數
		node* _pnode; //一個指向結點的指標
	};

	//模擬實作list
	template<class T>
	class list
	{
	public:
		typedef _list_node<T> node;
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		//默認成員函式
		list();
		list(const list<T>& lt);
		list<T>& operator=(const list<T>& lt);
		~list();

		//迭代器相關函式
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;

		//訪問容器相關函式
		T& front();
		T& back();
		const T& front() const;
		const T& back() const;

		//插入、洗掉函式
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void push_back(const T& x);
		void pop_back();
		void push_front(const T& x);
		void pop_front();

		//其他函式
		size_t size() const;
		void resize(size_t n, const T& val = T());
		void clear();
		bool empty() const;
		void swap(list<T>& lt);

	private:
		node* _head; //指向鏈表頭結點的指標
	};
}

結點類的模擬實作

我們經常說list在底層實作時就是一個鏈表，更準確來說，list實際上是一個帶頭雙向回圈鏈表，

因此，我們若要實作list，則首先需要實作一個結點類，而一個結點需要存盤的資訊有：資料、前一個結點的地址、后一個結點的地址，于是該結點類的成員變數也就出來了（資料、前驅指標、后繼指標），

而對于該結點類的成員函式來說，我們只需實作一個建構式即可，因為該結點類只需要根據資料來構造一個結點即可，而結點的釋放則由list的解構式來完成，

建構式

結點類的建構式直接根據所給資料構造一個結點即可，構造出來的結點的資料域存盤的就是所給資料，而前驅指標和后繼指標均初始化為空指標即可，

//建構式
_list_node(const T& val = T())
	:_val(val)
	, _prev(nullptr)
	, _next(nullptr)
{}

注意： 若構造結點時未傳入資料，則默認以list容器所存盤型別的默認建構式所構造出來的值為傳入資料，

迭代器類的模擬實作

迭代器類存在的意義

之前模擬實作string和vector時都沒有說要實作一個迭代器類，為什么實作list的時候就需要實作一個迭代器類了呢？

因為string和vector物件都將其資料存盤在了一塊連續的記憶體空間，我們通過指標進行自增、自減以及解參考等操作，就可以對相應位置的資料進行一系列操作，因此string和vector當中的迭代器就是原生指標，

但是對于list來說，其各個結點在記憶體當中的位置是隨機的，并不是連續的，我們不能僅通過結點指標的自增、自減以及解參考等操作對相應結點的資料進行操作，

而迭代器的意義就是，讓使用者可以不必關心容器的底層實作，可以用簡單統一的方式對容器內的資料進行訪問，

既然list的結點指標的行為不滿足迭代器定義，那么我們可以對這個結點指標進行封裝，對結點指標的各種運算子操作進行多載，使得我們可以用和string和vector當中的迭代器一樣的方式使用list當中的迭代器，例如，當你使用list當中的迭代器進行自增操作時，實際上執行了p = p->next陳述句，只是你不知道而已，

總結： list迭代器類，實際上就是對結點指標進行了封裝，對其各種運算子進行了多載，使得結點指標的各種行為看起來和普通指標一樣，（例如，對結點指標自增就能指向下一個結點）

迭代器類的模板引數說明

這里我們所實作的迭代器類的模板引數串列當中為什么有三個模板參數？

template<class T, class Ref, class Ptr>

在list的模擬實作當中，我們typedef了兩個迭代器型別，普通迭代器和const迭代器，

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

這里我們就可以看出，迭代器類的模板引數串列當中的Ref和Ptr分別代表的是參考型別和指標型別，

當我們使用普通迭代器時，編譯器就會實體化出一個普通迭代器物件；當我們使用const迭代器時，編譯器就會實體化出一個const迭代器物件，

若該迭代器類不設計三個模板引數，那么就不能很好的區分普通迭代器和const迭代器，

建構式

迭代器類實際上就是對結點指標進行了封裝，其成員變數就只有一個，那就是結點指標，其建構式直接根據所給結點指標構造一個迭代器物件即可，

//建構式
_list_iterator(node* pnode)
	:_pnode(pnode)
{}

++運算子的多載

首先是前置++，前置++原本的作用是將資料自增，然后回傳自增后的資料，我們的目的是讓結點指標的行為看起來更像普通指標，那么對于結點指標的前置++，我們就應該先讓結點指標指向后一個結點，然后再回傳“自增”后的結點指標即可，

//前置++
self operator++()
{
	_pnode = _pnode->_next; //讓結點指標指向后一個結點
	return *this; //回傳自增后的結點指標
}

對于后置++，我們則應該先記錄當前結點指標的指向，然后讓結點指標指向后一個結點，最后回傳“自增”前的結點指標即可，

//后置++
self operator++(int)
{
	self tmp(*this); //記錄當前結點指標的指向
	_pnode = _pnode->_next; //讓結點指標指向后一個結點
	return tmp; //回傳自增前的結點指標
}

說明： self是當前迭代器物件的型別：

typedef _list_iterator<T, Ref, Ptr> self;

–運算子的多載

對于前置- -，我們應該先讓結點指標指向前一個結點，然后再回傳“自減”后的結點指標即可，

//前置--
self operator--()
{
	_pnode = _pnode->_prev; //讓結點指標指向前一個結點
	return *this; //回傳自減后的結點指標
}

而對于后置- -，我們則應該先記錄當前結點指標的指向，然后讓結點指標指向前一個結點，最后回傳“自減”前的結點指標即可，

//后置--
self operator--(int)
{
	self tmp(*this); //記錄當前結點指標的指向
	_pnode = _pnode->_prev; //讓結點指標指向前一個結點
	return tmp; //回傳自減前的結點指標
}

==運算子的多載

當使用==運算子比較兩個迭代器時，我們實際上想知道的是這兩個迭代器是否是同一個位置的迭代器，也就是說，我們判斷這兩個迭代器當中的結點指標的指向是否相同即可，

bool operator==(const self& s) const
{
	return _pnode == s._pnode; //判斷兩個結點指標指向是否相同
}

!=運算子的多載

!=運算子剛好和==運算子的作用相反，我們判斷這兩個迭代器當中的結點指標的指向是否不同即可，

bool operator!=(const self& s) const
{
	return _pnode != s._pnode; //判斷兩個結點指標指向是否不同
}

*運算子的多載

當我們使用解參考運算子時，是想得到該位置的資料內容，因此，我們直接回傳當前結點指標所指結點的資料即可，但是這里需要使用參考回傳，因為解參考后可能需要對資料進行修改，

Ref operator*()
{
	return _pnode->_val; //回傳結點指標所指結點的資料
}

->運算子的多載

某些情景下，我們使用迭代器的時候可能會用到->運算子，
想想如下場景：
?當list容器當中的每個結點存盤的不是內置型別，而是自定義型別，例如日期類，那么當我們拿到一個位置的迭代器時，我們可能會使用->運算子訪問Date的成員：

	list<Date> lt;
	Date d1(2021, 8, 10);
	Date d2(1980, 4, 3);
	Date d3(1931, 6, 29);
	lt.push_back(d1);
	lt.push_back(d2);
	lt.push_back(d3);
	list<Date>::iterator pos = lt.begin();
	cout << pos->_year << endl; //輸出第一個日期的年份

注意： 使用pos->_year這種訪問方式時，需要將日期類的成員變數設定為公有，

對于->運算子的多載，我們直接回傳結點當中所存盤資料的地址即可，

Ptr operator->()
{
	return &_pnode->_val; //回傳結點指標所指結點的資料的地址
}

講到這里，可能你會覺得不對，按照這種多載方式的話，這里使用迭代器訪問日期類當中的成員變數時不是應該用兩個->嗎？

這里本來是應該有兩個->的，第一個箭頭是pos ->去呼叫多載的operator->回傳Date* 的指標，第二個箭頭是Date* 的指標去訪問物件當中的成員變數_year，

但是一個地方出現兩個箭頭，程式的可讀性太差了，所以編譯器做了特殊識別處理，為了增加程式的可讀性，省略了一個箭頭，

list的模擬實作

默認成員函式

建構式

list是一個帶頭雙向回圈鏈表，在構造一個list物件時，直接申請一個頭結點，并讓其前驅指標和后繼指標都指向自己即可，

//建構式
list()
{
	_head = new node; //申請一個頭結點
	_head->_next = _head; //頭結點的后繼指標指向自己
	_head->_prev = _head; //頭結點的前驅指標指向自己
}

拷貝建構式

拷貝建構式就是根據所給list容器，拷貝構造出一個物件，對于拷貝建構式，我們先申請一個頭結點，并讓其前驅指標和后繼指標都指向自己，然后將所給容器當中的資料，通過遍歷的方式一個個尾插到新構造的容器后面即可，

//拷貝建構式
list(const list<T>& lt)
{
	_head = new node; //申請一個頭結點
	_head->_next = _head; //頭結點的后繼指標指向自己
	_head->_prev = _head; //頭結點的前驅指標指向自己
	for (const auto& e : lt)
	{
		push_back(e); //將容器lt當中的資料一個個尾插到新構造的容器后面
	}
}

賦值運算子多載函式

對于賦值運算子的多載，這里提供兩種寫法：
寫法一：現代寫法
這是比較容易理解的一種寫法，先呼叫clear函式將原容器清空，然后將容器lt當中的資料，通過遍歷的方式一個個尾插到清空后的容器當中即可，

//傳統寫法
list<T>& operator=(const list<T>& lt)
{
	if (this != &lt) //避免自己給自己賦值
	{
		clear(); //清空容器
		for (const auto& e : lt)
		{
			push_back(e); //將容器lt當中的資料一個個尾插到鏈表后面
		}
	}
	return *this; //支持連續賦值
}

寫法二：現代寫法
現代寫法的代碼量較少，首先利用編譯器機制，故意不使用參考接收引數，通過編譯器自動呼叫list的拷貝建構式構造出來一個list物件，然后呼叫swap函式將原容器與該list物件進行交換即可，

//現代寫法
list<T>& operator=(list<T> lt) //編譯器接收右值的時候自動呼叫其拷貝建構式
{
	swap(lt); //交換這兩個物件
	return *this; //支持連續賦值
}

這樣做相當于將應該用clear清理的資料，通過交換函式交給了容器lt，而當該賦值運算子多載函式呼叫結束時，容器lt會自動銷毀，并呼叫其解構式進行清理，

解構式

對物件進行析構時，首先呼叫clear函式清理容器當中的資料，然后將頭結點釋放，最后將頭指標置空即可，

//解構式
~list()
{
	clear(); //清理容器
	delete _head; //釋放頭結點
	_head = nullptr; //頭指標置空
}

迭代器相關函式

begin和end

首先我們應該明確的是：begin函式回傳的是第一個有效資料的迭代器，end函式回傳的是最后一個有效資料的下一個位置的迭代器，

對于list這個帶頭雙向回圈鏈表來說，其第一個有效資料的迭代器就是使用頭結點后一個結點的地址構造出來的迭代器，而其最后一個有效資料的下一個位置的迭代器就是使用頭結點的地址構造出來的迭代器，（最后一個結點的下一個結點就是頭結點）

iterator begin()
{
	//回傳使用頭結點后一個結點的地址構造出來的普通迭代器
	return iterator(_head->_next);
}
iterator end()
{
	//回傳使用頭結點的地址構造出來的普通迭代器
	return iterator(_head);
}

當然，還需要多載一對用于const物件的begin函式和end函式，

const_iterator begin() const
{
	//回傳使用頭結點后一個結點的地址構造出來的const迭代器
	return const_iterator(_head->_next);
}
const_iterator end() const
{
	//回傳使用頭結點的地址構造出來的普通const迭代器
	return const_iterator(_head);
}

訪問容器相關函式

front和back

front和back函式分別用于獲取第一個有效資料和最后一個有效資料，因此，實作front和back函式時，直接回傳第一個有效資料和最后一個有效資料的參考即可，

T& front()
{
	return *begin(); //回傳第一個有效資料的參考
}
T& back()
{
	return *(--end()); //回傳最后一個有效資料的參考
}

當然，這也需要多載一對用于const物件的front函式和back函式，因為const物件呼叫front和back函式后所得到的資料不能被修改，

const T& front() const
{
	return *begin(); //回傳第一個有效資料的const參考
}
T& back()
{
	return *(--end()); //回傳最后一個有效資料的參考
}
const T& back() const
{
	return *(--end()); //回傳最后一個有效資料的const參考
}

插入、洗掉函式

insert

insert函式可以在所給迭代器之前插入一個新結點，

先根據所給迭代器得到該位置處的結點指標cur，然后通過cur指標找到前一個位置的結點指標prev，接著根據所給資料x構造一個待插入結點，之后再建立新結點與cur之間的雙向關系，最后建立新結點與prev之間的雙向關系即可，

//插入函式
void insert(iterator pos, const T& x)
{
	assert(pos._pnode); //檢測pos的合法性

	node* cur = pos._pnode; //迭代器pos處的結點指標
	node* prev = cur->_prev; //迭代器pos前一個位置的結點指標
	node* newnode = new node(x); //根據所給資料x構造一個待插入結點

	//建立newnode與cur之間的雙向關系
	newnode->_next = cur;
	cur->_prev = newnode;
	//建立newnode與prev之間的雙向關系
	newnode->_prev = prev;
	prev->_next = newnode;
}

erase

erase函式可以洗掉所給迭代器位置的結點，

先根據所給迭代器得到該位置處的結點指標cur，然后通過cur指標找到前一個位置的結點指標prev，以及后一個位置的結點指標next，緊接著釋放cur結點，最后建立prev和next之間的雙向關系即可，

//洗掉函式
iterator erase(iterator pos)
{
	assert(pos._pnode); //檢測pos的合法性
	assert(pos != end()); //洗掉的結點不能是頭結點

	node* cur = pos._pnode; //迭代器pos處的結點指標
	node* prev = cur->_prev; //迭代器pos前一個位置的結點指標
	node* next = cur->_next; //迭代器pos后一個位置的結點指標

	delete cur; //釋放cur結點

	//建立prev與next之間的雙向關系
	prev->_next = next;
	next->_prev = prev;
	
	return iterator(next); //回傳所給迭代器pos的下一個迭代器
}

push_back和pop_back

push_back和pop_back函式分別用于list的尾插和尾刪，在已經實作了insert和erase函式的情況下，我們可以通過復用函式來實作push_back和pop_back函式，

push_back函式就是在頭結點前插入結點，而pop_back就是洗掉頭結點的前一個結點，

//尾插
void push_back(const T& x)
{
	insert(end(), x); //在頭結點前插入結點
}
//尾刪
void pop_back()
{
	erase(--end()); //洗掉頭結點的前一個結點
}

push_front和pop_front

當然，用于頭插和頭刪的push_front和pop_front函式也可以復用insert和erase函式來實作，

push_front函式就是在第一個有效結點前插入結點，而pop_front就是洗掉第一個有效結點，

//頭插
void push_front(const T& x)
{
	insert(begin(), x); //在第一個有效結點前插入結點
}
//頭刪
void pop_front()
{
	erase(begin()); //洗掉第一個有效結點
}

其他函式

size

size函式用于獲取當前容器當中的有效資料個數，因為list是鏈表，所以只能通過遍歷的方式逐個統計有效資料的個數，

size_t size() const
{
	size_t sz = 0; //統計有效資料個數
	const_iterator it = begin(); //獲取第一個有效資料的迭代器
	while (it != end()) //通過遍歷統計有效資料個數
	{
		sz++;
		it++;
	}
	return sz; //回傳有效資料個數
}

擴展： 其實也可以給list多設定一個成員變數size，用于記錄當前容器內的有效資料個數，

resize

resize函式的規則：

1. 若當前容器的size小于所給n，則尾插結點，直到size等于n為止，
2. 若當前容器的size大于所給n，則只保留前n個有效資料，

實作resize函式時，不要直接呼叫size函式獲取當前容器的有效資料個數，因為當你呼叫size函式后就已經遍歷了一次容器了，而如果結果是size大于n，那么還需要遍歷容器，找到第n個有效結點并釋放之后的結點，

這里實作resize的方法是，設定一個變數len，用于記錄當前所遍歷的資料個數，然后開始變數容器，在遍歷程序中：

1. 當len大于或是等于n時遍歷結束，此時說明該結點后的結點都應該被釋放，將之后的結點釋放即可，
2. 當容器遍歷完畢時遍歷結束，此時說明容器當中的有效資料個數小于n，則需要尾插結點，直到容器當中的有效資料個數為n時停止尾插即可，

void resize(size_t n, const T& val = T())
{
	iterator i = begin(); //獲取第一個有效資料的迭代器
	size_t len = 0; //記錄當前所遍歷的資料個數
	while (len < n&&i != end())
	{
		len++;
		i++;
	}
	if (len == n) //說明容器當中的有效資料個數大于或是等于n
	{
		while (i != end()) //只保留前n個有效資料
		{
			i = erase(i); //每次洗掉后接收下一個資料的迭代器
		}
	}
	else //說明容器當中的有效資料個數小于n
	{
		while (len < n) //尾插資料為val的結點，直到容器當中的有效資料個數為n
		{
			push_back(val);
			len++;
		}
	}
}

clear

clear函式用于清空容器，我們通過遍歷的方式，逐個洗掉結點，只保留頭結點即可，

void clear()
{
	iterator it = begin();
	while (it != end()) //逐個洗掉結點，只保留頭結點
	{
		it = erase(it);
	}
}

empty

empty函式用于判斷容器是否為空，我們直接判斷該容器的begin函式和end函式所回傳的迭代器，是否是同一個位置的迭代器即可，（此時說明容器當中只有一個頭結點）

bool empty() const
{
	return begin() == end(); //判斷是否只有頭結點
}

swap

swap函式用于交換兩個容器，list容器當中存盤的實際上就只有鏈表的頭指標，我們將這兩個容器當中的頭指標交換即可，

void swap(list<T>& lt)
{
	::swap(_head, lt._head); //交換兩個容器當中的頭指標即可
}

注意： 在此處呼叫庫當中的swap函式需要在swap之前加上“::”（作用域限定符），告訴編譯器這里優先在全域范圍尋找swap函式，否則編譯器會認為你呼叫的就是你正在實作的swap函式（就近原則），