void TestList1()
{
	list<int> l1;                         // 構(gòu)造空的l1
	list<int> l2(4, 100);                 // l2中放4個(gè)值為100的元素
	list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左閉右開(kāi)的區(qū)間構(gòu)造l3
	list<int> l4(l3);                    // 用l3拷貝構(gòu)造l4

	// 以數(shù)組為迭代器區(qū)間構(gòu)造l5
	int array[] = { 16,2,77,29 };
	list<int> l5(array, array + sizeof(array) / sizeof(int));

	// 列表格式初始化C++11
	list<int> l6{ 1,2,3,4,5 };
	list<int> l7 = { 1,2,4,5,6,7,8 };
	// 用迭代器方式打印l5中的元素
	list<int>::iterator it = l5.begin();
	while (it != l5.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// C++11范圍for的方式遍歷
	for (auto& e : l5)
		cout << e << " ";

	cout << endl;
}

void PrintList(const list<int>& l)
{
	// 注意這里調(diào)用的是list的 begin() const，返回list的const_iterator對(duì)象
	for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
	{
		cout << *it << " ";
		// *it = 10; 編譯不通過(guò)
	}

	cout << endl;
}

void TestList2()
{
	int array[] = { 1, 2, 3, 4, 5, 6, };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	// 使用正向迭代器正向list中的元素
	// list<int>::iterator it = l.begin();   // C++98中語(yǔ)法
	auto it = l.begin();                     // C++11之后推薦寫(xiě)法
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 使用反向迭代器逆向打印list中的元素
	// list<int>::reverse_iterator rit = l.rbegin();
	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	//迭代器不支持 因?yàn)?list 迭代器是雙向 不支持 + -
	/*l.insert(l.begin() + 3);*/

	//想要實(shí)現(xiàn)第三個(gè)位置后插入一個(gè)數(shù)可以通過(guò)下面代碼
	it = l.begin();
	int k = 3;
	while (k--)
	{
		it++;//支持++
	}
	l.insert(it, 40);

	PrintList(l);

}

struct A {
public:
	A(int a1 = 1, int a2 = 1)
		:_a1(a1)
		, _a2(a2)
	{
		cout << "A(int a1=1,int a2=1)" << endl;
	}

	A(const A& aa)
		:_a1(aa._a1)
		, _a2(aa._a2)
	{
		cout << "A(const A& aa)" << endl;
	}
private:
	int _a1;
	int _a2;
};

void TestList3()
{
	int array[] = { 1, 2, 3 };
	list<int> L(array, array + sizeof(array) / sizeof(array[0]));

	// 在list的尾部插入4，頭部插入0
	L.push_back(4);
	L.push_front(0);
	PrintList(L);

	// 刪除list尾部節(jié)點(diǎn)和頭部節(jié)點(diǎn)
	L.pop_back();
	L.pop_front();
	PrintList(L);

	list<A>lt;
	A aa1(1, 1);
	lt.push_back(aa1);//有名對(duì)象尾插
	lt.push_back(A(2, 2));//匿名對(duì)象尾插
	//lt.push_back(3, 3);//不支持 push back只支持一個(gè)參數(shù)

	lt.emplace_back(aa1);
	lt.emplace_back(A(2, 2));
	cout << endl;
	// 前面的插入都是 構(gòu)造+拷貝構(gòu)造

	// (3,3)的插入 并沒(méi)有拷貝構(gòu)造 性能上來(lái)說(shuō)優(yōu)于 push back
	lt.emplace_back(3, 3);//支持 本質(zhì)支持直接傳構(gòu)造A對(duì)象的參數(shù)
}

// insert /erase 
void TestList4()
{
	int array1[] = { 1, 2, 3 };
	list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

	// 獲取鏈表中第二個(gè)節(jié)點(diǎn)
	auto pos = ++L.begin(); //pos 可以理解為下標(biāo)
	cout << *pos << endl;

	// 在pos前插入值為4的元素
	L.insert(pos, 4);
	PrintList(L);

	// 在pos前插入6個(gè)值為5的元素
	L.insert(pos, 6, 5);
	PrintList(L);

	// 在pos前插入[v.begin(), v.end)區(qū)間中的元素
	vector<int> v{ 7, 8, 9 };
	L.insert(pos, v.begin(), v.end());
	PrintList(L);

	// 刪除pos位置上的元素
	L.erase(pos);
	PrintList(L);

	// 刪除list中[begin, end)區(qū)間中的元素，即刪除list中的所有元素
	L.erase(L.begin(), L.end());
	PrintList(L);
}

// resize/swap/clear
void TestList5()
{
	// 用數(shù)組來(lái)構(gòu)造list
	int array1[] = { 1, 2, 3 };
	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	PrintList(l1);

	// 交換l1和l2中的元素
	list<int> l2;
	l1.swap(l2);
	PrintList(l1);
	PrintList(l2);

	// 將l2中的元素清空
	l2.clear();
	cout << l2.size() << endl;
}

void test_list4()//容器的 逆置與排序
{
	list<int>lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	print_list(lt);
	lt.reverse();
	print_list(lt);
	reverse(lt.begin(), lt.end());
	print_list(lt);
	reverse(++lt.begin(), --lt.end());
	print_list(lt);
	//算法庫(kù)里的排序和容器的排序都是默認(rèn)升序
	lt.sort();
	print_list(lt);
	//想要降序 則需要 仿函數(shù)
	//less<int>ls;//升序
	//greater<int>gt;//降序
	//還可以結(jié)合匿名對(duì)象使用
	lt.sort(greater<int>());
	print_list(lt);
}

void test_list5() // merge有序list合并  unique 有序list去除重復(fù)數(shù)據(jù) 
{
	std::list<double> first, second;

	first.push_back(3.1);
	first.push_back(2.2);
	first.push_back(2.9);

	second.push_back(3.7);
	second.push_back(7.1);
	second.push_back(1.4);

	first.sort();
	second.sort();

	//將 second和first合并 second置為空 前提兩list有序
	first.merge(second);
	print_list(first); 
	print_list(second);

	list<int>lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(1);
	lt.push_back(1);
	print_list(lt);
	lt.sort();
	//有序的數(shù)據(jù)去掉重復(fù)的數(shù)據(jù)
	lt.unique();
	print_list(lt);
}

void test_list6()
{
	//把一個(gè)鏈表結(jié)點(diǎn)轉(zhuǎn)移給另一個(gè)鏈表
	std::list<int> mylist1, mylist2;
	std::list<int>::iterator it;

	// set some initial values:
	for (int i = 1; i <= 4; ++i)
		mylist1.push_back(i);      // mylist1: 1 2 3 4

	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30

	it = mylist1.begin();
	++it;                         // points to 2
	
	mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                // mylist2 (empty)
                               // "it" still points to 2 (the 5th element)
	print_list(mylist1);
	print_list(mylist2);// splice 剪切功能


	//splice 還可以調(diào)整當(dāng)前l(fā)ist的順序

	list<int>lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	print_list(lt);
	int x = 0;
	cin >> x;
	it = find(lt.begin(), lt.end(), x);
	if (it != lt.end())
	{
		 // 調(diào)整當(dāng)前鏈表的元素順序  將 it指向元素 調(diào)整到 begin
		lt.splice(lt.begin(), lt, it);
		
		// //迭代器區(qū)間
		//lt.splice(lt.begin(), lt, it,lt.end());
	}
	print_list(lt);
}

void TestListIterator1()
{

	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函數(shù)執(zhí)行后，it所指向的節(jié)點(diǎn)已被刪除，因此it無(wú)效，在下一次使用it時(shí)，必須先給其賦值
			l.erase(it);
		++it;
	}
}

