C++学习日记 容器deque、stack、list、set

一、deque容器。
1、功能。
deque容器底层实现其实就是一个双端数组,可以对头部进行插入与删除的操作。

2、deque容器迭代器?
支持随机访问迭代器。

#include <iostream>
using namespace std;
#include <deque>
#include <algorithm>

void printDeque(deque <int> &d)
{
	for(deque<int>::iterator it = d.begin(); it!=d.end();it++)
	{
		cout << *it << " ";	
	}
	cout << endl;
} 

int main()
{
	deque <int>d1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_back(30);
	d1.push_back(40);
	printDeque(d1);

	deque <int>d2(d1.begin(),d1.end());
	printDeque(d2);

	deque <int>d3(10,100);
	printDeque(d3);

	deque <int>d4(d3);
	printDeque(d4);

	deque <int>d5;
	d5 = d4;
	printDeque(d5);

	deque <int>d6;
	d6.assign(d5.begin(),d5.end());
	printDeque(d6);

	deque <int>d7;
	d7.assign(10,9);
	printDeque(d7);

	if(d7.empty())
	{
		cout << "d7真的为空" << endl;
	}
	else{
		cout << "d7不为空" << endl;
		cout << "d7的大小:" << d7.size() << endl;
		//cout << "d7的容量:" << d7.capacity() << endl;
	}

	d7.push_back(100);
	d7.push_front(3);
	printDeque(d7);

	d7.pop_back();
	d7.pop_front();
	printDeque(d7);

	deque<int>::iterator it = d7.begin();
	d7.insert(it,1000);
	printDeque(d7);

	//d7.resize(15);
	//printDeque(d7);

	//d6.resize(15,6);
	//printDeque(d6);

	//d5.resize(5);
	//printDeque(d5);

	//d7.erase(d7.begin(),d7.end());
	//d7.clear();
	//printDeque(d7);

	cout << d7.at(1) << endl;
	cout << d7[1] << endl;

	cout << d7.front() << endl;
	cout << d7.back() << endl;

	cout << "---------------------------" << endl;
	deque <int>d8;
	d8.push_back(10);
	d8.push_back(20);
	d8.push_back(30);

	d8.push_front(100);
	d8.push_front(200);
	d8.push_front(300);

	cout << "=====排序前=====" << endl;
	printDeque(d8);

	//sort默认的排序方式是从小到大  升序
	//对于支持随机访问的迭代器容器,都可以利用sort算法来进行排序。
	//vector容器也是可以支持sort算法的。
	sort(d8.begin(),d8.end());
	
	cout << "=====排序后=====" << endl;
	printDeque(d8);

	return 0;
}

练习:考点:vector容器、deque容器、string容器、排序算法sort,、随机值rand()
案例描述:
有5名选手: 选手A,选手B,选手C,选手D,选手E。10个评委分别对每名选手打分,去除最高分,去除最低分,取平均分。

实现步骤。
1)创建五名选手,并存放在vector中。
2)遍历vector容器,取出来每一个选手,执行for循环,可以将10个评委的打分存放在一个deque的容器中。(提示:使用rand()随机分数即可,记得包含algorithm头文件)
3)利用sort算法对deque容器中分数排序,去除最高分和最低分。
4)deque容器遍历一遍,累加总分。
5)获取平均分。
6)将每一个选手的名字和平均分输出即可。 

#include <iostream>
using namespace std;
#include <vector>
#include <deque>
#include <algorithm>

class Person{
public:
	Person(string name,int score)
	{
		this->m_Name = name;
		this->m_Score = score;
	}

	string m_Name;
	int m_Score;
};

void createPerson(vector <Person> &v)
{
	string nameSeed = "ABCDE";

	int i;
	int score;
	string name;

	for(i=0;i<5;i++)
	{
		name = "Person";
		name += nameSeed[i];  //选手A

		score = 0;  //设置平均分为0

		//创建一个选手。
		Person p(name,score);

		v.push_back(p);
	}
}

void setScore(vector <Person> &v)
{
	int i;
	int score;
	int sum;
	int avg;
	for(vector<Person>::iterator it = v.begin() ; it!=v.end() ;it++)
	{
		deque <int>d;
		for(i=0;i<10;i++)
		{
			score = rand()%41+60;
			d.push_back(score);
		}

		
		sort(d.begin(),d.end());

		d.pop_back();
		d.pop_front();

		sum = 0;
		for(deque<int>::iterator dit = d.begin();dit!=d.end();dit++)
		{
			sum += *dit;
		}

		avg = sum / d.size();

		it->m_Score = avg;
	}
}

