1. 写在前面四个容易让人纠结的容器C STL里set、map这对老兄弟和unordered_set、unordered_map这对新面孔是日常开发里最容易让人纠结的选择。做开发这几年我见过不少同事在技术评审时为了到底用哪个争得面红耳赤也见过线上服务因为选错容器导致接口响应从毫秒级退化到秒级最后靠性能剖析工具定位才发现是红黑树的O(log N)查找在数据量上来之后扛不住了。先说结论级别的认知set和map底层是红黑树元素有序排列操作复杂度稳定在O(log N)unordered_set和unordered_map底层是哈希表元素无序排列平均复杂度O(1)最坏情况O(N)。看起来像是哈希全面胜出但实际工程里远远没那么简单——有序性、稳定性、内存布局、哈希函数质量、迭代器稳定性这些维度每一项都可能成为你选型的决定性因素。这篇内容我打算从底层数据结构讲起一路拆到时间复杂度、内存开销、迭代器失效规则最后结合我实际踩过的坑给出一套可落地的选型参考。不管你是刚接触STL的初学者还是已经写了几年C但没系统梳理过这块的朋友这篇文章应该都能帮你把这两个体系的差异彻底理清楚。2. 底层数据结构红黑树和哈希表到底差在哪2.1 红黑树高度平衡的背后是代价换稳定set和map依赖的底层数据结构是红黑树Red-Black Tree。红黑树是一种自平衡的二叉搜索树它通过给节点增加颜色属性红色或黑色来保证任意一条路径的长度不会超过另一条路径的两倍从而确保树的高度始终保持在对数级别。这意味着无论你怎么插入、删除元素set和map的查找、插入、删除操作的时间复杂度都严格稳定在O(log N)不会出现性能波动。红黑树的平衡策略在极端场景下依然可靠——比如你连续插入1000万个递增的元素它依然能保持树高大致为log2(1000万) ≈ 24层而不是退化成一个链表状的瘸腿树。但这棵严格平衡的树是有代价的代价就是每次插入或删除时结构可能需要通过旋转和变色来维持平衡性。虽然这些操作的摊还成本依然是O(log N)但在单次操作上红黑树的常数因子明显比哈希表大。换句话说数据量小的时候红黑树反而可能不如哈希表快因为哈希计算和桶定位的开销通常低于一次树节点的路径遍历。红黑树另一个非常重要的特性是中序遍历天然有序。因为元素在树中是按键值的大小关系排列的所以对set和map做begin()到end()的遍历得到的序列一定是按照std::less默认升序排列的有序序列。同时STL还提供了lower_bound、upper_bound、equal_range这类基于有序性的区间查找接口可以直接在O(log N)时间内找出大于等于某个值的最小元素一类的答案。如果需要按范围批量取数据比如找出所有价格在100到200之间的商品set和map几乎是现成答案。2.2 哈希表平均O(1)的高速路及其前提unordered_set和unordered_map底层是一个哈希表的概念。更准确地说C标准要求它们使用桶bucket加哈希冲突处理机制大多数实现GCC的libstdc和Clang的libc采用桶数组 链表/红黑树的链地址法。哈希表的工作原理其实和生活里的抽屉柜很像哈希函数把任意一个键key映射到一个整数哈希值再用这个整数对桶的数量取模得到这个键应该存在哪个抽屉里。查找的时候只要再次计算哈希值、定位到抽屉然后在抽屉里做比较。理想情况下所有键都均匀地落在不同的抽屉里查找时间就是O(1)——等于一次哈希计算加一次数组访问。但是抽屉均匀这个前提相当苛刻。它要求哈希函数质量足够好使不同键产生的哈希值尽量均匀分布否则大量键可能被映射到同一个桶里导致这个桶里的链表变得很长查找复杂度从O(1)退化为O(N)。C的标量类型int、double、char自带标准库的支持良好但自定义类型如果不提供高质量哈希函数就很容易踩到这个坑。后面我会专门用一节来讲这个。哈希表还有一个隐藏行为是扩容rehash。当桶里的元素数量超过负载因子max_load_factor默认通常是1.0时哈希表会重新申请一个更大的桶数组把已有元素全部重新哈希一遍迁移到新的桶里。这个操作是O(N)的虽然摊还下来每个元素只承受常数次迁移成本但在扩容的瞬间你可能会观察到一次明显的延迟尖峰。在对延迟敏感的高实时性场景下这个偶发尖峰是必须考虑的设计因素。2.3 顺序性差异带来的连锁反应底层结构的差异直接决定了API行为的不同这是初学者最容易忽略的set和map的迭代顺序是确定的、与插入顺序无关的从小到大升序遍历。连续两次遍历同一个容器顺序一定相同只要数据内容不变任何时间遍历顺序都不变。unordered_set和unordered_map的迭代顺序是未指定的实际取决于当前桶的数量、元素哈希值和插入的历史顺序。理论上是无规律的但实践里如果你不修改容器遍历顺序通常是稳定的桶结构没变一旦发生rehash遍历顺序就会大变。set和map提供lower_bound、upper_bound、equal_range、rbegin/rend反向迭代这些基于有序性的方法unordered_*版本不提供任何与“顺序”相关的方法。unordered_*容器额外提供了bucket_count()、bucket_size(i)、reserve(n)这些哈希表专属接口用来控制桶的数量和预分配容量这在有序版本中完全不存在。这四点差异实际影响的是你的使用模式如果你需要对元素做范围查询、找最大最小、做升序输出或者希望同内容必同顺序那就必须选set/map。如果核心诉求只有快速找到某个键对应的值顺序无关紧要unordered_*才是合理选择。3. 性能对比别只看大O要把常数因子也聊清楚3.1 时间复杂度不是全部很多人看到O(1)和O(log N)就断定哈希永远更快。从渐近复杂度的角度确实如此但在真实工程里还要看数据量落在哪个区间。在数据量很小比如少于100个元素时set和map的红黑树查找通常并不会落后于unordered_*太多有时甚至更快。原因是树的高度等于log2(N)100个元素的树高只有7层意味着一次查找只需要大概7次比较而哈希计算本身有整数运算开销同时桶数组的随机访问会引发更高的缓存未命中率。如果元素的比较操作本身很便宜比如比较整数或指针树版本的比较成本几乎可以忽略。数据量来到10万以上时情况就不同了。log2(100000) ≈ 17次比较而哈希一次计算加一次桶定位通常是常数次操作unordered_*的定位速度会明显领先。我实际测试过用std::map和std::unordered_map分别对100万个随机生成的键做查询unordered_map的查询总耗时大约是map的1/3到1/5插入操作也有类似的差距。这还是在默认哈希函数下的结果。可以通过一张表直观感受两个体系的复杂度差异操作set/mapunordered_set/unordered_map查找O(log N)平均O(1)最坏O(N)插入O(log N)摊还不变平均O(1)最坏O(N)rehash时O(N)删除O(log N)平均O(1)最坏O(N)区间查找支持O(log N K)输出区间内K个元素不支持只能逐一遍历顺序遍历升序确定且可预期无序与哈希值和桶结构相关lower_bound / upper_bound支持不支持但平均O(1)背后的真正含义取决于哈希函数质量和负载因子。如果你用的是默认的std::hashint整型键均匀分布的假设理应成立但如果你拿一个设计很差的字符串哈希比如把所有字符串映射到0~9去insert十万个样本那哈希表会退化成十个长链表性能直接崩塌到O(N)。自定义类型尤其需要注意。3.2 我实测的一组参考数据有一次优化一个离线任务数据集规模大概在200万键值对键是字符串。我在同一台机器上做了简单基准Release编译-O2插入200万条记录unordered_map耗时约1.2秒map约3.8秒。完成插入后查询全部200万个键unordered_map约0.35秒map约0.9秒。按键序遍历全部元素unordered_map约0.4秒但输出顺序完全乱序map约0.6秒且天然有序。结论很清楚在插入和点查询上unordered_map几乎全线领先但如果业务需要有序输出map省去了额外的排序步骤你如果用unordered_map就得先把键收集出来再sort排序本身也要O(N log N)。值得强调的是map的插入时间还包括了那么多红黑树自平衡旋转以及每个节点需要malloc分配独立内存块的成本。每个树节点是一次单独的内存分配而哈希表的桶数组是一块连续内存节点挂着链表。大量的malloc/free在碎片化的堆上会显著放大时间开销这也是大数据量下哈希表优势放大的原因之一。3.3 摊还分析与延迟尖峰的取舍摊还分析Amortized Analysis是个很有用的工具。哈希表的插入操作从单次来看不是稳定的O(1)——rehash的那一次要O(N)但把多次插入放在一起看每一次插入的平均成本依然能维持在常数级别因为rehash发生的频率被负载因子控制住了扩容因子通常是2倍所以总迁移成本是等比数列求和收敛于常数倍。这个性质对吞吐量导向的程序批处理、离线计算没有任何问题但对延迟敏感的程序在线服务单次请求处理路径要小心。一次请求触发了rehash这个请求的响应时间可能比平时慢一个数量级。而红黑树不会有这个问题它每次操作的时间上下波动非常小最坏情况就是O(log N)单位操作里没有突发的大规模迁移。注意如果你确认数据量上限定死可以用reserve预分配桶数从源头消灭rehash。std::unordered_mapint, int m; m.reserve(1000000);可以在插入前把桶数组扩充到位。这个动作很便宜强烈建议在知道预计容量时先做。4. 内存布局与额外开销往往是最容易被忽视的差异4.1 节点级开销的结构性对比红黑树的每个节点除了存储关键数据和值之外还要额外携带左孩子指针、右孩子指针、父指针、颜色标记和NIL哨兵信息。在64位平台上一个GCC实现的std::map节点光是指针和标记位就会占用大约40~48字节的额外空间。如果你存的是int这类4字节小键值树节点的总大小可能接近64字节而真正的数据只有8字节——内存利用率不到13%。哈希表的内存开销结构不同。桶数组本身是连续的内存每个桶只占一个指针大小但每个元素仍然是独立的堆节点包含元素数据和next指针。unordered_map的节点额外占用通常是一个指针加上可能的少量元信息比红黑树节点小但桶数组在rehash时会预留不少空抽屉。负载因子1.0意味着平均一个桶一个元素但桶数组长度略大于元素个数而且rehash翻倍后可能有一半的桶是空的。所以一个不太直观但真实的结论元素数量大了之后unordered_map总内存不一定比map小。桶数组的空白浪费、链表的节点开销叠加起来可能反而比红黑树还要费内存。我做过一个测试200万个int-int键值对std::map大概占用70MBunordered_map默认负载因子1.0大概也在60~80MB之间浮动。具体项目要实测为准不要凭O(1)性能就想当然认为内存也更优。4.2 缓存局部性为什么连续远比稀疏重要现代CPU访问内存时是以缓存行通常64字节为单位加载数据的。当你顺序遍历一个数组时CPU能够以接近内存带宽的速度预取数据但遍历std::map的红黑树节点时每次跳转都可能落到完全不同的内存地址缓存命中率极低内存带宽完全被浪费在等待上。哈希表的桶数组是连续的这使得unordered_*比红黑树更有缓存优势。但这种优势只在元素分布相对集中时明显节点本身是散落在堆上的跨节点访问遍历链表桶时依然会有缓存未命中。如果要极致性能用std::vector配合排序加二分查找std::lower_bound比std::map和unordered_map的缓存表现都要好这也是静态查找表场景下大家经常切换到vector的原因。4.3 大对象与字符串场景的特殊考量如果键是长字符串情况会更复杂。红黑树的比较操作是逐字符比较两个字符串的字典序每次查找可能要调用几十上百次字符比较而哈希首先要遍历字符串的每个字节算哈希值然后在桶里比较时再逐字符比较一次。看上去哈希多做了一次全量遍历但在桶内链表很短的情况下这种一次性遍历成本往往低于红黑树多次比较的累加成本。字符串的哈希计算还有缓存友好的优势它顺序读了一遍字符串CPU预取效率高而红黑树的字符串比较是随机跳转式比较每个节点可能在不同页面上。所以实践中unordered_map在字符串键场景下的领先幅度往往比整数键更大。实操心得如果键是自定义结构体一定要给哈希函数和等值比较函数都写好实现。漏了operator或者重载了operator但忘了给std::hash做特化编译期就会报错或运行期异常这类问题非常常见。5. 迭代器失效规则一句循环里删出bug背后的细节5.1 有序容器删除当前元素其他迭代器不受影响set和map的迭代器失效规则很宽容插入元素时除非被插入的元素正好是当前迭代器指向的位置实际上不会否则所有现有迭代器都不会失效删除元素时只有指向被删除元素的迭代器失效其他迭代器完全不受影响。这个特性来自红黑树实现中插入删除不会移动已有节点内存地址的事实。实际开发中下面这个循环在set和map中就是安全的std::mapint, int m; for (auto it m.begin(); it ! m.end(); ) { if (it-second 0) { it m.erase(it); // 或者 m.erase(it); } else { it; } }C11之后erase返回下一个有效的迭代器写起来更简单。老版本得用m.erase(it)的奇技淫巧本质是利用了删除只使被删迭代器失效这一保证。5.2 哈希容器删除同样宽松但rehash会摧毁全部迭代器unordered_set和unordered_map在单元素删除上与有序版本保持一致的宽松规则删除元素时只有指向该元素的迭代器失效其他迭代器不受影响插入元素时如果触发了rehash则所有迭代器都会失效。如果插入没有触发rehash则所有迭代器保持有效。这个规则给经验不足的开发者埋了个大坑。你在循环里插入元素时忘记了rehash的存在迭代器突然全部失效轻则UB未定义行为重则访问野指针直接线上崩溃。我建议的规避策略在需要大量插入之前根据预估容量提前reserve避免循环中插入触发rehash。如果无法预估尽量采用先收集再插入的两阶段模式不要在持有迭代器的情况下连续插入。遍历操作和插入操作最好分离不要一边持迭代器遍历一边往里插。5.3 指向元素的引用和指针红黑树保持稳定哈希表在rehash时失效除了迭代器引用和指针的失效规则也要提一嘴。set和map的节点地址在插入和删除其他元素时都不会发生移动因此元素的引用和指针是长期稳定的——有人会利用这个特性把指向map内某一个元素的指针保存下来在其他线程里继续使用前提是你做好了线程同步。哈希表则完全不同一旦rehash所有已有节点的地址都会被改写任何指向元素的裸指针、引用都会被悬挂dangling。所以哈希容器保存裸指针/引用的生命周期极短使用范围极大受限。如果你的数据结构设计里需要长期持有元素的地址那么set/map几乎是唯一选择。6. 自定义类型与哈希函数unordered_* 的高频坑6.1 为什么自定义类型需要等值哈希双件套有序容器对自定义类型的最小要求是能比较大小提供operator通常还要保证严格弱序strict weak ordering。而无序容器要求的是等值比较operator和哈希函数std::hash的专门化或传入自定义函数对象。很多人第一次用unordered_setMyType会直接被编译错误吓到static_assert failed: the hash predicate must be invocable with an argument of key type。原因就是标准库没有为任意结构体生成哈希函数的魔法必须自己提供。给一个示例自定义类型struct Person { std::string name; int age; bool operator(const Person other) const { return name other.name age other.age; } }; struct PersonHash { std::size_t operator()(const Person p) const { std::size_t h1 std::hashstd::string{}(p.name); std::size_t h2 std::hashint{}(p.age); // 把两个哈希值混合起来 return h1 ^ (h2 1); } }; std::unordered_setPerson, PersonHash people;h1 ^ (h2 1)这种组合写法是常见的混合两个哈希值的手法——左移一位避免相同输入顺序下碰撞再异或可以保持一定区分度。如果项目里已经用了某个第三方哈希库建议优先用它提供的混合函数通常比手写异或更均匀。6.2 哈希质量差导致的退化哈希函数质量的标准是均匀性和一致性。均匀性指不同键的哈希值应当尽量散布在整个空间一致性指同一个键的哈希值在多次调用时必须稳定相同。我遇到过一个真实案例有人把哈希函数写成了字符串长度 mod 桶数。结果所有相同长度的字符串都扎堆在同一个桶里标称O(1)的哈希表实际退化为O(K)——K是同长度字符串的数量。这批数据在十万级的时候线上接口就能明显感觉到卡顿剖析下来发现某个桶里的链表长度超过8000。默认的std::hashstd::string采用的是某种为字符串设计的实现通常基于轮转乘法或CTZ算法对绝大多数业务数据都能打散得比较均匀正常使用不需要自己造轮子。真正需要自定义哈希函数的场景是自定义结构体以及某些特定数据分布下默认哈希存在系统性碰撞比如你处理的数据键全是固定的几个整数——整数哈希本身就是恒等映射这种场景哈希表依然很稳。6.3 对哈希函数性能的节奏感哈希函数除了均匀还要快。有些开源实现提供了号称抵抗碰撞攻击的强加密哈希均匀性极好但对短字符串的哈希速度可能比std::hash慢一个数量级。做离线任务倒还好做在线热点路径就要把握好性价比。我的建议是优先用标准库自带哈希如果要做自定义先用简单的异或混合方案压测后发现碰撞严重再考虑更复杂的混合算法。不要一开始就上强哈希很多项目的性能瓶颈根本不在哈希碰撞上。7. 应用场景对照红黑树和哈希分别应该用在哪儿7.1 适合set/map的场景需要有序遍历输出比如排行榜数据需要按分数从高到低排列直接用map的倒序遍历rbegin()到rend()一步到位。需要范围查询找出价格在100~200之间的所有商品lower_bound(100)拿到起点然后遍历到upper_bound(200)为止一次搞定。需要频繁获取最小值/最大值begin()就是最小rbegin()就是最大O(1)获取。元素数量不大几千以内且插入删除不频繁此时O(log N)和O(1)差距不明显有序性带来的API便利反而是更大的收益。需要长期持有元素指针/引用红黑树节点地址稳定而哈希表rehash会移动一切。7.2 适合unordered_set/unordered_map的场景大量的查找操作比如缓存、索引、去重核心操作就是给定键找到/确认存在。百万级别数据量下哈希表的点查速度优势明显。大批量插入后不再频繁变化先reserve预留容量插入期间一次性rehash完毕后后续查询阶段零rehash、零迭代器失效问题。键值对象本身很大哈希表只需要哈希一次然后比对而红黑树的多次字典序比较会反复读取大对象成本高。对迭代顺序没有要求比如按用户ID查昵称数据库读出来的结果、排序逻辑都不关心容器内顺序。7.3 一个现实的决策经验法我个人的习惯判断流程是需要有序能力、范围查询、取最大最小→ 直接用set/map。只是纯粹键值存取→ 预估数据量如果超过1万选择unordered_*并且提前预留容量。数据量小、操作频繁立即插入立刻遍历→set/map可能更稳因为结构化内存分配在少量数据时成本不高。无法确定哈希函数质量但键是自定义对象→ 优先用迭代器有序性安全兜底选set/map如果对性能有硬要求再认真实现哈希函数后换哈希表。这个流程谈不上完美但覆盖面足够能在90%的日常场景里快速给出一个靠谱选择剩下的10%无非是靠基准测试来判断。7.4 混合使用也是一种思路有些系统会同时维护一份map和一份unordered_map来兼顾有序遍历和快速查询。听上去有点浪费内存但确实是一种做法——利用map做范围操作利用unordered_map做精确查找。代价是双份插入/删除操作代码里要维护一致性。多数场景我更推荐先单一容器等到性能剖析确认瓶颈后再引入第二份。8. 常见问题与排查技巧实录8.1 问题unordered版本迭代输出顺序飘忽不定现象程序运行两次明明数据一样遍历unordered_map打印出来的顺序不一样。原因两次运行中哈希表的rehash时间点不一定一致取决于插入顺序和分配器行为或者你用到了随机化种子某些实现的哈希表引入了哈希种子随机化来抵抗碰撞攻击。顺序不一致是哈希表的合法行为。排查办法如果你发现自己的代码对迭代顺序产生了依赖第一反应应该是这里不该用unordered版本而不是去猜测哈希种子。比如取前3个元素这类逻辑在无序容器里含义就不明确。8.2 问题自定义哈希函数后出现大量重复键被错误合并现象用unordered_set存结构体两个本应不同的键被判定相等只有一份留下来了。原因哈希函数不合格两个不同的键计算出了相同的哈希值并且桶内比较时operator被错误实现成忽略某个字段导致认为它们相等。哈希碰撞本来就应该被处理同一个桶内逐个比较键是否真正相等但如果operator本身有问题那哈希表就必然会合并键。排查办法先用一个循环对全部数据调用哈希函数统计哈希值分布。如果某个哈希值出现在大于10倍的期望频率上大概率是哈希函数或等值比较有问题。再打印operator的所有比较路径确认没有漏字段。8.3 问题map的卡顿被误认为死循环现象数据量很大的时候map执行一个批量操作看起来像是卡死了。其实它只是稳定地在做O(N log N)的工作不像哈希表那样均匀地平稳运行。排查办法打印日志看看当前处理到第几条记录别直接按暂停。如果进度条持续增长只是慢如果根本没有进度增长才考虑死循环。以及留意map在极端插入模式下升序/降序依然保持稳定这本身就是它的优势。8.4 问题rehash时的迭代器失效导致崩溃现象一段持有迭代器的循环代码在unordered_map上偶发崩溃且崩不崩取决于数据量。原因插入触发rehash此前保存的迭代器全部失效下次解引用访问了已释放的内存。排查办法检查插入操作之前是否reserve了足够的桶。用if (m.bucket_count() expected) m.reserve(expected);来预防检查是否在循环中一遍插入一遍遍历这几乎总是危险姿势。建议把待插入数据先收集到vector插入阶段从vector批量塞进容器避免在遍历容器本身时插。这张表汇总了我遇到的高频问题和对应思路症状疑似原因处理方式unordered版本输出顺序不稳定哈希种子随机化/rehash时机不同确认协议不依赖顺序否则换set/map自定义类型键被错误合并operator漏字段或哈希碰撞过于严重校验等值比较实现统计哈希分布大数据量map操作明显慢树节点较多内存分散log级别遍历路径长换成unordered版本并reserve若需有序打印日志确认推进速度持有迭代器后插入导致崩溃rehash导致迭代器失效避免边遍历边插入用reserve预分配桶unordered_map占用内存超出预期桶数组翻倍扩容空桶白占内存关注负载因子map可能内存更紧凑8.5 提高调试效率的多用工具组合调试容器相关问题时我常配合使用几下几种手段打印bucket_count()和max_load_factor()确认负载因子到底是多少。桶数量远大于元素数量时容器内存白占得厉害。自己写个小循环把每个桶内链表长度打出来直观判断哈希函数的均匀性。给unordered_*容器预留容量时用reserve不要笨办法地去insert一堆dummy元素再erase那样白白触发多次rehash。排查“到底是map慢还是整个程序慢”时用采样性能剖析工具看热点函数而不是靠猜。9. 实战案例复盘一次消息路由模块的容器选型最后讲一个我实际处理的案例正好把前面这些理论串起来。某项目有个消息路由模块需要维护一张会话ID - 处理状态的映射表。会话ID用于查找状态字段需要按活跃时间做淘汰和清理。最初实现里用了一个std::unordered_mapSessionId, State查找性能确实没得说但问题出在“按时间范围清理旧会话”上。因为unordered_map没有有序性清理时需要把全部会话ID都拿出来排序然后取前N个淘汰。日志量一上来每次清理的开销从一次范围遍历变成了全量排序删除复杂度被无谓放大。排查后才意识到会话状态的管理天然需要按时间取范围这个需求更适合std::map按时间键做范围查询。最终方案是调整数据结构维护一个很小的时间索引std::mapTimePoint, SessionId配合主表unordered_mapSessionId, State使用。插入时同时更新两份清理时只对时间索引做lower_bound遍历删除再回头从主表remove。实际效果单次清理成本从原来的O(N log N)降到了O(K log N)K为本次淘汰的会话数内存多花了约15%但吞吐量和延迟都显著改善。复盘这次调整本质上还是回到那个朴素的判断无序容器解决不了有序能力的需求反过来有序容器在点查询上也拼不过哈希表。选容器本质是选数据模型先想清楚业务需要什么能力再决定用什么容器表达。10. 我的选型心得和一些补充唠叨折腾过很多个项目我在容器选择上的核心心得是不要被O(1)唬住也不要被稳定有序绑架重点是识别业务能力需求再配合实测数据验证。如果你拿不准就先把代码写出来跑一个数据规模符合生产的基准测试看结果再定。几个补充tips分享给大家每次写unordered_map时先想清楚数据规模上界能reserve就reserve。这是成本最低的优化效果立竿见影。std::map对小数据量的性能并没想象中那么差尤其元素类型重、比较成本低时。如果你的数据量撑死几百条别为了性能硬上unordered_map牺牲有序性。对于一些明显适合有序语义的接口比如取第一个/最后一个找相邻元素map有一整套现成API改用unordered_map等于要自己造轮子。注意你的迭代器使用生命周期。如果指向元素的指针/引用被保存到别处选有序容器更稳妥。别忘记set底层就是只带键的map两者的特性和适用范围完全对应。一个结构体的set其实等价于键为结构体、值为空占位的map。自定义类型进unordered_*前先确认operator和哈希函数两者都正确并且满足“相等则哈希一定相等”的基本要求——如果两个对象operator为真但哈希不同哈希表内部行为会是未定义的查不到数据甚至崩溃。从选用容器的角度set/map和unordered_set/unordered_map没有绝对的高下之分只有哪个更适合你的场景。做技术决策时多问一句这个容器需要提供什么迭代语义大部分纠结都能迎刃而解。至于性能的极限还是要靠测试说话不要靠网上别人的一句结论打天下。
