【小码匠自习室】CSP-J/S复赛准备:STL复习(二)
注:本文部分内容源于厳選!C++ アルゴリズム実装に使える 25 の STL 機能【後編】,针对日文进行了翻译
标准库
标准库 | 说明 |
---|---|
vector | 动态数组 |
stack | 栈 |
queue | 队列 |
priority_queue | 优先队列 |
map | 有序映射 |
lower_bound | 二分查找 |
set | 集合 |
pair | 数据对 |
tuple | 元祖 |
vector
- 动态数组
- 时间复杂度:push_back、pop_back:O(1)
- vector用sort排序的时候,reverse也同样向下面处理
- 从头到尾排序: sort(a.begin(), a.end())
- 从开始的第l个到第r元素排序:sort(a.begin() + l, a.begin() + r)
程序 | 说明 |
---|---|
vector< int > a; | 定义vector变量: a |
a.push_back(x); | a的末尾插入值 |
a.pop_back(); | a的末尾的值被删除 |
a[i] | 获取a的第i个元素的值,是从0开始注意计数 |
a.size() | 获取a的元素数,返回整数 |
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 例1:对a进行各种操作(x1=105,x2=2,x3=146)
vector<int> a; // 此时a是空的
a.push_back(121); // 此时a={121}
a.push_back(105); // 此时a={112, 105}
a.push_back(193); // 此时a={12,105,193}
int x1 = a[1];
a.pop_back(); // 此时 a = {121, 105}
int x2 = a.size();
a.push_back(146); // 此时 a = {121, 105, 146}
int x3 = a[2];
cout << x1 << " " << x2 << " " << x3 << endl;
return 0;
}
stack
- 每次只取头部的值
程序 | 说明 |
---|---|
stack< int > a; | 定义stack变量为a |
a.push(x) | a的头部压入元素x |
a.pop() | 删除a的头部元素 |
a.top() | 获取a的头部元素 |
a.size() | 获取a的元素数 |
a.empty() | stack变量a的元素数0的时候返回:true,大于等于1的时候返回false |
#include <iostream>
#include <stack>
using namespace std;
int main() {
// 例1: a有各种操作(x1 = 156, x2 = 202, x3 = 117, x4 = 3, x5 = 0)
stack<int> a;
a.push(179); // 此时,从下到上 {179}
a.push(173); // 此时,从下到上 {179, 173}
a.push(156); // 此时,从下到上 {179, 173, 156}
int x1 = a.top();
a.pop(); // 此时,从下到上 {179, 173}
a.push(117); // 此时,从下到上 {179, 173, 117}
a.push(202); // 此时,从下到上 {179, 173, 117, 202}
int x2 = a.top();
a.pop(); // 此时,从下到上 {179, 173, 117}
int x3 = a.top();
int x4 = a.size();
int x5 = 0; if (a.empty()) x5 = 10000;
cout << x1 << " " << x2 << " "<< x3 << " " << x4 << " " << x5 << endl;
return 0;
}
queue
- 先进先出数据结构
- 时间复杂度:push、pop、front:O(1)
- 广度优先,最短路径经常利用该数据结构
程序 | 说明 |
---|---|
queue< int > a; | 定义queue类型变量a |
a.push(x) | a的末尾压入元素x |
a.pop() | 删除a最前面元素 |
a.front() | 获取a最前面元素 |
a.size() | 获取a的元素数 |
a.empty() | queue变量a的元素数0的时候返回:true,大于等于1的时候返回false |
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 例1: a有各种操作(x1 = 179, x2 = 173, x3 = 156, x4 = 3, x5 = 0 )
queue<int> a;
a.push(179); // 此时从前到后 {179}
a.push(173); // 此时从前到后 {179, 173}
a.push(156); // 此时从前到后{179, 173, 156}
int x1 = a.front();
a.pop(); // 此时从前到后 {173, 156}
a.push(117); // 此时从前到后 {173, 156, 117}
a.push(202); // 此时从前到后 {173, 156, 117, 202}
int x2 = a.front();
a.pop(); // 此时从前到后 {156, 117, 202}
int x3 = a.front();
int x4 = a.size();
int x5 = 0; if (a.empty()) x5 = 10000;
cout << x1 << " " << x2 << " "<< x3 << " " << x4 << " " << x5 << endl;
return 0;
}
priority_queue
- 管理有优先级的队列,每个元素都被赋予一个优先级,默认从小到大,用于控制元素被top获取的顺序
- priority_queue使用一个树结构追踪元素的相对位置。保证push()和pop()都是O(log(n))
- 与普通队列区别
- 队列中每个元素都与某个优先级相关联
- 具有最高优先级的元素将被首先删除
- 如果存在多个具有相同优先级的元素,则按照该元素在队列中顺序存储
- 常用方法
程序 | 说明 |
---|---|
a.push(x) | 添加元素x到优先级队列 |
a.emplace(x) | 优先队列的顶部插入一个新元素 |
a.pop() | 删除a中最小的元素(默认) |
a.top() | 返回a中最小的元素(默认) |
a.size() | 获取a中元素数 |
a.empty() | 变量a的元素数0的时候返回:true,大于等于1的时候返回false |
定义优先级队列语法
priority_queue<Type, Container, Functional>
- Type:数据类型
- Container:保存数据的容器
- Functional :元素比较方式
- 补充说明
- 在STL中,默认情况下(不加后面两个参数)是以vector为容器,以 operator< 为比较方式,所以在只使用第一个参数时,优先队列默认是一个最大堆,每次输出的堆顶元素是此时堆中的最大元素。
- 使用最小堆,则一般要把模板的三个参数都带进去
定义优先级队列
大顶堆(降序)
// 默认方式:构造一个空的优先队列(此优先队列默认为大顶堆)
priority_queue<int> Q1;
// 和上面的方式等同,int类型的元素、定义检索最大值的优先级队列
priority_queue<int, vector<int>, less<int>> Q2;
小顶堆(升序)
// int类型的元素,定义检索最小值的优先级队列
priority_queue<int, vector<int>, greater<int>> Q1;
// double类型的元素、定义检索最小值的优先级队列
priority_queue<double, vector<double>, greater<double>> Q2;
示例代码
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main() {
// 例1: Q有多种操作(x1 = 116, x2 = 110, x3 = 122, x4 = 2 )
priority_queue<int, vector<int>, greater<int>> Q;
Q.push(116); // 按最小顺序 {116}
Q.push(145); // 按最小顺序 {116, 145}
Q.push(122); // 按最小顺序 {116, 122, 145}
int x1 = Q.top();
Q.push(110); // 按最小顺序{110, 116, 122, 145}
int x2 = Q.top();
Q.pop(); // 按最小顺序{116, 122, 145}
Q.pop(); // 按最小顺序 {122, 145}
int x3 = Q.top();
int x4 = Q.size();
cout << x1 << " " << x2 << " " << x3 << " " << x4 << endl;
return 0;
}
map
- 有序映射
- 时间复杂度:访问元素O(logN)
程序 | 说明 |
---|---|
a[x] | 获取key=x的值或者设置key=x |
a.clear() | 初始化有序映射 |
定义
// 定义map,key:int, value:int
map<int, int> M1;
// 定义map,key:int, value:string
map<int, string> M2;
// 定义map,key:string, value:double
map<string, double> M3;
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<string, int> Map;
Map["qiita"] = 777;
Map["algorithm"] = 1111;
Map["competitive_programming"] = 1073741824;
cout << Map["algorithm"] << endl; // 输出1111
cout << Map["tourist"] << endl; // key不存在的时候,返回:0
return 0;
}
lower_bound
- 注意:对有序数组进行二分搜索,非有序数组会有问题
- 二分检索函数
- 对于数组a,a的第l到第r-1元素是按从小到大顺序排列,这时候:lower_bound(a+l, a+r, x) - a
- 返回从a[l]到a[r-1]中第一个大于或者等于x的索引
- 即、l≤i≤r−1、x≤a
_{i} 的最小的i的值
- 例如:a = {2, 3, 4, 6, 9, ...} 的时候,lower_bound(a, a + 5, 7) - a = 4
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
// 例1: a[i] < x的i有多少的计算(O(log N))
int N, a[100009];
cin >> N;
for (int i = 0; i < N; i++) cin >> a[i];
sort(a, a + N);
int x;
cin >> x;
cout << lower_bound(a, a + N, x) - a << endl;
return 0;
}
找不到值时索引如何返回?
- 默认返回
- 示例代码
int main() {
vector<int> v = {1, 2, 3, 4, 5};
int pos = *find(v.begin(), v.end(), 6);
cout << "算法【find】 索引 = " << pos << endl;
cout << "算法【find】 值 = " << v[pos] << endl;
pos = *lower_bound(v.begin(), v.end(), 6);
cout << "算法【lower_bound】 索引 = " << pos << endl;
cout << "算法【lower_bound】 值 = " << v[pos] << endl;
pos = *upper_bound(v.begin(), v.end(), 6);
cout << "算法【upper_bound】 索引 = " << pos << endl;
cout << "算法【upper_bound】 值 = " << v[pos] << endl;
}
- 执行结果
算法【find】 索引 = 0
算法【find】 值 = 1
算法【lower_bound】 索引 = 0
算法【lower_bound】 值 = 1
算法【upper_bound】 索引 = 0
算法【upper_bound】 值 = 1
upper_bound
注意:对有序数组进行二分搜索,非有序数组会有问题
二分检索函数
和lower_bound区别
- 执行结果
算法【find】 索引 = 2
算法【find】 值 = 3
算法【lower_bound】 索引 = 2
算法【lower_bound】 值 = 3
算法【upper_bound】 索引 = 3
算法【upper_bound】 值 = 4
- 返回第一个大于比较值的元素迭代器,注意是大于比较值
- 示例代码
int main() {
vector<int> v = {0, 2, 3, 4, 5};
int pos = *find(v.begin(), v.end(), 2);
cout << "算法【find】 索引 = " << pos << endl;
cout << "算法【find】 值 = " << v[pos] << endl;
pos = *lower_bound(v.begin(), v.end(), 2);
cout << "算法【lower_bound】 索引 = " << pos << endl;
cout << "算法【lower_bound】 值 = " << v[pos] << endl;
pos = *upper_bound(v.begin(), v.end(), 2);
cout << "算法【upper_bound】 索引 = " << pos << endl;
cout << "算法【upper_bound】 值 = " << v[pos] << endl;
}
binary_search
值v在有序队列中存在吗?
- 有该元素,返回:true
- 无该元素,返回:false
示例代码
int main() {
vector<int> v = {1, 2, 3, 5, 8};
bool isExist = binary_search(v.begin(), v.end(), 5);
cout << "算法【binary_search】 是否存在该值 = " << isExist << endl;
isExist = binary_search(v.begin(), v.end(), 6);
cout << "算法【binary_search】 是否存在该值 = " << isExist << endl;
}
- 执行结果
算法【binary_search】 是否存在该值 = 1
算法【binary_search】 是否存在该值 = 0
set
- 有序集合
- 集合元素的添加和删除是二分查找
- 两种
- set
- multiset
程序 | 说明 |
---|---|
a.insert(x) | 往集合a中插入元素x,如果集合中有相同的值不添加multiset中会添加 |
a.erase(x) | 从集合a中删除元素xmultiset中会删除所有元素x |
a.erase(y) | 从集合a删除迭代器y的元素xmultiset的时候,只有1个元素也删除 |
a.lower_bound(x) | 返回集合a中,大于等于a的最小元素的迭代器 |
a.clear() | 清空集合a |
#include <iostream>
#include <set>
using namespace std;
int main() {
// 例1: set有各种操作
set<int> Set;
Set.insert(37); // 此时set的元素 {37}
Set.insert(15); // 此时set的元素 {15, 37}
Set.insert(37); // 此时set的元素 {15, 37}
auto itr1 = Set.lower_bound(40);
if (itr1 == Set.end()) cout << "End" << endl;
else cout << (*itr1) << endl;
Set.erase(37); // 此时set的元素 {15}
Set.insert(46); // 此时set的元素 {15, 46}
auto itr2 = Set.lower_bound(20);
if (itr2 == Set.end()) cout << "End" << endl;
else cout << (*itr2) << endl;
// 例2: a[1],a[2],...,a[N]从小到打输出(如果有相同的元素,只输出一次)
set<int> b; int N, a[100009];
cin >> N;
for (int i = 1; i <= N; i++) cin >> a[i];
for (int i = 1; i <= N; i++) b.insert(a[i]);
auto itr = b.begin();
while (itr != b.end()) {
cout << (*itr) << endl;
itr++;
}
return 0;
}
pair
- 数据对
- pair有两个元素,定义pair变量为a
- 第一个元素:a.first
- 第二个元素:a.second
- 两个pair变量比较大小
- 第一个元素小的小
- 第一个元素相等,比较第二个元素,第二个元素小的小
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
using namespace std;
int N;
pair<int, string> a[100009];
int main() {
// 例1:输入N个人的成绩和姓名、按成绩搞的顺序降序排列
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a[i].second; // 输入名字
cin >> a[i].first; // 输入成绩
}
sort(a, a + N, greater<pair<int, string>>());
for (int i = 0; i < N; i++) {
cout << "Name = " << a[i].second << ", Score = " << a[i].first << endl;
}
return 0;
}
tuple
具有大于等于3个以上元素组成的数据组
- pair:两个元素组成
- tuple:大于两个元素组成,一个或者两个也可以
- 定义:tuple< v1,v2,...,vn > a, 例如想定义由int类型, int类型, string类型组成的tuple变量、则定义
tuple< int,int,string > a;
- 生成tuple类型:make_tuple(a1,a2,...,an),参照示例代码
- 比较:同pair,先第一个,在第二个,在第三个
#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 例1: 定义tuple
tuple<int, int, int> A;
cin >> get<0>(A) >> get<1>(A) >> get<2>(A);
cout << get<0>(A) + get<1>(A) + get<2>(A) << endl;
// 例2: vector也可以用tuple类型
vector<tuple<double, int, int>> B; int N;
cin >> N;
for (int i = 1; i <= N; i++) {
double p1; int p2, p3;
cin >> p1 >> p2 >> p3;
B.push_back(make_tuple(p1, p2, p3));
}
sort(B.begin(), B.end());
for (int i = 0; i < N; i++) printf("%.5lf %d %d\n", get<0>(B[i]), get<1>(B[i]), get<2>(B[i]));
return 0;
}
建议
- 如果可能,优先考虑使用容器:vector;
- 优先选择连续存储的数据结构;
- 如果需要在大量数据中快速查找元素,使用无序容器;
- 实现方式区别:
- map通常实现:红黑树
- unordered_map:哈希表
- 范围检查:
- 需要保证范围检查时用:at()
- 不需要保证范围检查时用:[]
参考资料
- 厳選!C++ アルゴリズム実装に使える 25 の STL 機能【前編】
- https://qiita.com/e869120/items/518297c6816adb67f9a5
- 厳選!C++ アルゴリズム実装に使える 25 の STL 機能【後編】
- https://qiita.com/e869120/items/702ca1c1ed6ff6770257
END