【小码匠自习室】CSP-J/S复赛准备：STL复习（二）

小码匠

发布于 2022-12-06 10:57:50

1.2K0

注：本文部分内容源于厳選！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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-10-18，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

c++

本文分享自小码匠和老码农微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

c++

登录后参与评论

0 条评论

热度

【小码匠自习室】CSP-J/S复赛准备：STL复习（二）

【小码匠自习室】CSP-J/S复赛准备：STL复习（二）

标准库

vector

stack

queue

priority_queue

定义优先级队列语法

定义优先级队列

map

定义

lower_bound

upper_bound

binary_search

set

pair

tuple

建议

参考资料

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