C++中的map使用方法详解

前言std::map是 C 标准库的有序关联容器键唯一、按比较器规定的顺序排列、底层通常是一棵平衡二叉搜索树。它最常被误解的地方有三个以为遍历顺序等于插入顺序以为operator[]只是读不知道它在键不存在时会插入一个默认值以为it-first可以像普通成员一样修改结果编译报错。这三个误解都源自同一个设计map的元素是std::pairconst Key, T键是常量因为一旦允许改键红黑树的有序结构就被破坏了。理解这一点operator[]为什么要默认构造、find为什么返回迭代器而不是值、删除为什么只能用erase就都顺了。本文按插入与访问 → 查找与删除 → 比较器与遍历的顺序讲重点放在接口的返回值、失效规则和几个容易写错的边界。示例以 C17 为基准contains这类 C20 才有的接口会单独标注。一、结构特征与选型std::mapKey, T, Compare, Allocator的四个模板参数里日常只用前两个。它的核心承诺是键唯一同一个键最多一个元素需要重复键用std::multimap。有序按Compare严格弱序排列遍历时从小到大。节点式存储每个元素单独分配节点插入删除不会让其他元素的引用、指针失效。对数复杂度查找、插入、删除都是 O(log n)。容器顺序查找内存适用std::map按键排序O(log n)每节点额外指针与颜色位需要有序遍历、范围查询std::unordered_map无序平均 O(1)最坏 O(n)桶数组 节点只做精确查找std::multimap按键排序O(log n)同 map允许重复键如果只需要按键快速查unordered_map通常更合适需要lower_bound、按序遍历、稳定的引用才选map。注意无序容器的遍历顺序标准不保证不能依赖。二、插入与访问map的插入接口有五个返回值与语义各不相同混用会产生不同的默认构造行为。// 适用于 C17#include map#include stringstd::mapstd::string, int m;m[apple] 1; // 不存在则插入 {apple, 0} 再赋值m.insert({banana, 2}); // 键已存在则不插入m.emplace(cherry, 3); // 原地构造m.try_emplace(date, 4); // C17键存在时不构造 valuem.insert_or_assign(apple, 10); // C17存在则赋值几个接口的差异值得记牢operator[]要求T可默认构造。键不存在时先插入T{}再返回引用因此用它查会悄悄改变容器大小。insert与emplace返回std::pairiterator, boolbool表示是否真正插入。键已存在时迭代器指向已有元素值不变。try_emplace与emplace的区别在于键已存在时emplace仍会构造实参再丢弃try_emplace不会构造 mapped 值。对昂贵的T这个差别有意义。insert_or_assign是有则改、无则插不要求T默认构造。at(key)在键不存在时抛std::out_of_range是只读访问的推荐写法const map上不能用operator[]。// 适用于 C17int ref m[apple]; // 键不存在时会插入ref 1;int v m.at(banana); // 不存在则抛异常不会插入auto it m.find(cherry); // 不存在返回 m.end()if (it ! m.end()) {it-second 30; // 值可改// it-first x; // 错误键是 const}map的迭代器解引用得到std::pairconst Key, T所以it-first的类型是const Keyit-second可写。这不是实现细节而是类型系统强制的约束。三、查找、范围与删除精确查找用find或count需要第一个不小于某键的元素用lower_bound需要范围用equal_range。这些接口都依赖比较器因此要求键之间可比较。// 适用于 C17#include iostreamauto it m.lower_bound(b); // 第一个键 b 的元素auto up m.upper_bound(b); // 第一个键 b 的元素auto range m.equal_range(b); // {lower_bound, upper_bound}for (auto p range.first; p ! range.second; p) {std::cout p-first p-second \n;}std::size_t n m.erase(apple); // 返回删除的元素个数0 或 1删除有三种重载返回类型不同重载返回说明erase(key)size_type删除的个数map为 0 或 1erase(iterator)指向被删元素之后的迭代器C11 起循环中安全使用erase(first, last)指向last的迭代器区间删除map是节点式容器插入不会让其他元素的迭代器、引用、指针失效删除只让指向被删元素的迭代器失效。这一点与std::vector的扩容全失效形成鲜明对比也是map常被用来存放地址稳定的对象的原因。循环删除要写成先取后继再删// 适用于 C17for (auto it m.begin(); it ! m.end(); ) {if (it-second 0) {it m.erase(it); // C11 起 erase 返回下一个位置} else {it;}}不要在erase(it)之后再去it那个迭代器已经失效自增是未定义行为。四、自定义比较器与遍历顺序默认比较器是std::lessKey对内置类型就是。自定义比较器必须满足严格弱序strict weak ordering不可自反、传递、且不可比较关系可传递。写成会破坏不可自反性std::map的行为随之变成未定义。// 适用于 C17#include algorithm#include cctype#include map#include stringstruct CaseInsensitiveLess {bool operator()(const std::string a, const std::string b) const {return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),[](unsigned char x, unsigned char y) {return std::tolower(x) std::tolower(y);});}};std::mapstd::string, int, CaseInsensitiveLess ci;比较器是容器类型的一部分两个使用不同比较器的map是不同类型不能互相赋值。比较器对象会被容器复制保存如果它持有状态要保证复制后语义一致。遍历顺序由比较器决定与插入顺序无关// 适用于 C17for (const auto kv : m) {// kv.first 递增排列}需要按值排序时不能直接对map用std::sort迭代器是双向的且元素键不可改应把元素复制到std::vectorstd::pairKey, T再排序或者维护一个反向索引。常见坑点1. 用operator[]做只读查找// ❌ 键不存在时插入默认值容器变大if (m[key] 0) { /* ... */ }// ✅ 查找用 find 或 atauto it m.find(key);if (it ! m.end() it-second 0) { /* ... */ }2. 在const map上用operator[]// ❌ 编译错误const 版本没有 operator[]int v cm[key];// ✅ 用 at可能抛异常或 findint v cm.at(key);3. 试图修改键// ❌ 键类型是 const Key编译错误it-first new;// ✅ 删旧插新m.erase(it);m.emplace(new, value);4. 比较器写成// ❌ 违反严格弱序行为未定义return a b;// ✅ 只用小于return a b;5. 循环里erase后继续自增// ❌ 迭代器已失效自增是未定义行为for (auto it m.begin(); it ! m.end(); it) {if (bad(*it)) m.erase(it);}// ✅ 用 erase 的返回值推进for (auto it m.begin(); it ! m.end(); ) {it bad(*it) ? m.erase(it) : std::next(it);}6. 以为遍历顺序是插入顺序// ❌ 依赖插入顺序做输出结果按键排序for (const auto kv : m) print(kv);// ✅ 需要插入顺序就另存一个 vector 记录键std::vectorstd::string order;7. 用emplace构造昂贵的值却忽略键已存在// ❌ 即使键存在实参也会被构造后丢弃m.emplace(key, BigObject(args...));// ✅ C17 用 try_emplace键存在时不构造m.try_emplace(key, args...);8. 在map上保存元素的地址后又erase了它// ❌ 指向被删元素的指针/引用悬垂T* p m[key];m.erase(key);// ✅ 删除后不再使用该地址其他元素的地址不受影响总结操作推荐接口关键点插入不覆盖insert/emplace/try_emplace返回pairiterator,bool插入或覆盖insert_or_assignC17不要求默认构造读取不存在则抛at可用于const map读取不存在则插operator[]会改变容器大小查找find/count返回迭代器或个数范围lower_bound/upper_bound依赖比较器删除erase按迭代器删除返回下一个位置std::map的接口不算多真正要记住的是三条约束键是常量、遍历按比较器排序、operator[]会插入。把查找和访问分开写find判空再取值或at直接抛异常再保证比较器是严格弱序日常使用中绝大多数坑都可以避开。