//節(jié)點
template<class T>
struct List_node
{
	T _data;
	List_node<T>* _prev;
	List_node<T>* _next;

	List_node(const T& x = T())
		:_data(x)
		,_prev(nullptr)
		,_next(nullptr)
	{}
};

//迭代器封裝
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef List_node<T> Node;//節(jié)點類名重命名
	//由于迭代器實現(xiàn)中,如++、--等重載函數(shù)返回值類型為__list_iterator，名字過長,這里我們重命名self意味自身
	typedef __list_iterator<T,Ref, Ptr> self;
	Node* _node;//成員變量

	__list_iterator(Node* node)//構(gòu)造出一個節(jié)點
		:_node(node)
	{}

	//前置++
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//前置--
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	
	//后置++
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	//后置--
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	
	//解引用操作符重載
	Ref operator*()
	{
		return _node->_data;
	}
	
	//用于訪問迭代器指向?qū)ο笾写鎯Φ氖亲远x類型
	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}

	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};

//list模擬實現(xiàn)
template<class T>
class List
{
	typedef List_node<T> Node;
public:
	//迭代器重命名，提供統(tǒng)一的接口，屏蔽底層實現(xiàn)細節(jié)和差異
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
private:
	Node* _head;//頭節(jié)點
	int _size;
};

const_iterator begin()const
{
	//return const_iterator(_head->_next);或
	return _head->_next;//單參數(shù)類型支持隱式類型轉(zhuǎn)換
}

const_iterator end()const
{
	return _head;
}

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

iterator end()
{
	return _head;
}

//初始化
void empty_Init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;

	_size = 0;
}

//無參構(gòu)造
List()
{
	empty_Init();
}

//析構(gòu)函數(shù)
~List()
{
	clear();
	delete _head;
	_head = nullptr;
}

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

//拷貝構(gòu)造
List(const List<T>& It)
{
	empty_Init();
	for (auto e : It)
	{
		push_back(e);
	}
}

void swap(const List<T>& It)
{
	std::swap(_head, It._head);
}

//賦值重載
List<T>& operator=(const List<T> It)
{
	swap(It);
	return *this;
}

iterator insert(iterator pos, const T& x)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(x);

	prev->_next = newnode;
	newnode->_prev = prev;

	newnode->_next = cur;
	cur->_prev = newnode;
	_size++;
	return newnode;
}

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	delete cur;
	prev->_next = next;
	next->_prev = prev;

	_size--;
	return next;
}

void push_back(const T& x)
{
	insert(end(), x);
}

void push_front(const T& x)
{
	insert(begin(), x);
}

void pop_back()
{
	erase(--end());
}

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

struct AA
{
	AA(int a1 = 0, int a2 = 0)
		:_a1(a1)
		,_a2(a2)
	{}

	int _a1;
	int _a2;
};

void test_list3()
{
	list<AA> lt;
	lt.push_back(AA(1, 1));
	lt.push_back(AA(2, 2));
	lt.push_back(AA(3, 3));

	list<AA>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout<<*it<<" ";
		++it;
	}
	cout << endl;
}

struct AA
{
	AA(int a1 = 0, int a2 = 0)
		:_a1(a1)
		,_a2(a2)
	{}

	int _a1;
	int _a2;
};

void test_list3()
{
	list<AA> lt;
	lt.push_back(AA(1, 1));
	lt.push_back(AA(2, 2));
	lt.push_back(AA(3, 3));

	list<AA>::iterator it = lt.begin();
	while (it != lt.end())
	{
		//cout << (*it)._a1<<" "<<(*it)._a2 << endl;
		cout << it->_a1 << " " << it->_a2 << endl;
		//上面編譯器訪問成員變量的真正行為如下：
		//cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl;
		++it;
	}
	cout << endl;
}

//大多數(shù)情況模板是class還是typename是一樣的，但當(dāng)有未實例化模板時，必須使用typename
//template<typename T>
void print_list(const list<T>& lt)
{
	// list<T>未實例化的類模板，編譯器不能去他里面去找
	// 編譯器就無法list<T>::const_iterator是內(nèi)嵌類型，還是靜態(tài)成員變量
	// 前面加一個typename就是告訴編譯器，這里是一個類型，等list<T>實例化
	// 再去類里面去取
	typename list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;  
}

// 模板(泛型編程)本質(zhì)，本來應(yīng)該由我們干的活交給編譯器
template<typename Container>
void print_container(const Container& con)
{
	typename Container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}