C++ STL 速查：vector / map / unordered_map
技术
2026.10.18
技术
C++ STL 速查：vector / map / unordered_map
把最常用的容器操作、复杂度和几个容易记混的 API 放在一页里，方便写题和写小工具时查。
本文目录
这篇是给自己用的速查，不追求覆盖所有 API。示例默认使用 C++20。
vector
#include <vector>
#include <algorithm>
std::vector<int> v = {3, 1, 2};
v.push_back(4); // 末尾插入
v.emplace_back(5); // 原地构造，通常比 push_back 少一次移动
v.pop_back(); // 删除末尾
v.reserve(100); // 预分配容量，避免多次扩容
v.resize(10); // 改变元素个数（会构造/析构）
std::sort(v.begin(), v.end());
auto it = std::lower_bound(v.begin(), v.end(), 3);
v.erase(v.begin()); // 删除第一个元素，O(n)
v.erase(v.begin() + 1, v.begin() + 3); // 删除区间 [1, 3)
| 操作 | 复杂度 | 备注 |
|---|---|---|
push_back / emplace_back |
均摊 O(1) | 扩容时可能 O(n) |
pop_back |
O(1) | 不释放容量 |
随机访问 v[i] |
O(1) | 不检查越界 |
insert / erase 中间 |
O(n) | 会移动后续元素 |
reserve(n) |
O(n) | 只改容量，不改 size |
map
std::map 是红黑树，按 key 有序，操作 O(log n)。
#include <map>
#include <string>
std::map<std::string, int> counts;
counts["apple"]++; // 不存在时会插入默认值 0
counts.insert({"banana", 2}); // 已存在则不会覆盖
counts.emplace("cherry", 3);
auto it = counts.find("apple");
if (it != counts.end()) {
it->second += 1;
}
for (const auto& [key, value] : counts) {
// 按 key 升序
}
operator[] 会插入元素，查存在性时优先用 find 或 contains（C++20）。
unordered_map
哈希表，平均 O(1)，不保证顺序。容易被卡哈希的题目里，可以换自定义哈希或改用 map。
#include <unordered_map>
#include <string>
std::unordered_map<std::string, int> index;
index.reserve(10000); // 预分配桶，减少 rehash
index["key"] = 1;
if (auto it = index.find("key"); it != index.end()) {
// it->second
}
| 容器 | 顺序 | 查找 | 插入 | 适用 |
|---|---|---|---|---|
map |
按 key 有序 | O(log n) | O(log n) | 需要有序遍历 |
unordered_map |
无序 | 平均 O(1) | 平均 O(1) | 只做映射 |
vector |
插入顺序 | O(n) | 末尾均摊 O(1) | 小规模或需要连续内存 |
常用算法
#include <algorithm>
#include <numeric>
#include <vector>
std::vector<int> v = {1, 2, 3, 4, 5};
std::sort(v.begin(), v.end());
std::reverse(v.begin(), v.end());
std::sort(v.begin(), v.end(), std::greater<>{});
bool has_three = std::binary_search(v.begin(), v.end(), 3);
auto it = std::find(v.begin(), v.end(), 4);
int sum = std::accumulate(v.begin(), v.end(), 0);
int max_value = *std::max_element(v.begin(), v.end());
std::erase_if(v, [](int x) { return x % 2 == 0; }); // C++20
写算法题时，先想清楚「需不需要有序」和「需不需要随机访问」，再选容器。大多数性能问题不是容器选错，而是选错之后没有测。[1]
这句话有点绝对。更准确地说：先选一个语义正确的容器，再用 profiler 决定要不要换。 ↩︎