译自《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提供。 如果您发现任何错误，或者想分享关于上述主题的更多信息，请写评论。