// 改正

void TestListIterator()
{

	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++);   //it = l.erase(it); erase 返回下一個(gè)位置的迭代器

	}
}

// 結(jié)點(diǎn)結(jié)構(gòu)體
template<class T>
struct list_node //默認(rèn)公有 struct
{
	T _data;
	list_node<T>* _prev;
	list_node<T>* _next;

	list_node(const T& data=T())
		:_data(data)
		,_prev(nullptr)
		,_next(nullptr)
	{}
	~list_node()
	{
		_next = nullptr;
		_prev = nullptr;
	}
};

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;

	void empty_init()
	{
		//_head = new Node;//這里寫(xiě)了 Node 帶參數(shù)構(gòu)造 所以報(bào)錯(cuò) 需要匿名參數(shù)
		_head = new Node(T());
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
	list()
	{
		empty_init();
	}

	list(initializer_list<T>il)
	{
		empty_init();

		for (auto& e : il)
		{
			push_back(e);
		}
		_size = il.size();
	}

private:
	Node* _head;
	size_t _size;
};

	template<class T>
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator<T> Self;

		Node* _node;//指針成員變量
		
		list_iterator(Node* node)
			:_node(node)
		{}
		
		T& operator*()
		{
			return _node->_data;
		}

		T* operator->()
		{
			return &(_node->_data);
		}

		//操作符重載 前置++ 與 后置++的區(qū)別是參數(shù)是否帶（int）
		// ++it 
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		// it++
		Self& operator++(int x)
		{
			Self tmp(*this);//淺拷貝
			_node = _node->_next;
			return tmp;
		}
		
		//--it
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		//it--
		Self& operator--(int x)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

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

