C++总结(7)：STL无序容器之unordered_set、unordered_map、unordered_multiset、unordered_multimap详解

前两节介绍了STL中的顺序容器和关联容器，本节来介绍一下无序容器。无序容器与关联容器类似，但是关联容器是顺序排序的，而无序容器实现了未排序(哈希)的数据结构。

文章目录

1 unordered_set2 unordered_map3 unordered_multiset4 unordered_multimap

1 unordered_set

无序集合(unordered_set)是一种使用哈希表实现的无序关联容器，其中键被哈希到哈希表的索引位置，因此插入操作总是随机的。无序集合上的所有操作在平均情况下都具有常数时间复杂度O(1)，但在最坏情况下，时间复杂度可以达到线性时间O(n)，这取决于内部使用的哈希函数，但实际上它们表现非常出色，通常提供常数时间的查找操作。

无序集合可以包含任何类型的键 - 预定义或用户自定义数据结构，但所有键必须是唯一的。它的语法如下：

std::unordered_set<data_type> name;

常用方法

size()和empty():用于获取大小和集合是否为空find():用于查找键insert()和erase():用于插入和删除元素

#include <bits/stdc++.h>using namespace std;int main(){unordered_set<string> stringSet;stringSet.insert("code");stringSet.insert("in");stringSet.insert("c++");stringSet.insert("is");stringSet.insert("fast");string key = "slow";if (stringSet.find(key) == stringSet.end())cout << key << " not found" << endl << endl; //输出此分支elsecout << "Found " << key << endl << endl;key = "c++";if (stringSet.find(key) == stringSet.end())cout << key << " not found\n";elsecout << "Found " << key << endl;  //输出此分支cout << "\nAll elements : ";unordered_set<string>::iterator itr;for (itr = stringSet.begin(); itr != stringSet.end(); itr++)cout << (*itr) << ' ';  //fast is code c++ in}

可以看到输出的顺序混乱，因为在无序集合中没有特定的数据存储顺序。

如果集合中不存在某个键，find()函数会返回一个指向end()的迭代器，否则会返回指向键位置的迭代器。迭代器充当键值的指针，因此我们可以使用*运算符来解引用它们以获取键。

基于无序集合的实际问题：已知一个整数数组，要找出其中的所有重复项。

#include <bits/stdc++.h>using namespace std;void printDuplicates(int arr[], int n){unordered_set<int> intSet;unordered_set<int> duplicate;for (int i = 0; i < n; i++) {if (intSet.find(arr[i]) == intSet.end())intSet.insert(arr[i]);elseduplicate.insert(arr[i]);}cout << "Duplicate item are : ";unordered_set<int>::iterator itr;for (itr = duplicate.begin(); itr != duplicate.end(); itr++)cout << *itr << " ";  //5 1 2}int main(){int arr[] = { 1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5 };int n = sizeof(arr) / sizeof(int);printDuplicates(arr, n);return 0;}

其他方法

Function Name	Function Description
insert()	插入一个新元素
begin()/end()	返回一个迭代器，指向第一个元素/最后一个元素后的理论元素
count()	计算在无序集合容器中特定元素的出现次数
find()	搜索元素
clear()	清空所有元素
cbegin()/cend()	返回一个常量迭代器，指向第一个元素/最后一个元素后的理论元素
bucket_size()	返回无序集合中特定桶(bucket)中的元素总数(元素通过哈希函数映射到不同的桶中)
erase()	移除单个或某个范围内的一系列元素
size()	返回元素数量
swap()	交换两个无序集合容器的值
emplace()	在无序集合容器中插入元素
max_size()	返回可以容纳的最大元素数量
empty()	检查无序集合容器是否为空
equal_range()	返回包括与给定值相等的所有元素的范围
hash_function()	用于获取容器所使用的哈希函数对象
reserve()	它用于请求容器预留足够的桶数，以容纳指定数量的元素
bucket()	返回特定元素的桶编号
bucket_count()	返回无序集合容器中的总桶数
load_factor()	用于获取当前容器的负载因子。负载因子:元素数量与桶数之比，用于衡量容器的填充程度
rehash()	设置容器的桶数以容纳一定数量的元素
max_load_factor()	获取或设置容器的最大负载因子
emplace_hint()	根据给定的提示位置(iterator)在容器中插入一个新元素
key_eq()	无序集合内部用于比较元素键值相等性的函数对象或谓词类型
max_bucket_count()	获取无序集合容器支持的最大桶数

