unordered_map详细介绍_程序猿小泽的博客-程序员宝宝_unordered_map

技术标签: C、C++  unordered_map详细介绍  

转载自关联容器:unordered_map详细介绍(附可运行代码)


1.介绍

最近使用到一个c++的容器——unordered_map,它是一个关联容器,内部采用的是hash表结构,拥有快速检索的功能。

1.1 特性

  1. 关联性:通过key去检索value,而不是通过绝对地址(和顺序容器不同)
  2. 无序性:使用hash表存储,内部无序
  3. Map : 每个值对应一个键值
  4. 键唯一性:不存在两个元素的键一样
  5. 动态内存管理:使用内存管理模型来动态管理所需要的内存空间

1.2 Hashtable和bucket

由于unordered_map内部采用的hashtable的数据结构存储,所以,每个特定的key会通过一些特定的哈希运算映射到一个特定的位置,我们知道,hashtable是可能存在冲突的(多个key通过计算映射到同一个位置),在同一个位置的元素会按顺序链在后面。所以把这个位置称为一个bucket是十分形象的(像桶子一样,可以装多个元素)。可以参考这篇介绍哈希表的文章

这里写图片描述

所以unordered_map内部其实是由很多哈希桶组成的,每个哈希桶中可能没有元素,也可能有多个元素。

