STL模板库

大家好，欢迎来到IT知识分享网。

什么是STL

STL 是“Standard Template Library”的缩写，中文译为“标准模板库” 。STL 是 C++ 标准库的一部分，不用单独安装。

• STL中六大组件：

• 1）容器（Container），是一种数据结构，如list，vector，和deques 。

• 2）迭代器（Iterator），提供了访问容器中对象的方法。

• 3）算法（Algorithm），是用来操作容器中的数据的模板函数。

• 4）仿函数（Function object）

• 5）迭代适配器（Adaptor）

• 6）空间配制器（allocator）

一，vector

vector定义

为了节省空间，有时我们会使用动态数组vector。

只需要包含#include<vector>

• 定义动态数组 vector<类型名>变量名

vector<int> a //定义a为一个int类型的动态数组 vector<char> a //定义 a 为一个char 类型的动态数组 vector<data> c //其中data为自定义的数据类型，可以为结构体

vector初始化

vector<int> a; //对a执行默认初始化 vector<int> a(n); //a初始化为包含n个元素的拷贝 vector<int> a(n,x); //v3包括了n个元素，都为x(x可省略)

vector动态数组的操作

vector<int> a;

例1：整数奇偶排序

描述 给定n个整数的序列，要求对其重新排序。

排序要求: 1.奇数在前，偶数在后；

2.奇数按从大到小排序；

3.偶数按从小到大排序。

输入

输入二行，第一行一个整数n，第二行包含n个整数，彼此以一个空格分开，每个整数的范围是大于等于0，小 于等于100。

输出

按照要求排序后输出一行，包含排序后的10个整数，数与数之间以一个空格分开。

样例输入

10

4 7 3 13 11 12 0  47 34 98

样例输出

47 13 11 7 3 0 4 12 34 98

代码 

#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> a, b; int n; int x; int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> x; if(x % 2 == 0) { a.push_back(x); } else { b.push_back(x); } } sort(b.rbegin(), b.rend()); for(int i = 0; i < b.size(); i++) cout << b[i] << ' '; sort(a.begin(), a.end()); for(int i = 0; i < a.size(); i++) cout << a[i] << ' '; return 0; }

二，map

在实际应用中，我们可以使用map容器来作为一个有序的映射表，可以将其看做是一个下 标可以是任何类型的数组。

• map是STL的一个关联容器，它以<key,value>一对一的形式存储，且map的内部自建一个 红黑树，使得其可以自动排序.

• key可以时任意的数据类型，比如int,char，包括用户自定义数据类型

• value是该key对应的存储的值

• 定义map <类型1，类型2>变量名;

#include<map> map<string,int> ma; //定义a为一个从string到int的一个映射

插入数据方法：

1.

a.insert(pair<string,int>(“abc”,4)); //当遇到相同的key时，它不会进行插入操作即覆盖原来的数据

2.

a [“abc”]=2; //当遇到相同的key时，覆盖原来的数据

访问map中的元素

ma[“abc”]=2; //将字符串”abc”映射到整数”2”上 cout<<ma[“abc”]<<endl; //屏幕上将输出整数2

map的操作

 例3、map容器常用方法举例

#include <iostream> #include <map> #include <string> using namespace std; map<string,int> ma; int main(){ ma["apple"]=1; ma["banana"]=2; ma["lemon"]=3; cout<<ma.size()<<endl; //输出map的大小 3 cout<<ma["apple"]<<endl; //输出 1 if(ma.count("pear")) cout<<"pear"<<endl; else cout<<"no pear"<<endl; //输出"no pear" cout<<ma.lower_bound("cow")->first<<endl; //输出"lemon" cout<<ma.lower_bound("cow")->second<<endl; //输出ma["lemon"]，即输出 3 return 0; }

出现次数超过一半的数(half.cpp) 

【题目描述】 给出一个含有n（0 < n ≤ 1000）个整数的数组，请找出其中出现次数超过一半的数。数组中的数大 于-50且小于50。

【输入】

第一行包含一个整数n，表示数组大小； 第二行包含n个整数，分别是数组中的每个元素，相邻两个元素之间用单个空格隔开。

【输出】 如果存在这样的数，输出这个数；否则输出no。

【输入样例】

3

1 2 2

【输出样例】 

2

代码 

#include <iostream> #include <cstdio> #include <map> using namespace std; map<int, int> ma; int n, x; int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> x; ma[x]++; } for(int i = -50; i <= 50; i++) { if(ma[i] * 2 > n) { cout << i; return 0; } } cout << "no"; return 0; } 

例4 查字典 cogs399题

全国英语四级考试就这样如期来了，可是小 y 依然没有做好充分准备。

为了能够大学毕业可怜的小 y 决定作弊。 y 费尽心机，在考试的时候夹带了一本字典进考场，但是现在的问题是，考试的时候可能有很多的单词要查，小 y 能不能来得及呢？

输入：第一行一个整数 N ，表示字典中一共有多少个单词（ N<=10000).

接下来每行表示一个单词，其中： 第一部分是一个长度 <= 100 的字符串，表示这个单词，全部小写字母，单词不会重复。 第二部分行是一个整数， 表示这个单词在字典中的页码。

接下来是一个整数 M ，表示要查的单词数 (M<=10000)

接下来 M 行，每行一个字符串，表示要查的单词，保证在字典中存在。 输出：M 行，每行一个整数，表示第 I 个单词在字典中的页数。

输入样例

2

scan 10

word 15

2

scan

word

输出样例

10

15 

代码

