文章目录1. 从“能查找的表”到“容易使用的容器”2. unordered_set插入一个键得到的不只是成功与否3. unordered_map插入、更新和查询要表达清楚4. 遍历时的三个边界键、const 与删除4.1 为什么 map 的 second 可以改first 却不能改4.2 删除之后旧迭代器不能再递增5. reserve 预留的是元素数量rehash 调整的是桶5.1 元素地址还在为什么迭代器却不能继续用6. 自定义键先决定什么叫“同一个”再写哈希7. 用同一张哈希表怎样同时封装 set 和 map8. 跨桶迭代器不仅需要知道“当前结点”9. 把插入结果接到 operator[]完整程序实现10. multi 系列与容器选择沿着需求继续判断11. 总结1. 从“能查找的表”到“容易使用的容器”上一篇已经实现了哈希表给定键计算桶下标在冲突链中确认目标。真正使用时我们更希望直接表达需求把学号放进集合里去重或者把单词映射到出现次数而不是每次都操作桶和链表。std::unordered_set和std::unordered_map就提供了这样的接口分别需要头文件unordered_set和unordered_map从 C11 起可用容器一个元素是什么用什么确定唯一性典型用途unordered_setK一个 K 对象整个键按键相等规则判断去重、判断是否出现unordered_mapK,Vpairconst K,V只看键 K不看值 V字典、计数、按编号找记录它们与 map/set 的不少接口相似但底层定位依据变成哈希与键相等判断。“无序”表示没有规定按键排序也没有规定保持插入顺序不表示每次遍历都随机打乱。2. unordered_set插入一个键得到的不只是成功与否假设一批记录中有重复编号我们希望保存不同的编号并查询某个编号是否出现过。#includeiostream#includeunordered_setintmain(){std::unordered_setintids{4,2,6,2};autofirstids.insert(7);autoagainids.insert(7);std::coutsize: ids.size()std::endl;std::coutinsert 7: first.second again.secondstd::endl;// 第二次插入返回的是已有元素的位置。std::coutexisting key: *again.firststd::endl;std::couthas 2: (ids.find(2)!ids.end())std::endl;std::coutcount 9: ids.count(9)std::endl;constautoremovedids.erase(2);constautoremoved_againids.erase(2);std::couterase 2: removed removed_againstd::endl;intsum0;for(intid:ids)sumid;std::coutremaining sum: sumstd::endl;}运行示例初始化列表{4,2,6,2}中重复的 2 只保留一个插入 7 后一共四个元素。insert返回pairiterator,boolsecond说明本次是否真正新增元素。first指向插入后的对应元素。若键已存在它指向原有元素不是end()。这让我们可以只查一次就判断是否首次出现并继续使用该元素。find(key)成功返回迭代器失败返回同一容器的end()end()是结束标记不能解引用。count(key)对唯一键容器只可能是 0 或 1。erase(key)返回删除数量因此第一次删除 2 返回 1第二次返回 0。size()是有效元素数empty()判断是否为零clear()删除全部元素。3. unordered_map插入、更新和查询要表达清楚map 系列最容易混淆的地方是把insert当成覆盖或者把[]当成只读查询。#includeiostream#includestring#includeunordered_mapintmain(){std::unordered_mapstd::string,std::stringdict;dict.insert({left,left side});autoretdict.insert({left,remaining});std::coutduplicate: ret.second ret.first-secondstd::endl;// []下标运算符key存在 → 覆盖原有valuedict[left]remaining;dict[sort]order;dict[string];// 不只是查询插入一个值为空字符串的新元素。// at(key)访问key对应的值存在则返回引用找不到直接抛异常std::coutleft: dict.at(left)std::endl;std::coutempty string: dict.at(string).empty()std::endl;constautoviewdict;autoitview.find(missing);std::coutmissing: (itview.end())std::endl;std::coutsize: dict.size()std::endl;std::unordered_mapstd::string,intcount;conststd::string words[]{apple,banana,apple};for(constautoword:words)count[word];std::coutapple: count.at(apple)std::endl;}运行示例insert({key,val})key 不存在插入成功ret.second truekey已经存在不会覆盖旧值插入失败ret.second false迭代器指向原有元素map[key]下标运算符key 存在直接覆盖原来 valuekey 不存在自动插入这个 keyvalue 使用该类型的默认值string 默认int 默认0.at(key)key 存在返回 value 引用key不存在直接抛出std::out_of_range异常不会新增元素.find(key)找到返回指向该键值对的迭代器找不到返回.end()迭代器不新增元素不抛异常统计单词次数经典写法count[word]第一次遇到 applecount[apple]默认 0 变成 1再次遇到 apple取出当前值 1 变成 2单纯想用下标查询时如果 key 不存在会直接新增元素。操作键存在键不存在是否可能新增元素insert({k,v})返回原元素位置与 false不覆盖插入并返回新位置与 true是find(k)返回元素迭代器返回 end否at(k)返回值的引用抛出std::out_of_range否operator[](k)返回值的引用插入键和值初始化后的值再返回引用是4. 遍历时的三个边界键、const 与删除4.1 为什么 map 的 second 可以改first 却不能改哈希表根据键决定元素归属。若元素仍在旧桶里键却被改成应进入另一个桶的内容后续查找就可能去错地方。因此 unordered_set 的迭代器以只读方式访问元素unordered_map 的value_type则是std::pairconst K,V键只读普通迭代器仍能修改值。for(autokv:dict)kv.second!;// 原值会改变kv.first 不可赋值。for(autokv:dict)kv.second?;// 修改的是副本原容器不变。for(constautokv:dict){// kv.first 和 kv.second 都通过只读引用访问。}还有一个容易混淆的区别const_iterator限制访问到的元素const iterator限制迭代器对象本身。后者不能再递增或重新赋值但在 map 中仍可能通过它修改second就像int* const不等于const int*。4.2 删除之后旧迭代器不能再递增#includeiostream#includeunordered_setintmain(){std::unordered_setintnumbers{1,2,3,4,5,6};for(autoitnumbers.begin();it!numbers.end();){if(*it%20)itnumbers.erase(it);// 使用返回的后继不再递增旧迭代器。elseit;}intsum0;for(intnumber:numbers)sumnumber;std::coutsize: numbers.size()std::endl;std::coutsum: sumstd::endl;}运行示例erase(it)返回被删元素的后继。删除分支直接接住这个返回值不再执行it保留分支才正常递增。若两个地方都递增可能跳过元素若删除后继续递增原 it就使用了失效迭代器。5. reserve 预留的是元素数量rehash 调整的是桶负载因子α size / bucket_count接口含义bucket_count()当前桶数不是元素数load_factor()当前元素数除以桶数max_load_factor(z)设置正的最大负载控制参数不要把设置本身当作立即完成重建reserve(n)按预计总元素数 n 和最大负载规划桶数n 不是“额外再加 n 个”rehash(n)请求桶数至少满足 n还需满足当前元素数量与最大负载约束实际桶数不一定等于 nbucket(key)、bucket_size(i)查询键的目标桶以及某个有效桶中的元素数begin(i)、end(i)只遍历第 i 个桶的局部迭代器范围i 必须小于 bucket_count5.1 元素地址还在为什么迭代器却不能继续用标准无序关联容器的 rehash 会使迭代器失效但不使已有元素的指针和引用失效。迭代器不仅用于访问元素还承载着“接下来怎样遍历”的含义所以当桶组织改变后旧遍历状态就不再可靠了。#includeiostream#includestring#includeunordered_mapintmain(){std::unordered_mapstd::string,intscores;// 设置最大负载因子为0.7// 当 load_factor() max_load_factor() 时后续插入会触发rehash扩容重建哈希桶scores.max_load_factor(0.7f);// reserve(n)预估总共存放100个元素预先分配足够的哈希桶减少后续插入的rehash开销//参数n是元素数量不是通的数量scores.reserve(100);scores.insert({Alice,90});// 获取Alice分数的指针保存这个内存地址int*savedscores.find(Alice)-second;// rehash(参数)请求桶数量至少达到传入的值会立刻重建哈希表scores.rehash(scores.bucket_count()*21);// rehash之后必须重新调用find获取新迭代器不能继续使用rehash前保存的迭代器autofreshscores.find(Alice);std::coutsame value address: (savedfresh-second)std::endl;*saved95;// fresh是新迭代器访问新内存地址的值std::coutscore: fresh-secondstd::endl;// bucket(key)查询Alice这个key落在第几个桶返回桶编号conststd::size_t bucketscores.bucket(Alice);boolfound_in_bucketfalse;// begin(bucket) / end(bucket)获取【单个桶】的局部迭代器范围只遍历这个桶内的元素for(autoitscores.begin(bucket);it!scores.end(bucket);it){if(it-firstAlice)found_in_buckettrue;}std::coutfound in local bucket: found_in_bucketstd::endl;return0;}运行示例操作已有元素迭代器已有元素指针、引用查找、读取、修改 map 的值保持有效保持有效插入且不触发 rehash保持有效保持有效插入触发 rehash全部失效原有元素的保持有效rehash可能重建的reserve重新取得后再用原有元素的保持有效erase被删元素的失效其余不因此失效被删元素的失效其余保持有效clear、销毁容器原元素的全部失效原元素的全部失效6. 自定义键先决定什么叫“同一个”再写哈希标准 unordered_set 的常用模板参数可以简化理解为unordered_setKey,Hash,KeyEqualunordered_mapKey,Value,Hash,KeyEqual实际声明还包括分配器参数本文保持默认。Key 不必自己提供“转成整数”的转换运算符要求是 Hash 能对键生成size_t哈希值KeyEqual 能判断两个键是否等价。默认分别是std::hashKey和std::equal_toKey后者通常调用。#includefunctional#includeiostream#includestring#includeunordered_setstructStudent{intid;std::string name;};// 此处定义“同一个键”为学号相同姓名不参与身份判断。structStudentHash{std::size_toperator()(constStudentstudent)const{returnstd::hashint()(student.id);}};structStudentEqual{booloperator()(constStudentleft,constStudentright)const{returnleft.idright.id;}};intmain(){std::unordered_setStudent,StudentHash,StudentEqualstudents;students.insert(Student{1001,Alice});autoresultstudents.insert(Student{1001,Alicia});autofoundstudents.find(Student{1001,});std::coutduplicate: result.secondstd::endl;std::coutname: found-namestd::endl;std::coutsize: students.size()std::endl;}运行示例第二条记录虽然姓名不同却与第一条等价因此不插入也不会自动更新姓名。查找时构造{1001,}仍可命中原因是我们自定义的相等规则根本不看姓名。KeyEqual 应构成等价关系自身与自身等价判断具有对称性与传递性。Hash 和 KeyEqual 的配合至少要守住这些条件equal(a,b)为 true必须有hash(a)hash(b)反向不成立。元素在容器内期间参与哈希和相等判断的内容要保持稳定。忽略大小写等自定义等价规则必须搭配相同语义的哈希不能只改其中一个。7. 用同一张哈希表怎样同时封装 set 和 map从使用回到实现关键变化是把两个类型分开K 是查找键的类型T 是结点存储的完整数据类型。哈希表不应在所有地方写死data.first因为 set 的数据可能只是一个整数。所以此时引入一个键提取仿函数KeyOfT就能统一为完整数据 T → KeyOfT(data) 得到 const K → Hash / KeyEqual → 定位与查重封装底层 K底层 TKeyOfT 返回什么unordered_setKKK元素自身的只读引用unordered_mapK,VKpairconst K,Vfirst 的只读引用8. 跨桶迭代器不仅需要知道“当前结点”如果一个桶里还有后继it直接沿 next 走如果到达链尾就要寻找下一个非空桶。只保存结点指针无法方便访问整张桶数组。所以这里的迭代器设计保存两个个信息当前结点和所属的表。递增规则如下当前结点有 next前进到 next桶下标保持不变。当前链已结束增加桶下标跳过空桶。找到非空桶指向桶头若已越过桶数组变成 end。begin()找第一个非空桶空表则返回 end。普通与只读迭代器共享遍历逻辑通过 Ref、Ptr 两个模板参数区分解引用类型T / T*或const T / const T*。9. 把插入结果接到 operator[]完整程序实现哈希表的 insert 返回元素位置与是否新增两个包装层就能直接复用它。map 的[]先查找命中返回 second缺失才构造value_type(key,V())并插入再返回新元素 second 的引用。unordered_map与unordered_set的使用与模拟实现10. multi 系列与容器选择沿着需求继续判断如果允许等价键重复出现可以使用unordered_multiset或unordered_multimap。它们并不是简单把哈希冲突当成重复等价由 KeyEqual 决定碰撞由哈希位置决定。multi 系列的单元素 insert 返回迭代器count可能大于 1erase(key)删除所有等价键的元素若只删一个可先 find 再按迭代器 erase。unordered_multimap没有[]或at因为同一个键不一定对应唯一值。#includeiostream#includestring#includeunordered_mapintmain(){std::unordered_multimapstd::string,intmarks;// 插入3条记录Alice存在两条重复keymarks.insert({Alice,80});marks.insert({Bob,70});marks.insert({Alice,90});// equal_range返回一对迭代器[begin, end)代表keyAlice所有元素区间autorangemarks.equal_range(Alice);inttotal0;// 遍历这个区间累加Alice所有分数for(autoitrange.first;it!range.second;it)totalit-second;// count统计key为Alice的元素个数std::coutAlice count: marks.count(Alice)std::endl;// 输出Alice所有分数总和std::coutAlice total: totalstd::endl;// erase(key)删除该key对应的全部元素返回删除元素数量std::couterase Alice: marks.erase(Alice)std::endl;// 删除后容器剩余元素数量std::coutremaining: marks.size()std::endl;}运行示例11. 总结实际场景中把有序与无序容器的选择放回具体需求需求或代价map/setunordered_map/unordered_set按键排序、上下界、范围查询提供对应能力不提供按键排序的成员上下界查询判断同一个键比较器定义的等价双方都不小于对方KeyEqualHash 必须与之兼容按键查找、插入、删除O(log N)还需计入比较成本通常平均 O(1)最坏 O(N)还需计入哈希与相等比较成本插入对已有迭代器的影响通常不使其失效要考虑 rehash性能和空间受结点、比较及实现影响额外桶空间受负载、冲突、哈希和实现影响字符串越长哈希本身需要读取的内容也越多把 O(1) 理解成“任何键都只花固定几条指令”并不准确。大量冲突可以让无序容器退化。使用时先明确需要集合还是映射需要唯一键还是重复键需要有序关系还是只需按键定位。选定无序容器后再把查询是否插入、键等价规则与迭代器有效期处理清楚接口就能与哈希表的结构一一对应起来。