C++ STL中的unordered_map用法指南

2021年3月17日14:16:25 发表评论 418 次浏览

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与

地图

:

地图(如

)是唯一键的有序序列, 而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 part  and
         // itr->second stroes the value part
         cout << itr->first << "  " << itr->second << endl;
      }
}

输出如下:

Found PI

lambda not found

All Elements : 
loge  1
e  2.718
log10  2.302
root3  1.732
PI  3.14
root2  1.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。

最近关于unordered_map的文章

本文作者:乌特卡什·特里维迪(Utkarsh Trivedi)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

被认为是行业中最受欢迎的技能之一, 我们拥有自己的编码基础C ++ STL通过激烈的问题解决过程来训练和掌握这些概念。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: