一. list介面函式總覽

namespace lyp
{
	//模擬實作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++(int);
		self operator--();
		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 的底層結構為帶頭雙向回圈鏈表，所以結點類里的成員變數有 T _val(資料)，_list_node< T >* _prev(前驅指標)，_list_node< T >* _next(后繼指標)，成員函式只需要建構式即可(初始化資料，初始化指標為nullptr)

template<class T>
struct _list_node
{
  _list_node(const T& val = T())
  	:_val(val)
  	,_prev(nullptr)
  	,_next(nullptr)
  {}
	T _val;                // 資料
	_list_node<T>* _prev;  // 前驅指標
	_list_node<T>* _next; // 后繼指標
}

三. 迭代器類模擬實作

前面的博客已經介紹過 vector 和 string 類的模擬實作，在 vector 和 string 中，迭代器均為原生指標，是因為vector和string底層實作均為陣列，在使用迭代器進行遍歷時可以支持 != 判斷是否到末尾，++ 移動到下一資料，但list為帶頭雙向回圈鏈表，若迭代器采用原生指標，不支持 != 操作，且++后不能移動到下一資料(底層是鏈表，空間不連續)，因此需要用一個類來封裝指標，對上述操作的運算子進行多載，使list能夠像vector/string一樣使用同樣的方式去進行遍歷

迭代器的成員變數 : node* _pnode; //一個指向結點的指標
迭代器的成員函式 : 運算子的多載

可能有讀者對模板引數比較疑惑，為什么會有三個模板引數呢?

template<class T,class Ref,class Ptr>

因為我們在list類中定義了兩個迭代器類，普通迭代器類，const迭代器類(Ref為 T&/const T& 型別，Ptr為 T*/const T* 型別)

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

當我們使用普通迭代器物件時，實體化出普通迭代器類(iterator)，使用const迭代器物件時，實體化出const迭代器類(const_iterator)

建構式

對封裝的指標進行初始化即可

_list_iterator(node* pnode)
	:_pnode(pnode)
{}

前置++和后置++

前置++/后置++都是將指標指向下一個資料，即 _pnode = _pnode->_next，前置++回傳++之后的值，后置++回傳原先的值，為了區分前置++和后置++,后置++比前置++多一個int引數

self 為當前迭代器型別

typedef _list_iterator<T,Ref,Ptr> self

// 前置++
self& operator++()
{
	_pnode = _pnode->_next;
	return *this;
}

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

前置- -和后置- -

前置- -/后置- -都是將指標指向前一個資料，即 _pnode = _pnode->_prev，前置- -回傳- -之后的值，后置- -回傳原先的值，為了區分前置- -和后置- -,后置- -比前置- -多一個int引數

self 為當前迭代器型別

// 前置- -
self& operator--()
{
	_pnode = _pnode->_prev;
	return *this;
}

// 后置- -
self& operator--(int)
{
	self tmp(*this);
	_pnode = _pnode->_prev;
	return tmp;
}

==/!=運算子多載

==運算子多載
比較兩個迭代器物件的_pnode指標指向是否相同

// ==運算子多載
bool operator==(const self& s)const
{
	return _pnode == s._pnode;
}

!=運算子多載
比較兩個迭代器物件的_pnode指標指向是否不同

// !=運算子多載
bool operator!=(const self& s)const
{
	return _pnode != s._pnode;
}

* 運算子多載

多載 * 運算子的目的是為了得到迭代器物件的_pnode指標所指向的資料

// * 運算子多載
Ref operator*()
{
	return _pnode->_val;
}

-> 運算子多載

多載 -> 運算子的目的是當list中的資料是自定義型別時，我們可以通過 -> 來訪問自定義型別的成員變數

// -> 運算子多載
Ptr operator->()
{
	return &_pnode->_val;
}

使用案例

class Date
{
public:
	int _year = 0;
	int _month = 1;
	int _day = 1;
}
int main()
{
	lt<Date> lt;
	lt.push_back(Date());
	list<Date>::iterator it = lt.begin();
	cout<<it->_year<<" "<<it->_month<<" "<<it->_day<<endl;
}

在這里編譯器做了一些優化
it->_year 本來應該是 it->->_year ，第一個->去呼叫operator->多載函式回傳T*的指標，第二個->用來去訪問自定義型別的成員變數，但是兩個箭頭程式的可讀性較差，所以編譯器做了優化，省略了一個箭頭

list模擬實作

建構式

list是一個帶頭雙向回圈鏈表，建構式的目的是創建一個頭結點，_next 和 _prev都指向自己

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

拷貝建構式

1). 申請一個頭結點，_next 和 _prev都指向自己
2). 將 lt 中的資料拷貝到新構造的容器中

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