2 unordered_map

无序映射(unordered_map)是一种关联容器，用于存储由键和映射值组成的元素。键值用于唯一标识元素，而映射值是与键相关联的内容。键和值都可以是任何预定义或用户定义的类型。简而言之，无序映射类似于一种字典类型的数据结构，可以在其中存储元素。

在内部，无序映射使用哈希表来实现，提供的键被哈希成哈希表的索引，因此数据结构的性能在很大程度上取决于哈希函数。但平均而言，从哈希表中搜索、插入和删除的成本是O(1)。

基本使用

#include <iostream>#include <unordered_map>using namespace std;int main(){    unordered_map<string, int> umap;    umap["GeeksforGeeks"] = 10;    umap["Practice"] = 20;    umap["Contribute"] = 30;    for (auto x : umap)        //Contribute=30 GeeksforGeeks=10 Practice=20        cout << x.first << "=" << x.second << ' ';}

方法

Methods/Functions	Description
at(K)	返回与元素作为键k相关的值的引用
begin()/end()	返回一个迭代器，指向第一个元素/最后一个元素后的理论元素
bucket(k)	返回键k所在的桶编号，即元素在映射中的位置。
bucket_count()	返回无序映射容器中的总桶数
bucket_size()	返回无序映射中每个桶中的元素数量
count()	计算具有给定键的元素在无序映射中出现的次数
equal_range(k)	返回包括与键k相等的所有元素的范围的边界
find()	搜索元素
empty()	检查无序映射容器是否为空
erase()	从无序映射容器中删除元素

C++11库还提供了用于查看内部使用的桶数、桶大小以及使用的哈希函数和各种哈希策略的函数(和unordered_set中类似)，但它们在实际应用中的用处较小。我们可以使用迭代器遍历无序映射中的所有元素。

#include <iostream>#include <unordered_map>using namespace std;int main(){    //三种插入方式    unordered_map<string, double> umap =    {        {"One", 1},        {"Two", 2},        {"Three", 3}    };    umap["PI"] = 3.14;    umap["root2"] = 1.414;    umap["root3"] = 1.732;    umap["log10"] = 2.302;    umap["loge"] = 1.0;    umap.insert(make_pair("e", 2.718));    string key = "PI";    if (umap.find(key) == umap.end())        cout << key << " not found\n\n";    else        cout << "Found " << key << "\n\n";  //输出此分支    key = "lambda";    if (umap.find(key) == umap.end())        cout << key << " not found\n";  //输出此分支    else        cout << "Found " << key << endl;    unordered_map<string, double>::iterator itr;    cout << "\nAll Elements : \n";    for (itr = umap.begin(); itr != umap.end(); itr++)    {        cout << itr->first << " " << itr->second << endl;  //遍历输出所有元素    }}

实例:计算各个字符出现的频率

#include <bits/stdc++.h>using namespace std;void printFrequencies(const string &str){    unordered_map<string, int> wordFreq;    stringstream ss(str);    string word;    while (ss >> word)        wordFreq[word]++;    unordered_map<string, int>:: iterator p;    for (p = wordFreq.begin(); p != wordFreq.end(); p++)        cout << "(" << p->first << ", " << p->second << ")\n";}int main(){    string str = "geeks for geeks geeks quiz practice qa for";    printFrequencies(str);    return 0;}

3 unordered_multiset

unordered_multiset是一种无序关联容器，类似于unordered_set。唯一的区别在于，我们可以在此容器中存储相同键的多个副本。

由于元素使用哈希存储，因此元素可以以任何顺序出现，但重复元素会在一起。语法如下：

std::unordered_set<data_type> name;

实例

