template<class T>
//struct也能定義類，默認(rèn)類的訪問限定符是 public
struct list_node
{
	//這個指針指向前一個節(jié)點(diǎn)
	list_node<T>* _prev;
	//這個指針指向后一個節(jié)點(diǎn)
	list_node<T>* _next;
	//這個是數(shù)據(jù)域中的元素
	T _data;
	
	//對節(jié)點(diǎn)使用匿名對象進(jìn)行初始化
	list_node(const T& data = T())
		:_prev(nullptr)
		,_next(nullptr)
		,_data(data)
	{}
};

//這里后面的兩個參數(shù)，在實際應(yīng)用時通常是T& , T* 或者是 const T& , const T*
//根據(jù)加與不加const 可以分別實例化出：普通正向迭代器與正向const迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	//將節(jié)點(diǎn)的類型進(jìn)行typedef方便使用
	typedef list_node<T> node;
	
	//將類自己進(jìn)行typedef方便使用
	typedef __list_iterator<T,Ref,Ptr> self;

	//成員變量 是一個指向節(jié)點(diǎn)的指針
	node* _pnode;

	//構(gòu)造函數(shù) 用一個節(jié)點(diǎn)的地址對迭代器進(jìn)行初始化，
	 __list_iterator(node* pnode)
		:_pnode(pnode)
	{}
};

template<class T>
class list
{
public:
	//將節(jié)點(diǎn)的類型進(jìn)行typedef方便使用
	typedef list_node<T> node;
	//將迭代器進(jìn)行typedef方便使用
	typedef __list_iterator<T, T&, T*> iterator;
	//將const迭代器進(jìn)行typedef方便使用
	typedef __list_iterator<T, const T&, const T*> const_iterator;
	//默認(rèn)構(gòu)造函數(shù)
	list()
	{
		empty_init();
	}
	//初始化函數(shù)
	void empty_init()
	{
		//申請一個頭節(jié)點(diǎn)，將節(jié)點(diǎn)的地址給_head
		_head = new node;
		//讓哨兵位節(jié)點(diǎn)的 前指針指向自己
		_head->_prev = _head;
		//讓哨兵位節(jié)點(diǎn)的 后指針指向自己
		_head->_next = _head;
	}
private:
	//指向哨兵位節(jié)點(diǎn)的指針
	node* _head;
};

// *運(yùn)算符重載
Ref operator*()
{
	//迭代器中的那個指針不能是nullptr
	assert(_pnode);
	//返回節(jié)點(diǎn)中的數(shù)據(jù)域中的數(shù)據(jù)
	return _pnode->_data;
}

//前置++運(yùn)算符
self& operator++()
{
	_pnode = _pnode->_next;
	return (*this);
}

//后置++運(yùn)算符
self operator++(int)
{
	//先保存++之前的結(jié)果
	self tmp(*this);
	_pnode = _pnode->_next;
	//返回++之前的值
	return tmp;
}

//前置--運(yùn)算符
self& operator--()
{
	_pnode = _pnode->_prev;
	return (*this);
}

//后置--運(yùn)算符
self operator--(int)
{
	self tmp(*this);
	_pnode = _pnode->_prev;
	return tmp;
}

struct Date
{
	int _year;
	int _month;
	int _day;
}
//it是迭代器，指向了存儲了Date類型的節(jié)點(diǎn)
//假設(shè):在沒有->操作符時,我們想要修改_year的值,
(*it)._year = 2023;
//如果有了-> 操作符，我們就能這樣操作，更加符合我們的使用習(xí)慣
it->_year = 2023;

// ->運(yùn)算符重載
Ptr operator->()
{
	return &(_pnode->_data);
}

it->->_year = 2023; 
//it-> 等價于 (&(_pnode->date)) 

//(&(_pnode->date))->year = 2023;

// !=運(yùn)算符重載
bool operator!=(const self& s)
{
	return _pnode != s._pnode;
}

// ==運(yùn)算符重載
bool operator==(const self& s)
{
	return _pnode == s._pnode;
}

//正向迭代器
iterator begin()
{
	//_head指向的是哨兵位的頭節(jié)點(diǎn)，_head的下一個才是第一個節(jié)點(diǎn)！
	//這里使用的是一個指針構(gòu)造的匿名對象做返回值，編譯器會對此進(jìn)行優(yōu)化，能夠增加效率
	return iterator(_head->_next);
}

iterator end()
{
	//由于是雙向循環(huán)鏈表，所以最后一個節(jié)點(diǎn)的下一個位置就是哨兵位節(jié)點(diǎn)
	return iterator(_head);
}

//const迭代器的思路與普通迭代器類似
const_iterator begin() const
{
	return const_iterator(_head->_next);
}
const_iterator end() const 
{
	return const_iterator(_head);
}

void insert(iterator pos, const T& x)
{
	//先申請一個節(jié)點(diǎn)，存儲我們要插入的數(shù)據(jù)
	node* new_node = new node(x);
	node* prev = pos._pnode->_prev;
	//鏈接過程
	prev->_next = new_node;
	new_node->_prev = prev;
	new_node->_next = pos._pnode;
	pos._pnode->_prev = new_node;
}

void push_front(const T& x)
{
	//在begin()位置進(jìn)行插入就是頭插！
	insert(begin(), x);
}

//尾插函數(shù)
void push_back(const T& x)
{
	//在end()位置進(jìn)行插入，就是尾插
	insert(end(), x);
}

iterator erase(iterator pos)
{
	assert(pos != end());
	//鏈接過程
	node* prev = pos._pnode->_prev;
	node* next = pos._pnode->_next;
	prev->_next = next;
	next->_prev = prev;
	
	//刪除節(jié)點(diǎn)
	delete pos._pnode;
	//返回指向原節(jié)點(diǎn)的下一個節(jié)點(diǎn)的迭代器，外部接收后可以防止迭代器失效！
	return iterator(next);
}

void pop_front()
{
	erase(begin());
}

void pop_back()
{
	//由于end()是最后一個節(jié)點(diǎn)的下一個位置，所以這里要對end()進(jìn)行一次自減運(yùn)算
	erase(--end());
}

void clear()
{
	list<T>::iterator it = begin();
	while (it != end())
	{
		//erase函數(shù)刪除相應(yīng)節(jié)點(diǎn)以后會返回下一個節(jié)點(diǎn)的迭代器
		it = erase(it);
	}
}

//swap函數(shù)
void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
}

//迭代器區(qū)間構(gòu)造,傳入的迭代器應(yīng)該至少是一個二元迭代器，能支持向前和向后遍歷，這時鏈表的最低要求。
template<class Biditerator>
list(Biditerator first, Biditerator last)
{
	//調(diào)用初始化函數(shù)
	empty_init();
	//遍歷迭代器同時將數(shù)據(jù)形成一個新節(jié)點(diǎn)插入鏈表中
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

//拷貝構(gòu)造
list(const list<T>& lt)
{
	//初始化
	empty_init();
	//用迭代器區(qū)間構(gòu)造創(chuàng)建一個新的list對象
	list<T> tmp(lt.begin(), lt.end());
	//將this指針指向的對象與這個新的tmp對象進(jìn)行交換，拷貝就變相完成了
	swap(tmp);
}

//賦值運(yùn)算符重載
//注意這里的傳參方式是傳值傳參
list<T>& operator=(list<T> lt)
{
	//將this指針指向的對象與這個lt對象進(jìn)行交換，賦值就變相完成了
	swap(lt);
	return (*this);
}

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