构造函数

deque容器基本概念

功能

  • 双端数组，可以对头端进行插入删除操作

deque与vector区别

  • vector对于头部的插入删除效率低，数据量越大，效率越低
  • deque相对而言，对头部的插入删除速度会比vector快
  • vector访问元素时的速度会比deque快，这和两者内部实现有关

deque内部工作原理

deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据

中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间

deque容器的迭代器也是支持随机访问的

deque构造函数

功能描述

  • deque容器构造

函数原型

1
2
3
4
deque<T> deqT;			//默认构造函数
deque(beg,end);			//构造函数将[beg,end)区间中的元素拷贝给本身
deque(n,elem);			//构造函数将n个elem拷贝给本身
deque(const deque &deq)	//拷贝构造函数

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<deque>
using namespace std;
//deque 构造函数
void printDeque(const deque<int>&d)
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		//*it = 100;	容器中的数据不可以修改了	
		cout << *it << " ";
	}
	cout << endl;
}
void test01()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);
	deque<int>d2(d1.begin(), d1.end());
	printDeque(d2);
	deque<int>d3(10, 100);
	printDeque(d3);
	deque<int>d4(d3);
	printDeque(d4);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

运行结果

1
2
3
4
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100

总结

deque容器和vector容器的构造方式几乎一致，灵活使用即可

赋值操作

deque赋值操作

功能描述

  • 给deque容器进行赋值

函数原型

1
2
3
deque& operator=(const deque &deq)	//重载等号操作符
assign(beg, end);					//将[beg,end)区间中的数据拷贝赋值给本身
assign(n, elem);					//将n个elem拷贝赋值给本身

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<deque>
using namespace std;
void printDeque(const deque<int>&d)
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{	
		cout << *it << " ";
	}
	cout << endl;
}
//deque容器赋值操作
void test01()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);
	// operator= 赋值
	deque<int>d2;
	d2 = d1;
	printDeque(d2);
	//assign 赋值
	deque<int>d3;
	d3.assign(d1.begin(), d1.end());
	printDeque(d3);
	deque<int>d4;
	d4.assign(10, 100);
	printDeque(d4);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

运行结果

1
2
3
4
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100 100 100 100 100 100

总结

deque赋值操作也与vector相同，需熟练掌握

大小操作

deque大小操作

功能描述

  • deque容器的大小进行操作

函数原型

1
2
3
4
5
6
deque.empty();			//判断容器是否为空
deque.size();			//返回容器中的元素的个数
deque.resize(num);		//重新指定容器的长度为num，若容器变长，则以默认值填充新位置
						//如果容器变短，则末尾超出容器长度的元素被删除
deque.resize(num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置
						//如果容器变短，则末尾超出容器长度的元素被删除

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<deque>
using namespace std;
//deque 容器大小操作
void printDeque(const deque<int>&d)
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{	
		cout << *it << " ";
	}
	cout << endl;
}
//deque容器赋值操作
void test01()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);
	if (d1.empty())
	{
		cout << "d1为空" << endl;
	}
	else
	{
		cout << "d1不为空" << endl;
		cout << "d1的大小为：" << d1.size() << endl;
		//deque容器没有容量概念
	}
	//重新指定大小
	//d1.resize(15);
	d1.resize(15, 1);
	printDeque(d1);
	d1.resize(5);
	printDeque(d1);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

运行结果

1
2
3
4
5
0 1 2 3 4 5 6 7 8 9
d1不为空
d1的大小为：10
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1
0 1 2 3 4

总结

  • deque没有容量的概念
  • 判断是否为空–empty
  • 返回元素个数–size
  • 重新指定个数–resize

插入和删除

deque插入和删除

功能描述

  • 向deque容器中插入和删除数据

函数原型

两端插入操作：

1
2
3
4
push_back(elem);	//在容器尾部添加一个数据
push_front(elem);	//在容器头部插入一个数据
pop_back();			//删除容器最后一个数据
pop_front();		//删除容器第一个数据

指定位置操作：

1
2
3
4
5
6
insert(pos.elem);	//在pos位置插入一个elem级元素的拷贝，返回新数据的位置
insert(pos,n,elem);	//在pos位置插入n个elem数据，无返回值
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值
clear();			//清空容器的所有数据
erase(beg,end);		//删除[beg,end)区间的数据，返回下一个数据的位置
erase(pos);			//删除pos位置的数据，返回下一个数据的位置

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<deque>
using namespace std;
//deque容器插入和删除
void printDeque(const deque<int>&d)
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{	
		cout << *it << " ";
	}
	cout << endl;
}
//两端操作
void test01()
{
	deque<int>d1;
	//尾插
	d1.push_back(10);
	d1.push_back(20);
	//头插
	d1.push_front(100);
	d1.push_front(200);
	//200 100 10 20
	printDeque(d1);
	//尾删
	d1.pop_back();
	//200 100 10
	printDeque(d1);
	//头删
	d1.pop_front();
	//100 10
	printDeque(d1);
}
void test02()
{
	deque<int>d1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_front(100);
	d1.push_front(200);
	//200 100 10 20
	printDeque(d1);
	//insert插入
	d1.insert(d1.begin(), 1000);
	//1000 200 100 10 20
	printDeque(d1);
	d1.insert(d1.begin(), 2, 10000);
	//10000 10000 1000 200 100 10 20
	printDeque(d1);
	//按照区间进行插入
	deque<int>d2;
	d2.push_back(1);
	d2.push_back(2);
	d2.push_back(3);
	d1.insert(d1.begin(), d2.begin(), d2.end());
	//1 2 3 10000 10000 1000 200 100 10 20
	printDeque(d1);
}
void test03()
{
	deque<int>d1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_front(100);
	d1.push_front(200);
	//删除
	deque<int>::iterator it = d1.begin();
	it++;
	d1.erase(it);
	//200 10 20
	printDeque(d1);
	//按区间方式删除
	//d1.erase(d1.begin(), d1.end());
	//清空
	d1.clear();
	printDeque(d1);
}
int main()
{
	test01();
	test02();
	test03();
	system("pause");
	return 0;
}

运行结果

1
2
3
4
5
6
7
8
200 100 10 20
200 100 10
100 10
200 100 10 20
1000 200 100 10 20
10000 10000 1000 200 100 10 20
1 2 3 10000 10000 1000 200 100 10 20
200 10 20

总结

  • 插入和删除提供的位置是迭代器
  • 尾插—push_back
  • 尾删—pop_back
  • 头插—push_front
  • 头删—pop_front

数据存取

deque数据存取

功能描述

  • 对deque中的数据的存取操作

函数原型

1
2
3
4
at(int idx);	//返回索引idx所指的数据
operator[];		//返回所以idx所指的数据
front();		//返回容器中第一个数据元素
back();			//返回容器中最后一个数据元素

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<deque>
using namespace std;
//deque容器数据存取
void test01()
{
	deque<int>d1;
	d.push_back(10);
	d.push_back(20);
	d.push_back(30);
	d.push_front(100);
	d.push_front(200);
	d.push_front(300);
	//通过[]方式访问元素
	//300 200 100 10 20 30
	for (int i = 0; i < d.size(); i++)
	{
		cout << d[i] << " ";
	}
	cout << endl;
	//通过at方式访问元素
	for (int i = 0; i < d.size(); i++)
	{
		cout << d.at(i) << " ";
	}
	cout << endl;
	cout << "第一个元素为：" << d.front() << endl;
	cout << "最后一个元素：" << d.back() << endl;
}
int main()
{
	test01();
	system("pause");
	return 0;
}

运行结果

1
2
3
4
300 200 100 10 20 30
300 200 100 10 20 30
第一个元素为：300
最后一个元素：30

总结

  • 除了用迭代器获取deque容器中元素，[]和at也可以
  • front返回容器第一个元素
  • back返回容器最后一个元素

排序操作

deque排序

功能描述

  • 利用算法实现对deque容器进行排序

算法

1
sort(iterator beg, iterator end);	//对beg和end区间内元素进行排序

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<deque>
#include<algorithm>	//标准算法头文件
using namespace std;
void printDeque(const deque<int>& d)
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
//deque容器排序
void test01()
{
	deque<int>d;
	d.push_back(10);
	d.push_back(20);
	d.push_back(30);
	d.push_front(100);
	d.push_front(200);
	d.push_front(300);
	//300 200 100 10 20 30
	printDeque(d);
	//排序 默认排序规则 从小到大 升序
	//对于支持随机访问的迭代器的容器，都可以利用sort算法对其进行排序
	//vector容器也可以利用 sort进行排序
	sort(d.begin(), d.end());
	cout << "排序后：" << endl;
	printDeque(d);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

运行结果

1
2
3
300 200 100 10 20 30
排序后：
10 20 30 100 200 300

总结

sort算法非常使用，使用时包含头文件algorithm即可

STL案例1-评委打分

案例描述

有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去掉评委中最低分，去平均分

实现步骤

  1. 创建五名选手，放到vector中
  2. 遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分存到deque容器中
  3. sort算法对deque容器中分数排序，去除最高和最低分
  4. deque容器遍历一遍，累加总分
  5. 获取平均分

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<algorithm>
#include<ctime>
using namespace std;
/*
有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去掉评委中最低分，去平均分
*/
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";
	for (int i = 0; i < 5; i++)
	{
		string name = "选手";
		name += nameSeed[i];
		int score = 0;
		Person p(name, score);
		//将创建的Person对象 放入到容器中
		v.push_back(p);
	}
}
//打分
void setScore(vector<Person>& v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		//将评委的分数 放入到deque容器中
		deque<int>d;
		for (int i = 0; i < 10; i++)
		{
			int score = rand() % 41 + 60;	//60~100
			d.push_back(score);
		}
		cout << "选手：" << it->m_Name << "打分：" << endl;
		for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			cout << *dit << " ";
		}
		cout << endl;
		//排序
		sort(d.begin(), d.end());
		//去除最高和最低分
		d.pop_back();
		d.pop_front();
		//取平均分
		int sum = 0;
		for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			sum += *dit;	//累加每个评委的分数
		}
		int avg = sum / d.size();
		//将平均分 赋值给选手身上
		it->m_Score = avg;
	}
}
void showScore(vector<Person>& v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "姓名：" << it->m_Name << "平均分：" << it->m_Score << endl;
	}
}
int main()
{
	//随机数种子
	srand((unsigned int)time(NULL));
	//1、创建5名选手
	vector<Person>v;	//存放选手容器
	createPerson(v);
	//测试
	/*for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "姓名：" << (*it).m_Name << "分数：" << (*it).m_Score << endl;
	}*/
	//2、给5名选手打分
	setScore(v);
	//3、显示最后得分
	showScore(v);
	system("pause");
	return 0;
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
选手：选手A打分：
87 76 84 69 65 65 75 79 83 86
选手：选手B打分：
70 65 60 66 94 76 70 70 91 88
选手：选手C打分：
83 100 64 80 76 75 64 95 67 95
选手：选手D打分：
69 100 73 73 98 99 62 72 85 97
选手：选手E打分：
88 97 77 78 89 76 62 79 93 80
姓名：选手A平均分：77
姓名：选手B平均分：74
姓名：选手C平均分：79
姓名：选手D平均分：83
姓名：选手E平均分：82