#include <iostream> #include <cstdio> #include <map> using namespace std; map<string, int> dic; char a[105]; int main() { int n, m, page; cin >> n; for(int i = 0; i < n; i++) { cin >> a >> page; dic[a] = page; } cin >> m; while(m--) { cin >> a; cout << dic[a] << endl; } return 0; } 

 学籍管理

【深基17.例6】学籍管理 – 洛谷

题目描述：您要设计一个学籍管理系统，最开始学籍数据是空的，然后该系统能够支持下面的操作（不超过 10^5条）：

• 插入与修改，格式：1 NAME SCORE：在系统中插入姓名为 NAME(由字母和数字组成不超过 20 个字符的字 符串，区分大小写) ，分数为 SCORE（0 < SCORE<2^31） 的学生。如果已经有同名的学生则更新这名学生的成 绩为 SCORE。如果成功插入或者修改则输出OK。

• 查询，格式：2 NAME：在系统中查询姓名为 NAME 的学生的成绩。如果没能找到这名学生则输出Not found，否则输出该生成绩。

• 删除，格式：3 NAME：在系统中删除姓名为 NAME 的学生信息。如果没能找到这名学生则输出Not found， 否则输出Deleted successfully。

• 汇总，格式：4：输出系统中学生数量。

输入格式：无

输出格式：无

输入

5

1 lxl 10

2 lxl

3 lxl

2 lxl

4

输出

OK

10

Delete successfully

Not found

0 

代码 

#include <iostream> #include <cstdio> #include <map> #define int long long using namespace std; map<string, int> m; int n, t, x; string s; signed main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> t; if(t == 1) { cin >> s >> x; m[s] = x; cout << "OK"; } if(t == 2) { cin >> s; if(m.count(s)) cout << m[s]; else cout << "Not found"; } if(t == 3) { cin >> s; if(m.count(s)) { m.erase(s); cout << "Deleted successfully"; }else cout << "Not found"; } if(t == 4) cout << m.size(); cout << endl; } return 0; } 

三，set

set 是一个内部自动有序且不含重复元素的容器。

• set 最主要的作用就是自动去重并按升序排序，适用于需要去重但是又不方便直接开数组的 情况。

• set 中的元素是唯一的。

 头文件 

#include <set>

需要使用 std 命名空间 using namespace std;

定义 set

set<type> s; //type 可以是任何基本类型或者容器

迭代器：

 set只能通过迭代器遍历，即遍历set集合前需先定义一个迭代器：

for(set<int>::iterator i = a.begin(); i != a.end(); i++) cout << *i << ' ';

明明的随机数

[NOIP2006 普及组] 明明的随机数 – 洛谷

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 11 到 1000 之间的随机整数 (N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第 1 行为 1 个正整数，表示所生成的随机数的个数 N。

第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第 1 行为 11 个正整数 M，表示不相同的随机数的个数。

第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

输入样例

10

20 40 32 67 40 20 89 300 400 15

输出样例

8

15 20 32 40 67 89 300 400 

代码 

#include <iostream> #include <cstdio> #include <set> using namespace std; set<int> a; int n, x; int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> x; a.insert(x); } cout << a.size() << endl; for(set<int>::iterator i = a.begin(); i != a.end(); i++) cout << *i << ' '; return 0; } 

四，pair

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就 是将key和value放在一起来保存。

另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。

pair的实现是一个结构体，主要的两个成员变量是first,second

因为是使用struct不是class，所以可以直接使用pair的成员变量。

pair基本用法 

pair<string, int> p1("hello world", 233); cout << p1.first << " " << p1.second; //每个pair 都有两个属性值 first 和second p1 = make_pair("lala", 322);

Pair赋值

pair<type1,type2> p1; //创建空pair对象p1 p1.first = v1; //分别对p1的first和second变量赋值 p1.second = v2;

Pair的排序

1.默认对pair的first进行排序

pair<int,int> p1[n]; sort(p1,p1+n); //按pair的first升序排序

2.自定义sort函数 

pair<int,int> p1[n]; bool cmp(pair<int,int> a,pair<int,int> b) { return a.second > b.second; } sort(p1,p1+n,cmp); //按pair的second降序排序

合影效果

小云和朋友们去爬香山，为美丽的景色所陶醉，想合影留念。如果他们站成一排，男生全部在左（从拍 照者的角度），并按照从矮到高的顺序从左到右排，女生全部在右，并按照从高到矮的顺序从左到右排， 请问他们合影的效果是什么样的（所有人的身高都不同）？

输入：第一行是人数n（2<=n<=40)且至少有1个男生和1个女生）。 后面紧跟n行，每行输入一个人的性别（男male或女female）和身高（浮点数，单位米），两个数据之 间以空格分隔。

输出：n个浮点数，模拟站好队后，拍照者眼中从左到右每个人的身高。每个浮点数需保留到小数点后2 位，相邻两个数之间用单个空格隔开。

样例输入

6

male 1.72

male 1.78

female 1.61

male 1.65

female 1.70

female 1.56

样例输出

1.65 1.72 1.78 1.70 1.61 1.56 

代码

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; pair<string, float> p[45]; bool cmp(pair<string, float> a, pair<string, float> b) { return a.second > b.second; } int n; int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> p[i].first >> p[i].second; } sort(p + 1, p + n + 1, cmp); for(int i = n; i >= 1; i--) { if(p[i].first == "male") printf("%.2f ", p[i].second); } for(int i = 1; i <= n; i++) { if(p[i].first == "female") printf("%.2f ", p[i].second); } return 0; } 

相关练习 

[CCC 2023 J2] Chili Peppers – 洛谷

单词分类 – 洛谷