C++中常见的STL用法 + 奇技淫巧

参考: OI-Wiki STL, 适合作为 TL;DR 版本

STL 基础模板

(1) vector, 变长数组

size()                   // 返回元素个数
empty()                  // 返回是否为空
clear()                  // 清空
front() / back()         // 首/末位元素       
push_back() / pop_back() //
begin() / end()          // 首/末位迭代器
vec[i]                   // 索引
// 支持比较运算，按字典序

(2) pair<int, int>, 二位元组

first       // 第一个元素
second      // 第二个元素
// 支持比较运算: 默认以first为第一关键字，以second为第二关键字（字典序）
// sort会默认比较

(3) string, 字符串

size()      // 返回字符串长度
empty()     // 判定是否为空
clear()     // 清空字符串
substr(起始下标，子串长度)  // 截下并返回子串

(4) queue, 队列

size()
empty()
push()    // 向队尾插入一个元素
pop()     // 弹出队头元素
front()   // 返回队头元素
back()    // 返回队尾元素

(5) priority_queue, 优先队列，默认是大根堆，即最大元素在堆顶 (优先队列堆顶一般存储优先级最大的元素，故默认值: "最大者" 优先级最高)

size()
empty()
push()   // 插入一个元素
top()    // 返回堆顶元素
pop()    // 弹出堆顶元素
// 定义成小根堆的方式, 需要一个容器来支撑它
priority_queue<int, vector<int>, greater<int>> q;

(6) stack, 栈

size()
empty()
push()  // 向栈顶插入一个元素
top()   // 返回栈顶元素
pop()   // 弹出栈顶元素

(7) deque, 双端队列

size()
empty()
clear()
front() / back()
push_back() / pop_back()     // 队尾元素的push / pop
push_front() / pop_front()   // 队首元素的push / pop
begin() / end()
deq[i]                       // 索引

(8) set, map, multiset, multimap

• 如果需要有序性和范围查询，用 map/set 系列
• 如果只需要快速查找而不关心顺序，用 unordered_ 开头的容器

size()
empty()
clear()
begin()/end()
++, -- // 返回前驱和后继，时间复杂度 O(logn)

// 基于红黑树 (平衡二叉树)

set / multiset
    insert()  // 插入一个数
    find()    // 查找一个数
    count()   // 返回某一个数的个数
    erase()
        // (1) 输入是一个数x，删除所有x 复杂度: O(k + logn)
        // (2) 输入一个迭代器，删除这个迭代器
    lower_bound() / upper_bound()
        lower_bound(x)  // 返回大于等于x的最小的数的迭代器
        upper_bound(x)  // 返回大于x的最小的数的迭代器

map / multimap
    insert()  // 插入的数是一个pair
    erase()   // 输入的参数是pair或者迭代器
    find()
    map[i]  // 注意, map支持索引, 但multimap不支持索引操作。时间复杂度是 O(logn)
    lower_bound() / upper_bound()

// 基于哈希表

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    // 哈希表中元素没有顺序关系
    // 和上面类似, 但是更快, 增删改查的时间复杂度是 O(1)
    // 不支持 lower_bound() / upper_bound(), 迭代器的++/--

(9) bitset, 圧位

bitset<10000> s;

~, &, |, ^
>>, <<
==, !=
s[i]       // 第i位

count()    // 返回有多少个1

any()      // 判断是否至少有一个1
none()     // 判断是否全为0

set()      // 把所有bit置成1
set(k, v)  // 将第k位变成v
reset()    // 把所有bit变成0
flip()     // 等价于~
flip(k)    // 把第k位取反

自定义排序

(1) 默认情况:

vector<int> arr;
sort(arr + 1, arr + n + 1);
// sort(初位置，末位置的下一位) 由于我们读入时是从arr[1]开始储存的，所以初位置是arr + 1
// 待排序的区间为左闭右开区间，[i, j）

vector<int> arr;
sort(arr.begin(), arr.end()); // 使用迭代器进行排序

(2) 自定义升序:

vector<int> arr;

bool cmp(const int &u, const int &v) // 自定义排序函数
{
    return u > v;
}

sort(arr + 1, arr + n + 1, cmp); // cmp回调函数

(3) 基于回调函数为结构体排序:

struct Q{
    int x;
    int d;
    int c;
    int g;
    int s;
};

//将两个结构体分别传入函数
bool cmp(Q f1,Q f2)
{
    if (f1.g < f2.g) return true;
    else if (f1.g==f2.g && f1.s>f2.s) return true;
    else if (f1.g==f2.g && f1.s==f2.s && f1.d>f2.d) return true;
    else if (f1.g==f2.g && f1.s==f2.s && f1.d==f2.d && f1.x<f2.x) return true;
    return false;
}

// ...

Q f[N];
sort(f, f+n, cmp);

(4) 基于堆实现结构体排序:

大根堆:

// 初始化
priority_queue<int> heap;
// 插入元素
heap.push(3);
// 访问堆顶元素
heap.top()
// 弹出堆顶元素
heap.pop()

小根堆:

// 初始化
priority_queue<int, vector<int>, greater<int>> heap;

基于堆为结构体排序:

struct Node {
    int val;
    bool operator>(const Node& other) const {
        // 如果当前节点的 val 值大于另一个节点的 val 值
        // 则当前节点"大于"另一个节点
        return val > other.val;
    }
};

priority_queue<Node, vector<Node>, greater<Node>> custom_heap;
// 创建了一个按 val 值升序排列的小根堆, 堆顶元素总是当前所有元素中 val 值最小的

加速输入输出

#include <iostream>
using namespace std;
int main() 
{
    // Preprocess
    ios::sync_with_stdio(false);
    cin.tie(0);
    // IO ...
}

头文件

acwing

万能头

include<bits/stdc++.h>

cstring

include<cstring>
// (1) memset: 下面的例子确保做整型运算不会爆
memset(arr, 0, sizeof(arr));     // 初始化成0
memset(arr, -1, sizeof(arr));    // 初始化成-1
memset(arr, 0x3f, sizeof(arr));  // 初始化成 +_INF
memset(arr, 0xc0, sizeof(arr));  // 初始化成 -_INF

// (2) string
string s, str; // 声明变量
str = "asdfghjkl" // 直接赋值
cin >> s; // 遇到空格结束输入
getline(cin, s); // 遇到换行结束输入 用于要输入空格的情况
cout << s; // 输出
int len = s.length(); // 得到字符串长度
swap(s, str);// 交换 s str

algorithm

#include<algorithm>
swap() 
lower_bound() & upper_bound()
reverse()
max() & min()
unique()
find()
erase()
substr()

math

abs(x)            // 绝对值
exp(x)            // 以e为底的指数函数
log(x)            // 以e为底的对数函数
pow(底数, 指数)    // 幂函数
sqrt(x)          // 开平方
ceil(x)          // 上取整
floor(x)         // 下取整
round(x)         // 四舍五入

STL

#include<vector> // vector
#include<stack>  // stack
#include<queue>  // queue, priority_queue
#include<set>    // set
#include<map>    // map