C++map,set,multiset,multimap详细解析

前言std::map、std::set、std::multimap、std::multiset是标准库的四个有序关联容器。它们共享同一套设计元素按比较器排好序查找、插入、删除都是对数复杂度迭代器是双向的插入和删除不会让其他元素的迭代器失效。差别只有两点键是否唯一以及是否把键映射到值。常见的误解有三个。第一把它们当成哈希表以为遍历顺序是插入顺序或不可预测——它们按比较器严格有序默认std::less就是升序。第二以为std::multimap也能用operator[]——下标访问只属于std::map因为一个键可能对应多个值下标语义无法定义。第三以为可以随便改map里的键——value_type是pairconst Key, T键是 const 的绕过类型系统去改会破坏树的结构属于未定义行为undefined behavior, UB。另一个需要澄清的点是底层实现。多数标准库用红黑树实现这四个容器但标准并没有规定必须用红黑树只规定了操作复杂度和迭代器/引用的稳定性。文章里说“通常是红黑树”是描述实现不是标准保证。本文按“共同性质 → 四者差异 → 比较器与键的不可变性 → 选型”的顺序展开最后给出常见错误。代码以 C17 为基准C20 的特性会单独注明。一、四个容器的共同性质四个容器都是有序关联容器ordered associative containers。它们要求键类型在比较器下形成严格弱序strict weak ordering并据此维护顺序。查找、插入、删除的复杂度上界都是 O(log n)遍历全部元素是 O(n)且按顺序访问。迭代器是双向迭代器bidirectional iterator支持和--不支持it n。插入操作不会使其他元素的迭代器、指针、引用失效删除只使指向被删元素的迭代器失效。这条稳定性来自节点式存储每个元素单独一个节点树只调整指针不搬移元素。元素的类型value_type值得记住容器value_type键是否 conststd::mapK, Vstd::pairconst K, V是std::setKK等价于const K是std::multimapK, Vstd::pairconst K, V是std::multisetKK是因此不能写it-first new_key。键参与树的排序改了键却不重新定位节点会破坏容器的不变式。四个容器都支持find、count、lower_bound、upper_bound、equal_range、erase。lower_bound返回第一个不小于给定键的位置upper_bound返回第一个大于给定键的位置equal_range返回这两者组成的 pair。二、四者的差异差异集中在唯一性与映射值上。std::map的键唯一每个键映射一个值提供operator[]和at()。operator[]在键不存在时会插入一个值初始化的元素并返回引用at()在键不存在时抛std::out_of_range。两者语义不同查表时不要顺手用operator[]否则一次“查询”会悄悄改变容器。std::set的键唯一元素本身既是键也是值不提供operator[]和at()。std::multimap允许重复键每个键可映射多个值。它不提供operator[]要访问一个键下的所有值用equal_range或count配合迭代。find返回其中任意一个不保证是第一个。std::multiset允许重复键同样不提供下标访问。插入返回值也不同容器insert(value)返回说明std::mapstd::pairiterator, boolbool 表示是否真的插入std::setstd::pairiterator, bool同上std::multimapiterator一定插入std::multisetiterator一定插入std::map::insert返回的bool是判断“键是否已存在”的常用方式。C17 还提供了insert_or_assign和try_emplace前者在键存在时赋值、不存在时插入后者只在键不存在时构造映射值避免无谓的构造与析构。需要“存在就不动、不存在才插入”的语义时try_emplace比operator[]更清晰。删除接口在 C11 之后也更统一erase(iterator)返回被删元素之后的迭代器erase(key)返回删除的元素个数对唯一键容器是 0 或 1对多键容器可能大于 1。三、比较器、异构查找与键的不可变比较器决定顺序也决定“什么算同一个键”。标准用等价equivalence而不是相等若comp(a, b)与comp(b, a)都为 false则 a 与 b 等价。默认std::less下等价就是自定义比较器下不一定。比较器必须满足严格弱序。写成会让comp(a, a)为真破坏传递性容器行为未定义。大小写不敏感的比较器是常见例子// 适用于 C17#include algorithm#include cctype#include stringstruct CaseInsensitive {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, CaseInsensitive counts;这个比较器把Alice与alice视为等价容器里只会保留先插入的那个键。若业务需要保留原始大小写又要求不区分大小写查找就要想清楚用哪个键存储或者改用其他索引结构。C14 起可以使用透明比较器transparent comparatorstd::less允许用与键类型不同但可比较的类型直接查找避免临时构造std::string// 适用于 C17#include functional#include map#include stringstd::mapstd::string, int, std::less table;table.emplace(alice, 1);auto it table.find(alice); // 不构造临时 std::stringC20 起还可以用table.contains(key)直接判断存在性语义比find(...) ! end()更直白在 C17 及以前用find或count。键的不可变性是硬约束。确实需要改键时C17 的节点句柄node handle提供了不重新分配内存的做法// 适用于 C17#include map#include string#include utilitystd::mapint, std::string source{{1, one}};std::mapint, std::string target{{2, two}};auto node source.extract(1); // 摘下节点source 不再含有它node.key() 3; // 节点独立存在时可以改键target.insert(std::move(node)); // 挂到另一棵树extract返回node_type它持有原来的节点键可以通过key()修改。这比const_cast安全得多后者修改键之后容器仍按旧位置组织查找会失效属于 UB。四、如何选型先问是否需要有序。如果只需要快速查找、不关心顺序std::unordered_map/std::unordered_set的平均查找是 O(1)代价是哈希质量、最坏情况退化和遍历顺序不保证。需要按序遍历、范围查询lower_bound或稳定的迭代器时才选有序容器。四个有序容器之间按“键是否唯一”和“是否要映射值”两问即可确定唯一键 映射值std::map唯一键 无映射值std::set重复键 映射值std::multimap重复键 无映射值std::multiset元素数量很小十几个且操作简单时排序的std::vectorstd::pairK, V加二分查找往往更快内存也更紧凑这是标准库之外常见的工程选择。C23 引入了std::flat_map/std::flat_set用连续存储加有序数组提供类似接口但插入删除会搬移元素迭代器失效规则也与节点容器不同使用前需确认工具链支持。完整示例四个容器的接口差异// 适用于 C17#include functional#include iostream#include map#include set#include stringint main() {std::mapstd::string, int, std::less ages;auto [it, inserted] ages.emplace(alice, 30);std::cout (inserted ? inserted : exists) \n;ages[bob] 25; // 不存在则插入std::cout ages.at(alice) \n;if (auto pos ages.find(carol); pos ages.end()) {std::cout carol not found\n;}std::multimapstd::string, int scores;scores.emplace(alice, 90);scores.emplace(alice, 85);scores.emplace(bob, 70);auto range scores.equal_range(alice);for (auto i range.first; i ! range.second; i) {std::cout i-first : i-second \n;}std::setint unique{3, 1, 2, 1};std::multisetint multi{3, 1, 2, 1};std::cout unique.size() multi.size() \n;}unique的初始列表里有重复的 1std::set只保留一个大小为 3multi保留两个 1大小为 4。ages[bob] 25先值初始化int再赋值对int没有额外成本如果映射类型构造成本高应改用try_emplace。常见坑点❌ 用if (m[key])判断键是否存在。✅operator[]在键不存在时插入值初始化的元素用find、atC20 起contains。❌ 对std::multimap写m[key]。✅ 多键容器没有operator[]用equal_range取该键的全部值。❌ 通过const_cast修改map的键。✅ 键参与排序改后容器不变式被破坏属于 UB用 C17 的extract改键再插入。❌ 自定义比较器写return a b;。✅ 不满足严格弱序容器行为未定义写return a b;。❌ 在for (auto it m.begin(); it ! m.end(); it)中m.erase(it);后继续it。✅it m.erase(it);C11 起erase返回下一个位置。❌ 以为遍历顺序是插入顺序。✅ 按比较器排序需要插入顺序就另存一个vector或改用其他结构。❌ 对std::set的元素做const_cast后修改。✅ 元素即键同样不可改要改就 erase 后重新 insert。❌ 用count判断存在性并遍历统计。✅ 唯一键容器用find更直接多键容器的count是 O(log n 出现次数)不是 O(1)。总结容器键唯一映射值operator[]insert返回典型用途std::map是是有pairiterator, bool字典、配置表std::set是否无pairiterator, bool去重、存在性集合std::multimap否是无iterator一键多值索引std::multiset否否无iterator可重复计数的有序集合四个容器的共同点是“有序 节点稳定 对数操作”差异只在键的唯一性和是否携带映射值。选型时先确认是否需要顺序再确认键是否允许重复使用时守住三条底线不用operator[]做纯查询、不修改键、不在遍历中让迭代器失效。做到这三点它们就是可靠且可预测的工具。