前两节介绍了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; //输出此分支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;}

其他方法

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

方法

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基本一致，这里不再列举，点此跳转。