list<AA>lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
auto ita = lta.begin();
while (ita != lta.end())
{
	//cout << *ita << ' '; //編譯不通過(guò) 結(jié)構(gòu)體并沒(méi)有重載流插入
	//cout << (*ita)._a1	 << ' '; 
	//cout << ita->_a1 << ' '; //為了可讀性省去了一個(gè)箭頭
	cout << ita.operator->()->_a1 << ' ';
	++ita;
}

//reference 引用  pointer 指針
template<class T , class Ref ,class Ptr>

Ref operator*() //現(xiàn)在返回const類型還是普通類型是通過(guò)編譯器推導(dǎo)的
{
	return _node->_data;
}

Ptr operator->()
{
	return &(_node->_data);
}

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

iterator begin()//第一個(gè)結(jié)點(diǎn)指針
{
	//iterator it(_head->_next);//構(gòu)造函數(shù)
	//return it; 優(yōu)化一下
	return _head->_next; //走的隱式類型轉(zhuǎn)換
}

// const 修飾begin 可以兼容拷貝構(gòu)造 否則出現(xiàn)權(quán)限放大 這是不允許的
const_iterator begin()const //前面的const 迭代器是指向元素或引用不可以改變內(nèi)容 后面的const是修飾this 對(duì)象不可以改變
{							//  隱含的this指針由 list * const this 變?yōu)?const list* const this 前者是指針不可以更改指向
	return _head->_next;
}

const_iterator cbegin()const
{
	return _head->_next;
}

iterator end()
{
	return _head; // 頭節(jié)點(diǎn) 左閉右開(kāi)
}

const_iterator end()const
{
	return _head;
}

const_iterator cend()const
{
	return _head;
}

void push_back(const T& x)
{
	//Node* newnode = new Node(x); //沒(méi)有寫(xiě)Node 構(gòu)造報(bào)錯(cuò)
	//_head->_prev->_next = newnode;
	//newnode->_next = _head;
	//newnode->_prev = _head->_prev;
	//_head->_prev = newnode;

	//++_size;
	insert(end(), x);//復(fù)用 insert
}

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

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

	return newnode;
}

void pop_back()
{
	erase(--end());
}
void pop_front()
{
	erase(begin());
}
iterator erase(iterator pos) //防止迭代器失效問(wèn)題
{
	assert(pos != end());//不可以刪除頭結(jié)點(diǎn)
	Node* prev = pos._node->_prev;;
	Node* next = pos._node->_next;

	prev->_next = next;
	next->_prev = prev;

	delete pos._node;
	--_size;
	return next;
}

//lt1(lt)
list( const list<T>& lt)
{
	empty_init();
	for (auto& e : lt)
	{
		push_back(e);
	}
}

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

}

//lt1=lt3
list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}

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

}

void clear()
{
	auto it = begin();
	while (it!=end())
	{
		//erase(it++);//可以這樣寫(xiě) 可以理解為 先進(jìn)行了 it++后再 執(zhí)行 erase 代碼塊里的內(nèi)容
		 it=erase(it);
	}
	_size = 0;
}