什么是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
vector c //其中data为自定义的数据类型，可以为结构体
vector初始化
vector
vector
vector
vector动态数组的操作
vector
例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
#include
#include
#include
using namespace std;
vector
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可以时任意的数据类型，比如int,char，包括用户自定义数据类型
• value是该key对应的存储的值
• 定义map <类型1，类型2>变量名;
#include
map
插入数据方法：
1.
a.insert(pair
2.
a [“abc”]=2; //当遇到相同的key时，覆盖原来的数据
访问map中的元素
ma[“abc”]=2; //将字符串”abc”映射到整数”2”上
cout< map的操作 例3、map容器常用方法举例 #include #include #include using namespace std; map int main(){ ma["apple"]=1; ma["banana"]=2; ma["lemon"]=3; cout< cout< if(ma.count("pear")) cout<<"pear"< else cout<<"no pear"< cout< cout< //输出ma["lemon"]，即输出 3 return 0; } 出现次数超过一半的数(half.cpp) 【题目描述】 给出一个含有n（0 < n ≤ 1000）个整数的数组，请找出其中出现次数超过一半的数。数组中的数大 于-50且小于50。 【输入】 第一行包含一个整数n，表示数组大小； 第二行包含n个整数，分别是数组中的每个元素，相邻两个元素之间用单个空格隔开。 【输出】 如果存在这样的数，输出这个数；否则输出no。 【输入样例】 3 1 2 2 【输出样例】 2 代码 #include #include #include using namespace std; map 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 #include #include using namespace std; map 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 #include #include #define int long long using namespace std; map 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 需要使用 std 命名空间 using namespace std; 定义 set set 迭代器： set只能通过迭代器遍历，即遍历set集合前需先定义一个迭代器： for(set 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 #include #include using namespace std; set 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 cout << *i << ' '; return 0; } 四，pair pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就 是将key和value放在一起来保存。 另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first,second 因为是使用struct不是class，所以可以直接使用pair的成员变量。 pair基本用法 pair cout << p1.first << " " << p1.second; //每个pair 都有两个属性值 first 和second p1 = make_pair("lala", 322); Pair赋值 pair p1.first = v1; //分别对p1的first和second变量赋值 p1.second = v2; Pair的排序 1.默认对pair的first进行排序 pair sort(p1,p1+n); //按pair的first升序排序 2.自定义sort函数 pair bool cmp(pair { 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 #include #include using namespace std; pair bool cmp(pair { 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 - 洛谷 单词分类 - 洛谷