C++中的unordered_multimap容器详解

C++中的unordered_multimap容器详解

1.unordered_multimap概述

unordered_multimap是C++11引入的关联容器，基于哈希表实现，允许存储重复键的键值对，提供快速的查找、插入和删除操作，平均时间复杂度为O(1)O(1)O(1)。

2. 基本特性

• 哈希表实现：使用哈希函数组织键值对
• 允许重复键：容器中可以包含多个相同键的键值对
• 无序存储：元素不以任何特定顺序存储
• 快速访问：平均情况下提供常数时间复杂度的查找
• 动态大小：可以根据需要自动扩展

3. 头文件与声明

#include<unordered_map>usingnamespacestd;unordered_multimap<int,string>umm1;// 空unordered_multimapunordered_multimap<string,double>umm2={{"pi",3.14},{"pi",3.1416}};// 初始化列表(允许重复键)unordered_multimap<char,int>umm3(10);// 初始桶数为10

4. 构造函数与初始化

4.1 默认构造

unordered_multimap<string,int>wordCounts;

4.2 范围构造

pair<string,int>arr[]={{"apple",5},{"apple",3},{"banana",2}};unordered_multimap<string,int>fruitCounts(arr,arr+3);

4.3 拷贝构造

unordered_multimap<string,int>umm2(umm1);

4.4 自定义哈希函数和相等比较

structCaseInsensitiveHash{size_toperator()(conststring&s)const{size_t h=0;for(charc:s){h+=tolower(c);}returnh;}};structCaseInsensitiveEqual{booloperator()(conststring&a,conststring&b)const{if(a.length()!=b.length())returnfalse;for(size_t i=0;i<a.length();++i){if(tolower(a[i])!=tolower(b[i]))returnfalse;}returntrue;}};unordered_multimap<string,int,CaseInsensitiveHash,CaseInsensitiveEqual>case_insensitive_mmap;

5. 容量操作

5.1size()

cout<<umm.size();// 返回键值对数量(包括重复键)

5.2empty()

if(umm.empty()){cout<<"unordered_multimap is empty";}

5.3max_size()

cout<<umm.max_size();// 返回可容纳的最大键值对数

6. 元素访问

6.1 迭代器访问

for(autoit=umm.begin();it!=umm.end();++it){cout<<it->first<<": "<<it->second<<endl;}

7. 修改操作

7.1insert()

umm.insert({"apple",5});// 插入单个键值对umm.insert({{"banana",3},{"banana",2}});// 插入初始化列表(允许重复键)umm.insert(arr,arr+2);// 插入范围autoit=umm.insert(make_pair("orange",4));// 返回指向插入元素的迭代器

7.2emplace()

autoit=umm.emplace("grape",7);// 原地构造键值对

7.3erase()

umm.erase("apple");// 删除所有键为"apple"的键值对autoit=umm.find("banana");if(it!=umm.end()){umm.erase(it);// 只删除一个键为"banana"的键值对}umm.erase(umm.begin(),umm.end());// 删除范围

7.4clear()

umm.clear();// 清空所有键值对

7.5swap()

unordered_multimap<string,int>umm2;umm.swap(umm2);// 交换两个unordered_multimap

8. 查找操作

8.1find()

autoit=umm.find("apple");// 返回指向第一个键为"apple"的迭代器if(it!=umm.end()){cout<<"Found: "<<it->second;}

8.2count()

cout<<umm.count("banana");// 返回键为"banana"的键值对数量

8.3equal_range()

autorange=umm.equal_range("apple");// 返回键为"apple"的键值对范围[pair]for(autoit=range.first;it!=range.second;++it){cout<<it->first<<": "<<it->second<<endl;}

9. 桶操作

9.1bucket_count()

cout<<umm.bucket_count();// 返回桶的数量

9.2max_bucket_count()

cout<<umm.max_bucket_count();// 返回最大桶数

9.3bucket_size()

cout<<umm.bucket_size(2);// 返回第2个桶中的键值对数

9.4bucket()

cout<<umm.bucket("apple");// 返回"apple"所在的桶索引

10. 哈希策略

10.1load_factor()

cout<<umm.load_factor();// 返回负载因子(键值对数/桶数)

10.2max_load_factor()

cout<<umm.max_load_factor();// 返回最大负载因子umm.max_load_factor(0.75);// 设置最大负载因子

10.3rehash()

umm.rehash(20);// 设置桶数为至少20

10.4reserve()

umm.reserve(100);// 预留空间至少容纳100个键值对

11. 完整示例

#include<iostream>#include<unordered_map>#include<string>usingnamespacestd;intmain(){// 创建并初始化unordered_multimapunordered_multimap<string,string>phonebook={{"Alice","123-4567"},{"Bob","234-5678"},{"Alice","345-6789"}};// 插入元素phonebook.insert({"Charlie","456-7890"});phonebook.emplace("Alice","567-8901");pair<string,string>entries[]={{"Bob","678-9012"},{"Dave","789-0123"}};phonebook.insert(entries,entries+2);// 查找元素cout<<"Number of Alice's phones: "<<phonebook.count("Alice")<<endl;autofound=phonebook.find("Bob");if(found!=phonebook.end()){cout<<"Found Bob's phone: "<<found->second<<endl;}// 遍历unordered_multimapcout<<"\nAll entries:"<<endl;for(constauto&entry:phonebook){cout<<entry.first<<": "<<entry.second<<endl;}// 使用equal_range处理重复键cout<<"\nAll of Alice's phones:"<<endl;autorange=phonebook.equal_range("Alice");for(autoit=range.first;it!=range.second;++it){cout<<it->second<<endl;}// 删除元素phonebook.erase("Bob");// 删除所有Bob的条目autoit=phonebook.find("Charlie");if(it!=phonebook.end()){phonebook.erase(it);// 只删除一个Charlie的条目}// 桶信息cout<<"\nBucket information:"<<endl;cout<<"Number of buckets: "<<phonebook.bucket_count()<<endl;cout<<"Current load factor: "<<phonebook.load_factor()<<endl;// 调整哈希表phonebook.rehash(10);cout<<"After rehash, bucket count: "<<phonebook.bucket_count()<<endl;// 容量信息cout<<"\nSize: "<<phonebook.size()<<endl;cout<<"Is empty: "<<(phonebook.empty()?"Yes":"No")<<endl;return0;}

12. 性能提示

1. 平均情况下查找、插入、删除时间复杂度为O(1)O(1)O(1)
2. 最坏情况下(哈希冲突严重)时间复杂度退化为O(n)O(n)O(n)
3. 负载因子过高会影响性能，可适时rehash()
4. 自定义键类型需要提供哈希函数和相等比较
5. 迭代器在插入操作后可能失效(重新哈希时)

13. 与multimap比较

14. 与unordered_map比较