賦值運算子多載

傳統寫法 :
1). 釋放除了頭結點以外的結點
2). 將 lt 中的資料拷貝到新構造的容器中

list<T>& operator=(const list<T>& lt)
{
  // 防止自己給自己賦值
	if(this != &lt)
	{
		clear(); // 清空資料
		for(const auto& e : lt) // 拷貝到新構造的容器中
		{
			push_back(e);
		}
	}
	return *this; // 支持連續賦值
}

現代寫法 :
1). 拷貝構造出 lt 物件
2). 交換 this 和 lt 的 _head 指標，出了作用域，lt 呼叫解構式，釋放掉原this的結點

list<T>& operator=(list<T> lt) // 拷貝構造
{
	std::swap(_head,lt._head); // 交換指標
	return *this; // 支持連續賦值
}

解構式

1). 使用 clear() 釋放除了頭結點以外的結點
2). 釋放掉頭結點

~list()
{
	clear(); // 釋放除了頭結點以外的結點
	delete _head; // 釋放掉頭結點
	_head = nullptr; // 置空頭指標
}

begin和end

begin() :
構造出指標指向第一個結點的迭代器物件
end() :
構造出指標指向頭結點的迭代器物件

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

front/back

front() :
回傳第一個結點資料的參考
end() :
回傳最后一個結點資料的參考

T& front()
{
	return *begin(); 
}
const T& front()const
{
	return *begin(); 
}
T& end()
{
	return *(--end()); 
}
const T& end()const
{
	return *(--end()); 
}

insert

1). 新開辟一個結點newnode(值為val)，得到當前結點的指標，前驅結點的指標
2). 前驅結點的_next 指向 newnode，newnode的_prev指向前驅結點
3). newnode的_next 指向當前結點，當前結點的_prev指向newnode

void insert(iterator pos,const T& val)
{
		assert(pos._pnode); // 斷言指標不為空
		node* cur = pos._pnode; // 當前結點指標
		node* prev = pos._pnode->_prev; // 前驅結點指標
		node* newnode = new node(val); // 新開辟結點

		prev->_next = newnode; // 前驅結點的_next 指向 newnode
		newnode->_prev = prev; // newnode的_prev指向前驅結點
		newnode->_next = cur;  // newnode的_next 指向當前結點
		cur->_prev = newnode;  // 當前結點的_prev指向newnode
}

erase

1). 得到前驅結點和后繼結點的指標
2). 前驅結點的_next 指向后繼結點
3). 后繼結點的_prev指向前驅結點
4). 洗掉當前結點，回傳洗掉位置的下一個位置

iterator erase(iterator pos)
{
	assert(!empty()); // 鏈表不為空
	assert(pos._pnode != _head); // 不能刪頭結點
	node* prev = pos._pnode->_prev; // 前驅結點指標
	node* next = pos._pnode->_next; // 后繼結點指標
	prev->_next = next; // 前驅結點的_next 指向后繼結點
	next->_prev = prev; // 后繼結點的_prev指向前驅結點
	delete pos._pnode;  // 洗掉當前結點
	return iterator(next); // 回傳洗掉位置的下一個位置
}

push_back/pop_back/push_front/pop_front

這四個函式都可以復用 insert 和 erase 函式

push_back :
尾插即在頭結點前插入一個結點
pop_back :
尾刪，洗掉最后一個結點
push_front :
頭插即在第一個結點前插入一個結點
pop_front :
頭刪，洗掉第一個結點

void push_back(const T& val)
{
	insert(end(),val);
}
void pop_back()
{
	erase(--end());
}
void push_front(const T& val)
{
	insert(begin(),val);
}
void pop_front()
{
	erase(begin());
}

size

獲取鏈表中有效結點的個數，遍歷一次鏈表即可得到，但這是O(n)的時間復雜度，如果要頻繁的使用size介面，可以在list類中加入_size成員變數

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

clear

只保留頭結點，遍歷鏈表呼叫erase介面進行洗掉，注意呼叫erase后 it 迭代器就已經失效了

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

empty

判斷容器是否為空

bool empty()const
{
	return begin() == end();
}

swap

交換容器的頭指標即可

void swap(list<T>& lt)
{
	std::swap(_head,lt._head);
}

resize

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

void resize(size_t n, const T& val = T())
{
		size_t len = size();
		if (n < len)
		{
			size_t count = len - n;
			while (count--)
			{
				pop_back();
			}
		}
		// n > len
		else
		{
			size_t count = n - len;
			while (count--)
			{
				push_back(val);
			}
		}
}