108 std:: multimap (关联容器)

作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58

1. 基本概念

1.1 定义

std::multimap 是 C++ STL 中的关联容器，存储键值对 (key-value)，允许重复键。

1.2 特点

基于红黑树实现的有序容器
按键自动排序（默认升序）
允许存在多个相同键的元素
查找效率：O(log n)
插入/删除效率：O(log n)

1.3 与 `std::map` 的区别

特性	`std::map`	`std::multimap`
键唯一性	是	否
插入相同键	覆盖	保留多个
`operator[]`	支持	不支持

2. 模板参数

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            template<
                        
                                class Key,
                        
                                class T,
                        
                                class Compare = std::less<Key>,
                        
                                class Allocator = std::allocator<std::pair<const Key, T>>
                        
                            > class multimap;

Key: 键类型
T: 值类型
Compare: 比较函数对象（默认 std::less<Key>）
Allocator: 内存分配器

3. 常用操作

3.1 构造与赋值

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 默认构造
                        
                            std::multimap<int, std::string> mm1;
                        
                            // 范围构造
                        
                            std::vector<std::pair<int, std::string>> vec = {{1, "a"}, {2, "b"}, {1, "c"}};
                        
                            std::multimap<int, std::string> mm2(vec.begin(), vec.end());
                        
                            // 拷贝构造
                        
                            std::multimap<int, std::string> mm3(mm2);
                        
                            // 初始化列表构造
                        
                            std::multimap<int, std::string> mm4 = {{3, "x"}, {1, "y"}, {2, "z"}};
                        
                            // 赋值操作
                        
                            mm1 = mm4;

3.2 元素访问

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 迭代器访问
                        
                            for(auto it = mm.begin(); it != mm.end(); ++it) {
                        
                                std::cout << it->first << ": " << it->second << std::endl;
                        
                            }
                        
                            // 范围for循环
                        
                            for(const auto& pair : mm) {
                        
                                std::cout << pair.first << ": " << pair.second << std::endl;
                        
                            }
                        
                            // 查找特定键的范围
                        
                            auto range = mm.equal_range(1);
                        
                            for(auto it = range.first; it != range.second; ++it) {
                        
                                std::cout << it->second << std::endl;
                        
                            }

3.3 容量查询

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            bool empty = mm.empty();  // 是否为空
                        
                            size_t size = mm.size();  // 元素数量
                        
                            size_t max_size = mm.max_size();  // 最大可能容量

3.4 修改操作

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 插入元素
                        
                            mm.insert(std::make_pair(4, "d"));
                        
                            mm.insert({{5, "e"}, {5, "f"}});  // 插入多个元素
                        
                            // 删除元素
                        
                            mm.erase(1);  // 删除所有键为1的元素
                        
                            auto it = mm.find(2);
                        
                            if(it != mm.end()) {
                        
                                mm.erase(it);  // 删除单个元素
                        
                            }
                        
                            // 清空容器
                        
                            mm.clear();

3.5 查找操作

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 查找键
                        
                            auto it = mm.find(3);  // 返回第一个匹配的迭代器
                        
                            // 计数
                        
                            size_t count = mm.count(3);  // 键为3的元素数量
                        
                            // 获取键的范围
                        
                            auto range = mm.equal_range(3);  // 返回pair<iterator, iterator>
                        
                            // 下界和上界
                        
                            auto lower = mm.lower_bound(3);  // 第一个不小于3的键
                        
                            auto upper = mm.upper_bound(3);  // 第一个大于3的键

4. 迭代器

4.1 迭代器类型

iterator: 可修改的迭代器
const_iterator: 不可修改的迭代器
reverse_iterator: 反向迭代器
const_reverse_iterator: 不可修改的反向迭代器

4.2 获取迭代器

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            auto begin = mm.begin();    // 起始迭代器
                        
                            auto end = mm.end();        // 结束迭代器
                        
                            auto rbegin = mm.rbegin();  // 反向起始
                        
                            auto rend = mm.rend();      // 反向结束

5. 高级特性

5.1 自定义比较函数

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            struct CaseInsensitiveCompare {
                        
                                bool operator()(const std::string& a, const std::string& b) const {
                        
                                    return strcasecmp(a.c_str(), b.c_str()) < 0;
                        
                                }
                        
                            };
                        
                            std::multimap<std::string, int, CaseInsensitiveCompare> mm;

5.2 内存管理

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 获取分配器
                        
                            auto alloc = mm.get_allocator();
                        
                            // 预分配空间（注意：multimap没有reserve方法，因为基于树结构）

5.3 C++17 结构化绑定

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            for(const auto& [key, value] : mm) {
                        
                                std::cout << key << ": " << value << std::endl;
                        
                            }

6. 性能考虑

6.1 时间复杂度

操作	时间复杂度
插入	O(log n)
删除	O(log n)
查找	O(log n)
遍历	O(n)

6.2 使用场景

需要按键排序且允许重复键
需要频繁按范围查询
需要保持数据有序性

6.3 替代方案

需要唯一键：std::map
不需要排序：std::unordered_multimap
大量插入删除：考虑哈希表结构

7. 示例代码

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            #include <iostream>
                        
                            #include <map>
                        
                            #include <string>
                        
                            int main() {
                        
                                std::multimap<int, std::string> students;
                        
                                // 插入学生成绩
                        
                                students.insert({85, "Alice"});
                        
                                students.insert({90, "Bob"});
                        
                                students.insert({85, "Charlie"});
                        
                                students.insert({78, "David"});
                        
                                students.insert({90, "Eve"});
                        
                                // 输出所有学生
                        
                                std::cout << "All students:\n";
                        
                                for(const auto& [score, name] : students) {
                        
                                    std::cout << name << ": " << score << "\n";
                        
                                }
                        
                                // 查找90分的学生
                        
                                std::cout << "\nStudents with 90:\n";
                        
                                auto range = students.equal_range(90);
                        
                                for(auto it = range.first; it != range.second; ++it) {
                        
                                    std::cout << it->second << "\n";
                        
                                }
                        
                                // 统计85分的学生数量
                        
                                std::cout << "\nNumber of students with 85: " 
                        
                                          << students.count(85) << "\n";
                        
                                return 0;
                        
                            }

8. 最佳实践

当需要保持元素有序且允许重复键时使用
优先使用 emplace 而非 insert 来避免不必要的拷贝
使用 equal_range 处理重复键的范围查询
考虑使用 lower_bound 和 upper_bound 进行范围查询
对于只读操作，使用 const_iterator 提高代码安全性

9. 常见错误

错误地假设键是唯一的（与 std::map 混淆）
试图使用 operator[] 访问元素（multimap 不支持）
在遍历时修改容器（可能导致迭代器失效）
忽略自定义比较函数的严格弱序要求

std::multimap 常用 API 的整理表格

名称	用途	原型	代码示例	注释
构造函数	创建 `multimap` 对象	`multimap<Key, T, Compare=less<Key>, Alloc=allocator<pair<const Key,T>>>`	`cpp std::multimap<int, string> mm;`	默认构造一个空的 `multimap`，使用 `less<Key>` 比较键。
insert	插入键值对	`iterator insert(const pair<const Key, T>& val);`	`cpp mm.insert({1, "apple"}); mm.insert(make_pair(2, "banana"));`	插入后返回指向新元素的迭代器。允许重复键。
emplace	原地构造并插入元素	`template <class... Args> iterator emplace(Args&&... args);`	`cpp mm.emplace(3, "cherry");`	避免拷贝/移动操作，效率可能高于 `insert`。
erase	删除元素	`size_type erase(const Key& key);`	`cpp mm.erase(2); // 删除所有键为2的元素`	返回被删除的元素数量。
clear	清空容器	`void clear() noexcept;`	`cpp mm.clear();`	容器大小变为0。
find	查找指定键的元素	`iterator find(const Key& key);`	`cpp auto it = mm.find(1); if (it != mm.end()) { /* 找到 */ }`	返回第一个匹配键的迭代器，未找到时返回 `end()`。
count	统计指定键的元素数量	`size_type count(const Key& key) const;`	`cpp size_t cnt = mm.count(1);`	返回键的重复次数。
lower_bound	返回第一个不小于指定键的元素的迭代器	`iterator lower_bound(const Key& key);`	`cpp auto it = mm.lower_bound(2);`	用于范围查询的起始位置。
upper_bound	返回第一个大于指定键的元素的迭代器	`iterator upper_bound(const Key& key);`	`cpp auto it = mm.upper_bound(2);`	用于范围查询的结束位置。
equal_range	返回匹配键的范围（`pair<iterator, iterator>`）	`pair<iterator, iterator> equal_range(const Key& key);`	`cpp auto [first, last] = mm.equal_range(1); for (auto it = first; it != last; ++it) { /* 处理所有键1 */ }`	相当于 `make_pair(lower_bound(), upper_bound())`。
size	返回元素数量	`size_type size() const noexcept;`	`cpp size_t s = mm.size();`	时间复杂度：O(1)。
empty	检查容器是否为空	`bool empty() const noexcept;`	`cpp if (mm.empty()) { /* 容器为空 */ }`	等价于 `size() == 0`。
begin/end	获取迭代器	`iterator begin() noexcept;` `iterator end() noexcept;`	`cpp for (auto it = mm.begin(); it != mm.end(); ++it) { cout << it->first << ": " << it->second << endl; }`	`begin()` 指向第一个元素，`end()` 指向尾后位置。
rbegin/rend	获取反向迭代器	`reverse_iterator rbegin() noexcept;`	`cpp for (auto rit = mm.rbegin(); rit != mm.rend(); ++rit) { /* 逆序遍历 */ }`	用于逆序遍历容器。
swap	交换两个 `multimap` 的内容	`void swap(multimap& other) noexcept;`	`cpp std::multimap<int, string> mm2; mm.swap(mm2);`	高效（仅交换内部指针）。

关键特性注释：

允许重复键：与 std::map 不同，multimap 允许多个元素拥有相同键。
排序保证：元素始终按键的升序排列（默认使用 std::less<Key>）。
迭代器稳定性：插入/删除操作不会使迭代器失效（除非指向被删除元素）。
复杂度：查找/插入/删除操作的时间复杂度为 O(log n)，基于红黑树实现。

文章目录

1	template<
2	class Key,
3	class T,
4	class Compare = std::less<Key>,
5	class Allocator = std::allocator<std::pair<const Key, T>>
6	> class multimap;

1	// 默认构造
2	std::multimap<int, std::string> mm1;
3
4	// 范围构造
5	std::vector<std::pair<int, std::string>> vec = {{1, "a"}, {2, "b"}, {1, "c"}};
6	std::multimap<int, std::string> mm2(vec.begin(), vec.end());
7
8	// 拷贝构造
9	std::multimap<int, std::string> mm3(mm2);
10
11	// 初始化列表构造
12	std::multimap<int, std::string> mm4 = {{3, "x"}, {1, "y"}, {2, "z"}};
13
14	// 赋值操作
15	mm1 = mm4;

1	// 迭代器访问
2	for(auto it = mm.begin(); it != mm.end(); ++it) {
3	std::cout << it->first << ": " << it->second << std::endl;
4	}
5
6	// 范围for循环
7	for(const auto& pair : mm) {
8	std::cout << pair.first << ": " << pair.second << std::endl;
9	}
10
11	// 查找特定键的范围
12	auto range = mm.equal_range(1);
13	for(auto it = range.first; it != range.second; ++it) {
14	std::cout << it->second << std::endl;
15	}

1	bool empty = mm.empty(); // 是否为空
2	size_t size = mm.size(); // 元素数量
3	size_t max_size = mm.max_size(); // 最大可能容量

1	// 插入元素
2	mm.insert(std::make_pair(4, "d"));
3	mm.insert({{5, "e"}, {5, "f"}}); // 插入多个元素
4
5	// 删除元素
6	mm.erase(1); // 删除所有键为1的元素
7	auto it = mm.find(2);
8	if(it != mm.end()) {
9	mm.erase(it); // 删除单个元素
10	}
11
12	// 清空容器
13	mm.clear();

1	// 查找键
2	auto it = mm.find(3); // 返回第一个匹配的迭代器
3
4	// 计数
5	size_t count = mm.count(3); // 键为3的元素数量
6
7	// 获取键的范围
8	auto range = mm.equal_range(3); // 返回pair<iterator, iterator>
9
10	// 下界和上界
11	auto lower = mm.lower_bound(3); // 第一个不小于3的键
12	auto upper = mm.upper_bound(3); // 第一个大于3的键

1	auto begin = mm.begin(); // 起始迭代器
2	auto end = mm.end(); // 结束迭代器
3	auto rbegin = mm.rbegin(); // 反向起始
4	auto rend = mm.rend(); // 反向结束

1	struct CaseInsensitiveCompare {
2	bool operator()(const std::string& a, const std::string& b) const {
3	return strcasecmp(a.c_str(), b.c_str()) < 0;
4	}
5	};
6
7	std::multimap<std::string, int, CaseInsensitiveCompare> mm;

1	// 获取分配器
2	auto alloc = mm.get_allocator();
3
4	// 预分配空间（注意：multimap没有reserve方法，因为基于树结构）

1	for(const auto& [key, value] : mm) {
2	std::cout << key << ": " << value << std::endl;
3	}

1	#include <iostream>
2	#include <map>
3	#include <string>
4
5	int main() {
6	std::multimap<int, std::string> students;
7
8	// 插入学生成绩
9	students.insert({85, "Alice"});
10	students.insert({90, "Bob"});
11	students.insert({85, "Charlie"});
12	students.insert({78, "David"});
13	students.insert({90, "Eve"});
14
15	// 输出所有学生
16	std::cout << "All students:\n";
17	for(const auto& [score, name] : students) {
18	std::cout << name << ": " << score << "\n";
19	}
20
21	// 查找90分的学生
22	std::cout << "\nStudents with 90:\n";
23	auto range = students.equal_range(90);
24	for(auto it = range.first; it != range.second; ++it) {
25	std::cout << it->second << "\n";
26	}
27
28	// 统计85分的学生数量
29	std::cout << "\nNumber of students with 85: "
30	<< students.count(85) << "\n";
31
32	return 0;
33	}

108 std:: multimap (关联容器)

1. 基本概念

1.1 定义

1.2 特点

1.3 与 std::map 的区别

2. 模板参数

3. 常用操作

3.1 构造与赋值

3.2 元素访问

3.3 容量查询

3.4 修改操作

3.5 查找操作

4. 迭代器

4.1 迭代器类型

4.2 获取迭代器

5. 高级特性

5.1 自定义比较函数

5.2 内存管理

5.3 C++17 结构化绑定

6. 性能考虑

6.1 时间复杂度

6.2 使用场景

6.3 替代方案

7. 示例代码

8. 最佳实践

9. 常见错误

关键特性注释：

1.3 与 `std::map` 的区别