int main()
{
	srand(time(NULL));

	vector <Person>v;
	createPerson(v);

	setScore(v);

	for(vector<Person>::iterator it = v.begin() ; it!=v.end() ;it++)
	{
		cout << "name = " << it->m_Name << "  score = " << it->m_Score << endl;
	}

	return 0;
}

二、stack容器。
stack是一种先进后出的数据结构,它只有一个出口,叫栈顶。
栈只有顶端才会被外界使用,因此栈不允许有遍历行为。

#include <iostream>
using namespace std;
#include <stack>

int main()
{
	stack <int>s;
	s.push(10);
	s.push(20);
	s.push(30);

	cout << "s栈的大小:" << s.size() << endl;

	stack <int>s2(s);
	cout << "s2栈的大小:" << s.size() << endl;

	stack <int>s3;
	s3 = s2;
	cout << "s3栈的大小:" << s.size() << endl;

	//只要栈不为空,那么就查看栈顶元素,执行出栈操作。
	while( !s.empty())
	{
		//查看栈顶元素
		cout << "栈顶元素:" << s.top() << endl;

		//出栈
		s.pop();
	}

	return 0;
}

三、queue容器。
概念:queue容器是一种先进先出的结构,它有两个口。

队列容器允许从一端新增元素,从另一端移除元素。
队列中队头与队尾才可以被外界使用,因此队列不允许有遍历行为。
队列中进数据  -> 入队。
队列中出数据  -> 出队。

#include <iostream>
using namespace std;
#include <queue>