#include <bits/stdc++.h>using namespace std;typedef unordered_multiset<int>::iterator umit;void printUset(unordered_multiset<int> ums){umit it = ums.begin();for (; it != ums.end(); it++)cout << *it << " ";cout << endl;}int main(){unordered_multiset<int> ums1;unordered_multiset<int> ums2( { 1, 3, 1, 7, 2, 3, 4, 1, 6 });ums1 = { 2, 7, 2, 5, 0, 3, 7, 5 };if (ums1.empty())cout << "unordered multiset 1 is empty\n";elsecout << "unordered multiset 1 is not empty\n";  //输出此分支cout << "The size of unordered multiset 2 is : " << ums2.size() << endl;  //9printUset(ums1);  //3 0 5 5 7 7 2 2ums1.insert(7);  //3 0 5 5 7 7 7 2 2printUset(ums1);int val = 3;if (ums1.find(val) != ums1.end())cout << "unordered multiset 1 contains " << val << endl;  //3elsecout << "unordered multiset 1 does not contains "<< val << endl;val = 5;int cnt = ums1.count(val);cout << val << " appears " << cnt << " times in unordered multiset 1 \n";  //5 2val = 9;if (ums1.count(val))cout << "unordered multiset 1 contains " << val << endl;elsecout << "unordered multiset 1 does not contains " << val << endl;  //9val = 1;pair<umit, umit> erange_it = ums2.equal_range(val);if (erange_it.first != erange_it.second)cout << val << " appeared atleast once in unoredered_multiset \n";  //1printUset(ums2);  //6 4 2 7 3 3 1 1 1ums2.erase(val);printUset(ums2);  //6 4 2 7 3 3 1ums1.clear();ums2.clear();if (ums1.empty())cout << "unordered multiset 1 is empty\n";  //输出此分支elsecout << "unordered multiset 1 is not empty\n";}

unordered_set与unordered_multiset比较

正如我们所看到的，大多数操作与 unordered_set 的操作方式相似，但有一些不同之处：

equal_range(Val)函数返回一个类型为pair的对，其中第一个迭代器指向Val的第一个位置，第二个迭代器指向Val在数据结构中的最后位置。而erase(Val)函数会从数据结构中删除所有其实例例如，如果某个值v在unordered_multiset中出现了t次，当调用 erase 时，v将被完全删除，这在许多情况下不是预期的行为

我们可以使用find函数来仅删除某个值的一个副本，因为 find 函数返回找到值的第一个位置的迭代器，我们可以将此迭代器传递给erase而不是传递实际值，从而仅删除一个副本。例子如下：

#include <bits/stdc++.h>using namespace std;typedef unordered_multiset<int>::iterator umit;void printUset(unordered_multiset<int> ums){umit it = ums.begin();for (; it != ums.end(); it++)cout << *it << " ";cout << endl;}void erase_one_entry(unordered_multiset<int>& ums,int val){umit it = ums.find(val);if (it != ums.end())ums.erase(it);}int main(){unordered_multiset<int> ums ({1, 3, 1, 7, 2, 3, 4, 1, 6});int val = 1;printUset(ums);  //6 4 2 7 3 3 1 1 1erase_one_entry(ums, val);printUset(ums);  //6 4 2 7 3 3 1 1}

方法

Function Name	Function Description
insert()	插入新元素
begin()/end()	返回一个迭代器，指向第一个元素/最后一个元素后的理论元素
empty()	检查容器是否为空
find(k)	返回指向具有元素值k的位置的迭代器
cbegin()/cend()	返回一个常量迭代器，指向第一个元素/最后一个元素后的理论元素
equal_range()	返回包括与给定值相等的所有元素的范围
emplace()	插入新元素
clear()	清空无序多重集容器的内容
count()	返回与给定值相等的元素数量
size()	返回元素数量
max_size	返回能够容纳的最大元素数量
swap()	交换两个无序多重集容器的内容
erase()	用于删除单个元素、所有具有特定值的元素或一个范围内的元素
bucket()	返回给定元素所在的桶编号
bucket_size(k)	返回包含元素k的桶中的元素数量
reserve()	它用于请求容器预留足够的桶数，以容纳指定数量的元素
max_bucket_count()	返回能够拥有的最大桶数
load_factor()	返回当前负载因子(元素数量与桶数之比)
max_load_factor()	返回最大负载因子
bucket_count()	返回总桶数
hash_function()	用于获取容器所使用的哈希函数对象
rehash()	将容器中的桶数设置为N或更多
key_eq()	根据比较两个key是否相等返回一个布尔值
emplace_hint()	根据给定的提示位置(iterator)在容器中插入一个新元素
get_allocator	获取存储的分配器对象，并返回用于构建容器的分配器对象

