C++ STL (标准模板库)
STL (Standard Template Library)：是 C++ 标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。
通俗来说：STL 就是将常见的数据结构（例如 顺序表，链表，栈，队列，二叉树，哈希...）以模板的形式进行封装，使用时，不用我们人为再去写，可以直接调用。并且包含常见的通用的泛型算法（一些常规的算法也不用自己实现，可以直接调用）。
STL 六大组件
容器（Container）： 各种数据结构，如
vector、list、deque、set、map等，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器。算法（Algorithm）： 各种常用算法，提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作，如
sort、find、copy、erase函数等。函数本身与它们操作的数据的结构和类型无关，因此它们可以在从简单数组到高度复杂容器的任何数据结构上使用。迭代器（Iterator）： 迭代器提供了访问容器中对象的方法，扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，共有 5 种类型，以及其他衍生变化，是一种将
operator*、operator->、operator++、operator--等指针操作予以重载的模板类。所有的 STL 容器附带有自己专属的迭代器，因为只有容器设计者才知道如何遍历自己的元素。c++11版本及以后就可以不用迭代器了。
仿函数（Functor）： 也称为函数对象（Function object），行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了
operator()的类或者模板类。适配器（Adaptor）： 一种用来修饰容器、仿函数或者迭代器接口的机制。例如 STL 提供的
queue和stack，就是一种空间配接器，因为它们的底部完全借助于deque。分配器（allocator）： 也称为空间配置器，负责空间的配置与管理。从实现的角度来看，配置器是一个实现了动态配置空间、空间管理、空间释放的模板类。
算法 (Algorithm)
头文件：#include <algorithm>
常用函数
sort()- 功能：
sort()函数可以对给定区间所有元素进行排序。 - 参数：
sort(begin, end, cmp)begin：指向待sort()的数组的第一个元素的指针。end：指向待sort()的数组的最后一个元素的下一个位置的指针。cmp：排序准则，可以不写，默认从小到大进行排序。
c++#include<iostream> #include<algorithm> using namespace std; int main(){ int num[10] = {6,5,9,1,2,8,7,3,4,0}; // greater<int>() 是一个仿函数，表示降序排列，这里只做演示，是一个伪代码 sort(num, num+10, greater<int>()); // 排序后 num 变为：9 8 7 6 5 4 3 2 1 0 return 0; }- 功能：
swap()交换两个数的值c++int a = 1, b = 2 ; cout << a << ' ' << b << '\n' ; swap(a, b) ;min()取最小值max()取最大值
💡 排序练习
P5740 【深基7.例9】最厉害的学生
题目描述
现有 名同学参加了期末考试，并且获得了每名同学的信息：姓名（不超过 个字符的仅有英文小写字母的字符串）、语文、数学、英语成绩（均为不超过 的自然数）。总分最高的学生就是最厉害的，请输出最厉害的学生各项信息（姓名、各科成绩）。如果有多个总分相同的学生，输出靠前的那位。
输入格式
第一行输入一个正整数 ，表示学生个数。
第二行开始，往下 行，对于每一行首先先输入一个字符串表示学生姓名，再输入三个自然数表示语文、数学、英语的成绩。均用空格相隔。
输出格式
输出最厉害的学生。
输入输出样例 #1
输入 #1
3
senpai 114 51 4
lxl 114 10 23
fafa 51 42 60输出 #1
senpai 114 51 4说明/提示
数据保证，，姓名为长度不超过 的字符串，语文、数学、英语成绩均为不超过 的自然数。
自定义 cmp 函数实现结构体排序
#include <bits/stdc++.h>
using namespace std ;
const int N = 1008 ;
struct node {
string name ;
int a, b, c ;
int sum ;
int num ;
} no[N];
// 自定义比较函数
bool cmp(node x, node y) {
// 如果总分相同
if (x.sum == y.sum) {
// 按学号从小到大
return x.num < y.num ;
}
// 否则按总分从大到小
return x.sum > y.sum ;
}
int main() {
int n ;
cin >> n ;
for (int i = 1 ; i <= n ; i ++) {
cin >> no[i].name >> no[i].a >> no[i].b >> no[i].c ;
no[i].sum = no[i].a + no[i].b + no[i].c ;
no[i].num = i ;
}
// 使用自定义的 cmp 函数进行排序
sort(no + 1, no + n + 1, cmp) ;
cout << no[1].name << ' ' << no[1].a << ' ' << no[1].b << ' ' << no[1].c <<'\n' ;
return 0 ;
}📦 容器 (Container)
容器是存放数据的数据结构，比如链表，数组，队列... 容器都是一个类（用法与结构体相似）。访问类对象内的函数或变量用点运算符 .。
vector (可变长度数组)
vector翻译为向量，但是这里使用“变长数组”的叫法更容易理解，也即“长度根据需要而自动改变的数组”。我们知道在C语言中，普通数组大小一旦确定就不能改变了，在做题时有时会碰到只用普通数组会超内存的情况，这时我们就可以使用vector来定义不定长数组节省空间。
定义
#include <vector>
vector<typename> name;
// 示例：
vector<int> v = {1, 2, 3};常用函数
push_back(x)：在 vector 后面添加一个元素x，时间复杂度 O(1)。pop_back()：删除 vector 最后一个元素，时间复杂度 O(1)。back()：返回最后一个元素的值。front()：返回第一个元素的值。size()：返回 vector 中元素的个数，时间复杂度 O(1)。clear()：清空 vector 中的所有元素，时间复杂度 O(N)。insert(it, x)：向迭代器it处插入一个元素x，时间复杂度 O(N)。erase(it)：删除迭代器it处的元素。erase(first, last)：删除[first, last)区间内的所有元素。
迭代器
vector<int> v = {1, 2, 3};
vector<int>::iterator it ;
// 传统迭代器遍历
for (it = v.begin() ; it != v.end() ; it ++) {
cout << *it << '\n' ;
}
// C++11
//
//
//
for (auto i : v) { // auto 自动推导类型
cout << i << ' ' ;
}练习
P1567 统计天数
题目描述
炎热的夏日，KC 非常的不爽。他宁可忍受北极的寒冷，也不愿忍受厦门的夏天。最近，他开始研究天气的变化。他希望用研究的结果预测未来的天气。
经历千辛万苦，他收集了连续 天的最高气温数据。
现在，他想知道最高气温一直上升的最长连续天数。
输入格式
第 1 行：一个整数 。
第 2 行：个空格隔开的整数，表示连续 天的最高气温。 最高气温 。
输出格式
1 行：一个整数，表示最高气温一直上升的最长连续天数。
输入输出样例 #1
输入 #1
10
1 2 3 2 4 5 6 8 5 9输出 #1
5#include <bits/stdc++.h>
using namespace std ;
int main() {
int n ;
cin >> n ;
vector<int> a;
for (int i = 1 ; i <= n ; i ++) {
int x ;
cin >> x ;
a.push_back(x) ;
}
int ans = 1, tmp = 1 ;
for (int i = 1 ; i < a.size() ; i ++) {
if (a[i] > a[i - 1]) {
tmp ++ ;
} else {
ans = max(ans, tmp) ;
tmp = 1 ;
}
}
ans = max(ans, tmp) ; // 别忘了最后一次的比较
cout << ans << '\n' ;
return 0 ;
}string (字符串)
C++ 在 STL 中加入了 string 类型，对字符串常用的需求功能进行了封装，使得操作起来更方便，且不易出错。
头文件
#include <string>定义
string a = "abcd";常用函数
+=：字符串拼接，假设有两个字符串a和b，可用a+=b或a=a+b来将b接到a的后面。==,!=,<,<=,>,>=：按字典序比较大小。length()/size()：返回字符串长度，O(1)。erase(it)：删除it处的字符，it为迭代器。erase(first, last)：删除[first, last)区间的字符，first,last为迭代器。erase(pos, length)：pos为开始删除的起始位置，length为删除的字符个数。clear()：清空字符串 O(1)。substr(pos, len)：返回从pos号位置开始、长度为len的子串，O(len)。find(str2)：当str2是str的子串时，返回其在str中第一次出现的位置；否则返回string::npos。O(NM)。front()：返回第一个字符。back()：返回最后一个字符。push_back(x)：将字符x加到字符串后。pop_back()：删除最后一个字符。
map (映射)
Map (映射) 元素包含两部分（key, value），key 和 value 可以是任意类型。在 map 里面，一个 key 对应一个 value，类似函数里一个 x 对应一个 y。并且在 map 里，key 不能重复，自动按 key 从小到大排序。
定义
#include <map>
map<int, int> mp; // 定义了一个 int 映射 int 的 map
map<int, char> mp; // int -> char常见函数
insert(make_pair(x, y))：插入 key 为x，value 为y的映射。insert({x,y})：C++11 版本之后，可以用花括号来生成 pair 二元组。遍历 map
c++map<int, int>::iterator i; for(i = mp.begin(); i != mp.end(); i++) { cout << i->first << ' ' << i->second; // first 是 key, second 是 value } // C++11 // // // for(auto i : mp) { cout << i.first << ' ' << i.second << '\n'; } // C++17 // // // for(auto [a,b] : mp) { // 结构化绑定 cout << a << ' ' << b << '\n'; }
练习
P1125 [NOIP 2008 提高组] 笨小猴
题目描述
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设 是单词中出现次数最多的字母的出现次数， 是单词中出现次数最少的字母的出现次数，如果 是一个质数，那么笨小猴就认为这是个 Lucky Word，这样的单词很可能就是正确的答案。
输入格式
一个单词，其中只可能出现小写字母，并且长度小于 。
输出格式
共两行，第一行是一个字符串，假设输入的单词是 Lucky Word，那么输出 Lucky Word，否则输出 No Answer；
第二行是一个整数，如果输入的单词是 Lucky Word，输出 的值，否则输出 。
输入输出样例 #1
输入 #1
error输出 #1
Lucky Word
2输入输出样例 #2
输入 #2
olympic输出 #2
No Answer
0说明/提示
【输入输出样例 1 解释】
单词 error 中出现最多的字母 \texttt r 出现了 次，出现次数最少的字母出现了 次，， 是质数。
【输入输出样例 2 解释】
单词 olympic 中出现最多的字母 \texttt i 出现了 次，出现次数最少的字母出现了 次，， 不是质数。
（本处原题面错误已经修正）
noip2008 提高第一题
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std ;
map<char, int> cnt; // 统计每个字符出现的次数
// 判断是否为素数
bool judge(int x) {
if (x == 0 || x == 1) {
return false ;
}
for (int i = 2 ; i * i <= x ; i ++) {
if (x % i == 0) {
return false ;
}
}
return true ;
}
int main() {
string s ;
cin >> s ;
for (auto i : s) {
cnt[i] ++ ; // map可以直接用[]来访问和修改value
}
int minn = inf, maxn = -1 ;
for (auto i : s) {
minn = min(minn, cnt[i]) ;
maxn = max(maxn, cnt[i]) ;
}
if (judge(maxn - minn)) {
cout << "Lucky Word" << '\n' ;
cout << maxn - minn << '\n' ;
} else {
cout << "No Answer\n0\n" ;
}
return 0 ;
}queue (队列)
队列是一种先进先出 (FIFO) 的数据结构。和现实中的队列一个样，从队尾添加元素，从队头删除元素。
定义
#include <queue>
queue<typename> name;常用函数
push(x)：将x入队（到队尾）。pop()：将队首元素出队。front()：返回队首元素。back()：返回队尾元素。size()：返回队列元素个数。empty()：返回队列是否为空。为空时返回true。
练习
B3616 【模板】队列
题目描述
请你实现一个队列（queue），支持如下操作：
push(x)：向队列中加入一个数 。pop()：将队首弹出。如果此时队列为空，则不进行弹出操作，并输出ERR_CANNOT_POP。query()：输出队首元素。如果此时队列为空，则输出ERR_CANNOT_QUERY。size()：输出此时队列内元素个数。
输入格式
第一行，一个整数 ，表示操作的次数。
接下来 行，每行表示一个操作。格式如下：
1 x，表示将元素x加入队列。2，表示将队首弹出队列。3，表示查询队首。4，表示查询队列内元素个数。
输出格式
输出若干行，对于每个操作，按「题目描述」输出结果。
每条输出之间应当用空行隔开。
输入输出样例 #1
输入 #1
13
1 2
3
4
1 233
3
2
3
2
4
3
2
1 144
3输出 #1
2
1
2
233
0
ERR_CANNOT_QUERY
ERR_CANNOT_POP
144说明/提示
样例解释
首先插入 2，队首为 2、队列内元素个数为 1。
插入 233，此时队首为 2。
弹出队首，此时队首为 233。
弹出队首，此时队首为空。
再次尝试弹出队首，由于队列已经为空，此时无法弹出。
插入 144，此时队首为 144。
数据规模与约定
对于 的测试数据，满足 ，且被插入队列的所有元素值是 以内的正整数。
#include <bits/stdc++.h>
using namespace std ;
int main() {
int n ;
cin >> n ;
queue<int> q ;
while (n --) {
int op ;
cin >> op ;
if (op == 1) {
int x ;
cin >> x ;
q.push(x) ;
} else if (op == 2) {
if (q.empty()) {
cout << "ERR_CANNOT_POP" << '\n' ;
} else {
q.pop() ;
}
} else if (op == 3) {
if (q.empty()) {
cout << "ERR_CANNOT_QUERY" << '\n' ;
} else {
cout << q.front() << '\n' ;
}
} else {
cout << q.size() << '\n' ;
}
}
return 0 ;
}stack (栈)
栈是一种先进后出 (LIFO) 的数据结构，并且只能在栈顶进行插入和删除操作。
定义
#include <stack>
stack<typename> name;常用函数
push(x)：将x压入栈（到栈顶）。pop()：将栈顶元素弹出。top()：返回栈顶元素。size()：返回栈中元素个数。empty()：返回栈是否为空。
练习
B3614 【模板】栈
题目描述
请你实现一个栈（stack），支持如下操作：
push(x)：向栈中加入一个数 。pop()：将栈顶弹出。如果此时栈为空则不进行弹出操作，输出Empty。query()：输出栈顶元素，如果此时栈为空则输出Anguei!。size()：输出此时栈内元素个数。
输入格式
本题单测试点内有多组数据。
输入第一行是一个整数 ，表示数据组数。对于每组数据，格式如下：
每组数据第一行是一个整数，表示操作的次数 。
接下来 行，每行首先由一个字符串，为 push，pop，query 和 size 之一。若为 push，则其后有一个整数 ，表示要被加入的数， 和字符串之间用空格隔开；若不是 push，则本行没有其它内容。
输出格式
对于每组数据，按照「题目描述」中的要求依次输出。每次输出占一行。
输入输出样例 #1
输入 #1
2
5
push 2
query
size
pop
query
3
pop
query
size输出 #1
2
1
Anguei!
Empty
Anguei!
0说明/提示
样例 1 解释
对于第二组数据，始终为空，所以 pop 和 query 均需要输出对应字符串。栈的 size 为 0。
数据规模与约定
对于全部的测试点，保证 ，且单个测试点内的 之和不超过 ，即 。保证 。
提示
- 请注意大量数据读入对程序效率造成的影响。
- 因为一开始数据造错了，请注意输出的
Empty不含叹号，Anguei!含有叹号。
#include <bits/stdc++.h>
#define int unsigned long long
//
//
//
using namespace std ;
void solve() {
stack<int> s ;
int n ;
cin >> n ;
while (n --) {
string ss ;
cin >> ss ;
if (ss == "push") {
int x ;
cin >> x ;
s.push(x) ;
} else if (ss == "pop") {
if (s.empty()) {
cout << "Empty" << '\n' ;
} else {
s.pop() ;
}
} else if (ss == "query") {
if (s.empty()) {
cout << "Anguei!" << '\n' ;
} else {
cout << s.top() << '\n' ;
}
} else { // "size"
cout << s.size() << '\n' ;
}
}
}
signed main() {
ios::sync_with_stdio(false) ; // 加速cin
cin.tie(0) ; // 解除cin和cout的绑定
int T ;
cin >> T ;
while (T --) {
solve() ;
}
return 0 ;
}set (集合)
Set 集合，是一个内部自动有序且不含重复元素的容器。若插入重复元素，会自动忽略该次插入操作，并且 set 里面的元素自动从小到大排序。
定义
#include <set>
set<typename> name;访问
Set 只能通过迭代器访问。
set<int> st;
// ... 插入元素 ...
// 1. 迭代器
set<int>::iterator it;
for(it = st.begin(); it != st.end(); it++) {
printf("%d", *it); // 可以通过 *it 来访问 set 里的元素
}
// 2. C++11
//
//
//
for(auto i : st) {
printf("%d", i);
}常用函数
insert(x)：将x插入 set 中，并自动递增排序和去重，时间复杂度为 O(logN)。find(x)：返回 set 中值为x的迭代器，时间复杂度为 O(logN)。如果找不到，返回s.end()。erase(it)：it为所需要删除元素的迭代器。时间复杂度为 O(1)。erase(x)：删除值为x的元素，时间复杂度为 O(logN)。erase(first, last)：删除区间[first, last)内的元素，first,last为迭代器。size()：返回 set 内元素个数。clear()：清空 set 中的所有元素。
练习
P1138 第 k 小整数
题目描述
现有 个正整数，要求出这 个正整数中的第 个最小整数（相同大小的整数只计算一次）。
输入格式
第一行为 和 ; 第二行开始为 个正整数的值，整数间用空格隔开。
输出格式
第个最小整数的值；若无解，则输出 NO RESULT。
输入输出样例 #1
输入 #1
10 3
1 3 3 7 2 5 1 2 4 6输出 #1
3说明/提示
，，正整数均小于 。
方法一 (使用 set):
set 自动排序和去重，非常适合这道题。
#include <bits/stdc++.h>
using namespace std ;
int main() {
set<int> s ;
int n, k ;
cin >> n >> k ;
for (int i = 1 ; i <= n ; i ++) {
int x ;
cin >> x ;
s.insert(x) ; // 自动去重和排序
}
if (k > s.size()) { // 如果k大于去重后的元素个数
cout << "NO RESULT" << '\n' ;
} else {
int pos = 1 ;
for (auto i : s) { // 遍历set
if (pos == k) {
cout << i << '\n' ;
break ;
}
pos ++ ;
}
}
return 0 ;
}方法二 (使用 vector + map 或 bool 数组去重):
手动去重，然后排序。
#include <bits/stdc++.h>
using namespace std ;
map<int, bool> vis ; // 用map标记是否出现过
int main() {
vector<int> a ;
int n, k ;
cin >> n >> k ;
for (int i = 1 ; i <= n ; i ++) {
int x ;
cin >> x ;
if (vis[x]) { // 如果出现过
continue ;
}
vis[x] = true ; // 标记为出现过
a.push_back(x) ;
}
if (k > a.size()) {
cout << "NO RESULT" << '\n' ;
} else {
sort(a.begin(), a.end()) ; // 排序
cout << a[k - 1] << '\n' ; // vector下标从0开始，第k个是 a[k-1]
}
return 0 ;
}