麦地

Back

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。


二、构造与比较器#


三、访问元素: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_range
cpp

at 不会插入,但竞赛一般不用异常处理流程,更多用 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。

四、插入与更新#

语义对照表:

操作 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#

注意 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, 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';
cpp

2. 坐标 → 编号的动态映射#

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;     // 不存在才分配新编号
};
cpp

3. 按键找最近值#

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));
}
cpp

4. map 套 vector:一个 key 挂多个值#

map<string, vector<int>> groups;
groups[s].push_back(x);       // 自动创建空 vector 再追加
// 通常比 multimap 更好用
cpp

5. 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。

十二、高频错误清单#

  1. 用 m[k] 做纯查询 → key 不存在时隐式插入,污染 map、改变 size。
  2. find 后没判 end() 就用 it->second → 未定义行为。
  3. 以为 insert 会覆盖旧值 → 不会,覆盖用 m[k]=v 或 insert_or_assign。
  4. 试图修改 key:it->first = x → 编译错误,key 是 const。
  5. 遍历时 auto [k,v] 不加引用 → 每个键值对被复制。
  6. 取 m.begin() / --it 前没判空判边界 → 未定义行为。
  7. 降序 map 里套用升序的二分语义 → lower_bound 含义已反转。
  8. 把 m[k] 当成”第 k 个元素” → map 没有顺序下标概念,k 是 key。
  9. 大 key(长 string)频繁比较 → 每次 O(log n) 都带 key 比较成本,注意常数。

十三、一页速记#

五句口诀:

  1. map = key 唯一 + 按键有序的键值对,红黑树,操作 O(log n)。
  2. m[k] 会隐式插入,纯查询用 find/count。
  3. insert 不覆盖,覆盖用 m[k]=v 或 insert_or_assign。
  4. key 不可改、value 可改;遍历用 auto &[k, v]。
  5. 要前驱后继、有序遍历用 map;只要快查用 unordered_map。
Comment seems to stuck. Try to refresh?✨