2. 模版

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;
 
  

    主要使用的也是模板的前2个参数<键,值>(需要更多的介绍可以点击这里

    unordered_map<const Key, T> map;
     
      

      2.1 迭代器

      unordered_map的迭代器是一个指针,指向这个元素,通过迭代器来取得它的值。

      unordered_map<Key,T>::iterator it;
      (*it).first;             // the key value (of type Key)
      (*it).second;            // the mapped value (of type T)
      (*it);                   // the "element value" (of type pair<const Key,T>) 
       
        

        它的键值分别是迭代器的first和second属性。

        it->first;               // same as (*it).first   (the key value)
        it->second;              // same as (*it).second  (the mapped value) 
         
          

          3. 功能函数

          3.1 构造函数

          unordered_map的构造方式有几种:
          - 构造空的容器
          - 复制构造
          - 范围构造
          - 用数组构造

          3.1.2示例代码

          // constructing unordered_maps
          #include <iostream>
          #include <string>
          #include <unordered_map>
          using namespace std;
          
          typedef unordered_map<string,string> stringmap;
          
          stringmap merge (stringmap a,stringmap b) {
            stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
          }
          
          int main ()
          {
            stringmap first;                              // 空
            stringmap second ( {
             {
             "apple","red"},{
             "lemon","yellow"}} );       // 用数组初始
            stringmap third ( {
             {
             "orange","orange"},{
             "strawberry","red"}} );  // 用数组初始
            stringmap fourth (second);                    // 复制初始化
            stringmap fifth (merge(third,fourth));        // 移动初始化
            stringmap sixth (fifth.begin(),fifth.end());  // 范围初始化
          
            cout << "sixth contains:";
            for (auto& x: sixth) cout << " " << x.first << ":" << x.second;
            cout << endl;
          
            return 0;
          }
           
            

            输出结果:

            sixth contains: apple:red lemon:yellow orange:orange strawberry:red
            
             
              

              3.2 容量操作

              3.2.1 size

              size_type size() const noexcept;
              
               
                

                返回unordered_map的大小

                3.2.2 empty

                bool empty() const noexcept;
                
                 
                  

                  - 为空返回true
                  - 不为空返回false,和用size() == 0判断一样。

                  3.3 元素操作

                  3.3.1 find

                  iterator find ( const key_type& k );
                  
                   
                    

                    查找key所在的元素。
                    - 找到:返回元素的迭代器。通过迭代器的second属性获取值
                    - 没找到:返回unordered_map::end

                    3.3.2 insert

                    插入有几种方式:
                    - 复制插入(复制一个已有的pair的内容)
                    - 数组插入(直接插入一个二维数组)
                    - 范围插入(复制一个起始迭代器和终止迭代器中间的内容)
                    - 数组访问模式插入(和数组的[]操作很相似)

                    具体的例子可以看后面示例代码。

                    3.3.3 at

                    mapped_type& at ( const key_type& k );
                    
                     
                      

                      查找key所对应的值
                      - 如果存在:返回key对应的值,可以直接修改,和[]操作一样。
                      - 如果不存在:抛出 out_of_range 异常.

                      mymap.at(“Mars”) = 3396; //mymap[“Mars”] = 3396

                      3.3.4 erase

                      擦除元素也有几种方式:

                      • 通过位置(迭代器)

                      iterator erase ( const_iterator position );
                      
                       
                        
                        • 通过key

                        • size_type erase ( const key_type& k );
                          
                           
                              
                          • 通过范围(两个迭代器)

                          • iterator erase ( const_iterator first, const_iterator last );
                            
                             
                                

                              3.3.5 clear

                              void clear() noexcept
                              
                               
                                  

                                清空unordered_map

                                3.3.6 swap

                                void swap ( unordered_map& ump );
                                
                                 
                                    

                                  交换两个unordered_map(注意,不是交换特定元素,是整个交换两个map中的所有元素)

                                  3.3.7 示例代码

                                  // unordered_map::insert
                                  #include <iostream>
                                  #include <string>
                                  #include <unordered_map>
                                  using namespace std;
                                  
                                  void display(unordered_map<string,double> myrecipe,string str)
                                  {
                                      cout << str << endl;
                                      for (auto& x: myrecipe)
                                          cout << x.first << ": " << x.second << endl;
                                      cout << endl;
                                  }
                                  
                                  int main ()
                                  {
                                      unordered_map<string,double>
                                      myrecipe,
                                      mypantry = {
                                       {
                                       "milk",2.0},{
                                       "flour",1.5}};
                                  
                                      /****************插入*****************/
                                      pair<string,double> myshopping ("baking powder",0.3);
                                      myrecipe.insert (myshopping);                        // 复制插入
                                      myrecipe.insert (make_pair<string,double>("eggs",6.0)); // 移动插入
                                      myrecipe.insert (mypantry.begin(), mypantry.end());  // 范围插入
                                      myrecipe.insert ({
                                       {
                                       "sugar",0.8},{
                                       "salt",0.1}});    // 初始化数组插入(可以用二维一次插入多个元素,也可以用一维插入一个元素)
                                      myrecipe["coffee"] = 10.0;  //数组形式插入
                                  
                                      display(myrecipe,"myrecipe contains:");
                                  
                                      /****************查找*****************/
                                      unordered_map<string,double>::const_iterator got = myrecipe.find ("coffee");
                                  
                                      if ( got == myrecipe.end() )
                                          cout << "not found";
                                      else
                                          cout << "found "<<got->first << " is " << got->second<<"\n\n";
                                      /****************修改*****************/
                                      myrecipe.at("coffee") = 9.0;
                                      myrecipe["milk"] = 3.0;
                                      display(myrecipe,"After modify myrecipe contains:");
                                  
                                  
                                      /****************擦除*****************/
                                      myrecipe.erase(myrecipe.begin());  //通过位置
                                      myrecipe.erase("milk");    //通过key
                                      display(myrecipe,"After erase myrecipe contains:");
                                  
                                      /****************交换*****************/
                                      myrecipe.swap(mypantry);
                                      display(myrecipe,"After swap with mypantry, myrecipe contains:");
                                  
                                      /****************清空*****************/
                                      myrecipe.clear();
                                      display(myrecipe,"After clear, myrecipe contains:");
                                      return 0;
                                  }
                                   
                                      

                                    输出结果:

                                    myrecipe contains:
                                    salt: 0.1
                                    milk: 2
                                    flour: 1.5
                                    coffee: 10
                                    eggs: 6
                                    sugar: 0.8
                                    baking powder: 0.3
                                    
                                    found coffee is 10
                                    
                                    After modify myrecipe contains:
                                    salt: 0.1
                                    milk: 3
                                    flour: 1.5
                                    coffee: 9
                                    eggs: 6
                                    sugar: 0.8
                                    baking powder: 0.3
                                    
                                    After erase myrecipe contains:
                                    flour: 1.5
                                    coffee: 9
                                    eggs: 6
                                    sugar: 0.8
                                    baking powder: 0.3
                                    
                                    After swap with mypantry, myrecipe contains:
                                    flour: 1.5
                                    milk: 2
                                    
                                    After clear, myrecipe contains:
                                    
                                     
                                        

                                      3.4 迭代器和bucket操作

                                      3.4.1 begin

                                        iterator begin() noexcept;
                                        local_iterator begin ( size_type n );
                                      
                                       
                                          
                                        • begin() : 返回开始的迭代器(和你的输入顺序没关系,因为它的无序的)
                                        • begin(int n) : 返回n号bucket的第一个迭代器

                                        3.4.2 end

                                          iterator end() noexcept;
                                          local_iterator end( size_type n );
                                        
                                         
                                            
                                          • end(): 返回结束位置的迭代器
                                          • end(int n) : 返回n号bucket的最后一个迭代器

                                          3.4.3 bucket

                                          size_type bucket ( const key_type& k ) const;
                                          
                                           
                                              

                                            返回通过哈希计算key所在的bucket(注意:这里仅仅做哈希计算确定bucket,并不保证key一定存在bucket中!)

                                            3.4.4 bucket_count

                                            size_type bucket_count() const noexcept;
                                            
                                             
                                                

                                              返回bucket的总数

                                              3.4.5 bucket_size

                                              size_type bucket_size ( size_type n ) const;
                                               
                                                  

                                                返回第i个bucket的大小(这个位置的桶子里有几个元素,注意:函数不会判断n是否在count范围内)

                                                3.4.6 示例代码

                                                // unordered_map::bucket_count
                                                #include <iostream>
                                                #include <string>
                                                #include <unordered_map>
                                                using namespace std;
                                                
                                                int main ()
                                                {
                                                    unordered_map<string,string> mymap =
                                                    {
                                                        {
                                                     "house","maison"},
                                                        {
                                                     "apple","pomme"},
                                                        {
                                                     "tree","arbre"},
                                                        {
                                                     "book","livre"},
                                                        {
                                                     "door","porte"},
                                                        {
                                                     "grapefruit","pamplemousse"}
                                                    };
                                                    /************begin和end迭代器***************/
                                                    cout << "mymap contains:";
                                                    for ( auto it = mymap.begin(); it != mymap.end(); ++it )
                                                        cout << " " << it->first << ":" << it->second;
                                                    cout << endl;
                                                    /************bucket操作***************/
                                                     unsigned n = mymap.bucket_count();
                                                
                                                    cout << "mymap has " << n << " buckets.\n";
                                                
                                                    for (unsigned i=0; i<n; ++i)
                                                    {
                                                        cout << "bucket #" << i << "'s size:"<<mymap.bucket_size(i)<<" contains: ";
                                                        for (auto it = mymap.begin(i); it!=mymap.end(i); ++it)
                                                            cout << "[" << it->first << ":" << it->second << "] ";
                                                        cout << "\n";
                                                    }
                                                
                                                    cout <<"\nkey:'apple' is in bucket #" << mymap.bucket("apple") <<endl;
                                                    cout <<"\nkey:'computer' is in bucket #" << mymap.bucket("computer") <<endl;
                                                
                                                    return 0;
                                                }
                                                
                                                 
                                                    

                                                  输出结果:

                                                  mymap contains: door:porte grapefruit:pamplemousse tree:arbre apple:pomme book:livre house:maison
                                                  mymap has 7 buckets.
                                                  bucket #0's size:2 contains: [book:livre] [house:maison]
                                                  bucket #1's size:0 contains:
                                                  bucket #2's size:0 contains:
                                                  bucket #3's size:2 contains: [grapefruit:pamplemousse] [tree:arbre]
                                                  bucket #4's size:0 contains:
                                                  bucket #5's size:1 contains: [apple:pomme]
                                                  bucket #6's size:1 contains: [door:porte]
                                                  
                                                  key:'apple' is in bucket #5
                                                  
                                                  key:'computer' is in bucket #6
                                                  
                                                   
                                                      

                                                    最后

                                                    unordered_map常用的功能函数介绍就这么多了,还有一些比较不常用的功能的介绍,可以参考这里

                                                  版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
                                                  本文链接:https://blog.csdn.net/lizhengze1117/article/details/96728468

                                                  智能推荐

                                                  2020程序员大厂面试流程,面试游刃有余!_程序员-小枫的博客-程序员宝宝

                                                  电话面试面试官打电话的形式考查应聘者,会提前约好时间 有些面试官喜欢搞突然袭击,建议应聘者在投出简历之后的一两个星期之内,保证手机电池能至少连续通话一小时。应聘者不要长时间待在很嘈杂的环境下。 电话面试只能依靠声音,描述复杂算法的时候尽可能形象把细节说清楚。 例如,现场面试的时候,如果要描述二叉树的结构,可以用笔在白纸上画出来,电话面试则需要把二叉树中有哪些节点,每个节点的左节点是什么,右节点是什么都说得很清楚。共享桌面面试应聘者把自己的桌面远程分享给面试官,面试官可以观看应聘者编程和调试的过

                                                  Navicat报错:[Err] 1055 - Expression #1 ... incompatible with sql_mode=only_full_group_by_宫懋鸡丁的博客-程序员宝宝_navicat错误1055

                                                  问题描述今天使用Navicat连接mysql,运行建表sql后发现如下报错:[Err] 1055 - Expression #1 of ORDER BY clause is not in GROUP BY clause and contains nonaggregated column 'information_schema.PROFILING.SEQ' which is not functionally dependent on columns in GROUP BY clause;this

                                                  JSP页面使用EL表达式获取域对象中的值_程序员小宁的博客-程序员宝宝_jsp获取对象的值

                                                  &lt;%@ page import="cn.gpxxg.domain.User" %&gt;&lt;%@ page import="java.util.*" %&gt;&lt;%@ page contentType="text/html;charset=UTF-8" language="java" %&gt;&lt;html&gt;&lt;head&gt; &lt;title&gt;JSP页面使用EL表达式获取域对象中的值&lt;/title&gt;&lt;/head&gt;&lt;.

                                                  STL 源码剖析 算法 stl_algo.h -- partition_zhsenl的博客-程序员宝宝

                                                  partition------------------------------------------------------------------------描述:partition 会将区间[first,last) 中的元素重新排列。所有被一元条件运算 pred 判定为 true 的元素,都会被放在区间的前段,被判定为 false 的元素,都会被放在区间的后段。partition 不稳定,不保证 partition 后元素保留在原始相对位置, stable_partition 稳定思路:

                                                  TaskBuilder与VSCode、Eclipse有什么区别?_Nodejs_home的博客-程序员宝宝_vscode和eclipse哪个好

                                                  Visual Studio Code(简称“VS Code” )是Microsoft在2015年4月30日Build开发者大会上正式宣布一个运行于 Mac OS X、Windows和 Linux 之上的,针对于编写现代Web和云应用的跨平台源代码编辑器, 可在桌面上运行,并且可用于Windows,macOS和Linux。它具有对JavaScript,TypeScript和Node.js的内置支持,并具有丰富的其他语言(例如C++,C#,Java,Python,PHP,Go)和运行时(例如.NET和Unity

                                                  封了1000多个IP地址段,服务器现在坚如磐石,对付几个小毛贼还是很轻松的_云寻觅的博客-程序员宝宝

                                                  封了1000多个IP地址段,服务器现在坚如磐石root登陆权限取消,防火墙装上,关闭所有没必要的端口,外层加装路由器映射,修改常用端口,将常用端口改成陷阱程序,只要访问我这些陷阱端口,程序直接drop这个ip对付几个小毛贼还是很轻松的iptables -I INPUT -s 123.44.55.0/24 -j DROP &&       iptables -

                                                  随便推点

                                                  Hibernate持久化对象的状态:瞬时状态、持久化状态、托管状态_p0inter的博客-程序员宝宝_对象:持久化,瞬时化

                                                  瞬时状态:对象由new操作符创建,但没有和session关联,也就是我们刚刚创建的对象,还没有保存到数据库中去持久化状态:对象被保存到数据库中去了,并且还与session有关联托管状态:对象已经被保存中去了,但与session没有关联了下面用代码解释一下:@Test public void test() { Customer c = new Customer();//瞬时状态 ...

                                                  django源码解读: setting懒加载_木子林_的博客-程序员宝宝_django懒加载

                                                  前言上次我们了解了django启动原理,细心的朋友可能发现django中的setting配置文件加载时懒加载,接下来我们了解下setting的懒加载懒加载我们从manager.py进入management/__init__.py,我们可以看到导入有这个from django.conf import settings,我们进入setting后就可以看到懒加载源码class LazySettings(LazyObject): """ 全局Django设置或自定义设置对象的惰性代

                                                  利用vue实现的一些小案例_冰雪为融的博客-程序员宝宝_vue案例

                                                  1、利用hash过滤数据核心代码:js代码:&amp;lt;script&amp;gt; var vm = new Vue({ el:'#app', data:{ isShow:'red' } }); function hash(){ var hash = window.location.ha...

                                                  H5内嵌在IOS的Webview中适配刘海屏CSS解决方案_jiangjialuan2的博客-程序员宝宝

                                                  摘要首先我们采用了rem单位进行布局,通过JS来动态计算网页的视窗宽度,动态设置html的font-size,在各种手机浏览器中打开都没问题。一切都比较完美。环境部分安卓机webview内嵌h5页面编辑工具HBuild X使用方法function setPX(){ const html = document.getElementsByTagName(‘html’)[0];const realFs = parseFloat(window.getComputedStyle(html).fontS

                                                  基于.Net进行前端开发的技术栈发展路线(一)_weixin_30555515的博客-程序员宝宝

                                                  前言今天想讲讲的是我的技术树。我最初是做CS开发的,第一阶段的技术经历是以Powerbuilder来做CS开发,第二阶段开始基于C#做winform开发,眼看前端开发越来越流行,需要更广泛的技术栈势在必行。因此以.Net为基础,我开始拓展自己的技术栈。从14年到18年,跨越了很多界限,到现在为止,应该说.Net,Java,Android,基于nodejs的web开发都积累了一些经验,可以...