C++ unordered_multiset 和 unordered_multimap 完全指南

1. 概述

1.1 什么是 multi 容器？

C++ STL 提供了四种 “multi” 容器，它们都允许存储重复元素或键：

容器	特点	底层实现	时间复杂度
`multiset`	有序多重集合	红黑树	O(log n)
`multimap`	有序多重映射	红黑树	O(log n)
`unordered_multiset`	无序多重集合	哈希表	O(1) 平均
`unordered_multimap`	无序多重映射	哈希表	O(1) 平均

1.2 为什么需要它们？

核心需求： 需要存储重复元素，且需要快速查找。

典型场景：

统计元素出现频次
一对多的关系映射
允许重复的快速查找

2. unordered_multiset 详解

2.1 基本概念

unordered_multiset 是一个无序的多重集合，允许存储重复元素，基于哈希表实现。

#include <unordered_set>
#include <iostream>
 
std::unordered_multiset<int> umset = {1, 2, 2, 3, 3, 3};
// 元素可以重复，顺序不保证

2.2 核心特性

特性	说明
允许重复	同一个值可以存储多次
无序	元素顺序不确定（哈希表）
快速查找	O(1) 平均时间复杂度
无随机访问	不支持 `[]` 操作符

2.3 常用操作

插入元素

std::unordered_multiset<int> umset;
 
// 单个插入
umset.insert(10);
umset.insert(10);  // 允许重复
 
// 批量插入
umset.insert({20, 20, 30, 30, 30});
 
// 范围插入
std::vector<int> vec = {40, 40, 50};
umset.insert(vec.begin(), vec.end());

查找和计数

std::unordered_multiset<int> umset = {1, 2, 2, 3, 3, 3};
 
// 计数：返回某元素的数量
size_t count = umset.count(3);  // 返回 3
 
// 查找：返回第一个匹配元素的迭代器
auto it = umset.find(2);
if (it != umset.end()) {
    std::cout << "找到: " << *it << std::endl;
}
 
// equal_range：返回所有匹配元素的范围
auto range = umset.equal_range(3);
std::cout << "元素 3 出现次数: " << std::distance(range.first, range.second) << std::endl;
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";
}

删除元素

std::unordered_multiset<int> umset = {1, 2, 2, 3, 3, 3};
 
// 删除所有匹配的元素
size_t removed = umset.erase(3);  // 删除所有 3，返回删除的数量（3）
 
// 删除单个元素（通过迭代器）
auto it = umset.find(2);
if (it != umset.end()) {
    umset.erase(it);  // 只删除一个 2
}
 
// 删除范围
auto range = umset.equal_range(2);
umset.erase(range.first, range.second);  // 删除所有剩余的 2

遍历

std::unordered_multiset<int> umset = {1, 2, 2, 3, 3, 3};
 
// 方法1: 基于范围的 for 循环
for (int val : umset) {
    std::cout << val << " ";
}
 
// 方法2: 迭代器
for (auto it = umset.begin(); it != umset.end(); ++it) {
    std::cout << *it << " ";
}

2.4 实战示例

示例 1: 统计单词频次

#include <unordered_set>
#include <string>
#include <iostream>
#include <sstream>
 
void wordFrequency(const std::string& text) {
    std::unordered_multiset<std::string> words;
    std::istringstream iss(text);
    std::string word;
    
    // 插入所有单词
    while (iss >> word) {
        words.insert(word);
    }
    
    // 统计每个单词的频次
    std::unordered_set<std::string> unique_words(words.begin(), words.end());
    for (const auto& w : unique_words) {
        std::cout << w << ": " << words.count(w) << std::endl;
    }
}
 
// 使用
wordFrequency("hello world hello cpp world world");
// 输出:
// hello: 2
// world: 3
// cpp: 1

示例 2: 检测重复元素

#include <unordered_set>
#include <vector>
 
bool hasDuplicates(const std::vector<int>& nums) {
    std::unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num) > 0) {
            return true;  // 发现重复
        }
        seen.insert(num);
    }
    return false;
}
 
// 或者直接用 multiset
bool hasDuplicates2(const std::vector<int>& nums) {
    std::unordered_multiset<int> umset(nums.begin(), nums.end());
    return umset.size() != std::unordered_set<int>(nums.begin(), nums.end()).size();
}

3. unordered_multimap 详解

3.1 基本概念

unordered_multimap 是一个无序的多重映射，允许同一个键对应多个值。

#include <unordered_map>
#include <string>
 
std::unordered_multimap<std::string, int> umm;
umm.insert({"Alice", 90});
umm.insert({"Alice", 95});  // 同一个键可以有多个值
umm.insert({"Bob", 85});

3.2 核心特性

特性	说明
允许重复键	同一个键可以对应多个值
无序	键值对顺序不确定
快速查找	O(1) 平均时间复杂度
不支持 `[]`	无法使用下标访问（因为一键多值）

3.3 常用操作

插入元素

std::unordered_multimap<std::string, int> umm;
 
// 使用 insert
umm.insert({"Alice", 90});
umm.insert({"Alice", 95});
umm.insert(std::make_pair("Bob", 85));
 
// 批量插入
umm.insert({
    {"Charlie", 88},
    {"Charlie", 92},
    {"David", 78}
});
 
// 注意：不能使用 umm["Alice"] = 90，因为不支持 []

查找元素

std::unordered_multimap<std::string, int> umm = {
    {"Alice", 90},
    {"Alice", 95},
    {"Bob", 85}
};
 
// 方法1: count - 返回某键的数量
size_t count = umm.count("Alice");  // 返回 2
 
// 方法2: find - 返回第一个匹配的元素
auto it = umm.find("Alice");
if (it != umm.end()) {
    std::cout << it->first << ": " << it->second << std::endl;
    // 输出: Alice: 90 或 Alice: 95 (不确定顺序)
}
 
// 方法3: equal_range - 返回所有匹配的键值对
auto range = umm.equal_range("Alice");
std::cout << "Alice 的所有成绩: ";
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";
}
// 输出: Alice 的所有成绩: 90 95 (顺序不定)

删除元素

std::unordered_multimap<std::string, int> umm = {
    {"Alice", 90},
    {"Alice", 95},
    {"Bob", 85}
};
 
// 删除所有匹配的键
size_t removed = umm.erase("Alice");  // 删除所有 Alice 的记录，返回 2
 
// 删除单个键值对（通过迭代器）
auto range = umm.equal_range("Alice");
for (auto it = range.first; it != range.second;) {
    if (it->second == 90) {
        it = umm.erase(it);  // 只删除成绩为 90 的记录
    } else {
        ++it;
    }
}
 
// 删除特定范围
auto range2 = umm.equal_range("Bob");
umm.erase(range2.first, range2.second);  // 删除所有 Bob 的记录

遍历

std::unordered_multimap<std::string, int> umm = {
    {"Alice", 90},
    {"Alice", 95},
    {"Bob", 85}
};
 
// 遍历所有键值对
for (const auto& [key, value] : umm) {  // C++17 结构化绑定
    std::cout << key << ": " << value << std::endl;
}
 
// 遍历特定键的所有值
auto range = umm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

3.4 实战示例

示例 1: 学生选课系统

#include <unordered_map>
#include <string>
#include <iostream>
 
class CourseEnrollment {
private:
    std::unordered_multimap<std::string, std::string> enrollment;
    
public:
    // 学生选课
    void enroll(const std::string& student, const std::string& course) {
        enrollment.insert({student, course});
    }
    
    // 学生退课
    void drop(const std::string& student, const std::string& course) {
        auto range = enrollment.equal_range(student);
        for (auto it = range.first; it != range.second; ++it) {
            if (it->second == course) {
                enrollment.erase(it);
                return;
            }
        }
    }
    
    // 查询学生的所有课程
    void printCourses(const std::string& student) const {
        auto range = enrollment.equal_range(student);
        std::cout << student << " 的课程: ";
        for (auto it = range.first; it != range.second; ++it) {
            std::cout << it->second << " ";
        }
        std::cout << std::endl;
    }
    
    // 统计学生的选课数量
    size_t getCourseCount(const std::string& student) const {
        return enrollment.count(student);
    }
};
 
// 使用
int main() {
    CourseEnrollment system;
    
    system.enroll("Alice", "Math");
    system.enroll("Alice", "Physics");
    system.enroll("Alice", "Chemistry");
    system.enroll("Bob", "Math");
    
    system.printCourses("Alice");  // Alice 的课程: Math Physics Chemistry
    std::cout << "Alice 选了 " << system.getCourseCount("Alice") << " 门课" << std::endl;
    
    system.drop("Alice", "Physics");
    system.printCourses("Alice");  // Alice 的课程: Math Chemistry
    
    return 0;
}

示例 2: 倒排索引

#include <unordered_map>
#include <string>
#include <sstream>
#include <iostream>
 
class InvertedIndex {
private:
    std::unordered_multimap<std::string, int> index;  // 单词 -> 文档ID
    
public:
    // 添加文档
    void addDocument(int docId, const std::string& content) {
        std::istringstream iss(content);
        std::string word;
        while (iss >> word) {
            index.insert({word, docId});
        }
    }
    
    // 搜索包含某单词的所有文档
    void search(const std::string& word) const {
        auto range = index.equal_range(word);
        std::cout << "包含 \"" << word << "\" 的文档: ";
        for (auto it = range.first; it != range.second; ++it) {
            std::cout << it->second << " ";
        }
        std::cout << std::endl;
    }
};
 
// 使用
int main() {
    InvertedIndex idx;
    
    idx.addDocument(1, "hello world");
    idx.addDocument(2, "hello cpp");
    idx.addDocument(3, "world of cpp");
    
    idx.search("hello");  // 包含 "hello" 的文档: 1 2
    idx.search("cpp");    // 包含 "cpp" 的文档: 2 3
    idx.search("world");  // 包含 "world" 的文档: 1 3
    
    return 0;
}

示例 3: 图的邻接表表示

#include <unordered_map>
#include <iostream>
 
class Graph {
private:
    std::unordered_multimap<int, int> edges;  // 节点 -> 邻居节点
    
public:
    // 添加边
    void addEdge(int from, int to) {
        edges.insert({from, to});
    }
    
    // 获取某节点的所有邻居
    void printNeighbors(int node) const {
        auto range = edges.equal_range(node);
        std::cout << "节点 " << node << " 的邻居: ";
        for (auto it = range.first; it != range.second; ++it) {
            std::cout << it->second << " ";
        }
        std::cout << std::endl;
    }
    
    // 获取节点的度
    size_t getDegree(int node) const {
        return edges.count(node);
    }
};
 
// 使用
int main() {
    Graph g;
    
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    
    g.printNeighbors(1);  // 节点 1 的邻居: 2 3 4
    std::cout << "节点 1 的度: " << g.getDegree(1) << std::endl;  // 3
    
    return 0;
}

4. 性能对比

4.1 时间复杂度对比

操作	`unordered_multiset/map`	`multiset/map`	`vector`
插入	O(1) 平均	O(log n)	O(1) 末尾，O(n) 中间
查找	O(1) 平均	O(log n)	O(n)
删除	O(1) 平均	O(log n)	O(n)
遍历	O(n)	O(n)	O(n)

4.2 空间复杂度

容器	空间复杂度	额外开销
`unordered_multiset/map`	O(n)	哈希表桶 + 指针
`multiset/map`	O(n)	红黑树节点指针
`vector`	O(n)	较小（连续存储）

4.3 性能测试

#include <unordered_set>
#include <set>
#include <chrono>
#include <iostream>
 
void performanceTest() {
    const int N = 100000;
    
    // unordered_multiset 插入测试
    auto start = std::chrono::high_resolution_clock::now();
    std::unordered_multiset<int> umset;
    for (int i = 0; i < N; ++i) {
        umset.insert(i % 1000);  // 允许重复
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "unordered_multiset 插入: " << duration.count() << "ms" << std::endl;
    
    // multiset 插入测试
    start = std::chrono::high_resolution_clock::now();
    std::multiset<int> mset;
    for (int i = 0; i < N; ++i) {
        mset.insert(i % 1000);
    }
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "multiset 插入: " << duration.count() << "ms" << std::endl;
    
    // 查找测试
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000; ++i) {
        umset.count(i);
    }
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "unordered_multiset 查找: " << duration.count() << "μs" << std::endl;
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000; ++i) {
        mset.count(i);
    }
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "multiset 查找: " << duration.count() << "μs" << std::endl;
}
 
// 典型输出:
// unordered_multiset 插入: 12ms
// multiset 插入: 28ms
// unordered_multiset 查找: 45μs
// multiset 查找: 120μs

5. 最佳实践

5.1 何时使用 unordered_multiset

✅ 适合使用的场景：

需要存储重复元素
不关心元素顺序
需要快速查找（O(1)）
频繁的插入和删除操作

❌ 不适合使用的场景：

需要有序输出
数据量小（哈希表开销可能大于收益）
需要范围查询（如：查找所有 < 10 的元素）

5.2 何时使用 unordered_multimap

✅ 适合使用的场景：

一对多的关系映射
需要快速查找某键的所有值
频繁插入/删除单个键值对
不关心键值对顺序

❌ 不适合使用的场景：

需要按键有序遍历
经常需要获取某键的所有值（此时 map<K, vector<V>> 更方便）
需要修改值（需要先删除再插入）

5.3 unordered_multimap vs `map<K, vector<V>>`

场景	推荐容器	原因
频繁插入/删除单个键值对	`unordered_multimap`	无需操作 vector
经常获取某键的所有值	`map<K, vector<V>>`	直接访问更方便
需要对值进行批量操作	`map<K, vector<V>>`	vector 支持排序、去重等
键值对相对独立	`unordered_multimap`	更符合语义
需要随机访问第 N 个值	`map<K, vector<V>>`	vector 支持 `[]`

5.4 自定义哈希函数

// 为自定义类型提供哈希函数
struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};
 
// 方法1: 特化 std::hash
namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            return hash<string>()(p.name) ^ (hash<int>()(p.age) << 1);
        }
    };
}
 
// 方法2: 提供自定义哈希函数对象
struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ 
               (std::hash<int>()(p.age) << 1);
    }
};
 
// 使用
std::unordered_multiset<Person> umset1;  // 使用 std::hash<Person>
std::unordered_multiset<Person, PersonHash> umset2;  // 使用自定义哈希

5.5 负载因子调优

std::unordered_multiset<int> umset;
 
// 查看负载因子
std::cout << "负载因子: " << umset.load_factor() << std::endl;
std::cout << "最大负载因子: " << umset.max_load_factor() << std::endl;
 
// 设置最大负载因子（默认 1.0）
umset.max_load_factor(0.75);  // 降低碰撞概率，但增加内存消耗
 
// 预留空间以减少重新哈希
umset.reserve(1000);  // 预留至少 1000 个元素的空间
 
// 查看桶信息
std::cout << "桶数量: " << umset.bucket_count() << std::endl;

6. 常见陷阱

6.1 误用 `[]` 操作符

std::unordered_multimap<std::string, int> umm;
 
// ❌ 错误：unordered_multimap 不支持 []
// umm["Alice"] = 90;  // 编译错误！
 
// ✅ 正确：使用 insert
umm.insert({"Alice", 90});

6.2 遍历时修改容器

std::unordered_multiset<int> umset = {1, 2, 2, 3};
 
// ❌ 错误：迭代器失效
for (auto it = umset.begin(); it != umset.end(); ++it) {
    if (*it == 2) {
        umset.erase(it);  // 迭代器失效！
    }
}
 
// ✅ 正确：使用 erase 的返回值
for (auto it = umset.begin(); it != umset.end();) {
    if (*it == 2) {
        it = umset.erase(it);  // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

6.3 忽略哈希碰撞

// 糟糕的哈希函数会导致性能下降
struct BadHash {
    size_t operator()(int x) const {
        return 0;  // 所有元素都映射到同一个桶！
    }
};
 
std::unordered_multiset<int, BadHash> umset;
// 此时查找性能退化为 O(n)

6.4 equal_range 的正确使用

std::unordered_multimap<std::string, int> umm = {
    {"Alice", 90},
    {"Alice", 95}
};
 
// ✅ 正确
auto range = umm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";
}
 
// ❌ 错误：不要修改 range 的边界
auto range2 = umm.equal_range("Alice");
range2.first++;  // 跳过第一个元素
// 现在 range2 可能不完整

6.5 未检查空容器

std::unordered_multiset<int> umset;
 
// ❌ 错误：未检查是否为空
auto it = umset.find(10);
std::cout << *it << std::endl;  // 如果未找到，解引用无效迭代器！
 
// ✅ 正确
auto it2 = umset.find(10);
if (it2 != umset.end()) {
    std::cout << *it2 << std::endl;
}

7. 总结

7.1 快速参考表

需求	推荐容器
存储重复元素 + 快速查找	`unordered_multiset`
存储重复元素 + 需要有序	`multiset`
一对多映射 + 快速查找	`unordered_multimap`
一对多映射 + 需要有序	`multimap`
一对多映射 + 频繁获取所有值	`map<K, vector<V>>`

7.2 核心要点

unordered_multiset: 无序多重集合，允许重复，O(1) 查找
unordered_multimap: 无序多重映射，一键多值，O(1) 查找
性能优势: 平均 O(1) 的插入、查找、删除
使用场景: 频次统计、一对多关系、允许重复的快速查找
注意事项: 无序、哈希函数、负载因子、迭代器失效

7.3 进一步学习

C++ Reference - unordered_multiset
C++ Reference - unordered_multimap
《Effective STL》- Scott Meyers
《C++ Primer (5th Edition)》- Stanley Lippman

附录：完整示例代码

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <string>
 
int main() {
    // unordered_multiset 示例
    std::unordered_multiset<int> umset = {1, 2, 2, 3, 3, 3};
    std::cout << "元素 3 的数量: " << umset.count(3) << std::endl;
    
    // unordered_multimap 示例
    std::unordered_multimap<std::string, int> umm;
    umm.insert({"Alice", 90});
    umm.insert({"Alice", 95});
    umm.insert({"Bob", 85});
    
    auto range = umm.equal_range("Alice");
    std::cout << "Alice 的成绩: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Sean's Blog

Explorer

unordered_multiset 和 unordered_multimap

C++ unordered_multiset 和 unordered_multimap 完全指南

1. 概述

1.1 什么是 multi 容器？

1.2 为什么需要它们？

2. unordered_multiset 详解

2.1 基本概念

2.2 核心特性

2.3 常用操作

插入元素

查找和计数

删除元素

遍历

2.4 实战示例

示例 1: 统计单词频次

示例 2: 检测重复元素

3. unordered_multimap 详解

3.1 基本概念

3.2 核心特性

3.3 常用操作

插入元素

查找元素

删除元素

遍历

3.4 实战示例

示例 1: 学生选课系统

示例 2: 倒排索引

示例 3: 图的邻接表表示

4. 性能对比

4.1 时间复杂度对比

4.2 空间复杂度

4.3 性能测试

5. 最佳实践

5.1 何时使用 unordered_multiset

5.2 何时使用 unordered_multimap

5.3 unordered_multimap vs map<K, vector<V>>

5.4 自定义哈希函数

5.5 负载因子调优

6. 常见陷阱

6.1 误用 [] 操作符

6.2 遍历时修改容器

6.3 忽略哈希碰撞

6.4 equal_range 的正确使用

6.5 未检查空容器

7. 总结

7.1 快速参考表

7.2 核心要点

7.3 进一步学习

附录：完整示例代码

目录

Graph View

5.3 unordered_multimap vs `map<K, vector<V>>`

6.1 误用 `[]` 操作符