string

字符串，substr(起始位置，长度)、c_str()

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    string a = "yxc";
    a += "def";
    a += "c";
    // 从哪开始，返回多长（可省略）
    cout << a.substr(1, 2) << endl;
    printf("%s\n", a.c_str());
    return 0;
}

queue

队列，push()、front()、pop()，没有 clear()

int main() {
    queue<int> q;
    // ^ 没有clear的清空方法
    q = queue<int>();
    return 0;
}

deque

双端队列，支持随机访问 []。相当于加强版 vector。效率较低，不常用

front、back、push_back、pop_back、push_front、pop_front

priority_queue

优先队列，默认是大根堆。push()、top()、pop()。头文件queue

int main() {
    priority_queue<int> heap;
    // ^ 定义小根堆
    // 方式 1 每次插入负数
    // heap.push(-x);
    // 方式 2 多加两个参数
    priority_queue<int, vector<int>, greater<int>> heap;
    return 0;
}

stack

栈，push()、top()、pop()；与队列用法类似

set、map、multiset、multimap

基于平衡二叉树（红黑树），动态维护有序序列。begin、end支持++、--操作，返回前驱后继（有序序列的前一个数或后一个数）。增删改查大部分 \(O(log_2n)\)

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> s;
    multiset<int> ms;
    s.insert(1);
    // 找不到返回 end 迭代器
    s.find(1);
    // 返回某个数的个数
    s.count(1);
    // 删除所有等于这个数的节点 O(k + logn) k是x的个数
    ms.erase(1);
    // 删除这个迭代器
    ms.erase(ms.find(1));
    // 大于等于 x 的最小的数的迭代器，不存在返回end
    s.lower_bound(0);
    // 大于 x 的最小的数的迭代器，不存在返回end
    s.upper_bound(0);
    return 0;
}

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> a;
    a.insert({"abc", 123});
    // erase 跟 set 一样
    // 可以像数组一样用 map，时间复杂度 O(logn)
    count << a["abc"] << endl;
    // 也支持 lower_bound、upper_bound
    return 0;
}

unordered_

没有顺序，基于哈希表实现。与上面类似。但增删改查时间复杂度是 \(O(1)\)

不支持 lower_bound、upper_bound；不支持迭代器 ++ --

bitset

压位。C++里bool是1字节，如果要开1024个bool数组需要1024个字节，如果用压位，只需要128B

1e4 * 1e4 布尔矩阵，需要 1e8B，约100MB，题目给的 64MB，用压位可以缩小到12MB

int main() {
    bitset<10000> s;
    // ~ & | ^ >> << == != []
    // count() 返回有多少个 1
    // any() 判断是否至少有1个 1
    // none() 判断是否全为 0
    // set() 把所有位置1
    // set(k,v) 将第k位变成v
    // reset() 把所有位变成0
    // flip() 等价于 ~
    // flip(k) 把第k位取反
    return 0;
}