前两节介绍了STL中的顺序容器和关联容器，本节来介绍一下无序容器。无序容器与关联容器类似，但是关联容器是顺序排序的，而无序容器实现了未排序(哈希)的数据结构。
文章目录
1 unordered_set2 unordered_map3 unordered_multiset4 unordered_multimap
1 unordered_set
无序集合(unordered_set)是一种使用哈希表实现的无序关联容器，其中键被哈希到哈希表的索引位置，因此插入操作总是随机的。无序集合上的所有操作在平均情况下都具有常数时间复杂度O(1)，但在最坏情况下，时间复杂度可以达到线性时间O(n)，这取决于内部使用的哈希函数，但实际上它们表现非常出色，通常提供常数时间的查找操作。
无序集合可以包含任何类型的键 - 预定义或用户自定义数据结构，但所有键必须是唯一的。它的语法如下：
std::unordered_set
常用方法
size()和empty():用于获取大小和集合是否为空find():用于查找键insert()和erase():用于插入和删除元素
#include
using namespace std;
int main()
{
unordered_set
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
for (itr = stringSet.begin(); itr != stringSet.end(); itr++)
cout << (*itr) << ' '; //fast is code c++ in
}
可以看到输出的顺序混乱，因为在无序集合中没有特定的数据存储顺序。
如果集合中不存在某个键，find()函数会返回一个指向end()的迭代器，否则会返回指向键位置的迭代器。迭代器充当键值的指针，因此我们可以使用*运算符来解引用它们以获取键。
基于无序集合的实际问题：已知一个整数数组，要找出其中的所有重复项。
#include
using namespace std;
void printDuplicates(int arr[], int n)
{
unordered_set
unordered_set
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
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 NameFunction Descriptioninsert()插入一个新元素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
#include
using namespace std;
int main()
{
unordered_map
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/FunctionsDescriptionat(K)返回与元素作为键k相关的值的引用begin()/end()返回一个迭代器，指向第一个元素/最后一个元素后的理论元素bucket(k)返回键k所在的桶编号，即元素在映射中的位置。bucket_count()返回无序映射容器中的总桶数bucket_size()返回无序映射中每个桶中的元素数量count()计算具有给定键的元素在无序映射中出现的次数equal_range(k)返回包括与键k相等的所有元素的范围的边界find()搜索元素empty()检查无序映射容器是否为空erase()从无序映射容器中删除元素
C++11库还提供了用于查看内部使用的桶数、桶大小以及使用的哈希函数和各种哈希策略的函数(和unordered_set中类似)，但它们在实际应用中的用处较小。我们可以使用迭代器遍历无序映射中的所有元素。
#include
#include
using namespace std;
int main()
{
//三种插入方式
unordered_map
{
{"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
cout << "\nAll Elements : \n";
for (itr = umap.begin(); itr != umap.end(); itr++)
{
cout << itr->first << " " << itr->second << endl; //遍历输出所有元素
}
}
实例:计算各个字符出现的频率
#include
using namespace std;
void printFrequencies(const string &str)
{
unordered_map
stringstream ss(str);
string word;
while (ss >> word)
wordFreq[word]++;
unordered_map
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
实例
#include
using namespace std;
typedef unordered_multiset
void printUset(unordered_multiset
{
umit it = ums.begin();
for (; it != ums.end(); it++)
cout << *it << " ";
cout << endl;
}
int main()
{
unordered_multiset
unordered_multiset
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
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
using namespace std;
typedef unordered_multiset
void printUset(unordered_multiset
{
umit it = ums.begin();
for (; it != ums.end(); it++)
cout << *it << " ";
cout << endl;
}
void erase_one_entry(unordered_multiset
int val)
{
umit it = ums.find(val);
if (it != ums.end())
ums.erase(it);
}
int main()
{
unordered_multiset
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
}
方法
Function NameFunction Descriptioninsert()插入新元素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
using namespace std;
typedef unordered_multimap
void printUmm(unordered_multimap
{
unit it = umm.begin();
for (; it != umm.end(); it++){
cout << "<" << it->first << ", " << it->second << "> " << endl;
}
}
int main()
{
unordered_multimap
unordered_multimap
{ { "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
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
using namespace std;
void printUmm(unordered_multimap
{
auto it1 = umm.begin();
for (; it1 != umm.end(); it1++) {
cout << "<" << it1->first << ", " << it1->second << "> " << endl;
}
}
int main()
{
unordered_multimap
{ "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基本一致，这里不再列举，点此跳转。
好文阅读
您阅读本篇文章共花了：
发表评论