class Person{
public:
	Person(string name,int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

int main()
{
	queue <Person>q;

	Person p1("唐僧",200);
	Person p2("孙悟空",100);
	Person p3("猪八戒",50);
	Person p4("沙僧",30);

	q.push(p1);
	q.push(p2);
	q.push(p3);
	q.push(p4);

	cout << "队列的大小:" << q.size() << endl;

	//只要队列不为空,那么就查看队尾与队头的元素。
	while( !q.empty() )
	{
		cout << "------------" << endl;
		cout << "队头元素 - 姓名:" << q.front().m_Name << " 年龄:" << q.front().m_Age << endl;
		cout << "队尾元素 - 姓名:" << q.back().m_Name << " 年龄:" << q.back().m_Age << endl;
		q.pop();
	}

	return 0;
}

四、list容器。
功能: 链式储存数据。
迭代器: 由于链表不是一段连续空间,所以链表的迭代器只能支持前移和后移,属于双向迭代器。1、基本函数。

#include <iostream>
using namespace std;
#include <list>

void printList(list <int> &L)
{
	for(list<int>::iterator it = L.begin();it!=L.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	list <int>L1;

	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);

	printList(L1);

	list <int>L2(L1.begin(),L1.end());
	printList(L2);

	list <int>L3(10,100);
	printList(L3);

	list <int>L4(L3);
	printList(L4);

	list <int>L5;
	L5.assign(L4.begin(),L4.end());
	printList(L5);

	list <int>L6;
	L6 = L5;
	printList(L6);

	cout << "=====互换前=====" << endl;
	printList(L2);
	printList(L6);
	cout << "L6的大小:" << L6.size() << endl;

	L6.swap(L2);

	cout << "=====互换后=====" << endl;
	printList(L2);
	printList(L6);
	cout << "L6的大小:" << L6.size() << endl;

	if(L6.empty())
	{
		cout << "L6为空" << endl;
	}
	else{
		cout << "L6不为空" << endl;
	}

	L6.resize(10,7);
	printList(L6);

	L6.push_back(10);
	printList(L6);

	L6.pop_back();
	printList(L6);

	L6.push_front(20);
	printList(L6);

	L6.pop_front();
	printList(L6);

	list<int>::iterator it = L6.begin();
	it++;
	cout << *it << endl;  //20

	L6.insert(it,1000);
	printList(L6);

	cout << *it << endl;

	L6.erase(it);
	printList(L6);

	//L6.clear();
	//printList(L6);

	L6.remove(7);
	printList(L6);

	cout << L6.front() << endl;
	cout << L6.back() << endl;

	return 0;
}

2、反转与排序。

#include <iostream>
using namespace std;
#include <list>
#include <algorithm>

//反转与排序。
void printList(list <int> &L)
{
	for(list<int>::iterator it = L.begin();it!=L.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

bool mycompare(int v1,int v2)
{
	//降序:让第一个数字大于第二个数字就可以了。
	return v1 > v2;
}

int main()
{
	list <int>L1;
	L1.push_back(20);
	L1.push_back(10);
	L1.push_back(30);
	L1.push_back(50);
	L1.push_back(40);

	cout << "反转前:" << endl;
	printList(L1);

	L1.reverse();

	cout << "反转后:" << endl;
	printList(L1);

	cout << "======排序前=====" << endl;
	printList(L1);

	//所有不支持随机访问迭代器的容器,不可以使用标准算法sort()
	//sort(L1.begin(),L1.end());
	
	//不支持随机访问迭代器的容器,内部都会提供一些对应的算法给它。
	//L1.sort();  //默认是升序的。
	
	L1.sort(mycompare);  //实现降序

	cout << "======排序后=====" << endl;
	printList(L1);

	return 0;
}

五、set容器的基本概念。
简介:所有元素都会在插入时自动被排序。
本质:set/multiset容器底层结构就是二叉树。

set/multiset区别?
set不允许容器中有重复的元素。
multiset允许容器中有重复的元素。

无论你是使用set,还是multiset,头文件都是#include <set>

#include <iostream>
using namespace std;
#include <set>

void printSet(set <int>&s)
{
	for(set<int>::iterator it = s.begin();it!=s.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	set <int>s;

	//set容器没有push_back,只有insert。
	s.insert(10);
	s.insert(10);
	s.insert(40);
	s.insert(30);
	s.insert(50);
	s.insert(20);
	s.insert(90);
	s.insert(80);

	printSet(s);  //默认已经按升序排序了

	set <int>s2(s);
	printSet(s2);

	set <int>s3;
	s3 = s2;
	printSet(s3);

	if(s3.empty())
	{
		cout << "s3为空" << endl;
	}
	else{
		cout << "s3不为空" << endl;
		cout << "s3的大小:" << s3.size() << endl;
	}

	set <int>s4;
	s4.insert(100);
	s4.insert(300);
	s4.insert(400);
	s4.insert(200);

	cout << "交换前" << endl;
	printSet(s3);
	printSet(s4);

	s3.swap(s4);

	cout << "交换后" << endl;
	printSet(s3);
	printSet(s4);

	//s3.clear();
	//printSet(s3);
	
	s3.erase(s3.begin());
	printSet(s3);


	set<int>::iterator pos = s3.find(500);
	if(pos != s3.end())
	{
		cout << "找到该元素:" << *pos << endl;
	}
	else{
		cout << "未找到该元素" << endl;
	}

	cout << s3.count(500) << endl;

	return 0;
}

六、pair对组的创建。
功能描述:
成对出现的数据,利用对组可以返回两个数据。

对组怎么创建?
方法有两种:
pair<type,type> p(value1,value2);
pair<type,type> p = make_pair(value1,value2);

#include <iostream>
using namespace std;

//对组的创建
/*
pair<type,type> p(value1,value2);
pair<type,type> p = make_pair(value1,value2);
*/

int main()
{	
	//第一种方式:
	pair<string,int> p("Tom",18);
	cout << "姓名:" << p.first << "年龄:" << p.second << endl;

	//第二种方式:
	pair<string,int> p2 = make_pair("ggy",18);
	cout << "姓名:" << p2.first << " 年龄:" << p2.second << endl;

	return 0;
}

七、set容器的排序。  --  set容器存放内置数据类型。

#include <iostream>
using namespace std;
#include <set>

//set容器存放内置数据类型
//set容器的降序
class Mycompare{
public:
	//重载()
	bool operator()(int v1,int v2)
	{
		return v1 > v2;
	}
};

int main()
{
	set <int>s1;  //默认是升序。

	//插入之前

	s1.insert(10);
	s1.insert(40);
	s1.insert(20);
	s1.insert(50);
	s1.insert(30);

	//插入之后  
	for(set <int>::iterator it = s1.begin();it!=s1.end();it++)   
	{
		cout << *it << " ";
	}
	cout << endl;

	cout << "---------------------" << endl;
	set <int,Mycompare>s2;  //默认是降序。

	//插入之前
	s2.insert(10);
	s2.insert(40);
	s2.insert(20);
	s2.insert(50);
	s2.insert(30);

	//插入之后  
	for(set <int,Mycompare>::iterator it = s2.begin();it!=s2.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;




	//sort();   因为二叉树set容器是双向迭代器,所以不可以使用标准算法sort。
	//s.sort(); 内部也没有提供sort算法。
	
	//思考:能不能在插入之后,再进行降序?
	//答案:不可以的。
	
	//怎么才能降序?
	//答案:必须在插入之前,就要告诉它,要降序排序。

	return 0;
}

总结:
set容器,默认是升序的。
如果想降序,自己再写一个类,然后在类中重载(),让第一个数字大于第二个数字。
把类名写入到定义二叉树set对象<>里面即可,例如: set<int>s  ->  set<int,Mycompare>s;

上一篇:必会算法总结3—拓扑排序


下一篇:Java中栈和队列的使用及区别