1. 项目概述被忽视的“多值”哈希容器在C的日常开发里std::unordered_set和std::unordered_map这对哈希表兄弟几乎是每个开发者工具箱里的常客。无论是做数据去重、快速查找还是缓存实现它们都扮演着关键角色。但如果你打开标准库的容器全家福会发现一个名字更长、但出场率极低的成员std::unordered_multiset。我敢说超过90%的C程序员在项目里从未主动使用过它甚至可能只在面试八股文里见过这个名字。这其实挺可惜的因为它在解决一类特定问题时比手动“造轮子”要优雅和高效得多。简单来说std::unordered_multiset就是一个允许存储重复键Key的无序集合。你可以把它理解为一个“值就是键”的std::unordered_multimap或者一个“允许重复元素”的std::unordered_set。它的核心价值在于当你需要快速统计、管理或查询一组允许重复的、无序的数据时它能提供接近O(1)时间复杂度的插入、查找和计数操作。想象一下这样的场景你需要实时分析一段文本中每个单词出现的频率或者监控一个数据流中不同事件ID发生的次数又或者在一个游戏里管理同一类道具的多个实例比如玩家背包里的10个“治疗药水”。在这些情况下unordered_multiset就是为你量身定制的工具。然而现实是很多开发者遇到这类需求时第一反应可能是用std::vector手动遍历或排序或者用std::unordered_mapT, int来手动计数。前者在数据量大时效率堪忧后者虽然可行但增加了“值”这个冗余维度代码意图不够直观。unordered_multiset的“冷门”恰恰反映了我们对标准库工具认知的不全面。接下来我们就深入这个被忽略的容器看看它的设计哲学、核心用法并深入到开源项目的源码中学习高手们是如何将它物尽其用的。2. 核心原理与设计哲学解析2.1 与兄弟容器的本质区别要理解unordered_multiset最好的方式就是把它放在家族中进行对比。我们把它和unordered_set、unordered_map放在一起看。std::unordered_setT这是一个经典的哈希集合。它的核心承诺是“唯一性”。对于给定的哈希函数和相等比较器集合中不会存在两个相等的元素。当你尝试插入一个已经存在的元素时insert方法会返回一个pairiterator, bool其中bool为false表示插入失败如果使用emplace也是类似逻辑。它的内部可以看作一个存储了唯一键的哈希表。std::unordered_multisetT这是本次的主角。它移除了“唯一性”约束。多个相等的元素可以同时存在于容器中。它的insert方法永远成功总是返回指向新插入元素的迭代器。因此size()可以大于bucket_count()。它的存在本质上是为了高效处理“多重集”这个数学概念。std::unordered_mapK, V与std::unordered_multimapK, V这对映射容器与上述集合容器的关系类似。map要求键唯一而multimap允许重复键。unordered_multiset可以看作是unordered_multimapT, void的一种特化只不过接口更专注于元素本身。选择哪一个根本上是业务逻辑决定的需要确保唯一性用于去重或存在性检查-unordered_set。需要存储键值对且键唯一-unordered_map。需要存储键值对且键可重复-unordered_multimap。需要存储可重复的元素并对其进行快速计数、批量删除等操作-unordered_multiset。2.2 底层数据结构与性能特征unordered_multiset的底层通常也是基于哈希表实现的具体来说是“开链法”separate chaining的哈希桶。每个桶bucket是一个链表或类似结构所有哈希到同一位置的元素都会被放入这个链表中。对于允许重复元素的multiset插入操作变得非常简单计算元素的哈希值找到对应的桶然后将新元素插入到该桶的链表前端通常如此以实现O(1)插入。它不需要像set那样先去检查整个桶里是否有重复元素。这使得unordered_multiset的平均时间复杂度依然非常优秀插入insert平均O(1)最坏O(n)当哈希冲突极端严重时。查找find平均O(1)最坏O(n)。注意find会返回指向第一个找到的匹配元素的迭代器。计数count平均O(1)最坏O(n)。这个操作是multiset的亮点它需要遍历整个匹配的桶链表来统计数量。删除erase通过迭代器删除平均O(1)最坏O(n)。通过值删除erase(value)这会删除所有等于该值的元素其时间复杂度平均为O(1) O(匹配元素数)最坏O(n)。这是一个需要特别注意的行为。注意count操作在元素重复很多时最坏情况可能退化为O(n)因为它需要遍历桶内所有相同元素。如果你的场景中某个元素重复量极大例如上百万次且频繁调用count这可能成为性能瓶颈。此时需要评估哈希函数的质量和负载因子。2.3 关键API与使用模式unordered_multiset的API大部分与unordered_set相同但有几个关键区别体现了其“多重”特性insert总是成功它不返回pair而是直接返回指向新插入元素的迭代器。这是最直观的区别。std::unordered_multisetint ms; auto it ms.insert(42); // 总是成功it指向新插入的42 ms.insert(42); // 再插入一个42同样成功count(key)返回数量这是它的核心优势之一。直接告诉你这个元素在容器里有多少个副本。std::cout ms.count(42); // 输出2equal_range(key)返回迭代器对由于find只返回第一个匹配元素如果你想获取所有等于key的元素范围就需要equal_range。它返回一个pairiterator, iterator表示这个范围的起止。auto range ms.equal_range(42); for (auto it range.first; it ! range.second; it) { std::cout *it ; } // 输出42 42 注意顺序是不确定的erase(key)删除所有匹配项这是一个“批量”操作。如果你只想删除其中一个必须通过迭代器。ms.erase(42); // 删除所有值为42的元素现在ms为空 ms.insert(42); ms.insert(42); auto it ms.find(42); if (it ! ms.end()) { ms.erase(it); // 只删除第一个找到的42 } std::cout ms.count(42); // 输出1理解这些API的细微差别是正确、高效使用unordered_multiset的基础。很多陷阱都源于用set的思维惯性去操作multiset。3. 开源项目实战案例深度剖析理论说再多不如看看真实的战场。我们深入到几个知名开源项目的源码中看看unordered_multiset是如何被实际应用的。这不仅能巩固理解更能学到一流的工程实践。3.1 案例一Clang编译器中的符号表管理近似场景Clang/LLVM是一个巨大的C项目其内部有复杂的中间表示和符号管理。虽然我无法直接找到一个标标准准的unordered_multiset用例因为很多自定义结构使用了自己的哈希表实现但我们可以分析一个非常类似的需求模式来理解multiset的用武之地。考虑编译器在解析一个C源文件时需要处理重载函数。在同一个作用域内多个函数可以拥有相同的名字即符号名只要它们的参数类型不同。编译器需要快速查询“在当前作用域里名为‘foo’的函数有哪些”一个朴素的做法是使用unordered_mapstd::string, std::vectorFunctionDecl*。键是函数名值是一个列表存储所有重载函数声明。这当然可以工作。但换一个角度如果我们把FunctionDecl*本身作为元素并定义一个自定义的哈希函数和相等比较器只比较函数名的哈希和相等性那么unordered_multisetFunctionDecl*, NameHash, NameEqual就成为了一个更直接的模型。插入一个函数声明就是简单的insert查询所有同名函数就是equal_range(funcName)。容器本身直接表达了“可重复键的集合”这一概念代码更清晰。在LLVM的某些辅助数据结构或分析模块中你可能会看到这种模式的变体。例如在管理可能重复的调试信息符号或者在某些非关键路径的统计收集代码中使用标准库容器能极大简化代码。从中学到的经验当你发现自己在用mapT, vectorU来模拟一个“键可重复”的映射时就应该立刻想到unordered_multiset或multimap。后者将“值容器”的逻辑内化提供了更统一、更不易出错的接口。3.2 案例二游戏引擎中的对象ID或事件管理我们来看一个更具体的假设性案例灵感来源于一些轻量级游戏引擎或网络服务器。假设有一个游戏服务器需要管理成千上万个玩家发出的“攻击事件”。每个事件有一个event_id可能重复比如同一个技能ID和一个时间戳。服务器的一个系统需要快速取出所有特定event_id的事件进行处理。使用unordered_multiset的方案struct GameEvent { int event_id; int64_t timestamp; // ... 其他数据 }; struct EventIdHash { std::size_t operator()(const GameEvent e) const { return std::hashint{}(e.event_id); } }; struct EventIdEqual { bool operator()(const GameEvent a, const GameEvent b) const { return a.event_id b.event_id; } }; std::unordered_multisetGameEvent, EventIdHash, EventIdEqual active_events; // 插入事件 active_events.insert(GameEvent{1001, getCurrentTime()}); active_events.insert(GameEvent{1002, getCurrentTime()}); active_events.insert(GameEvent{1001, getCurrentTime()}); // 重复event_id允许插入 // 处理所有event_id为1001的事件 auto range active_events.equal_range(GameEvent{1001, 0}); // 构造一个临时对象用于查找timestamp被忽略 for (auto it range.first; it ! range.second; ) { processEvent(*it); it active_events.erase(it); // 处理完后删除注意迭代器失效问题用返回值更新it }在这个例子中我们通过自定义哈希和相等比较器让unordered_multiset只关注event_id。这比使用unordered_mapint, vectorGameEvent更简洁因为equal_range直接给出了迭代器范围无需访问中间层的vector。实操心得自定义哈希和相等比较器是使用unordered_multiset处理复杂类型的关键。务必确保两个比较器逻辑一致如果EventIdEqual(a, b)返回true那么EventIdHash(a)和EventIdHash(b)必须返回相同的值。否则会导致元素存储在错误的桶中引发未定义行为。3.3 案例三高性能网络库中的连接或会话管理在一些网络框架中可能需要根据客户端IP地址或IP:Port对来管理连接。有时一个客户端地址可能会建立多个连接例如浏览器并发请求。我们需要快速统计来自某个IP的连接数或者批量关闭某个IP的所有连接。这里unordered_multiset又可以派上用场。我们可以将连接对象或它的标识符存入集合哈希和比较均基于IP地址。class Connection; // 前向声明 std::unordered_multisetstd::shared_ptrConnection, IPHash, IPEqual connections_by_ip; // 当新连接建立时 connections_by_ip.insert(new_conn); // 获取某个IP的活跃连接数 int count connections_by_ip.count(dummy_conn_with_target_ip); // 强制断开某个IP的所有连接 auto range connections_by_ip.equal_range(dummy_conn_with_target_ip); for (auto it range.first; it ! range.second; ) { (*it)-force_close(); it connections_by_ip.erase(it); // 从管理容器中移除 }这种做法的好处是管理逻辑按IP分组和存储结构高度统一。当需要实现如“单IP连接数限制”的功能时count()操作是O(1)的平均复杂度非常高效。注意事项在类似网络编程的场景中需要特别注意迭代器失效和线程安全。上述例子中在遍历equal_range返回的范围并执行erase时我们使用了erase的返回值来更新迭代器这是安全的。但如果是在多线程环境下任何对容器的插入、删除操作都需要通过锁如std::mutex或更精细的并发数据结构如并发哈希表来保护unordered_multiset本身不是线程安全的。4. 高级用法、陷阱与性能调优掌握了基本用法和场景后我们来看看一些进阶技巧和容易踩的坑。4.1 自定义哈希与相等比较器的艺术这是使用unordered_multiset乃至所有无序容器最需要技巧的地方。除了前面提到的哈希与相等逻辑必须一致外还有几个要点哈希质量差的哈希函数会导致大量冲突使容器退化成链表性能急剧下降。对于自定义结构体一个好的做法是组合其成员的标准哈希值。struct Player { std::string account_id; std::string region; int level; }; struct PlayerHash { std::size_t operator()(const Player p) const { // 使用std::hash组合 boost::hash_combine是更好的选择 std::size_t h1 std::hashstd::string{}(p.account_id); std::size_t h2 std::hashstd::string{}(p.region); std::size_t h3 std::hashint{}(p.level); // 一个简单的组合方式注意这可能不是最佳的 return h1 ^ (h2 1) ^ (h3 2); } };对于生产环境建议参考boost::hash_combine的实现它能产生分布更好的哈希值。相等比较的代价相等比较器Equal可能会被频繁调用尤其是在冲突的桶内查找时。确保它的实现是轻量级的。如果比较很昂贵可能需要重新设计哈希函数以减少冲突。只比较“键”部分正如前面的游戏事件例子我们经常只希望容器根据对象的某一部分键来管理重复性。这时哈希和相等比较器都只应关注那个“键”部分忽略其他字段。这是unordered_multiset比unordered_map更灵活的地方因为“值”部分就是对象本身。4.2 迭代器失效与删除操作的陷阱无序容器的迭代器失效规则需要牢记插入元素可能导致迭代器失效如果插入操作引起了重哈希即元素数量超过max_load_factor() * bucket_count()。但指向具体元素的引用和指针仍然有效。删除元素指向被删除元素的迭代器会失效。但是指向其他未删除元素的迭代器、引用和指针仍然有效。这对于unordered_multiset的erase操作尤为重要。当你用erase(key)删除所有匹配项时这些元素的迭代器自然都失效了。当你用迭代器删除一个元素时只有当前迭代器失效。因此安全的遍历删除模式是std::unordered_multisetint ms {1, 2, 2, 3, 2, 4}; int value_to_remove 2; // 错误做法删除后迭代器失效再会导致未定义行为 // for (auto it ms.begin(); it ! ms.end(); it) { // if (*it value_to_remove) { // ms.erase(it); // } // } // 正确做法1利用erase返回值C11起 for (auto it ms.begin(); it ! ms.end(); ) { if (*it value_to_remove) { it ms.erase(it); // erase返回被删除元素之后元素的迭代器 } else { it; } } // 正确做法2使用equal_range进行范围删除 auto range ms.equal_range(value_to_remove); ms.erase(range.first, range.second); // 一次性删除整个范围第二种方法erase(range.first, range.second)通常更高效因为它可能触发容器内部更优化的批量删除逻辑。4.3 性能调优负载因子与桶的数量unordered_multiset的性能高度依赖于哈希冲突的程度。有两个关键参数可以调整负载因子Load Factorload_factor() size() / bucket_count()。它衡量桶的平均填充程度。默认的最大负载因子max_load_factor()通常是1.0。当load_factor() max_load_factor()时容器会自动增加桶的数量并重哈希rehash这是一个O(n)的操作。调小max_load_factor例如0.7容器会更早地进行重哈希保持更稀疏的桶从而减少冲突提升查找/插入速度但会消耗更多内存。调大max_load_factor例如1.5容器能容纳更多元素才重哈希更节省内存但冲突可能更严重性能下降。std::unordered_multisetint ms; ms.max_load_factor(0.75); // 设置为0.75桶的数量Bucket Count你可以在构造时或之后通过rehash或reserve来指定一个预期的桶数量。rehash(n)将桶数量设置为至少n并可能触发重哈希。reserve(n)将容器容量桶数量设置为至少能容纳n个元素而不会超过最大负载因子。这通常比rehash更直观。std::unordered_multisetint ms; ms.reserve(10000); // 预分配足够空间避免插入过程中的多次重哈希 for (int i 0; i 10000; i) { ms.insert(gen_value()); }如果你能提前知道元素数量的大致范围使用reserve是提升性能最有效的手段之一。性能测试小技巧在关键路径上使用unordered_multiset时最好用真实或模拟的数据进行性能剖析Profiling。关注load_factor()、bucket_count()以及max_load_factor。如果发现冲突严重某个桶的bucket_size特别大可能需要优化哈希函数。5. 替代方案对比与选型指南unordered_multiset并非银弹在很多场景下其他数据结构可能是更好的选择。我们来做一个系统的对比。数据结构核心特性适用场景不适用场景与unordered_multiset对比std::unordered_multiset哈希表允许重复元素O(1)平均查找/插入。1.快速计数count。2.按重复键批量操作equal_range,erase(key)。3. 元素顺序无关紧要。1. 需要元素有序遍历。2. 重复元素数量极多且频繁count最坏O(n)。3. 内存极度受限无法接受哈希表开销。基准std::vectorstd::sort/std::binary_search动态数组排序后二分查找。1. 数据一次性加载后续以查询为主。2. 需要内存连续缓存友好。3. 需要有序遍历。1. 频繁的插入/删除中间位置操作O(n)。2. 实时性要求高的动态数据集。向量在静态或批量处理数据时有序二分查找的O(log n)可能优于哈希表的常数因子开销。但动态增删效率低。std::multiset红黑树允许重复元素元素自动排序O(log n)查找/插入。1. 需要元素始终有序。2. 需要范围查询如找到所有在[A, B]区间的元素。3. 对最坏情况时间复杂度有严格要求避免哈希冲突导致的O(n)。1. 对平均插入/查找性能要求极高且不关心顺序。2. 内存开销比哈希表更敏感树节点开销通常更大。有序多集用O(log n)的确定性时间换取了有序性。如果不需要顺序unordered版本通常更快。std::unordered_mapT, int哈希表键唯一值用于计数。1.仅需要计数功能且后续不需要按元素本身进行其他操作。2. 代码逻辑更直观map[key]。1. 需要基于元素本身进行equal_range式的范围遍历。2. 需要存储的“元素”本身就是完整的对象而不仅仅是计数。计数映射是模拟multiset计数的常见方式。它更节省空间一个计数 vs. 多个重复对象但失去了直接管理重复对象本身的能力。std::unordered_mapT, std::vectorU哈希表键唯一值为列表。1. 键对应的“值”是复杂的关联数据而不仅仅是重复的键本身。2. 需要对同一键下的多个值进行复杂的列表操作。1. 键和值本质是同一个对象或对象的键部分。2. 只需要简单的存在性检查、计数或批量删除。映射到向量功能最强大也最通用但接口更复杂需要手动管理vector。unordered_multiset是它的一个特化和简化。选型决策流程图是否需要存储键值对是 - 考虑(unordered_)map或(unordered_)multimap。存储的元素是否允许重复否 - 考虑(unordered_)set。允许重复且主要操作是快速插入、查找、计数且不关心顺序是 -首选unordered_multiset。是否需要元素始终保持有序是 - 考虑multiset。数据是否相对静态以查询为主是 - 考虑排序后的vector。是否只需要统计次数不需要保留重复元素本身是 - 考虑unordered_mapT, int。6. 一个完整的实战示例简易单词频率统计器让我们用一个完整的、可编译运行的例子来整合所有知识点。这个程序模拟一个简单的日志处理器统计来自不同模块的日志消息的出现频率。#include iostream #include string #include unordered_set #include unordered_map #include vector #include algorithm #include chrono #include random // 案例使用 unordered_multiset 进行单词频率统计和查询 void demo_word_frequency() { std::cout 示例使用 unordered_multiset 统计单词频率 \n; // 模拟一段文本单词可重复 std::vectorstd::string words { the, quick, brown, fox, jumps, over, the, lazy, dog, the, fox, is, quick, and, the, dog, is, lazy }; // 方法1使用 unordered_multiset (最直接) std::unordered_multisetstd::string word_multiset(words.begin(), words.end()); std::cout 使用 unordered_multiset:\n; for (const auto word : {the, fox, is, unknown}) { std::cout Word word appears word_multiset.count(word) times.\n; } // 展示 equal_range 的用法 std::cout \n所有 the 的位置迭代器值实际无序: ; auto [begin, end] word_multiset.equal_range(the); // C17 结构化绑定 for (auto it begin; it ! end; it) { std::cout (*it) ; // 打印地址证明是不同对象 } std::cout \n; // 方法2使用 unordered_map 手动计数 (常见替代方案) std::unordered_mapstd::string, int word_count_map; for (const auto word : words) { word_count_map[word]; } std::cout \n使用 unordered_map 计数:\n; std::cout Word the appears word_count_map[the] times.\n; // 性能对比简单演示 std::cout \n----- 简单性能对比 -----\n; constexpr size_t NUM_ELEMENTS 100000; std::vectorint data(NUM_ELEMENTS); std::mt19937 gen(42); std::uniform_int_distribution dis(1, 1000); // 生成1-1000的随机数会有大量重复 std::generate(data.begin(), data.end(), [](){ return dis(gen); }); // 测试 unordered_multiset 插入和计数 { auto start std::chrono::high_resolution_clock::now(); std::unordered_multisetint test_ms; test_ms.reserve(NUM_ELEMENTS); // 预分配避免重哈希 for (int val : data) { test_ms.insert(val); } // 随机查询一些值的计数 long long total_count 0; for (int i 0; i 1000; i) { total_count test_ms.count(dis(gen)); } auto end std::chrono::high_resolution_clock::now(); auto duration std::chrono::duration_caststd::chrono::microseconds(end - start); std::cout unordered_multiset 插入 NUM_ELEMENTS 元素并查询1000次计数耗时: duration.count() 微秒\n; } // 测试 unordered_map 插入和计数 { auto start std::chrono::high_resolution_clock::now(); std::unordered_mapint, int test_map; test_map.reserve(NUM_ELEMENTS); for (int val : data) { test_map[val]; } long long total_count 0; for (int i 0; i 1000; i) { auto it test_map.find(dis(gen)); total_count (it ! test_map.end()) ? it-second : 0; } auto end std::chrono::high_resolution_clock::now(); auto duration std::chrono::duration_caststd::chrono::microseconds(end - start); std::cout unordered_map 插入 NUM_ELEMENTS 元素并查询1000次计数耗时: duration.count() 微秒\n; } std::cout \n\n; } // 案例自定义类型的 unordered_multiset void demo_custom_type() { std::cout 示例自定义类型在 unordered_multiset 中的应用 \n; struct LogMessage { std::string module; int level; // 1:DEBUG, 2:INFO, 3:ERROR std::string content; // 重载 运算符用于默认的 Equal 比较但我们需要自定义只比较module // bool operator(const LogMessage other) const { // return module other.module level other.level content other.content; // } // 注意对于我们的场景我们不使用默认的而是自定义比较器。 }; // 自定义哈希只对 module 字符串哈希 struct LogModuleHash { std::size_t operator()(const LogMessage msg) const { return std::hashstd::string{}(msg.module); } }; // 自定义相等比较只比较 module struct LogModuleEqual { bool operator()(const LogMessage a, const LogMessage b) const { return a.module b.module; } }; using LogMultiset std::unordered_multisetLogMessage, LogModuleHash, LogModuleEqual; LogMultiset logMessages; // 插入一些日志 logMessages.insert({Network, 2, Connection established.}); logMessages.insert({Database, 1, Query started.}); logMessages.insert({Network, 3, Timeout occurred!}); logMessages.insert({Network, 2, Data packet sent.}); logMessages.insert({UI, 2, Window rendered.}); // 查询某个模块的所有日志数量 std::string targetModule Network; LogMessage dummyMsg{targetModule, 0, }; // 用于查找的临时对象 int networkLogCount logMessages.count(dummyMsg); std::cout Module targetModule has networkLogCount log messages.\n; // 获取并打印某个模块的所有日志内容 std::cout Details of targetModule logs:\n; auto [begin, end] logMessages.equal_range(dummyMsg); for (auto it begin; it ! end; it) { std::cout [Level it-level ] it-content \n; } // 删除某个模块的所有ERROR日志 for (auto it begin; it ! end; ) { if (it-level 3) { // ERROR level it logMessages.erase(it); } else { it; } } networkLogCount logMessages.count(dummyMsg); std::cout After removing ERROR logs, Module targetModule has networkLogCount log messages left.\n; std::cout \n; } int main() { demo_word_frequency(); demo_custom_type(); return 0; }这个示例展示了基础用法count,equal_range。与unordered_map的对比在纯计数场景下两者性能接近但multiset的接口更贴近“多重集合”的语义。自定义类型的使用如何通过自定义哈希和相等比较器让容器只关注对象的一部分module字段。安全的遍历删除在equal_range返回的范围内结合erase返回值来安全地删除特定条件的元素。编译并运行这个程序你可以直观地看到unordered_multiset是如何工作的以及它在特定场景下的简洁性。7. 总结与个人使用体会回顾整篇文章我们从为什么unordered_multiset被忽略开始深入剖析了它的原理、与其它容器的区别、核心API的微妙之处并通过开源项目的思维案例和完整代码示例展示了它的实用场景。最后我们还探讨了性能调优和与其他数据结构的选型对比。我个人的体会是unordered_multiset的“冷门”并非因为它无用而是因为它的应用场景相对特定且容易被其他更通用的结构如mapvector所替代。但正是这种特定性使得它在解决“允许重复的快速查找、计数”这类问题时代码显得异常清晰和优雅。它让数据结构的意图直接体现在类型声明中减少了手动管理中间容器的复杂度。在实际项目中当我遇到需要频繁查询某个元素是否存在且可能多次存在或者需要快速获取某个元素的所有实例时unordered_multiset总会是我的备选方案之一。尤其是在原型设计阶段用它来快速实现一个功能代码会非常简洁。如果后续性能分析成为瓶颈再考虑更换为更底层的结构或优化哈希函数也不迟。最后一个小技巧如果你不确定该用set还是multiset问自己一个问题“在我的业务逻辑里两个完全相同的元素同时存在是否有意义”如果答案是“有”那么multiset就是你的朋友。给它一个机会或许你会发现那些曾经需要额外代码处理的“重复数据”现在可以被容器优雅地管理起来。
C++ unordered_multiset 哈希容器：原理、实战与性能优化指南
1. 项目概述被忽视的“多值”哈希容器在C的日常开发里std::unordered_set和std::unordered_map这对哈希表兄弟几乎是每个开发者工具箱里的常客。无论是做数据去重、快速查找还是缓存实现它们都扮演着关键角色。但如果你打开标准库的容器全家福会发现一个名字更长、但出场率极低的成员std::unordered_multiset。我敢说超过90%的C程序员在项目里从未主动使用过它甚至可能只在面试八股文里见过这个名字。这其实挺可惜的因为它在解决一类特定问题时比手动“造轮子”要优雅和高效得多。简单来说std::unordered_multiset就是一个允许存储重复键Key的无序集合。你可以把它理解为一个“值就是键”的std::unordered_multimap或者一个“允许重复元素”的std::unordered_set。它的核心价值在于当你需要快速统计、管理或查询一组允许重复的、无序的数据时它能提供接近O(1)时间复杂度的插入、查找和计数操作。想象一下这样的场景你需要实时分析一段文本中每个单词出现的频率或者监控一个数据流中不同事件ID发生的次数又或者在一个游戏里管理同一类道具的多个实例比如玩家背包里的10个“治疗药水”。在这些情况下unordered_multiset就是为你量身定制的工具。然而现实是很多开发者遇到这类需求时第一反应可能是用std::vector手动遍历或排序或者用std::unordered_mapT, int来手动计数。前者在数据量大时效率堪忧后者虽然可行但增加了“值”这个冗余维度代码意图不够直观。unordered_multiset的“冷门”恰恰反映了我们对标准库工具认知的不全面。接下来我们就深入这个被忽略的容器看看它的设计哲学、核心用法并深入到开源项目的源码中学习高手们是如何将它物尽其用的。2. 核心原理与设计哲学解析2.1 与兄弟容器的本质区别要理解unordered_multiset最好的方式就是把它放在家族中进行对比。我们把它和unordered_set、unordered_map放在一起看。std::unordered_setT这是一个经典的哈希集合。它的核心承诺是“唯一性”。对于给定的哈希函数和相等比较器集合中不会存在两个相等的元素。当你尝试插入一个已经存在的元素时insert方法会返回一个pairiterator, bool其中bool为false表示插入失败如果使用emplace也是类似逻辑。它的内部可以看作一个存储了唯一键的哈希表。std::unordered_multisetT这是本次的主角。它移除了“唯一性”约束。多个相等的元素可以同时存在于容器中。它的insert方法永远成功总是返回指向新插入元素的迭代器。因此size()可以大于bucket_count()。它的存在本质上是为了高效处理“多重集”这个数学概念。std::unordered_mapK, V与std::unordered_multimapK, V这对映射容器与上述集合容器的关系类似。map要求键唯一而multimap允许重复键。unordered_multiset可以看作是unordered_multimapT, void的一种特化只不过接口更专注于元素本身。选择哪一个根本上是业务逻辑决定的需要确保唯一性用于去重或存在性检查-unordered_set。需要存储键值对且键唯一-unordered_map。需要存储键值对且键可重复-unordered_multimap。需要存储可重复的元素并对其进行快速计数、批量删除等操作-unordered_multiset。2.2 底层数据结构与性能特征unordered_multiset的底层通常也是基于哈希表实现的具体来说是“开链法”separate chaining的哈希桶。每个桶bucket是一个链表或类似结构所有哈希到同一位置的元素都会被放入这个链表中。对于允许重复元素的multiset插入操作变得非常简单计算元素的哈希值找到对应的桶然后将新元素插入到该桶的链表前端通常如此以实现O(1)插入。它不需要像set那样先去检查整个桶里是否有重复元素。这使得unordered_multiset的平均时间复杂度依然非常优秀插入insert平均O(1)最坏O(n)当哈希冲突极端严重时。查找find平均O(1)最坏O(n)。注意find会返回指向第一个找到的匹配元素的迭代器。计数count平均O(1)最坏O(n)。这个操作是multiset的亮点它需要遍历整个匹配的桶链表来统计数量。删除erase通过迭代器删除平均O(1)最坏O(n)。通过值删除erase(value)这会删除所有等于该值的元素其时间复杂度平均为O(1) O(匹配元素数)最坏O(n)。这是一个需要特别注意的行为。注意count操作在元素重复很多时最坏情况可能退化为O(n)因为它需要遍历桶内所有相同元素。如果你的场景中某个元素重复量极大例如上百万次且频繁调用count这可能成为性能瓶颈。此时需要评估哈希函数的质量和负载因子。2.3 关键API与使用模式unordered_multiset的API大部分与unordered_set相同但有几个关键区别体现了其“多重”特性insert总是成功它不返回pair而是直接返回指向新插入元素的迭代器。这是最直观的区别。std::unordered_multisetint ms; auto it ms.insert(42); // 总是成功it指向新插入的42 ms.insert(42); // 再插入一个42同样成功count(key)返回数量这是它的核心优势之一。直接告诉你这个元素在容器里有多少个副本。std::cout ms.count(42); // 输出2equal_range(key)返回迭代器对由于find只返回第一个匹配元素如果你想获取所有等于key的元素范围就需要equal_range。它返回一个pairiterator, iterator表示这个范围的起止。auto range ms.equal_range(42); for (auto it range.first; it ! range.second; it) { std::cout *it ; } // 输出42 42 注意顺序是不确定的erase(key)删除所有匹配项这是一个“批量”操作。如果你只想删除其中一个必须通过迭代器。ms.erase(42); // 删除所有值为42的元素现在ms为空 ms.insert(42); ms.insert(42); auto it ms.find(42); if (it ! ms.end()) { ms.erase(it); // 只删除第一个找到的42 } std::cout ms.count(42); // 输出1理解这些API的细微差别是正确、高效使用unordered_multiset的基础。很多陷阱都源于用set的思维惯性去操作multiset。3. 开源项目实战案例深度剖析理论说再多不如看看真实的战场。我们深入到几个知名开源项目的源码中看看unordered_multiset是如何被实际应用的。这不仅能巩固理解更能学到一流的工程实践。3.1 案例一Clang编译器中的符号表管理近似场景Clang/LLVM是一个巨大的C项目其内部有复杂的中间表示和符号管理。虽然我无法直接找到一个标标准准的unordered_multiset用例因为很多自定义结构使用了自己的哈希表实现但我们可以分析一个非常类似的需求模式来理解multiset的用武之地。考虑编译器在解析一个C源文件时需要处理重载函数。在同一个作用域内多个函数可以拥有相同的名字即符号名只要它们的参数类型不同。编译器需要快速查询“在当前作用域里名为‘foo’的函数有哪些”一个朴素的做法是使用unordered_mapstd::string, std::vectorFunctionDecl*。键是函数名值是一个列表存储所有重载函数声明。这当然可以工作。但换一个角度如果我们把FunctionDecl*本身作为元素并定义一个自定义的哈希函数和相等比较器只比较函数名的哈希和相等性那么unordered_multisetFunctionDecl*, NameHash, NameEqual就成为了一个更直接的模型。插入一个函数声明就是简单的insert查询所有同名函数就是equal_range(funcName)。容器本身直接表达了“可重复键的集合”这一概念代码更清晰。在LLVM的某些辅助数据结构或分析模块中你可能会看到这种模式的变体。例如在管理可能重复的调试信息符号或者在某些非关键路径的统计收集代码中使用标准库容器能极大简化代码。从中学到的经验当你发现自己在用mapT, vectorU来模拟一个“键可重复”的映射时就应该立刻想到unordered_multiset或multimap。后者将“值容器”的逻辑内化提供了更统一、更不易出错的接口。3.2 案例二游戏引擎中的对象ID或事件管理我们来看一个更具体的假设性案例灵感来源于一些轻量级游戏引擎或网络服务器。假设有一个游戏服务器需要管理成千上万个玩家发出的“攻击事件”。每个事件有一个event_id可能重复比如同一个技能ID和一个时间戳。服务器的一个系统需要快速取出所有特定event_id的事件进行处理。使用unordered_multiset的方案struct GameEvent { int event_id; int64_t timestamp; // ... 其他数据 }; struct EventIdHash { std::size_t operator()(const GameEvent e) const { return std::hashint{}(e.event_id); } }; struct EventIdEqual { bool operator()(const GameEvent a, const GameEvent b) const { return a.event_id b.event_id; } }; std::unordered_multisetGameEvent, EventIdHash, EventIdEqual active_events; // 插入事件 active_events.insert(GameEvent{1001, getCurrentTime()}); active_events.insert(GameEvent{1002, getCurrentTime()}); active_events.insert(GameEvent{1001, getCurrentTime()}); // 重复event_id允许插入 // 处理所有event_id为1001的事件 auto range active_events.equal_range(GameEvent{1001, 0}); // 构造一个临时对象用于查找timestamp被忽略 for (auto it range.first; it ! range.second; ) { processEvent(*it); it active_events.erase(it); // 处理完后删除注意迭代器失效问题用返回值更新it }在这个例子中我们通过自定义哈希和相等比较器让unordered_multiset只关注event_id。这比使用unordered_mapint, vectorGameEvent更简洁因为equal_range直接给出了迭代器范围无需访问中间层的vector。实操心得自定义哈希和相等比较器是使用unordered_multiset处理复杂类型的关键。务必确保两个比较器逻辑一致如果EventIdEqual(a, b)返回true那么EventIdHash(a)和EventIdHash(b)必须返回相同的值。否则会导致元素存储在错误的桶中引发未定义行为。3.3 案例三高性能网络库中的连接或会话管理在一些网络框架中可能需要根据客户端IP地址或IP:Port对来管理连接。有时一个客户端地址可能会建立多个连接例如浏览器并发请求。我们需要快速统计来自某个IP的连接数或者批量关闭某个IP的所有连接。这里unordered_multiset又可以派上用场。我们可以将连接对象或它的标识符存入集合哈希和比较均基于IP地址。class Connection; // 前向声明 std::unordered_multisetstd::shared_ptrConnection, IPHash, IPEqual connections_by_ip; // 当新连接建立时 connections_by_ip.insert(new_conn); // 获取某个IP的活跃连接数 int count connections_by_ip.count(dummy_conn_with_target_ip); // 强制断开某个IP的所有连接 auto range connections_by_ip.equal_range(dummy_conn_with_target_ip); for (auto it range.first; it ! range.second; ) { (*it)-force_close(); it connections_by_ip.erase(it); // 从管理容器中移除 }这种做法的好处是管理逻辑按IP分组和存储结构高度统一。当需要实现如“单IP连接数限制”的功能时count()操作是O(1)的平均复杂度非常高效。注意事项在类似网络编程的场景中需要特别注意迭代器失效和线程安全。上述例子中在遍历equal_range返回的范围并执行erase时我们使用了erase的返回值来更新迭代器这是安全的。但如果是在多线程环境下任何对容器的插入、删除操作都需要通过锁如std::mutex或更精细的并发数据结构如并发哈希表来保护unordered_multiset本身不是线程安全的。4. 高级用法、陷阱与性能调优掌握了基本用法和场景后我们来看看一些进阶技巧和容易踩的坑。4.1 自定义哈希与相等比较器的艺术这是使用unordered_multiset乃至所有无序容器最需要技巧的地方。除了前面提到的哈希与相等逻辑必须一致外还有几个要点哈希质量差的哈希函数会导致大量冲突使容器退化成链表性能急剧下降。对于自定义结构体一个好的做法是组合其成员的标准哈希值。struct Player { std::string account_id; std::string region; int level; }; struct PlayerHash { std::size_t operator()(const Player p) const { // 使用std::hash组合 boost::hash_combine是更好的选择 std::size_t h1 std::hashstd::string{}(p.account_id); std::size_t h2 std::hashstd::string{}(p.region); std::size_t h3 std::hashint{}(p.level); // 一个简单的组合方式注意这可能不是最佳的 return h1 ^ (h2 1) ^ (h3 2); } };对于生产环境建议参考boost::hash_combine的实现它能产生分布更好的哈希值。相等比较的代价相等比较器Equal可能会被频繁调用尤其是在冲突的桶内查找时。确保它的实现是轻量级的。如果比较很昂贵可能需要重新设计哈希函数以减少冲突。只比较“键”部分正如前面的游戏事件例子我们经常只希望容器根据对象的某一部分键来管理重复性。这时哈希和相等比较器都只应关注那个“键”部分忽略其他字段。这是unordered_multiset比unordered_map更灵活的地方因为“值”部分就是对象本身。4.2 迭代器失效与删除操作的陷阱无序容器的迭代器失效规则需要牢记插入元素可能导致迭代器失效如果插入操作引起了重哈希即元素数量超过max_load_factor() * bucket_count()。但指向具体元素的引用和指针仍然有效。删除元素指向被删除元素的迭代器会失效。但是指向其他未删除元素的迭代器、引用和指针仍然有效。这对于unordered_multiset的erase操作尤为重要。当你用erase(key)删除所有匹配项时这些元素的迭代器自然都失效了。当你用迭代器删除一个元素时只有当前迭代器失效。因此安全的遍历删除模式是std::unordered_multisetint ms {1, 2, 2, 3, 2, 4}; int value_to_remove 2; // 错误做法删除后迭代器失效再会导致未定义行为 // for (auto it ms.begin(); it ! ms.end(); it) { // if (*it value_to_remove) { // ms.erase(it); // } // } // 正确做法1利用erase返回值C11起 for (auto it ms.begin(); it ! ms.end(); ) { if (*it value_to_remove) { it ms.erase(it); // erase返回被删除元素之后元素的迭代器 } else { it; } } // 正确做法2使用equal_range进行范围删除 auto range ms.equal_range(value_to_remove); ms.erase(range.first, range.second); // 一次性删除整个范围第二种方法erase(range.first, range.second)通常更高效因为它可能触发容器内部更优化的批量删除逻辑。4.3 性能调优负载因子与桶的数量unordered_multiset的性能高度依赖于哈希冲突的程度。有两个关键参数可以调整负载因子Load Factorload_factor() size() / bucket_count()。它衡量桶的平均填充程度。默认的最大负载因子max_load_factor()通常是1.0。当load_factor() max_load_factor()时容器会自动增加桶的数量并重哈希rehash这是一个O(n)的操作。调小max_load_factor例如0.7容器会更早地进行重哈希保持更稀疏的桶从而减少冲突提升查找/插入速度但会消耗更多内存。调大max_load_factor例如1.5容器能容纳更多元素才重哈希更节省内存但冲突可能更严重性能下降。std::unordered_multisetint ms; ms.max_load_factor(0.75); // 设置为0.75桶的数量Bucket Count你可以在构造时或之后通过rehash或reserve来指定一个预期的桶数量。rehash(n)将桶数量设置为至少n并可能触发重哈希。reserve(n)将容器容量桶数量设置为至少能容纳n个元素而不会超过最大负载因子。这通常比rehash更直观。std::unordered_multisetint ms; ms.reserve(10000); // 预分配足够空间避免插入过程中的多次重哈希 for (int i 0; i 10000; i) { ms.insert(gen_value()); }如果你能提前知道元素数量的大致范围使用reserve是提升性能最有效的手段之一。性能测试小技巧在关键路径上使用unordered_multiset时最好用真实或模拟的数据进行性能剖析Profiling。关注load_factor()、bucket_count()以及max_load_factor。如果发现冲突严重某个桶的bucket_size特别大可能需要优化哈希函数。5. 替代方案对比与选型指南unordered_multiset并非银弹在很多场景下其他数据结构可能是更好的选择。我们来做一个系统的对比。数据结构核心特性适用场景不适用场景与unordered_multiset对比std::unordered_multiset哈希表允许重复元素O(1)平均查找/插入。1.快速计数count。2.按重复键批量操作equal_range,erase(key)。3. 元素顺序无关紧要。1. 需要元素有序遍历。2. 重复元素数量极多且频繁count最坏O(n)。3. 内存极度受限无法接受哈希表开销。基准std::vectorstd::sort/std::binary_search动态数组排序后二分查找。1. 数据一次性加载后续以查询为主。2. 需要内存连续缓存友好。3. 需要有序遍历。1. 频繁的插入/删除中间位置操作O(n)。2. 实时性要求高的动态数据集。向量在静态或批量处理数据时有序二分查找的O(log n)可能优于哈希表的常数因子开销。但动态增删效率低。std::multiset红黑树允许重复元素元素自动排序O(log n)查找/插入。1. 需要元素始终有序。2. 需要范围查询如找到所有在[A, B]区间的元素。3. 对最坏情况时间复杂度有严格要求避免哈希冲突导致的O(n)。1. 对平均插入/查找性能要求极高且不关心顺序。2. 内存开销比哈希表更敏感树节点开销通常更大。有序多集用O(log n)的确定性时间换取了有序性。如果不需要顺序unordered版本通常更快。std::unordered_mapT, int哈希表键唯一值用于计数。1.仅需要计数功能且后续不需要按元素本身进行其他操作。2. 代码逻辑更直观map[key]。1. 需要基于元素本身进行equal_range式的范围遍历。2. 需要存储的“元素”本身就是完整的对象而不仅仅是计数。计数映射是模拟multiset计数的常见方式。它更节省空间一个计数 vs. 多个重复对象但失去了直接管理重复对象本身的能力。std::unordered_mapT, std::vectorU哈希表键唯一值为列表。1. 键对应的“值”是复杂的关联数据而不仅仅是重复的键本身。2. 需要对同一键下的多个值进行复杂的列表操作。1. 键和值本质是同一个对象或对象的键部分。2. 只需要简单的存在性检查、计数或批量删除。映射到向量功能最强大也最通用但接口更复杂需要手动管理vector。unordered_multiset是它的一个特化和简化。选型决策流程图是否需要存储键值对是 - 考虑(unordered_)map或(unordered_)multimap。存储的元素是否允许重复否 - 考虑(unordered_)set。允许重复且主要操作是快速插入、查找、计数且不关心顺序是 -首选unordered_multiset。是否需要元素始终保持有序是 - 考虑multiset。数据是否相对静态以查询为主是 - 考虑排序后的vector。是否只需要统计次数不需要保留重复元素本身是 - 考虑unordered_mapT, int。6. 一个完整的实战示例简易单词频率统计器让我们用一个完整的、可编译运行的例子来整合所有知识点。这个程序模拟一个简单的日志处理器统计来自不同模块的日志消息的出现频率。#include iostream #include string #include unordered_set #include unordered_map #include vector #include algorithm #include chrono #include random // 案例使用 unordered_multiset 进行单词频率统计和查询 void demo_word_frequency() { std::cout 示例使用 unordered_multiset 统计单词频率 \n; // 模拟一段文本单词可重复 std::vectorstd::string words { the, quick, brown, fox, jumps, over, the, lazy, dog, the, fox, is, quick, and, the, dog, is, lazy }; // 方法1使用 unordered_multiset (最直接) std::unordered_multisetstd::string word_multiset(words.begin(), words.end()); std::cout 使用 unordered_multiset:\n; for (const auto word : {the, fox, is, unknown}) { std::cout Word word appears word_multiset.count(word) times.\n; } // 展示 equal_range 的用法 std::cout \n所有 the 的位置迭代器值实际无序: ; auto [begin, end] word_multiset.equal_range(the); // C17 结构化绑定 for (auto it begin; it ! end; it) { std::cout (*it) ; // 打印地址证明是不同对象 } std::cout \n; // 方法2使用 unordered_map 手动计数 (常见替代方案) std::unordered_mapstd::string, int word_count_map; for (const auto word : words) { word_count_map[word]; } std::cout \n使用 unordered_map 计数:\n; std::cout Word the appears word_count_map[the] times.\n; // 性能对比简单演示 std::cout \n----- 简单性能对比 -----\n; constexpr size_t NUM_ELEMENTS 100000; std::vectorint data(NUM_ELEMENTS); std::mt19937 gen(42); std::uniform_int_distribution dis(1, 1000); // 生成1-1000的随机数会有大量重复 std::generate(data.begin(), data.end(), [](){ return dis(gen); }); // 测试 unordered_multiset 插入和计数 { auto start std::chrono::high_resolution_clock::now(); std::unordered_multisetint test_ms; test_ms.reserve(NUM_ELEMENTS); // 预分配避免重哈希 for (int val : data) { test_ms.insert(val); } // 随机查询一些值的计数 long long total_count 0; for (int i 0; i 1000; i) { total_count test_ms.count(dis(gen)); } auto end std::chrono::high_resolution_clock::now(); auto duration std::chrono::duration_caststd::chrono::microseconds(end - start); std::cout unordered_multiset 插入 NUM_ELEMENTS 元素并查询1000次计数耗时: duration.count() 微秒\n; } // 测试 unordered_map 插入和计数 { auto start std::chrono::high_resolution_clock::now(); std::unordered_mapint, int test_map; test_map.reserve(NUM_ELEMENTS); for (int val : data) { test_map[val]; } long long total_count 0; for (int i 0; i 1000; i) { auto it test_map.find(dis(gen)); total_count (it ! test_map.end()) ? it-second : 0; } auto end std::chrono::high_resolution_clock::now(); auto duration std::chrono::duration_caststd::chrono::microseconds(end - start); std::cout unordered_map 插入 NUM_ELEMENTS 元素并查询1000次计数耗时: duration.count() 微秒\n; } std::cout \n\n; } // 案例自定义类型的 unordered_multiset void demo_custom_type() { std::cout 示例自定义类型在 unordered_multiset 中的应用 \n; struct LogMessage { std::string module; int level; // 1:DEBUG, 2:INFO, 3:ERROR std::string content; // 重载 运算符用于默认的 Equal 比较但我们需要自定义只比较module // bool operator(const LogMessage other) const { // return module other.module level other.level content other.content; // } // 注意对于我们的场景我们不使用默认的而是自定义比较器。 }; // 自定义哈希只对 module 字符串哈希 struct LogModuleHash { std::size_t operator()(const LogMessage msg) const { return std::hashstd::string{}(msg.module); } }; // 自定义相等比较只比较 module struct LogModuleEqual { bool operator()(const LogMessage a, const LogMessage b) const { return a.module b.module; } }; using LogMultiset std::unordered_multisetLogMessage, LogModuleHash, LogModuleEqual; LogMultiset logMessages; // 插入一些日志 logMessages.insert({Network, 2, Connection established.}); logMessages.insert({Database, 1, Query started.}); logMessages.insert({Network, 3, Timeout occurred!}); logMessages.insert({Network, 2, Data packet sent.}); logMessages.insert({UI, 2, Window rendered.}); // 查询某个模块的所有日志数量 std::string targetModule Network; LogMessage dummyMsg{targetModule, 0, }; // 用于查找的临时对象 int networkLogCount logMessages.count(dummyMsg); std::cout Module targetModule has networkLogCount log messages.\n; // 获取并打印某个模块的所有日志内容 std::cout Details of targetModule logs:\n; auto [begin, end] logMessages.equal_range(dummyMsg); for (auto it begin; it ! end; it) { std::cout [Level it-level ] it-content \n; } // 删除某个模块的所有ERROR日志 for (auto it begin; it ! end; ) { if (it-level 3) { // ERROR level it logMessages.erase(it); } else { it; } } networkLogCount logMessages.count(dummyMsg); std::cout After removing ERROR logs, Module targetModule has networkLogCount log messages left.\n; std::cout \n; } int main() { demo_word_frequency(); demo_custom_type(); return 0; }这个示例展示了基础用法count,equal_range。与unordered_map的对比在纯计数场景下两者性能接近但multiset的接口更贴近“多重集合”的语义。自定义类型的使用如何通过自定义哈希和相等比较器让容器只关注对象的一部分module字段。安全的遍历删除在equal_range返回的范围内结合erase返回值来安全地删除特定条件的元素。编译并运行这个程序你可以直观地看到unordered_multiset是如何工作的以及它在特定场景下的简洁性。7. 总结与个人使用体会回顾整篇文章我们从为什么unordered_multiset被忽略开始深入剖析了它的原理、与其它容器的区别、核心API的微妙之处并通过开源项目的思维案例和完整代码示例展示了它的实用场景。最后我们还探讨了性能调优和与其他数据结构的选型对比。我个人的体会是unordered_multiset的“冷门”并非因为它无用而是因为它的应用场景相对特定且容易被其他更通用的结构如mapvector所替代。但正是这种特定性使得它在解决“允许重复的快速查找、计数”这类问题时代码显得异常清晰和优雅。它让数据结构的意图直接体现在类型声明中减少了手动管理中间容器的复杂度。在实际项目中当我遇到需要频繁查询某个元素是否存在且可能多次存在或者需要快速获取某个元素的所有实例时unordered_multiset总会是我的备选方案之一。尤其是在原型设计阶段用它来快速实现一个功能代码会非常简洁。如果后续性能分析成为瓶颈再考虑更换为更底层的结构或优化哈希函数也不迟。最后一个小技巧如果你不确定该用set还是multiset问自己一个问题“在我的业务逻辑里两个完全相同的元素同时存在是否有意义”如果答案是“有”那么multiset就是你的朋友。给它一个机会或许你会发现那些曾经需要额外代码处理的“重复数据”现在可以被容器优雅地管理起来。
