C++中map和set的使用详细攻略-北京尧图网络

前言std::map和std::set是标准库里的有序关联容器ordered associative container。set存不重复的键map存键值对两者都按比较器排好序查找、插入、删除的复杂度都是对数级。它们底层通常实现为平衡二叉搜索树主流实现是红黑树但标准只规定接口和复杂度不规定具体树形。典型误解有三个。第一把std::map当成哈希表哈希表是std::unordered_mapmap保证有序遍历unordered_map不保证。第二用m[key]做「只读查找」如果键不存在operator[]会插入一个默认构造的值查找变成了写入。第三以为insert会覆盖已有值对map来说键已存在时insert什么都不做返回的bool是false。本文按「共同模型—set—map—自定义比较器—与无序容器对比」展开最后给出一个词频统计与排序的完整例子。代码基准为 C17。一、共同的模型有序、节点式、对数复杂度四个有序关联容器容器存储内容键是否唯一允许重复键的版本std::setKey键是std::multisetKeystd::mapKey, Tstd::pairconst Key, T是std::multimapKey, T共同特性有序。默认按std::lessKey排序遍历顺序是键的升序对自定义类型则按比较器定义的顺序。节点式。每个元素单独分配一个节点节点里保存键、值对map和树结构所需的指针。插入不会使其他元素的迭代器失效删除只使被删元素的迭代器失效。双向迭代器。可以、--但不支持随机访问没有it n。对数复杂度。find、count、insert、erase、lower_bound、upper_bound都是 O(log n)。键不可变。set的元素整体是 constmap的元素类型是std::pairconst Key, T键不能改值可以改。因为键不可变想「修改」一个set元素或map的键只能先删除再插入C17 提供了extract可以取出节点、改键后再插回避免重新分配// 适用于 C17#include map#include string#include utilityvoid rename_key(std::mapstd::string, int m,const std::string oldKey,const std::string newKey) {auto node m.extract(oldKey); // 取出节点不销毁if (node.empty()) {return; // 键不存在}node.key() newKey; // 修改键m.insert(std::move(node)); // 插回}二、set去重与有序集合std::set的核心操作操作说明insert(value)返回pairiterator, boolbool表示是否真的插入emplace(args...)原位构造返回同上erase(key)返回删除的元素个数set为 0 或 1erase(iterator)返回被删元素之后的迭代器C11 起find(key)找到返回迭代器否则返回end()count(key)set返回 0 或 1lower_bound(key)第一个不小于 key 的元素upper_bound(key)第一个大于 key 的元素contains(key)C20 起可用返回bool用insert的返回值可以同时完成「插入」和「判断是否已存在」// 适用于 C17#include set#include stringbool add_unique(std::setstd::string names, const std::string name) {const auto result names.insert(name);return result.second; // true 表示之前不存在本次插入成功}set最常见的用途是去重。把一段数据全部insert重复元素会被自动忽略遍历set得到的是升序结果。如果只关心「是否存在」而不关心顺序std::unordered_set的平均查找是常数级通常更快。区间查询用lower_bound和upper_bound配合// 适用于 C17#include setvoid print_range(const std::setint values, int low, int high) {// [low, high] 闭区间从第一个 low 到第一个 highfor (auto it values.lower_bound(low);it ! values.upper_bound(high); it) {// *it 在范围内}}注意upper_bound(high)每次循环条件都会重新计算虽然它是对数复杂度但放在循环里仍然浪费。更好的写法是先保存终点迭代器。另外set的迭代器是双向的不能写成it 1。三、map键值映射与几个易混接口std::map的元素类型是std::pairconst Key, T。遍历时可以用结构化绑定C17// 适用于 C17#include iostream#include map#include stringvoid dump(const std::mapstd::string, int m) {for (const auto [key, value] : m) {std::cout key value \n;}}3.1 operator[] 会插入// 适用于 C17#include map#include stringstd::mapstd::string, int scores;scores[alice] 90; // 键不存在插入 (alice, 0)再赋值为 90int a scores[alice]; // 已存在返回引用int b scores[bob]; // 不存在插入 (bob, 0)b 为 0最后一行是陷阱只想读取却意外增加了元素。只读查找用find或at// 适用于 C17auto it scores.find(carol);if (it ! scores.end()) {int value it-second;}// 或者不存在时抛 std::out_of_rangeint value scores.at(carol);operator[]还要求mapped_type可默认构造因为它必须先造一个值再返回引用。at没有这个要求但键不存在时抛异常。C17 的try_emplace则只在键不存在时构造值避免不必要的临时对象// 适用于 C17auto [it, inserted] scores.try_emplace(dave, 75);3.2 insert 不覆盖已有值// 适用于 C17std::mapstd::string, int m;m.insert({alice, 90});m.insert({alice, 100}); // 键已存在什么也不做// m[alice] 仍是 90要「存在则覆盖、不存在则插入」有三种写法m[key] value;简单但要求值可默认构造且会先构造再赋值。m.insert_or_assign(key, value);C17语义最直接返回pairiterator, bool。先find再决定赋值或emplace控制最细但代码更长。3.3 erase 的正确写法删除指定键m.erase(key)返回删除个数。删除迭代器指向的元素时C11 起erase返回下一个迭代器// 适用于 C17for (auto it m.begin(); it ! m.end(); ) {if (it-second 0) {it m.erase(it); // 用返回值继续} else {it;}}如果写成m.erase(it); it;it在erase之后已经失效再自增是未定义行为。3.4 用 emplace 构造复杂值emplace把参数直接转发给元素类型的构造函数省去临时pair// 适用于 C17#include map#include string#include vectorstd::mapstd::string, std::vectorint groups;groups.emplace(evens, std::vectorint{2, 4, 6});对mapemplace的实参需要能构造pairconst Key, T即使键已存在待插入的元素也可能被构造后立即销毁所以实参的构造开销省不掉。try_emplace则保证键存在时连 mapped 值都不构造对昂贵的值类型更友好。四、比较器、无序容器与完整示例map和set的第三个模板参数是比较器类型默认std::lessKey。自定义比较器必须满足严格弱序strict weak ordering对任意 acomp(a, a)必须为false非自反若comp(a, b)为真则comp(b, a)必须为假非对称传递性等价关系可传递。用作为比较器会破坏非自反性属于未定义行为——std::sort、std::set、std::map都要求严格弱序这不是「结果可能不太对」而是标准明确规定的 UB。按长度给字符串排序的set// 适用于 C17#include set#include stringstruct ByLength {bool operator()(const std::string a, const std::string b) const {if (a.size() ! b.size()) {return a.size() b.size();}return a b; // 长度相同时按字典序保证严格弱序}};std::setstd::string, ByLength words;如果只按长度比较、长度相同就返回false那么两个等长但内容不同的字符串会被视为「等价」set会认为它们重复只保留其中一个。加上字典序作为次级比较才能既按长度排序又保留所有不同字符串。比较器是有状态的也可以把状态存在比较器对象里构造容器时传入实例。注意比较器会被拷贝状态变化不会反映到容器中所以不要写依赖可变状态的比较逻辑。C14 起可以用透明比较器std::less支持异质查找heterogeneous lookup例如用const char*直接在std::setstd::string里查找而不构造临时std::string// 适用于 C17#include functional#include set#include stringstd::setstd::string, std::less names;names.insert(alice);auto it names.find(alice); // 不构造临时 std::stringC14 起与无序容器怎么选维度std::map/std::setstd::unordered_map/std::unordered_set底层结构平衡二叉搜索树通常红黑树哈希表查找复杂度O(log n)平均 O(1)最坏 O(n)是否有序是按比较器否迭代器稳定性插入不影响其他元素rehash 可能使迭代器失效键的要求可比较严格弱序可哈希可相等比较范围查询lower_bound/upper_bound天然支持不支持需要额外排序最坏情况稳定 O(log n)哈希冲突严重时退化选择标准很直接需要按序遍历、范围查询、稳定最坏复杂度用map/set只做点查找、不关心顺序、有合适的哈希函数用无序版本。不要因为「哈希是 O(1)」就无脑选unordered_map——它的常数并不小最坏情况还会退化而且std::hash对自定义类型需要自己特化。完整示例词频统计并按键值排序下面的例子统计单词出现次数再把结果按「次数降序、单词升序」输出。map负责去重和计数vector负责按值排序这是两者最常见的配合方式。// 适用于 C17#include algorithm#include iostream#include map#include sstream#include string#include utility#include vectorstd::mapstd::string, int count_words(const std::string text) {std::mapstd::string, int freq;std::istringstream iss(text);std::string word;while (iss word) {freq[word]; // 不存在时插入 0再自增}return freq;}int main() {const std::string text apple banana apple cherry banana apple;auto freq count_words(text);std::vectorstd::pairstd::string, int ranked(freq.begin(), freq.end());std::sort(ranked.begin(), ranked.end(),[](const auto lhs, const auto rhs) {if (lhs.second ! rhs.second) {return lhs.second rhs.second; // 次数降序}return lhs.first rhs.first; // 同次数按单词升序});for (const auto [word, count] : ranked) {std::cout word count \n;}return 0;}几个检查点freq[word]在这里是合适的因为确实需要「不存在就插入」。std::vector的区间构造接受两个迭代器把map的pairconst std::string, int转成pairstd::string, int需要一次拷贝这是允许的。排序 lambda 必须满足严格弱序次数相等时用单词比较兜底两个条件覆盖了所有不等情况相等时返回false。如果单词量很大且只取前 K 个全量排序就浪费了可以用std::partial_sort或维护一个大小为 K 的小顶堆。具体选择取决于数据规模和 K 的大小应当按复杂度分析而不是凭感觉。常见坑点❌ 用m[key]做「查一下有没有」结果容器里多出一堆默认值。✅ 只读用find或atoperator[]的语义是「不存在就插入」。❌ 以为m.insert({key, value})会覆盖旧值。✅ 键已存在时insert不修改要覆盖用insert_or_assignC17或m[key] value。❌ 比较器写成return a b;。✅ 必须是严格弱序用违反非自反性行为是未定义。❌ 遍历时m.erase(it); it;。✅it m.erase(it);使用返回的下一个迭代器。❌ 试图修改set里的元素或修改map的键。✅ 键是 const删除后重新插入或 C17 用extract取出节点改键再插回。❌ 认为std::map的遍历顺序是插入顺序。✅ 遍历顺序由比较器决定默认是键升序需要插入顺序得另存一个vector。❌ 用std::map却对每个元素再调用一次find把 O(n log n) 的操作做成 O(n log² n)。✅ 直接遍历迭代器或用lower_bound加 hint 插入已有迭代器就不要重新查。❌ 把指针作为map的键期待按指向的内容排序。✅ 默认比较的是地址需要内容比较就自定义比较器或用std::string/值类型作键。总结主题要点底层通常红黑树O(log n)有序遍历set去重、排序、insert返回pairiterator,boolmap元素是pairconst Key, T键不可改operator[]键不存在会插入默认值只读用find/atinsert不覆盖已有键覆盖用insert_or_assign比较器必须严格弱序等价元素会被视为重复迭代器插入不影响其他元素删除只影响被删元素选型要顺序和范围查询用map/set纯查找可考虑无序版本map和set的接口不难难的是记住每个操作对「已存在的键」采取什么策略operator[]插入、insert忽略、insert_or_assign覆盖、try_emplace不构造。把这四个语义分清再守住比较器的严格弱序和迭代器失效规则日常使用基本不会出问题。

C++中map和set的使用详细攻略

相关推荐

蓝牙Mesh网络入门：从泛洪机制到配网实操避坑指南

libnids源码深度解读：TCP重组与IP分片注释实战

ESP32-S3开发板深度解析：双核架构、原生USB与AI边缘部署实战

更多资讯

CNN人脸识别从零搭建：数据清洗到模型推理全流程实战指南

FreeRTOS从裸机到实战：任务调度、内存管理与避坑指南

SPI屏嵌入式信息面板实战：从接线到点亮，跑通第一个系统状态Demo

MCAL功能安全分析实战：失效模式、诊断覆盖率与故障注入

50步还是8步？MOSS-Image-Base-bf16采样参数完全指南：Euler Flow Matching、CFG与Shift调优

GGUF 量化原理新手详解：Ling-3.0-tiny-GGUF 的 Q4_K_M 如何以 4.8GB 保全心智

今日更新

智能硬件视频会议集成：从芯片选型到场景落地的全栈实践

FFmpeg音视频处理与5路RTMP推流实战：从原理到118克盒子部署

RK3528+1GB内存如何变身直播节点？硬编解码与六协议实战复盘

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？