#include"iostream"
#include"list"
#include"algorithm"
using namespace std;
//链表：
//	list 表示双向链表
//	forward_list  向前链表，操作在表头
/*
vector:
随机访问快，既下标运算
尾部添加，在不申请空间的情况下，非常快
不支持快速插入与删除，比较慢

list:
随机访问慢，也支持下标
支持快速插入与删除
*/

struct Node{
	int a;
	char c;
	Node(int d=0,char e='0'){
		a = d;
		c = e;
	}
	bool operator==(const Node &f){
		if(this->a == f.a && this->c ==f.c){
			return true;
		}
		return false;
	}
	bool operator< (const Node &f){
		if(f.a<this->a)
			return true;
		return false;
	}
};




void fun(Node &d){

	cout<<d.a<<"+"<<d.c<<"\n";


}

void ListDefine(){
	list<Node> lst1(5);//初始化多个元素，初始值为0
	for_each(lst1.begin(),lst1.end(),fun);
	//Node node={12,'a'};

	Node node(12,'a');
	cout<<".................."<<endl;
	list<Node> lst2(6,node);//多个指定的值，实现初始化
	for_each(lst2.begin(),lst2.end(),fun);

	cout<<".................."<<endl;
	list<Node> lst3(lst2);//采用另一个，实现自己的初始化
	for_each(lst3.begin(),lst3.end(),fun);


	list<Node>::iterator ite1 = lst3.begin();
	//因为链表不是一块连续的地址，所以没有ite1+=1;表示指针的偏移是没有意义的
	//但是他可以自己加加，既：ite1++；
	//没有加法运算，只能自加加；
	ite1++;
	ite1++;

	cout<<".................."<<endl;
	list<Node> lst4(ite1,lst3.end());//采用另一个中的一部分，实现对其初始化
	for_each(lst4.begin(),lst4.end(),fun);

}
void ListSize(){
	//此时的是list没有capacity（容量）概念，应为他不需要申请空间，需要添加节点，直接在尾部添加就可以。
	//Node node={12,'o'};
	Node node(12,'o');
	list<Node> lst1(6,node);
	for_each(lst1.begin(),lst1.end(),fun);
	cout<<lst1.size()<<endl;

	cout<<".................."<<endl;
	lst1.resize(3);
	for_each(lst1.begin(),lst1.end(),fun);
	cout<<lst1.size()<<endl;

}
void ListCountAdd(){
	//Node node = {12,'o'};
	Node node(12,'o');
	list<Node> lst1(6,node);
	list<Node>::iterator ite1 = lst1.begin();
	for(ite1;ite1!=lst1.end();ite1++){

		cout<<ite1->a<<"+"<<ite1->c<<endl;

	}
	cout<<".................."<<endl;
	cout<<lst1.back().a<<"+"<<lst1.back().c<<endl;
	cout<<lst1.front().a<<"+"<<lst1.front().c<<endl;

	Node node1(17,'a');

	lst1.push_front(node1);
	cout<<".................."<<endl;
	for_each(lst1.begin(),lst1.end(),fun);

	cout<<".................."<<endl;
	Node node2(20,'a');


	Node node3(80,'a');
	lst1.insert(lst1.begin(),node2);
	lst1.insert(lst1.begin(),3,node3);
	for_each(lst1.begin(),lst1.end(),fun);

}

void ListDeleteNode(){
	list<Node> lst1;
	lst1.push_front(Node(12,'a'));
	lst1.push_front(Node(13,'b'));
	lst1.push_front(Node(14,'c'));
	lst1.push_front(Node(14,'c'));
	lst1.push_front(Node(16,'e'));
	lst1.push_front(Node(17,'f'));
	for_each(lst1.begin(),lst1.end(),fun);


	//cout<<"........................."<<endl;
	//lst1.pop_back();//尾删除
	//for_each(lst1.begin(),lst1.end(),fun);
	//	cout<<"........................."<<endl;
	//lst1.pop_front();//头删除
	//for_each(lst1.begin(),lst1.end(),fun);


	//cout<<"........................."<<endl;
	//list<Node>::iterator ite = lst1.begin();
	//ite++;
	//ite++;
	//lst1.erase(ite);
	//for_each(lst1.begin(),lst1.end(),fun);

	//cout<<"........................."<<endl;
	//lst1.erase((--lst1.end()));
	//for_each(lst1.begin(),lst1.end(),fun);


	cout<<"........................."<<endl;
	lst1.remove(Node(17,'f'));
	for_each(lst1.begin(),lst1.end(),fun);

	cout<<"........................."<<endl;
	lst1.unique();
	for_each(lst1.begin(),lst1.end(),fun);

	//赋值，采用=,或者assign
	cout<<"........................."<<endl;
	list<Node> lst2 = lst1;
	for_each(lst2.begin(),lst2.end(),fun);


	cout<<"........................."<<endl;
	lst2.assign(1,Node(17,'f'));
	for_each(lst2.begin(),lst2.end(),fun);

	cout<<"........................."<<endl;
	list<Node> lst3;
	lst3.assign(5,Node(17,'f'));
	for_each(lst3.begin(),lst3.end(),fun);

}
void ListDo(){

	list<Node> lst1;
	lst1.push_front(Node(12,'a'));
	lst1.push_front(Node(16,'e'));
	lst1.push_front(Node(17,'f'));
	lst1.push_front(Node(14,'c'));
	lst1.push_front(Node(13,'b'));
	lst1.push_front(Node(14,'c'));



	list<Node> lst2;
	lst2.push_front(Node(50,'c'));
	lst2.push_front(Node(80,'b'));
	lst2.push_front(Node(70,'c'));



	cout<<"........................."<<endl;
	for_each(lst1.begin(),lst1.end(),fun);
	lst1.swap(lst2);
	for_each(lst1.begin(),lst1.end(),fun);
	cout<<"........................."<<endl;

	//lst2
	for_each(lst2.begin(),lst2.end(),fun);
	//顺序颠倒
	lst2.reverse();
	cout<<"........................."<<endl;
	for_each(lst2.begin(),lst2.end(),fun);

	cout<<"........................."<<endl;
	lst2.sort();
	for_each(lst2.begin(),lst2.end(),fun);
	// merge 是合并有序的两个链表
	cout<<"........................."<<endl;
	lst2.merge(lst1);
	for_each(lst2.begin(),lst2.end(),fun);


	cout<<"........................."<<endl;
	list<Node>::iterator ite = find(lst2.begin(),lst2.end(),Node(14,'c'));
	cout<<ite->a<<"+++"<<ite->c<<endl;
}

int main(){
	//ListDefine();
	ListSize();
	//ListCountAdd();
	//ListDeleteNode();
	ListDo();
	system("pause");
	return 0;
}