4 unordered_multimap

无序多重映射(unordered_multimap)类似于unordered_set，但它可以存在多个相同的键。

实例

#include <bits/stdc++.h>using namespace std;typedef unordered_multimap<string, int>::iterator unit;void printUmm(unordered_multimap<string, int> umm){unit it = umm.begin();for (; it != umm.end(); it++){cout << "<" << it->first << ", " << it->second << "> " << endl;}}int main(){unordered_multimap<string, int> umm1;unordered_multimap<string, int> umm2({ { "apple", 1 },{ "ball", 2 },{ "apple", 10 },{ "cat", 7 },{ "dog", 9 },{ "cat", 6 },{ "apple", 1 } });umm1 = umm2;printUmm(umm1);  //输出所有元素if (umm2.empty())cout << "unordered multimap 2 is empty\n";elsecout << "unordered multimap 2 is not empty\n";  //输出此分支cout << "Size of unordered multimap 1 is " << umm1.size() << endl;  //7string key = "apple";unit it = umm1.find(key);if (it != umm1.end()) {cout << "\nkey " << key << " is there in unordered " << " multimap 1\n";  //applecout << "\none of the value associated with " << key << " is " << it->second << endl;  //apple 1}elsecout << "\nkey " << key << " is not there in unordered" << " multimap 1\n";int cnt = umm1.count(key);cout << "\ntotal values associated with " << key << " are " << cnt << "\n\n";  //apple 3printUmm(umm2);umm2.insert(make_pair("dog", 11));umm2.insert({ { "alpha", 12 }, { "beta", 33 } });cout << "\nAfter insertion of <alpha, 12> and <beta, 33>\n";printUmm(umm2);  //输出所有元素umm2.erase("apple");cout << "\nAfter deletion of apple\n";printUmm(umm2);  //输出所有元素umm1.clear();umm2.clear();if (umm2.empty())cout << "\nunordered multimap 2 is empty\n";  //输出此分支elsecout << "\nunordered multimap 2 is not empty\n";}

在上面的代码中，大多数操作与unordered_map类似，但需要注意以下几点：

我们可以使用初始化列表一次性初始化和插入多个键值对由于与键关联的值不唯一，可以有多个值与单个键关联，因此unordered_multimap没有[]运算符，不能将[]运算符应用于它们erase函数删除与提供的键关联的所有值的实例find函数返回与该键关联的所有键值对中的任何实例的迭代器

如何访问/删除特定键的值

如果我们想要检查特定值是否存在，我们需要循环遍历所有键值对，直到找到特定值，如果我们在unordered_multimap中找到了特定值，可以使用erase(position)从unordered_multimap中删除该特定值。

#include <bits/stdc++.h>using namespace std;void printUmm(unordered_multimap<string, int>& umm){auto it1 = umm.begin();for (; it1 != umm.end(); it1++) {cout << "<" << it1->first << ", " << it1->second << "> " << endl;}}int main(){unordered_multimap<string, int> umm{{ "apple", 1 }, { "ball", 2 }, { "apple", 10 },{ "cat", 7 }, { "dog", 9 }, { "cat", 6 },{ "apple", 1 }};auto it = umm.begin();while (it != umm.end()) {if (it->second == 1)break;it++;}if (it != umm.end())umm.erase(it);cout << "After deletion of value 1 from umm" << endl;printUmm(umm);return 0;}

unordered_multimap的方法与unordered_multiset基本一致，这里不再列举，点此跳转。

本文链接：https://www.kjpai.cn/news/2024-04-29/163354.html，文章来源：网络cs，作者：淼淼，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！