unordered_map是一个关联的容器, 用于存储由键值和映射值的组合形成的元素。键值用于唯一地标识元素, 并且映射值是与键关联的内容。键和值都可以是预定义或用户定义的任何类型。
内部unordered_map使用以下方式实现
哈希表
哈希表, 提供给map的键被散列到散列表的索引中, 这就是为什么数据结构的性能在很大程度上取决于散列函数, 但平均而言
搜索, 插入和删除
哈希表中的值是O(1)。
// C++ program to demonstrate functionality of unordered_map
#include <
iostream>
#include <
unordered_map>
using namespace std;
int main()
{
// Declaring umap to be of <
string, int>
type
// key will be of string type and mapped value will
// be of double type
unordered_map<
string, int >
umap;
// inserting values by using [] operator
umap[ "lsbin" ] = 10;
umap[ "Practice" ] = 20;
umap[ "Contribute" ] = 30;
// Traversing an unordered map
for ( auto x : umap)
cout <
<
x.first <
<
" " <
<
x.second <
<
endl;
}
输出如下:
Contribute 30
lsbin 10
Practice 20
unordered_map与
无序集
:
在unordered_set中, 我们只有键, 没有值, 这些键主要用于查看集中是否存在。例如, 考虑对单个单词的频率进行计数的问题。我们无法使用unordered_set(或set), 因为我们无法存储计数。
unordered_map与
地图
:
【C++ STL中的unordered_map用法指南】地图(如
组
)是唯一键的有序序列, 而unordered_map中的键可以以任何顺序存储, 因此是无序的。
映射被实现为平衡的树结构, 这就是为什么可以维持元素之间的顺序(通过特定的树遍历)的原因。映射操作的时间复杂度为O(Log n), 而unordered_map的平均时间复杂度为O(1)。
unordered_map上的方法
许多功能都可以在unordered_map上使用。其中最有用的是–运算符=, 运算符[], 用于容量的空白和大小, 用于迭代器的开始和结束, 用于查找的查找和计数, 用于修改的插入和擦除。
C ++ 11库还提供了查看内部使用的存储桶计数, 存储桶大小以及使用的哈希函数和各种哈希策略的功能, 但它们在实际应用中用处不大。
我们可以使用Iterator遍历unordered_map的所有元素。下面的示例代码显示了初始化, 索引和迭代:
// C++ program to demonstrate functionality of unordered_map
#include <
iostream>
#include <
unordered_map>
using namespace std;
int main()
{
// Declaring umap to be of <
string, double>
type
// key will be of string type and mapped value will
// be of double type
unordered_map<
string, double >
umap;
// inserting values by using [] operator
umap[ "PI" ] = 3.14;
umap[ "root2" ] = 1.414;
umap[ "root3" ] = 1.732;
umap[ "log10" ] = 2.302;
umap[ "loge" ] = 1.0;
// inserting value by insert function
umap.insert(make_pair( "e" , 2.718));
string key = "PI" ;
// If key not found in map iterator to end is returned
if (umap.find(key) == umap.end())
cout <
<
key <
<
" not found\n\n" ;
// If key found then iterator to that key is returned
else
cout <
<
"Found " <
<
key <
<
"\n\n" ;
key = "lambda" ;
if (umap.find(key) == umap.end())
cout <
<
key <
<
" not found\n" ;
else
cout <
<
"Found " <
<
key <
<
endl;
//iterating over all value of umap
unordered_map<
string, double >
:: iterator itr;
cout <
<
"\nAll Elements : \n" ;
for (itr = umap.begin();
itr != umap.end();
itr++)
{
// itr works as a pointer to pair<
string, double>
// type itr->
first stores the key partand
// itr->
second stroes the value part
cout <
<
itr->
first <
<
"" <
<
itr->
second <
<
endl;
}
}
输出如下:
Found PIlambda not foundAll Elements :
loge1
e2.718
log102.302
root31.732
PI3.14
root21.414
基于unordered_map的实际问题–给定一个字符串, 找到单个单词的频率。
Input :str = "geeks for geeks geeks quiz practice qa for";
Output : Frequencies of individual words are
(practice, 1)
(for, 2)
(qa, 1)
(quiz, 1)
(geeks, 3)
以下是使用unordered_map的C ++解决方案。
// C++ program to find freq of every word using
// unordered_map
#include <
bits/stdc++.h>
using namespace std;
// Prints frequencies of individual words in str
void printFrequencies( const string &
str)
{
// declaring map of <
string, int>
type, each word
// is mapped to its frequency
unordered_map<
string, int >
wordFreq;
// breaking input into word using string stream
stringstream ss(str);
// Used for breaking words
string word;
// To store individual words
while (ss >
>
word)
wordFreq[word]++;
// now iterating over word, freq pair and printing
// them in <
, >
format
unordered_map<
string, int >
:: iterator p;
for (p = wordFreq.begin();
p != wordFreq.end();
p++)
cout <
<
"(" <
<
p->
first <
<
", " <
<
p->
second <
<
")\n" ;
}// Driver code
int main()
{
string str = "geeks for geeks geeks quiz "
"practice qa for" ;
printFrequencies(str);
return 0;
}
输出如下:
(qa, 1)
(quiz, 1)
(practice, 1)
(geeks, 3)
(for, 2)
unordered_map的方法:
- 在():C ++中的此函数unordered_map返回对该值的引用, 其元素为键k。
- 开始():返回一个迭代器, 该迭代器指向unordered_map容器中容器中的第一个元素
- 结束():返回一个迭代器, 该迭代器指向unordered_map容器中容器中最后一个元素之后的位置
- 桶():返回带有键k的元素在地图上所在的存储区编号。
- bucket_count:bucket_count用于计数总数。 unordered_map中的存储桶数。不需要任何参数即可传递给该函数。
- bucket_size:返回unordered_map每个存储段中的元素数。
- 计数():计算具有给定键的unordered_map中存在的元素数。
- 等距:返回范围的边界, 该范围包括容器中的所有元素, 且键的比较值等于k。
本文作者:乌特卡什·特里维迪(Utkarsh Trivedi)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
被认为是行业中最受欢迎的技能之一, 我们拥有自己的编码基础C ++ STL通过激烈的问题解决过程来训练和掌握这些概念。
推荐阅读
- redux中间件 – Redux教程
- Java环境部署(安装和环境变量设置)
- 在R编程中计算向量的累积最大值– cummax()函数用法介绍
- PHP Ds Sequencealloc()函数用法介绍
- 算法(将所有出现的元素移动到链表的结尾)
- PHP cal_from_jd()函数用法详细介绍
- 算法设计(未排序数组的均值和中位数的程序)
- 如何使用JavaScript获取文本输入字段的值()
- Arcesium面试体验(在FTE校园内)