译自《unordered_map in STL and its applications》
unordered_map是一个关联容器，用于存储通过键值和映射值的组合形成的元素。 键值用于唯一标识元素，映射值是与键值相关联的内容。键和值都可以是预定义或用户定义的任何类型。 unordered_map内部使用哈希表实现，提供给映射的键被散列成哈希表的索引，这就是数据结构的性能依赖于哈希函数的原因，但平均来说，从哈希表查找的成本是O(1)。 在最坏的情况下，unordered_map可能需要O(n）时间，但实际上它要快得多，并且优于基于树的映射。
unordered_map vs unordered_set ：
在unordered_set中，我们只有键，没有值，这些主要用于查看集合中的存在/不存在。 例如，考虑对单个词的频率进行计数的问题。 我们不能使用unordered_set(或set），因为我们不能存储计数。
unordered_map vs map ：
map(如set)是唯一键的有序序列，而在unordered_map中键可以以任何顺序存储，因此无序。 映射被实现为平衡树结构，这就是为什么可以通过特定树遍历来维护元素之间的顺序的原因。 映射操作的时间复杂度为O(Log n)，而对于unordered_set，平均值为O(1）。
unordered_set的方法
有很多函数可用于unordered_map。 最有用的是 - operator =，operator []，empty()和size()，iterator的begin()和end()，find()和count()用于查找，insert()和erase()用于修改。 C++ 11库还提供了查看内部使用的桶数(bucket count)，桶大小(bucket size)以及使用的散列函数和各种哈希策略的函数，但它们在实际应用中不太有用。 我们可以使用Iterator迭代unordered_map的所有元素。 初始化，索引和迭代显示在以下示例代码中：
// C++ program to demonstrate functionality of unordered_map
#include <bits/stdc++.h>
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 part and
// itr->second stores the value part
cout << itr->first << " " << itr->second << endl;
}
}
输出如下：
Found PI
lambda not found
All Elements :
loge 1
log10 2.302
root3 1.732
e 2.718
root2 1.414
PI 3.14
一个基于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_set的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;
}
输出如下：
(practice, 1)
(for, 2)
(qa, 1)
(quiz, 1)
(geeks, 3)
本文由Utkarsh Trivedi提供。 如果您发现任何错误，或者想分享关于上述主题的更多信息，请写评论。
