C++ map 算法竞赛笔记#
定位:
map<K, V>是有序键值映射:key 唯一、按 key 自动排序,底层通常是红黑树。 插入、查找、删除均为O(log n),遍历时按键升序。它是”需要有序的unordered_map”。
#include <map>
#include <bits/stdc++.h> // 竞赛一把梭cpp一、核心特性#
| 特性 | 说明 |
|---|---|
| 键值对存储 | 元素类型是 pair<const K, V> |
| 按键有序 | 遍历顺序 = key 的排序顺序,与插入顺序无关 |
| 键唯一 | 重复插入同一 key 不会新增元素,只可能修改 value |
| 键不可改 | first 是 const;value 可以随便改 |
| 底层结构 | 平衡二叉搜索树(通常是红黑树) |
| 无下标随机访问 | m[k] 是按键访问,不是按下标访问 |
| 支持二分 | lower_bound / upper_bound 都是按键查找 |
与 set 的关系:map ≈ 每个 key 上额外挂了一个 value 的 set。
二、构造与比较器#
map<string, int> m1; // 默认 key 升序
map<int, int, greater<int>> m2; // key 降序
map<int, int> m3 = {{1, 10}, {2, 20}}; // 列表初始化
// pair / tuple 作 key:默认字典序
map<pair<int,int>, int> mp;
mp[{1, 2}] = 100;
// 自定义比较器(严格弱序)
struct Cmp {
bool operator()(const string& a, const string& b) const {
if (a.size() != b.size()) return a.size() < b.size(); // 先按长度
return a < b; // 再按字典序
}
};
map<string, int, Cmp> cm;cpp三、访问元素:operator[]、at、find#
1. operator[]:方便但有隐式插入#
map<string, int> m;
m["apple"] = 3; // 不存在则插入 {apple, 0},再赋值为 3
int x = m["apple"]; // 3
int y = m["banana"]; // 不存在!自动插入 {banana, 0},返回 0
// 此时 m.size() 已经 +1,哪怕你只是想"查一下"cpp规则:m[k] 在 key 不存在时会自动插入默认值。只读查询时这是污染源。
2. at:安全读取,不存在抛异常#
int x = m.at("apple"); // 3
// m.at("ghost"); // 不存在则抛 out_of_rangecppat 不会插入,但竞赛一般不用异常处理流程,更多用 find。
3. find / count:只查询不插入(推荐)#
auto it = m.find("apple");
if (it != m.end()) {
cout << it->first << ' ' << it->second; // apple 3
}
if (m.count("apple")) { /* 存在 */ } // 结果只有 0 或 1
if (m.contains("apple")) { /* C++20 */ }cpp选择规则:
- 需要”读或写”且确定要默认值 →
m[k]; - 只想查询是否存在 →
find/count; - 不存在时想报错 →
at。
四、插入与更新#
map<string, int> m;
// 1. operator[]:插入或覆盖
m["a"] = 1;
m["a"] = 10; // 覆盖旧值
// 2. insert:key 已存在时不覆盖
m.insert({"b", 2});
m.insert({"b", 99}); // 失败,b 仍为 2
auto [it, ok] = m.insert({"c", 3}); // ok 表示是否新插入
// 3. emplace:原位构造,语义同 insert(不覆盖)
m.emplace("d", 4);
// 4. try_emplace(C++17):不存在才构造,且不覆盖
m.try_emplace("e", 5);
m.try_emplace("e", 50); // 无效,e 仍为 5
// 5. insert_or_assign(C++17):存在则覆盖,不存在则插入
m.insert_or_assign("e", 50); // e 变为 50cpp语义对照表:
| 操作 | key 不存在 | key 已存在 |
|---|---|---|
m[k] = v |
插入并赋值 | 覆盖 |
insert({k,v}) / emplace |
插入 | 不改动 |
try_emplace(k, v) |
插入 | 不改动(且不会多余构造 value) |
insert_or_assign(k, v) |
插入 | 覆盖 |
计数场景最常见写法:
map<string, int> cnt;
string s;
while (cin >> s) cnt[s]++; // 不存在则插入 0 再 ++,简洁且正确cpp五、遍历与修改 value#
map<string, int> m = {{"apple", 3}, {"banana", 5}, {"cat", 2}};
// C++17 结构化绑定:按键升序输出
for (const auto &[key, value] : m)
cout << key << ' ' << value << '\n';
// 修改 value:用引用
for (auto &[key, value] : m) value *= 2;
// 错误:key 是 const,不能修改
// for (auto &[key, value] : m) key = "x"; // 编译错误
// 反向遍历
for (auto it = m.rbegin(); it != m.rend(); ++it)
cout << it->first << '\n';
// 传统迭代器写法
for (auto it = m.begin(); it != m.end(); ++it)
cout << it->first << ' ' << it->second;cpp注意 for (auto [k, v] : m) 不加 & 会复制每个键值对,大 value 时浪费性能。
六、删除与清空#
m.erase("apple"); // 按 key 删除,返回删除个数(0 或 1)
auto it = m.find("banana");
if (it != m.end()) m.erase(it); // 按迭代器删除,先判 find != end
m.erase(m.begin()); // 删除最小 key
m.clear(); // 清空
m.size();
m.empty();cpp与 multiset 不同:map 的 key 唯一,erase(key) 最多删一个,没有”删全部副本”的坑。
七、按键二分:前驱与后继(竞赛核心)#
map<int, string> m = {{1, "a"}, {3, "b"}, {7, "c"}, {9, "d"}};
auto it = m.lower_bound(5); // 第一个 key >= 5 → {7, "c"}
auto jt = m.upper_bound(7); // 第一个 key > 7 → {9, "d"}
// 严格前驱:最后一个 key < x
auto it2 = m.lower_bound(7);
if (it2 != m.begin()) {
--it2; // {3, "b"}
}
// 边界检查必须完整
if (it == m.end()) { /* 所有 key 都 < 5 */ }
// 最小 / 最大 key(先判空)
if (!m.empty()) {
auto minPair = *m.begin();
auto maxPair = *m.rbegin();
}cpp降序 map<int, V, greater<int>> 中,lower_bound 语义反转为”第一个 key ≤ x”。
八、复杂度表#
| 操作 | 复杂度 |
|---|---|
m[k] / at / find / count |
O(log n) |
insert / emplace / try_emplace / insert_or_assign |
O(log n) |
erase(key) |
O(log n) |
erase(迭代器) |
均摊 O(1) |
lower_bound / upper_bound |
O(log n) |
取 begin / rbegin |
O(1) |
| 遍历全部 | O(n) |
注意:key 是 string 等复杂类型时,每次比较还有 key 本身的比较代价。
九、竞赛应用模板#
1. 有序频率表 / 动态字典#
map<string, int> cnt;
for (int i = 0; i < n; i++) {
string s; cin >> s;
cnt[s]++;
}
// 按字典序输出统计结果
for (auto &[s, c] : cnt) cout << s << ' ' << c << '\n';cpp2. 坐标 → 编号的动态映射#
map<long long, int> id;
int nxt = 0;
auto getId = [&](long long x) {
auto it = id.find(x);
if (it != id.end()) return it->second;
return id[x] = ++nxt; // 不存在才分配新编号
};cpp3. 按键找最近值#
map<int, int> m; // key: 位置,value: 数据
// 查询与 x 最接近的 key
auto it = m.lower_bound(x);
long long best = LLONG_MAX;
if (it != m.end()) best = min(best, (long long)abs(it->first - x));
if (it != m.begin()) {
auto pre = prev(it);
best = min(best, (long long)abs(pre->first - x));
}cpp4. map 套 vector:一个 key 挂多个值#
map<string, vector<int>> groups;
groups[s].push_back(x); // 自动创建空 vector 再追加
// 通常比 multimap 更好用cpp5. pair 作 key:二维状态记忆化#
map<pair<int,int>, long long> memo;
long long dfs(int i, int j) {
if (baseCase) return ...;
auto key = make_pair(i, j);
auto it = memo.find(key);
if (it != memo.end()) return it->second; // 命中缓存
return memo[key] = 计算结果; // 记忆化
}cpp十、迭代器失效规则#
| 操作 | 影响 |
|---|---|
insert / emplace 等 |
不失效任何迭代器 |
erase(迭代器) |
仅被删元素失效 |
erase(key) |
仅该 key 的元素失效 |
clear |
全部失效 |
| 无 rehash | 不像 unordered_map 有扩容失效 |
遍历时安全删除:
for (auto it = m.begin(); it != m.end();) {
if (it->second == 0) it = m.erase(it);
else ++it;
}cpp十一、容器选型#
| 需求 | 选择 |
|---|---|
| 键值映射 + 需要 key 有序 | map |
| 键值映射 + 只要快速查询 | unordered_map(平均 O(1)) |
| 一个 key 多个 value | multimap 或 map<K, vector<V>> |
| key 是连续小整数 | vector<V> 直接当下标映射,最快 |
| 只要 key 不要 value | set |
| 需要按 value 找 key | 反向再建一个 map,或换数据结构 |
map vs unordered_map:
- 遍历有序、需要前驱后继、担心哈希攻击 →
map; - 纯查询更新、数据量大、追求常数小 →
unordered_map。
十二、高频错误清单#
- 用
m[k]做纯查询 → key 不存在时隐式插入,污染 map、改变 size。 find后没判end()就用it->second→ 未定义行为。- 以为
insert会覆盖旧值 → 不会,覆盖用m[k]=v或insert_or_assign。 - 试图修改 key:
it->first = x→ 编译错误,key 是 const。 - 遍历时
auto [k,v]不加引用 → 每个键值对被复制。 - 取
m.begin()/--it前没判空判边界 → 未定义行为。 - 降序 map 里套用升序的二分语义 →
lower_bound含义已反转。 - 把
m[k]当成”第 k 个元素” → map 没有顺序下标概念,k 是 key。 - 大 key(长 string)频繁比较 → 每次
O(log n)都带 key 比较成本,注意常数。
十三、一页速记#
map<K, V> m;
// 增 / 改
m[k] = v; // 插入或覆盖
m.insert({k, v}); // 已存在则不覆盖
m.try_emplace(k, v); // 不存在才构造(C++17)
m.insert_or_assign(k, v); // 存在则覆盖(C++17)
// 查
m.find(k); // 返回迭代器,不插入
m.count(k); // 0 或 1
m.at(k); // 不存在抛异常
// m[k] 只读查询会隐式插入,慎用
// 删
m.erase(k);
auto it = m.find(k);
if (it != m.end()) m.erase(it);
// 有序遍历
for (auto &[k, v] : m) { } // 按键升序
// 按键二分
m.lower_bound(k); // 首个 key >= k
m.upper_bound(k); // 首个 key > k
// 计数
cnt[s]++;cpp五句口诀:
map= key 唯一 + 按键有序的键值对,红黑树,操作O(log n)。m[k]会隐式插入,纯查询用find/count。insert不覆盖,覆盖用m[k]=v或insert_or_assign。- key 不可改、value 可改;遍历用
auto &[k, v]。 - 要前驱后继、有序遍历用
map;只要快查用unordered_map。