算法竞赛中最常用的 C++ STL 组件。持续更新。
完整文档见 cppreference.com。
| 操作 | 说明 | 复杂度 |
|---|---|---|
| vector<int> v | 空 vector | O(1) |
| vector<int> v(n) | n 个 0 | O(n) |
| vector<int> v(n, x) | n 个 x | O(n) |
| v.push_back(x) | 末尾插入 x | 均摊 O(1) |
| v.pop_back() | 删除末尾元素 | O(1) |
| v.size() | 元素个数 | O(1) |
| v[i] | 下标访问（不检查） | O(1) |
| v.clear() | 清空 | O(n) |
| v.back() | 最后一个元素 | O(1) |
| string s | 空字符串 | O(1) |
| s += "abc" | 追加（比 + 快） | O(m) |
| s.substr(i, len) | 子串 | O(len) |
| s.find("abc") | 返回下标，未找到返回 npos | O(n) |
| s == t | 判等 | O(n) |
| s[i] | 字符访问 | O(1) |
| stack<int> s | 空栈 | O(1) |
| s.push(x) | 入栈 | O(1) |
| s.pop() | 出栈（不返回值） | O(1) |
| s.top() | 栈顶 | O(1) |
| s.empty() | 是否空 | O(1) |
| queue<int> q | 空队列 | O(1) |
| q.push(x) | 入队 | O(1) |
| q.pop() | 出队（不返回值） | O(1) |
| q.front() | 队首 | O(1) |
| q.back() | 队尾 | O(1) |
| 操作 | 说明 | 复杂度 |
|---|---|---|
| set<int> s | 有序集合，无重复 | — |
| map<int,int> m | 有序键值对 | — |
| s.insert(x) | 插入 | O(log n) |
| s.erase(x) | 删除 | O(log n) |
| s.count(x) | 是否存在（返回 0 或 1） | O(log n) |
| m[key] = val | 赋值/插入 | O(log n) |
| s.begin() / s.end() | 迭代器首/尾后 | O(1) |
| unordered_set<int> us | 无序集合 | — |
| us.insert(x) | 插入 | 平均 O(1) |
| us.count(x) | 是否存在 | 平均 O(1) |
| us.erase(x) | 删除 | 平均 O(1) |
unordered_ 就别用 set/map——哈希容器平均更快。但当需要「按大小顺序遍历」时，必须用有序的 set/map。
| sort(v.begin(), v.end()) | 升序排序 | O(n log n) |
| sort(v.rbegin(), v.rend()) | 降序排序 | O(n log n) |
| binary_search(v.begin(), v.end(), x) | 是否存在 x（需有序） | O(log n) |
| lower_bound(v.begin(), v.end(), x) | 第一个 ≥ x 的位置 | O(log n) |
| upper_bound(v.begin(), v.end(), x) | 第一个 > x 的位置 | O(log n) |
| reverse(v.begin(), v.end()) | 反转 | O(n) |
| min(a, b) / max(a, b) | 两个值的最值 | O(1) |
| min_element(v.begin(), v.end()) | 返回最小值的迭代器 | O(n) |
| max_element(v.begin(), v.end()) | 返回最大值的迭代器 | O(n) |
*min_element(v.begin(), v.end()) 加 * 取到值本身。
| accumulate(v.begin(), v.end(), 0) | 求和，0 是初始值 | O(n) |
| accumulate(v.begin(), v.end(), 0LL) | 用 long long 防溢出 | O(n) |
速查表持续更新中 · 最后更新 2024 夏