C++总结(7)：STL无序容器之unordered

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

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; //输出此分支	else		cout << "Found " << key << endl << endl;	key = "c++";	if (stringSet.find(key) == stringSet.end())		cout << key << " not found\n";	else		cout << "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]);		else			duplicate.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;}

其他方法

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 << ' ';}

方法

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";	else		cout << "unordered multiset 1 is not empty\n";  //输出此分支	cout << "The size of unordered multiset 2 is : " << ums2.size() << endl;  //9	printUset(ums1);  //3 0 5 5 7 7 2 2	ums1.insert(7);  //3 0 5 5 7 7 7 2 2	printUset(ums1);	int val = 3;	if (ums1.find(val) != ums1.end())		cout << "unordered multiset 1 contains " << val << endl;  //3	else		cout << "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 2	val = 9;	if (ums1.count(val))		cout << "unordered multiset 1 contains " << val << endl;	else		cout << "unordered multiset 1 does not contains " << val << endl;  //9	val = 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";  //1	printUset(ums2);  //6 4 2 7 3 3 1 1 1	ums2.erase(val);	printUset(ums2);  //6 4 2 7 3 3 1	ums1.clear();	ums2.clear();	if (ums1.empty())		cout << "unordered multiset 1 is empty\n";  //输出此分支	else		cout << "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 1	erase_one_entry(ums, val);	printUset(ums);  //6 4 2 7 3 3 1 1}

方法

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";	else		cout << "unordered multimap 2 is not empty\n";  //输出此分支	cout << "Size of unordered multimap 1 is " << umm1.size() << endl;  //7	string key = "apple";	unit it = umm1.find(key);	if (it != umm1.end()) { 		cout << "\nkey " << key << " is there in unordered " << " multimap 1\n";  //apple		cout << "\none of the value associated with " << key << " is " << it->second << endl;  //apple 1	}	else		cout << "\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 3	printUmm(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";  //输出此分支	else		cout << "\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基本一致，这里不再列举，点此跳转。