C++ STL中的无序映射-yiteyi-C++库

无序映射是一个关联的容器，它存储由键值和映射值组合而成的元素。键值用于唯一标识元素，映射值是与键值关联的内容。键和值都可以是预定义或用户定义的任何类型。

null

内部无序的_映射是使用哈希表，提供给映射的键被散列到哈希表的索引中，这就是为什么数据结构的性能很大程度上取决于哈希函数，但平均而言，它的成本是 搜索、插入和删除 从哈希表中可以看出是O（1）。

注：在最坏的情况下，它的时间复杂度可以从O（1）到O（n） ^2. )，尤其是对于大素数。你可以在网上阅读更多关于这方面的信息如何在c中高效地使用无序地图 .在这种情况下，最好使用地图来避免出现错误。

C++

                         // 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 int type                       
                                                 unordered_map<string,                                     int                                     > umap;                       
           
                                                 // inserting values by using [] operator                       
                                                 umap[                                     "GeeksforGeeks"                                     ] = 10;                       
                                                 umap[                                     "Practice"                                     ] = 20;                       
                                                 umap[                                     "Contribute"                                     ] = 30;                       
           
                                                 // Traversing an unordered map                       
                                                 for                                     (                                     auto                                     x : umap)                       
                                                 cout << x.first <<                                     " "                                     << x.second << endl;                       
           
                         }                       

输出：

Contribute 30GeeksforGeeks 10Practice 20

无序地图vs 无序集 : 在无序集合中，我们只有键，没有值，这些主要用于查看集合中的存在/不存在。例如，考虑计数单个单词的频率的问题。我们不能使用无序的集合（或集合），因为我们不能存储计数。

无序地图vs 地图 : 地图（比如设置 )是唯一键的有序序列，而在无序映射中，键可以以任意顺序存储，因此无序。映射被实现为一个平衡的树结构，这就是为什么可以保持元素之间的顺序（通过特定的树遍历）。map操作的时间复杂度为O（logn），而对于无序的_-map，平均时间复杂度为O（1）。

无序_图上的方法 有很多功能可以在无序的地图上工作。其中最有用的是–operator=、operator[]、empty and size for capacity、begin and end for the iterator、find and count for lookup、insert and erase for modification。 C++11库还提供了查看内部使用的bucket count、bucket size、hash函数和各种hash策略的函数，但它们在实际应用中用处不大。我们可以使用迭代器迭代无序_映射的所有元素。初始化、索引和迭代如以下示例代码所示：

C++

                         // 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"                                     ;                       
           
                                                 // If key found then iterator to that key is returned                       
                                                 else                       
                                                 cout <<                                     "Found "                                     << key <<                                     ""                                     ;                       
           
                                                 key =                                     "lambda"                                     ;                       
                                                 if                                     (umap.find(key) == umap.end())                       
                                                 cout << key <<                                     " not found"                                     ;                       
                                                 else                       
                                                 cout <<                                     "Found "                                     << key << endl;                       
           
                                                 //    iterating over all value of umap                       
                                                 unordered_map<string,                                     double                                     >:: iterator itr;                       
                                                 cout <<                                     "All Elements : "                                     ;                       
                                                 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 PIlambda not foundAll Elements : loge  1e  2.718log10  2.302root3  1.732PI  3.14root2  1.414

一个基于无序映射的实际问题 –给定一串单词，找出单个单词的频率。

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)

下面是使用无序的映射的C++解决方案。

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 <<                                     ")"                                     ;                       
                         }                       
           
                         // 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)

无序映射的方法：

在这个函数在C++ unQuordEdMAP中返回元素的引用，作为元素k。
开始：返回一个迭代器，该迭代器指向无序映射容器中容器中的第一个元素
结束（）：返回一个迭代器，指向无序映射容器中容器中最后一个元素之后的位置
bucket（）：返回键为k的元素在地图中所处的桶号。
桶数： bucket_count用于计算无序_映射中的bucket总数。无需参数即可传递到此函数中。
桶大小：返回无序映射的每个存储桶中的元素数。
计数（）：使用给定键计算无序_映射中存在的元素数。
等距：返回一个范围的边界，该范围包含容器中的所有元素，其键的比较值等于k。
find（）：返回元素的迭代器。
empty（）：检查无序映射容器中的容器是否为空。
erase（）：擦除无序映射容器中容器中的元素。

最近关于无序地图的文章 本文由乌特卡什·特里维迪。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章