STL应用——vector

STL 应用

【容器通用函数】

• .size()：容器内的元素个数，无符号整型
• .empty()：判断容器是否为空，返回一个bool值
• .front()：返回容器第一个元素
• .back()：返回容器最后一个元素
• .begin()：指向容器第一个元素的指针
• .end()：指向容器最后一个元素的下一个位置的指针
• .swap(b)：交换两个容器的内容。
• ::iterator：迭代器

【迭代器】

迭代器是一个广义的指针，可以是指针，也可以是对其进行类似指针操作的对象。模板使算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型。

举个栗子：使用迭代器输出vector容器中的元素：

for(vector<int> ::iterator it = a.begin();it != a.end(); it ++){
	cout << *it << endl;
}
1
2
3

vector

vector（向量）是一个封装了动态大小数组的顺序容器（SequenceContainer）。顺序容器中的元素按照严格的线性顺序排序，可以通过元素在序列中的位置访问对应的元素，支持数组表示法和随机访问。vector使用一个内存分配器动态处理存储需求。使用vector时需要引入头文件#include。

创建

vector能够存放各种类型的对象，可以是C++标准数据类型，也可以是结构体类型。

举个栗子：

vector<int>a;   //创建一个空的vector，数据类型为int，数组名为a

vector<int>a(100); //创建一个vector，数组名为a，元素个数为100，所有数的初值都是0

vector<int>a(10,666); //创建一个vector，数组名为a，元素个数为10，所有数的初值都是666

vector<int>b(a);  //b是a的复制

vector<int>b(a.begin() + 3, a.end() - 3); //复制[a.begin() + 3, a.end() - 3]区间内的元素到vector中
1
2
3
4
5
6
7
8
9

【创建二维数组】

vector<int>a[5]; //相当于创建了5个vector，每个都是一个数组
1

增加

向vector中添加元素，可以从尾部添加，也可以从中间添加。

从中间插入时需要将插入位置之后的所有元素后移，时间复杂度为O (n )，效率较低。

举个栗子：

a.push_back(5); //在向量尾部增加一个元素5

a.insert(a.begin() + 1 , 10); //在a.begin() + 1指向元素前插入一个10

a.insert(a.begin() + 1 , 5 , 10); //在a.begin() + 1 指向元素前插入 5 个 10

a.insert(a.begin() + 1, b , b + 3); //在a.begin() + 1指向元素前插入b向量的区间元素
1
2
3
4
5
6
7

删除

可以删除尾部元素、指定位置的元素、区间，还可以清空整个向量。

举个栗子：

a.pop_back();  //删除向量中的最后一个元素

a.erase(a.begin() + 1); //删除指定位置的元素

a.erase(a.begin() + 3, a.end() - 3); //删除区间[first , last]中的元素

a.clear();   //清空向量
1
2
3
4
5
6
7

遍历

可以用数组表示法，也可以用迭代器对向量元素进行访问。

for(int i = 0 ; i < a.size(); i ++){
	cout << a[i] << "\t";
}
for(vector<int> ::iterator it = a.begin(); it < a.end() ; it ++){
	cout << *it << "\t";
}
1
2
3
4
5
6

改变向量的大小

resize可以改变当前向量的大小，如果它比当前向量大，则填充默认值；如果比当前向量小，则舍弃后面的部分。

a.resize(5);  //设置向量的大小为5，如果在当前向量内有8个元素，则舍弃后面3个
1

【间谍】

题目描述（HDU3527）： X国的情报委员收到一份可靠的信息，信息表明Y国将派间谍去窃取X国的机密文件。X国指挥官手中有两份名单列表，一份是Y国派往X国的间谍名单列表，另一份是X国以前派往Y国的间谍名单列表。这两份名单列表可能有些重叠。因为间谍可能同时扮演两个角色，称之为“双重间谍”。因此，Y国可以把双重间谍送回X国。很明显，这对X国是有利的，因为双重间谍可以把Y国的机密文件带回，而不必担心被Y国边境拘留。所以指挥官决定抓住由Y国派出的间谍，让普通人和双重间谍进入。那么你能确定指挥官需要抓捕的间谍名单吗？

输入：

有几个测试用例。每个测试用例都包含4部分。第1部分包含3个正整数A 、B 、C ，A 是进入边境的人数，B 是Y国将派出的间谍人数，C 是X国以前派到Y国的间谍人数。第2部分包含A 个字符串，为进入边境的人员名单。第3部分包含B 个字符串，为由Y国派出的间谍名单。第4部分包含C 个字符串，即双重间谍的名单。每个测试用例后都有一个空白行。在一份名单列表中不会有任何名字重复，如果有重复的名字出现在两份名单列表中，则表示同一个人。

输出：

输出指挥官抓捕的间谍名单（按列表B的出现顺序）。如果不应捕获任何人，则输出“No enemy spy”。

题解：

#include
#include
#include
#include

using namespace std;

vector<string> x, y , z , res; //x为进入边境的名单、y为Y国间谍、z为双重间谍，res为抓捕名单即答案 

int main(){
	
	int a , b , c;
	
	string s; 
	
	while(cin >> a >> b >> c){
		x.clear();
		y.clear();
		z.clear();
		res.clear();
		
		
		for(int i = 0 ; i < a ; i ++){
			cin >> s;
			x.push_back(s);
		}
		
		for(int i = 0 ; i < b ; i++){
			cin >> s;
			y.push_back(s);
		}
		
		for(int i = 0 ; i < c; i ++){
			cin >> s;
			z.push_back(s);
		}
		
		for(int i = 0 ; i < b ; i++){
			//判断第二行(Y国派来的间谍)在第一行(进入边境的名单)出现
			//但是没在第三行(双重间谍)中出现的字符串
			if(find(x.begin() , x.end() , y[i]) != x.end()){
				if(find(z.begin() , z.end() , y[i]) == z.end()){
					res.push_back(y[i]);
				}
			} 
		}
		
		if(!res.size()){
			cout << "No enemy spy\n";
		}
		else{
			for(int i = 0 ; i < res.size() ; i++){
				if(i != 0){
					cout << " ";
				}
				cout << res[i];
			}
			cout << endl;
		}
	}
	return 0;
}

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

运行结果