精华内容
下载资源
问答
  • C++11 unordered_mapmap(插入,遍历,Find)效率对比。
  • 主要介绍了C++中的哈希容器unordered_map使用示例,本文直接给出实例代码,并讲解了一些hash table的知识,需要的朋友可以参考下
  • unordered_mapunordered_set的模拟实现 (一)哈希表的特性及概念 定义: 哈希表(Hash table,也叫散列表),是根据关键字值(key,value)直接进行访问的数据结构。也就是说,它通过把关键字映射到表中一个位置来...
  • 一个C++stl:unordered_map实现实例,用于了解熟悉算法。
  • Find_Duplicates_using_unordered_map 查找数组中的所有重复项,以及O(n)运行时中重复元素的频率。
  • mapunordered_map的差别和使用?mapunordered_map的差别和使用?1、map的基本使用操作2、unordered_map的基本使用操作3、mapunordered_map的差别和使用场景参考 mapunordered_map的差别和使用? mapunordered...

    map和unordered_map的差别和使用?

    map和unordered_map都是c++中可以充当字典(key-value)来用的数据类型,但是其基本实现是不一样的。

    1、map的基本使用操作

    • map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树);
    • 红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素。
      • map中的元素是按照二叉搜索树(又名二叉查找树、二叉排序树,特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根节点的键值)存储的,使用中序遍历可将键值按照从小到大遍历出来
    • map的查询、插入、删除操作的时间复杂度都是O(logn)

    基本使用操作-

    #include<iostream>
    #include<map>
    #include<string>
      
    using namespace std;
      
    int main()
    {
        // 构造函数
        map<string, int> dict;
         
        // 插入数据的三种方式
        dict.insert(pair<string,int>("apple",2));
        dict.insert(map<string, int>::value_type("orange",3));
        dict["banana"] = 6;
      
        // 判断是否有元素
        if(dict.empty())
            cout<<"该字典无元素"<<endl;
        else
            cout<<"该字典共有"<<dict.size()<<"个元素"<<endl;
      
        // 遍历
        map<string, int>::iterator iter;
        for(iter=dict.begin();iter!=dict.end();iter++)
            cout<<iter->first<<ends<<iter->second<<endl;
      
        // 查找
        if((iter=dict.find("banana"))!=dict.end()) //  返回一个迭代器指向键值为key的元素,如果没找到就返回end()
            cout<<"已找到banana,其value为"<<iter->second<<"."<<endl;
        else
            cout<<"未找到banana."<<endl;
      
        if(dict.count("watermelon")==0) // 返回键值等于key的元素的个数
            cout<<"watermelon不存在"<<endl;
        else
            cout<<"watermelon存在"<<endl;
         
        pair<map<string, int>::iterator, map<string, int>::iterator> ret;
        ret = dict.equal_range("banana"); // 查找键值等于 key 的元素区间为[start,end),指示范围的两个迭代器以 pair 返回
        cout<<ret.first->first<<ends<<ret.first->second<<endl;
        cout<<ret.second->first<<ends<<ret.second->second<<endl;
      
        iter = dict.lower_bound("boluo"); // 返回一个迭代器,指向键值>=key的第一个元素。
        cout<<iter->first<<endl;
        iter = dict.upper_bound("boluo"); // 返回一个迭代器,指向值键值>key的第一个元素。
        cout<<iter->first<<endl;
        return 0;
    }
    

    2、unordered_map的基本使用操作

    • unordered_map和map类似,都是存储的key-value的值,可以通过key快速索引到value。
      • 不同的是unordered_map不会根据key的大小进行排序,存储时是根据key的hash值判断元素是否相同,即unordered_map内部元素是无序的。
    • unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。
    • hash_table一般是由一个大vector,vector元素节点可挂接链表来解决冲突来实现。
      • hash_table最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;
      • 而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。

    注意:

    哈希表的查询时间虽然是O(1),但是并不是unordered_map查询时间一定比map短,因为实际情况中还要考虑到数据量,而且unordered_map的hash函数的构造速度也没那么快,所以不能一概而论,应该具体情况具体分析。

    基本使用操作-

    #include<string> 
    #include<iostream> 
    #include<unordered_map>
    using namespace std; 
       
    int main()
    {
        unordered_map<string, int>  dict; // 声明unordered_map对象
         
        // 插入数据的三种方式
        dict.insert(pair<string,int>("apple",2));
        dict.insert(unordered_map<string, int>::value_type("orange",3));
        dict["banana"] = 6;
         
        // 判断是否有元素
        if(dict.empty())
            cout<<"该字典无元素"<<endl;
        else
            cout<<"该字典共有"<<dict.size()<<"个元素"<<endl;
         
        // 遍历
        unordered_map<string, int>::iterator iter;
        for(iter=dict.begin();iter!=dict.end();iter++)
            cout<<iter->first<<ends<<iter->second<<endl;
         
        // 查找
        if(dict.count("boluo")==0)
            cout<<"can't find boluo!"<<endl;
        else
            cout<<"find boluo!"<<endl;
         
        if((iter=dict.find("banana"))!=dict.end())
            cout<<"banana="<<iter->second<<endl;
        else
            cout<<"can't find boluo!"<<endl;
         
        return 0;
    }
    

    3、map和unordered_map的差别和使用场景

    map:

    1、优点:

    • 有序性:二叉查找树一个重要的性质是有序,这是map结构最大的优点,且中序遍历时取出的元素是有序的。
    • 红黑树,内部实现一个红黑书使得map的很多操作在O(logn)的时间复杂度下就可以实现,因此效率非常的高

    2、缺点:

    空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间

    3、适用处:

    对于那些有顺序要求的问题,用map会更高效一些

    unordered_map:

    1、优点:

    因为内部实现了哈希表,因此其查找速度非常的快

    2、缺点:
    hash_table最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。

    3、适用处:
    对于查找问题,unordered_map会更加高效一些,因此遇到查找问题,常会考虑一下用unordered_map

    总结:

    • 内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高
    • 但是unordered_map执行效率要比map高很多,看数据量
    • 在需要有序性或者对单次查询有时间要求的应用场景下,应使用map,其余情况应使用unordered_map。

    实验对比

    #include <iostream>
    #include <string>
    #include <sstream>
    #include <list>
    #include <map>
    #include <time.h>
    #include <stdio.h>
    #include <unistd.h>
    #include <unordered_map>
    
    using namespace std;
    
    const int num = 100000;
    
    class timer {
    public:
    	clock_t start;
    	clock_t end;
    	string name;
    	timer(string n) {
    		start = clock();
    		name = n;
    	}
    	~timer() {
    		end = clock();
    		printf("%s time: %f \n", name.c_str(), 
    			(end - start) * 1.0 / CLOCKS_PER_SEC * 1000);
    	}
    };
    
    template<typename T> 
    void insert(T & conta, string name) {
    	srand((unsigned)time(NULL));  
    	timer t1(name);
    	for (int i = 0; i < num / 2; i++) {
    		int key = rand();
    		conta.insert(pair<int, int>(i, i));
    		conta.insert(pair<int, int>(key, i));
    	}
    
    }
    
    template<typename T>
    void find(T & conta, string name) {
    	srand((unsigned)time(NULL));  
    	timer t1(name);
    	for (int i = 0; i < num / 2; i++) {
    		int key = rand();
    		conta.find(key);
    		conta.find(i);
    	}
    }
    
    template<typename T>
    void erase(T & conta, string name) {
    	srand((unsigned)time(NULL));  
    	timer t1(name);
    	for (int i = 0; i < num / 2; i++) {
    		conta.erase(i);
    		int key = rand();
    		conta.erase(key);
    	}
    }
    
    
    void test_map() {
    	map<int, int> m1;
    	insert<map<int, int> >(m1, "map insert");
    	find<map<int, int> >(m1, "map find");	
    	erase<map<int, int> >(m1, "map erase");
    }
    
    void test_unordered_map() {
    	unordered_map<int, int> m2;
    	insert<unordered_map<int, int> >(m2, "unordered_map insert");	
    	find<unordered_map<int, int> >(m2, "unordered_map find");
    	erase<unordered_map<int, int> >(m2, "unordered_map erase");
    }
    
    int main(){
    	test_map();
    	test_unordered_map();
    }
    

    编译指令

    g++ -o3 -o main main.cpp
    ./main
    

    1、10w量级的耗时,可以看出,map在增删查三项上均弱于unordered_map,内存使用map略少,但不明显:

    map insert time: 71.064000
    map find time: 30.305000
    map erase time: 45.373000
    unordered_map insert time: 42.139000
    unordered_map find time: 11.316000
    unordered_map erase time: 31.453000
    
    map内存:5096K
    unordered_map内存:6712K
    

    100w量级的耗时,结论同上。

    map insert time: 955.625000
    map find time: 574.289000
    map erase time: 623.460000
    unordered_map insert time: 575.636000
    unordered_map find time: 166.449000
    unordered_map erase time: 294.509000
    
    map内存:47M
    unordered_map内存:50M
    

    参考

    1、https://blog.csdn.net/BillCYJ/article/details/78985895
    2、https://zhuanlan.zhihu.com/p/48066839

    展开全文
  • 文章目录1.unordered_map1.介绍2.性质3.模板4.定义迭代器5.功能函数5.1构造函数5.2 容量操作:size、empty5.3 元素操作:find、insert、at、erase、clear、swap、for循环打印5.4 迭代器和bucket操作2.unordered_set...

    1.unordered_map

    1.介绍

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

    2.性质

    • 关联性:一个将key和value关联起来的容器,它可以高效的根据单个key值查找对应的value。通过key去检索value,而不是通过绝对地址(和顺序容器不同)
    • 无序性:使用hash表存储,内部无序,可以使用[]操作符来访问key值对应的value值。
    • Map : 每个值对应一个键值
    • 键唯一性:不存在两个元素的键一样
    • 动态内存管理:使用内存管理模型来动态管理所需要的内存空间
    • 1.2 Hashtable和bucket
    • 由于unordered_map内部采用的hashtable的数据结构存储,所以,每个特定的key会通过一些特定的哈希运算映射到一个特定的位置,我们知道,hashtable是可能存在冲突的(多个key通过计算映射到同一个位置),在同一个位置的元素会按顺序链在后面。所以把这个位置称为一个bucket是十分形象的(像桶子一样,可以装多个元素)。可以参考这篇介绍哈希表的文章

    在这里插入图片描述

    • 1)元素在容器无顺序,不提供按顺序遍历
      2)在极端条件下,查找时间复杂度不是O(1),用的时间复杂度会提高很多
      3)占用的空间可能会更多
      4)在1000W以上不如set,hash冲突,性能降低很多;1000W以下就比set好
    • 所以unordered_map内部其实是由很多哈希桶组成的,每个哈希桶中可能没有元素,也可能有多个元素。

    3.模板

    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;
    

    4.定义迭代器

    • 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) 
    

    5.功能函数

    unordered_map的构造方式有几种:

    • 构造空的容器
    • 复制构造
    • 范围构造
    • 用数组构造

    代码:

    5.1构造函数

    // constructing unordered_maps
    #include <iostream>
    #include <string>
    #include <unordered_map>
    using namespace std;
    
    typedef unordered_map<string,string> stringmap;//定义unordered_map容器
    
    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
    

    5.2 容量操作:size、empty

    //size
    size_type size() const noexcept;//返回unordered_map的大小
    
    //empty
    bool empty() const noexcept;	//为空返回true,不为空返回false,和用size() == 0判断一样。
    

    5.3 元素操作:find、insert、at、erase、clear、swap、for循环打印

    //查找
    iterator find ( const key_type& k );//查找key所在的元素。找到:返回元素的迭代器。通过迭代器的second属性获取值,没找到:返回unordered_map::end
    
    //插入
    插入有几种方式:
    
    复制插入(复制一个已有的pair的内容)
    数组插入(直接插入一个二维数组)
    范围插入(复制一个起始迭代器和终止迭代器中间的内容)
    数组访问模式插入(和数组的[]操作很相似)
    
    //查找并修改-at
    mapped_type& at ( const key_type& k );
    查找key所对应的值
    如果存在:返回key对应的值,可以直接修改,和[]操作一样。
    如果不存在:抛出 out_of_range 异常.
    mymap.at(“Mars”) = 3396; //mymap[“Mars”] = 3396
    
    //删除元素
    iterator erase ( const_iterator position );//通过位置(迭代器)
    size_type erase ( const key_type& k );	   //通过key
    iterator erase ( const_iterator first, const_iterator last );//通过范围(两个迭代器)
    
    //清空容器
    void clear() noexcept	//清空unordered_map
    
    //交换容器
    void swap ( unordered_map& ump );//交换两个unordered_map(注意,不是交换特定元素,是整个交换两个map中的所有元素)
    
    //遍历unorder_map代码
    #include <iostream>
    #include <unordered_map>
    using namespace std;
    int main()
    {
    	string key="123";
    	int value=4;
    	unordered_map<string, int> unomap;//创建一个key为string类型,value为int类型的unordered_map
    	unomap.emplace(key, value);//使用变量方式,插入一个元素
    	unomap.emplace("456", 7);//也可以直接写上key和value的值
    	cout<<unomap["123"];//通过key值来访问value
    
    	cout<<endl;
    	for(auto x:unomap)//遍历整个map,输出key及其对应的value值
    		cout<<x.first<<"  "<<x.second<<endl;
    
    	for(auto x:unomap)//遍历整个map,并根据其key值,查看对应的value值
    		cout<<unomap[x.first]<<endl;
    }
    
    

    代码:

    // 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;
    	
    	/****************打印*****************/
    	for(auto x:unomap)//遍历整个map,输出key及其对应的value值
    	{
    	x.second = 0;	
    	cout<<x.second<<endl;//全是  000;;	
    	}
    	cout<<x.second<<endl;//回复原来的数值的。彻底改变:使用find彻底找到这个数值,然后在进行改,可以保证作用域是整个程序。
    	for(auto x:unomap)//遍历整个map,输出key及其对应的value值
    	{
    	auto it = umap.find(key) //改
    	if(it != umap.end()) 
    	    it->second = new_value; 
    	}		
    
    }
    
    
    • 输出结果
    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:
    
    

    5.4 迭代器和bucket操作

    //begin
    iterator begin() noexcept;//begin() : 返回开始的迭代器(和你的输入顺序没关系,因为它的无序的)
    local_iterator begin ( size_type n );//begin(int n) : 返回n号bucket的第一个迭代器
    
    //end
    iterator end() noexcept;	//end(): 返回结束位置的迭代器
    local_iterator end( size_type n );//end(int n) : 返回n号bucket的最后一个迭代器
    
    //bucket
    size_type bucket ( const key_type& k ) const;
    //返回通过哈希计算key所在的bucket(注意:这里仅仅做哈希计算确定bucket,并不保证key一定存在bucket中!)
    
    //bucket_count
    size_type bucket_count() const noexcept;//返回bucket的总数
    
    //bucket_size
    size_type bucket_size ( size_type n ) const;//返回第n个bucket的大小(这个位置的桶子里有几个元素,注意:函数不会判断n是否在count范围内)
    
    

    代码:

    // 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常用的功能函数介绍就这么多了,还有一些比较不常用的功能的介绍,可以参考这里

    2.unordered_set

    2.1性质

    • unordered_set 容器提供了和 unordered_map 相似的能力,但 unordered_set 可以用保存的元素作为它们自己的键。T 类型的对象在容器中的位置由它们的哈希值决定,因而需要定义一个 Hash< T > 函数。基本类型可以省去Hash< T >方法。

    • 不能存放重复元素。

    • 可指定buckets个数,可进行初始化,也可后期插入元素

    • 1、无序集是一种容器,它以不特定的顺序存储惟一的元素,并允许根据元素的值快速检索单个元素。
      2、在unordered_set中,元素的值同时是唯一标识它的键。键是不可变的,只可增删,不可修改
      3、在内部,unordered_set中的元素没有按照任何特定的顺序排序,而是根据它们的散列值组织成桶,从而允许通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。
      4、unordered_set容器比set容器更快地通过它们的键访问单个元素,尽管它们在元素子集的范围迭代中通常效率较低。
      5、容器中的迭代器至少是前向迭代器。

    std::unordered_set<string> example;
    std::unordered_set<string> things {16}; // 16 buckets
    std::unordered_set<string> words {"one", "two", "three", "four"};// Initializer list
    std::unordered_set<string> copy_wrds {words}; // Copy constructor
    
    

    2.2 unordered_set函数

    2.2.1 构造函数

    在这里插入图片描述

    2.2.2 迭代器

    在这里插入图片描述

    2.2.3 各种操作

    在这里插入图片描述

    • unordered_set<Key, Hash, KeyEqual, Allocator>::insert
      在这里插入图片描述

    • unordered_set<Key, Hash, KeyEqual, Allocator>::find
      在这里插入图片描述

    • unordered_set<Key, Hash, KeyEqual, Allocator>::erase
      在这里插入图片描述

    • 迭代
      在这里插入图片描述

    • 改变unordered_set中的值
      在这里插入图片描述

    • 在unordered_set中使用struct的完整例子
      HDUOJ 1004 选出频率最大的字符串

    /**
     * @Copyright (C)  2019  all rights reserved
     * @file Max_Frequency.cpp
     * @author Rinko
     * @date 2019-09-17 
     */
    
    #include<iostream>
    #include<string>
    #include<unordered_set>
    using namespace std;
    #define print(x) cout << x << endl
    #define input(x) cin>>x
    
    struct balloon{
        string color;           //颜色
        mutable int count;      //数量,初始为0,mutable表示可修改!!
        balloon(string n):color(n),count(0){}
        void addCount(){
            count++;
        }
    };
    
    //指定符合hash函数的operator==重载
    //比较相等只看color
    bool operator==(const struct  balloon & X,const struct balloon & Y){
        return hash<string>()(X.color) == hash<string>()(Y.color);
    }
    
    struct balloon_hash{     //指定hash函数,作为模板的第二个参数
        //hash值为color的hash值
        size_t operator()(const struct balloon& _r) const {
            string tmp=_r.color;
            return std::hash<string>()(tmp);
        }
    };
    
    int main()
    {
        int n;
        while (cin >> n){
            if(n == 0)  break;
            unordered_set<balloon, balloon_hash> balloons;
            int maxCount = 0;
            string maxString = "";
            string temp;
            for(unsigned i = 0; i < n; ++i){
                input(temp);
                //成员函数 insert() 可以插入作为参数传入的单个元素。
                //在这种情况下,它会返回一个 pair 对象,
                //这个 pair 对象包含一个迭代器,以及一个附加的布尔值用来说明插入是否成功。
                //如果元素被插入,返回的迭代器会指向新元素;如果没有被插入,迭代器指向阻止插入的元素。
                //初始count = 0,若插入成功,则数量加一,若不成功,则已有的那个balloon数量加一
                auto x = balloons.insert(balloon(temp));
                x.first->count += 1;
            }
            unordered_set<balloon,balloon_hash>::iterator iter = balloons.begin();
            while(iter != balloons.end()){
                if(iter->count > maxCount){
                    maxCount = iter->count;
                    maxString = iter->color;
                }
                iter++;
            }
            print(maxString);
        }
        return 0;
    }
    
    

    2.3 代码使用案例 :

    • 案例1
    #include <iostream>
    #include <unordered_set>
    #include <array>
    #include <string>
    using namespace std;
    
    int main()
    {
    	unordered_set<string> myset1 = { "yellow", "green", "blue" };
    	array<string, 2> myarray = { "black", "white" };
    	string mystring = "red";
    
    	myset1.insert(mystring);                        // copy insertion
    	myset1.insert(mystring + "dish");                 // move insertion
    	myset1.insert(myarray.begin(), myarray.end());  // range insertion
    	myset1.insert({ "black", "white" });           // initializer list insertion
    
    
    	unordered_set<std::string> myset2 =
    	{ "USA", "Canada", "France", "UK", "Japan", "Germany", "Italy" };
    
    	myset2.erase(myset2.begin());                    // erasing by iterator
    	myset2.erase("France");                         // erasing by key
    	myset2.erase(myset2.find("Japan"), myset2.end()); // erasing by range
    	
    	//capacity
    	cout << myset1.size() << endl;
    	cout << myset2.size() << endl;
    	cout << myset1.empty() << endl;
    	cout << myset2.empty() << endl;
    
    	myset1.clear();
    	myset2.clear();
    
    	cout << myset1.size() << endl;
    	cout << myset2.size() << endl;
    	cout << myset1.empty() << endl;
    	cout << myset2.empty() << endl;
    
    	system("pause");
    	return 0;
    }
    
    • 案例2
    #include <iostream>
    #include <unordered_set>
    using namespace std;
    
    
    namespace wzj001{
        void coutUnorderedSet(std::unordered_set<int>& m, string funcName) {
            std::unordered_set<int>::iterator it;
            std::cout << funcName << ": ";
            for ( it = m.begin(); it != m.end(); it++ )
                std::cout << *it << " ";
            std::cout << std::endl;
        }
        
        void initUnorderSet(unordered_set<int>& tmp)
        {
            for(int i = 0; i < 10; i++)
                tmp.insert(i);
        }
        
        string turnBoolToString(bool tmp)
        {
            return tmp ? "true" : "false";
        }
        
        void basicOperationUnorderedSet()
        {
            //定义
            std::unordered_set<int> c;
            // 普通插入,返回pair<迭代器,插入是否成功>
            pair<unordered_set<int>::iterator, bool> c_insert = c.insert(1);
            cout << "指向key的迭代器: " << *c_insert.first  << "   插入是否成功 "<< turnBoolToString(c_insert.second)<<endl;
            pair<unordered_set<int>::iterator, bool> c_insert2 = c.insert(2);
            cout << "指向key的迭代器: " << *c_insert2.first << "   插入是否成功 "<< turnBoolToString(c_insert2.second)<<endl;
            pair<unordered_set<int>::iterator, bool> c_insert3 = c.insert(1);
            cout << "指向key的迭代器: " << *c_insert3.first << "   插入是否成功 "<< turnBoolToString(c_insert3.second)<<endl;
            
            //按指定区域插入
            std::unordered_set<int> c_insert_region;
            c_insert_region.insert(c.begin(), c.end());
            coutUnorderedSet(c_insert_region, "按指定区域插入");
            
            //构造插入
            std::unordered_set<int> c_emplace;
            c_emplace.emplace(1);
            c_emplace.emplace(2);
            c_emplace.emplace(3);
            coutUnorderedSet(c_emplace, "构造插入");
            
            //迭代器插入
            std::unordered_set<int> c_emplace_hint;
            c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 1);
            c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 2);
            c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 3);
            coutUnorderedSet(c_emplace_hint, "迭代器插入");
            
            //删除
            std::unordered_set<int> c_erase;
            initUnorderSet(c_erase);
            coutUnorderedSet(c_erase, "初始化c_erase");
            //指定位置删除
            c_erase.erase(c_erase.begin());
            coutUnorderedSet(c_erase, "指定位置删除");
            
            //指定key删除
            c_erase.erase(8);
            coutUnorderedSet(c_erase, "指定key删除");
            
            //指定区域删除
            c_erase.erase(c_erase.begin(), c_erase.end());
            coutUnorderedSet(c_erase, "指定区域删除");
            
            //交换
            c.swap(c_emplace);
            coutUnorderedSet(c, "交换");
            
        }
        
        void unorderSetElementLookup()
        {
            //查找
            std::unordered_set<int> c_find;
            initUnorderSet(c_find);
            std::unordered_set<int>::iterator find_iter = c_find.find(10);
            if(find_iter != c_find.end())
            {
                cout<< "找到元素 : "<< *find_iter << endl;
            }
            else
                cout<< "没找到 !"<< endl;
            
            cout << "value出现次数 :" <<c_find.count(1)<< endl; //set key不可重复
            
            pair<std::unordered_set<int>::iterator, std::unordered_set<int>::iterator> tmp = c_find.equal_range(5);
            
            if(tmp.first != c_find.end()&& tmp.second != c_find.end())
            {
                cout << "该值所在区间为[" << *tmp.first << "," << *tmp.second << "]" << endl;
            }
        }
        
        void unorderSetBuckets()
        {
            //篮子操作
            std::unordered_set<int> c_buckets;
            initUnorderSet(c_buckets);
            cout << "篮子个数: "    << c_buckets.bucket_count()<< endl;
            cout << "篮子大小: " << c_buckets.bucket_size(1) << endl;
            cout << "最大篮子个数: " << c_buckets.max_bucket_count() << endl;
            cout << "该值所在篮子序号: " << c_buckets.bucket(3) << endl;
        }
        
        void unorderSetHashPolicy()
        {
            std::unordered_set<int> c_;
            cout << "负载: "<< c_.load_factor()<< endl;
            initUnorderSet(c_);
            cout << "负载: "<< c_.load_factor()<< endl;//使用的篮子数/篮子总数  默认的篮子数为11
            cout << "最大负载: "<< c_.max_load_factor() << endl;
            c_.reserve(100);//预设篮子数 ,但是还没有设定
            c_.rehash(3);//设定篮子数
        }
        
        void unorderSetObservers()
        {
            std::unordered_set<int> c_;
            initUnorderSet(c_);
            std::unordered_set<int>::hasher xxx = c_.hash_function();
            std::unordered_set<int>::key_equal zzz = c_.key_eq();
            cout << "hash_func: " << xxx(11111) << endl;
            cout << "key_eq: " << turnBoolToString(zzz(11111,11111)) << endl;
        }
    }
    
    
    int main()
    {
        wzj001::basicOperationUnorderedSet();
        wzj001::unorderSetElementLookup();
        wzj001::unorderSetBuckets();
        wzj001::unorderSetHashPolicy();
        wzj001::unorderSetObservers();
    }
    
    展开全文
  •  ...unordered_map底层使用的数据结构是哈希表(hash table),因此在unordered_map中查找、添加或删除元素时间复杂度都是常数时间O(1)。此外,unordered_map中的元素是无序的。    

           

    一、基本原理

            unordered_map是C++标准库提供的关联容器之一,保存的是键值对(key-value),我们可以通过key快速查找到其对应的value。unordered_map底层使用的数据结构是哈希表(hash table),因此在unordered_map中查找、添加或删除元素时间复杂度都是常数时间O(1)。此外,unordered_map中的元素是无序的

           
    unordered_map使用场景:

            现在假设有一个寝室501,寝室有4个学生,我们要用一种容器来保存这4个学生的学号和姓名,需求是我要通过学号来查找这个学号对应的姓名。

            此时我们用一个unordered_map来保存,学号作为key,姓名作为value,一个学生的这两个信息作为unordered_map的一个元素pair(pair用法总结),我们可以通过学号来得到对应的姓名。

            也许你会有这样的疑问,为什么要用unordered_map呢,我用一个二维数组不是也一样能存放寝室4个学生的学号和姓名吗?

            是的,存是可以存,但是操作的时间复杂度就不一样了,比如我知道学号"sc0303",我想查找对应的姓名,如果用unordered_map保存的,根据哈希表的特性,只需要O(1)的时间就能查到对应的姓名。如果用的二维数组保存的,需要从头遍历二维数组的第一列,需要O(n)的时间才能查到。这就是使用unordered_map的意义。

            也许你还会有这样的疑问,为什么要用unordered_map呢,我用一个map也一样能存吗?

            用map和unordered_map的区别在于,map基于红黑树,是按关键字有序排列的,unordered_map基于哈希表,是散列存放的(无序)。当你需要进行范围查询“比学号sc0302大的同学的姓名”,那么使用map就更方便,因为map中元素已经按照学号(关键字)有序排好了,但是如果这种场景下使用unordered_map,你要进行范围查找只能一个一个去比较了。在进行等值查询时unordered_map只需要O(1)的时间就能查到,但map却需要O(log(n))的时间,因此等值查询时使用unordered_map更快。

            具体选用哪种容器还是要看使用场景,它们各有优势。

           

           

           

    二、用法

           unordered_map中的元素是一对对键值对,类型pair,用法可参考博客pair用法总结
           

    初始化

    unordered_map<T1,T2>    容器名;T1、T2是类型名,可以是基本数据类型int、double等,也可以是类类型string等
    unordered_map<T1,T2>   m1;创建一个名为m1的空unordered_map,key的类型为T1,value的类型为T2
    unordered_map<T1,T2>   m1{p1,p2……};m1中的元素被初始化为p1,p2……,p1、p2是pair类型
    unordered_map<T1,T2>   m1{{key1,value1},{key2,value2}……};m1中的元素被初始化为 键值对{key1,value1},{key2,value2}……
    unordered_map<T1,T2>   m2(m1);m2中包含和m1一样的元素
    unordered_map<T1,T2>   m2=m1;m2中包含和m1一样的元素

    程序示例:

    pair<string, string> p1("sc0301","小杨");	            // 方式一,创建一个pair名为p1
    pair<string, string> p2 = make_pair("sc0302", "小马");	// 方式二,make_pair函数返回一个用"sc0302"和 "小马"初始化的pair
    pair<string, string> p3("sc0303", "小王");
    pair<string, string> p4("sc0304", "小何");
    
    unordered_map<string, string> m1;                 // 创建一个空unordered_map
    unordered_map<string, string> m2{ p1,p2,p3,p4 };  // 创建一个包含键值对p1、p2、p3、p4的unordered_map
    unordered_map<string, string> m3{ {"sc0301","小杨"},{"sc0302", "小马"},{"sc0303", "小王"},{"sc0304", "小何"} }; // 效果同上一句
    unordered_map<string, string> m4(m2);   // 创建一个unordered_map,m4中包含和m2一样的元素
    unordered_map<string, string> m5 = m2;  // 创建一个unordered_map,m5中包含和m2一样的元素
    

           

    访问元素

    访问元素
    T2 value = m1[key];得到关键字key对应的值value
    m1.at(key);得到关键字key对应的值value
    *iter访问迭代器iter指向的元素
    获取迭代器
    m1.begin();获取指向m1首元素的迭代器
    m1.end();获取指向m1尾元素的后一个位置的迭代器
    m1.rbegin();获取指向m1首元素的前一个位置的迭代器
    m1.rend();获取指向m1尾元素的迭代器
    m1.cbegin(); m1.cend();含义同上,但获取到的是const_iterator
    m1.crbegin(); m1.crend();含义同上,但获取到的是const_iterator

    程序示例:

    string p2_name = m2["sc0302"];	   // 得到学号(关键字)"sc0302"对应的姓名(值)
    string p3_name = m2.at("sc0303");  // 得到学号"sc0303"对应的姓名	      
    
    unordered_map<string, string>::iterator it1 = m2.begin();	 // 得到指向m2首元素的迭代器
    unordered_map<string, string>::iterator it2 = m2.end();    // 得到指向m2尾元素的下一个位置的迭代器
    pair<string, string> p11 = *it1;   // 得到m2的首元素{"sc0301","小杨"}
    string p1_ID = it1->first;         // 得到m2的首元素{"sc0301","小杨"}的fisrt成员
    string p1_name = it1->second;	   // 得到m2的首元素{"sc0301","小杨"}的second成员
    

           

    遍历容器

    1、使用迭代器

    for (auto it_b = m2.begin(), it_e = m2.end(); it_b != it_e;++it_b) {
    	pair<string, string> current = *it_b;
    	cout << "学号:" << it_b->first << "; 姓名:" << it_b->second << endl;
    	// 上面这一句等同于下面这一句
    	cout << "学号:" << current.first << "; 姓名:" << current.second << endl;
    }
    

    2、范围for语句

    for (auto p : m2) {
    	cout << "学号:" << p.first << "; 姓名:" << p.second << endl;
    }
    

           

    添加、修改元素

    m1.insert(p1);在unordered_map中插入已有的pair
    m1.insert({key1,value1});在unordered_map中插入键值对{key1,value1}
    m1.insert(pair<T1, T2> (key1, value1));// 创建一个无名pair对象,并插入到unordered_map中
    m1.insert(make_pair(key1, value1));// 创建一个无名pair对象,并插入到unordered_map中
    m1.insert(unordered_map<T1, T2>::value_type (key1, value1));// 创建一个无名pair对象,并插入到unordered_map中
    m1[key] = value;如果key不存在则插入该键值对,如果key已存在则修改该key对应的value
    m1.emplace(p1);在unordered_map中插入已有的pair
    m1.emplace(pair<T1, T2> (key1, value1));// 创建一个无名pair对象,并插入到unordered_map中

    程序示例:

    m1.insert(p1);	                   // 在unordered_map中插入已有的pair
    m1.insert({ "sc0302", "小马" });   // 插入键值对{ "sc0302", "小马" }
    m1.insert(pair<string, string> ("sc0303", "小王"));  // 创建一个无名pair对象,并插入到unordered_map中	
    m1.insert(make_pair("sc0303", "小王"));              // 要插入的关键字已在容器中,emplace/insert什么都不做
    m1.insert(unordered_map<string, string>::value_type("sc0303", "小王"));   // 要插入的关键字已在容器中,emplace/insert什么都不做
    m1["sc0304"] = "小何";             // 如果key不存在则插入该键值对,如果key已存在则修改该key对应的value。
    
    m1.emplace(p1);			                             // 要插入的关键字已在容器中,emplace/insert什么都不做
    m1.emplace(pair<string, string>("sc0303", "小王"));  // 要插入的关键字已在容器中,emplace/insert什么都不做
    

           

    删除元素

    m1.erase(key)删除关键字为key的元素
    m1.erase(iter);删除迭代器iter指向的元素
    m1.erase(iter1,iter2);删除迭代器iter1和ter2指向的范围中元素
    m1.clear();删除m1中的所有元素

    程序示例:

    m1.erase("sc0301");		  // 删除关键字为"sc0301"的元素
    auto iter = m1.begin();   // 指向m2的首元素的迭代器
    m1.erase(iter);           // 删除迭代器指向的元素
    auto iter1 = m1.begin(), iter2 = m1.end();
    m1.erase(iter1, iter2);   // 删除迭代器iter1、iter2指向的范围中的元素
    m2.clear();               // 删除容器中的全部元素
    

           

    unordered_map的大小

    m1.szie();获得m1的大小
    m1.empty();若m1为空返回值为true,否则返回值为false

    程序示例:

    int s = m3.size();    // 获得m1的大小
    bool e = m3.empty();  // 若m1为空返回值为true,否则返回值为false
    

           

    查找

    m1.find(key)返回一个迭代器,指向第一个关键字为key的元素,若key不在容器中,则返回尾后迭代器
    m1.count(key);返回关键字等于key的元素的数量。对于不允许重复关键字的容器unordered_map,返回的值是0或1

    程序示例:

    unordered_map<string, string>::iterator it = m4.find("sc0301");  // 查找关键字为"sc0301"的元素,返回一个迭代器
    if (it == m4.end()) {         // 若"sc0301"不在容器中,则it等于尾后迭代器
    	cout << "未找到!" << endl;
    }
    else {
    	pair<string, string> result1 = *it;	// 找到了
    }
    
    int result2 = m4.count("sc0305");  // 查找关键字为"sc0301"的元素,返回关键字等于"sc0301"的元素数量
    if (result2==0) {
    	cout << "未找到!" << endl;
    }
    else {
    	cout << "找到了!" << endl;
    }
    
    unordered_map<string, string>::iterator it_up = m4.upper_bound("sc0301");  // 返回一个迭代器,指向第一个关键字大于"sc0301"的元素
    pair<string, string> result3 = *it_up;
    

           

    三、程序示例

    #include <iostream>
    #include <string>
    #include <utility>
    #include <unordered_map>
    
    using namespace std;
    
    int main() {	
    	// 初始化-----------------------------------------------------------------------------------
    	pair<string, string> p1("sc0301","小杨");	            // 方式一,创建一个pair名为p1
    	pair<string, string> p2 = make_pair("sc0302", "小马");	// 方式二,make_pair函数返回一个用"sc0302"和 "小马"初始化的pair
    	pair<string, string> p3("sc0303", "小王");
    	pair<string, string> p4("sc0304", "小何");
    
    	unordered_map<string, string> m1;                 // 创建一个空unordered_map
    	unordered_map<string, string> m2{ p1,p2,p3,p4 };  // 创建一个包含键值对p1、p2、p3、p4的unordered_map
    	unordered_map<string, string> m3{ {"sc0301","小杨"},{"sc0302", "小马"},{"sc0303", "小王"},{"sc0304", "小何"} }; // 效果同上一句
    	unordered_map<string, string> m4(m2);   // 创建一个unordered_map,m4中包含和m2一样的元素
    	unordered_map<string, string> m5 = m2;  // 创建一个unordered_map,m5中包含和m2一样的元素
    
    	// 访问元素-----------------------------------------------------------------------------------
    	string p2_name = m2["sc0302"];	   // 得到学号(关键字)"sc0302"对应的姓名(值)	
    	string p3_name = m2.at("sc0303");  // 得到学号"sc0303"对应的姓名	      
    	
    	unordered_map<string, string>::iterator it1 = m2.begin();	 // 得到指向m2首元素的迭代器
    	unordered_map<string, string>::iterator it2 = m2.end();    // 得到指向m2尾元素的下一个位置的迭代器
    	pair<string, string> p11 = *it1;   // 得到m2的首元素{"sc0301","小杨"}
    	string p1_ID = it1->first;         // 得到m2的首元素{"sc0301","小杨"}的fisrt成员
    	string p1_name = it1->second;	   // 得到m2的首元素{"sc0301","小杨"}的second成员
    
    	// 遍历容器-----------------------------------------------------------------------------------
    	for (auto it_b = m2.begin(), it_e = m2.end(); it_b != it_e;++it_b) {
    		pair<string, string> current = *it_b;
    		cout << "学号:" << it_b->first << "; 姓名:" << it_b->second << endl;
    		// 上面这一句等同于下面这一句
    		cout << "学号:" << current.first << "; 姓名:" << current.second << endl;
    	}
    
    	for (auto p : m2) {
    		cout << "学号:" << p.first << "; 姓名:" << p.second << endl;
    	}
    
    	// 添加、修改元素-----------------------------------------------------------------------------------
    	m1.insert(p1);	                   // 在unordered_map中插入已有的pair
    	m1.insert({ "sc0302", "小马" });   // 插入键值对{ "sc0302", "小马" }
    	m1.insert(pair<string, string> ("sc0303", "小王"));  // 创建一个无名pair对象,并插入到unordered_map中	
    	m1.insert(make_pair("sc0303", "小王"));              // 要插入的关键字已在容器中,emplace/insert什么都不做
    	m1.insert(unordered_map<string, string>::value_type("sc0303", "小王"));   // 要插入的关键字已在容器中,emplace/insert什么都不做
    	m1["sc0304"] = "小何";             // 如果key不存在则插入该键值对,如果key已存在则修改该key对应的value。
    
    	m1.emplace(p1);			                             // 要插入的关键字已在容器中,emplace/insert什么都不做
    	m1.emplace(pair<string, string>("sc0303", "小王"));  // 要插入的关键字已在容器中,emplace/insert什么都不做
    
    	// 删除元素-----------------------------------------------------------------------------------
    	m1.erase("sc0301");		  // 删除关键字为"sc0301"的元素
    	auto iter = m1.begin();   // 指向m2的首元素的迭代器
    	m1.erase(iter);           // 删除迭代器指向的元素
    	auto iter1 = m1.begin(), iter2 = m1.end();
    	m1.erase(iter1, iter2);   // 删除迭代器iter1、iter2指向的范围中的元素
    	m2.clear();               // 删除容器中的全部元素
    
    	// 大小-----------------------------------------------------------------------------------
    	int s = m3.size();    // 获得m1的大小
    	bool e = m3.empty();  // 若m1为空返回值为true,否则返回值为false
    
    	// 查找-----------------------------------------------------------------------------------
    	unordered_map<string, string>::iterator it = m4.find("sc0301");  // 查找关键字为"sc0301"的元素,返回一个迭代器
    	if (it == m4.end()) {         // 若"sc0301"不在容器中,则it等于尾后迭代器
    		cout << "未找到!" << endl;
    	}
    	else {
    		pair<string, string> result1 = *it;	// 找到了
    	}
    
    	int result2 = m4.count("sc0305");  // 查找关键字为"sc0301"的元素,返回关键字等于"sc0301"的元素数量
    	if (result2==0) {
    		cout << "未找到!" << endl;
    	}
    	else {
    		cout << "找到了!" << endl;
    	}
    }
    
    展开全文
  • unordered_map

    2018-10-17 22:16:44
    std::unordered_map() template &lt; class Key, // unordered_map::key_type class T, // unordered_map::mapped_type ...

    std::unordered_map()

    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;

    无序映射是关联容器,其存储由键值和映射值的组合形成的元素,并且允许基于其键快速检索各个元素。

    在unordered_map中,键值通常用于唯一标识元素,而映射值是具有与此键关联的内容的对象。键和映射值的类型可能不同。

    无序映射实现直接访问运算符(operator []),允许使用其键值作为参数直接访问映射值。

    unordered_map容器的迭代器指向此value_type的元素。因此,对于一个名为it的迭代器,它指向一个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>)

    或者可以这样访问它:

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

    构造函数:

    empty (1)
    explicit unordered_map ( size_type n = /* see below */,
                             const hasher& hf = hasher(),
                             const key_equal& eql = key_equal(),
                             const allocator_type& alloc = allocator_type() );
    explicit unordered_map ( const allocator_type& alloc );
    
    range (2)
    template <class InputIterator>
      unordered_map ( InputIterator first, InputIterator last,
                      size_type n = /* see below */,
                      const hasher& hf = hasher(),
                      const key_equal& eql = key_equal(),
                      const allocator_type& alloc = allocator_type() );
    
    copy (3)
    unordered_map ( const unordered_map& ump );
    unordered_map ( const unordered_map& ump, const allocator_type& alloc );
    
    move (4)
    unordered_map ( unordered_map&& ump );
    unordered_map ( unordered_map&& ump, const allocator_type& alloc );
    
    initializer list (5)
    unordered_map ( initializer_list<value_type> il,
                    size_type n = /* see below */,
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& alloc = allocator_type() );

    关于范围构造函数:将 InputIterator迭代器指定范围[ first, last) 内值,作为参数赋给构造函数,函数模板类型可以是任何类型的输入迭代器

    例子:

    #include<iostream>
    #include<unordered_map>
    #include<string>
    
    typedef std::unordered_map<std::string,std::string> stringmap;
    
    stingmap merge(stringmap a, stringmap b)
    {
        stringmap temp(a);temp.insert(b.begin(),b.end());return temp;
    }
    int main()
    {
        stringmap first; //empty
        stringmap second( {{"apple", "red"},{"lemon","yellow"}});
        stringmap third ( {{"orange","orange"},{"strawberry","red"}} );  // init list
        stingmap fourth(second);
        stringmap fifth(merge(third,first));
        sringmap sixth(fifth.begin(),fifth.end());
    
        std::cout << "sixth contains:";
        for (auto& x: sixth) std::cout << " " << x.first << ":" << x.second;
        std::cout << std::endl;
        
        return 0;
    }

    unordered_map::at()

    mapped_type& at ( const key_type& k );
    const mapped_type& at ( const key_type& k ) const;

    返回对unordered_map中带有键k的元素的映射值的引用。 如果k与容器中任何元素的键不匹配,则该函数抛出out_of_range异常。

    例子:

    // unordered_map::at
    #include <iostream>
    #include <string>
    #include <unordered_map>
    
    int main ()
    {
      std::unordered_map<std::string,int> mymap = {
                    { "Mars", 3000},
                    { "Saturn", 60000},
                    { "Jupiter", 70000 } };
    
      mymap.at("Mars") = 3396;
      mymap.at("Saturn") += 272;
      mymap.at("Jupiter") = mymap.at("Saturn") + 9638;
    
      for (auto& x: mymap) {
        std::cout << x.first << ": " << x.second << std::endl;
      }
    
      return 0;
    }

    unordered_map::begin()

    container iterator (1)
          iterator begin() noexcept;
    const_iterator begin() const noexcept;
    
    bucket iterator (2)
          local_iterator begin ( size_type n );
    const_local_iterator begin ( size_type n ) const;

     返回指向unordered_map容器(1)或其中一个存储桶(2)中的第一个元素的迭代器。请注意,unordered_map对象不保证哪个特定元素被视为其第一个元素。但是,在任何情况下,从开始到结束的范围都涵盖容器(或存储桶)中的所有元素,直到无效。

    参数: n --桶号码。这应低于bucket_count。它是一个可选参数,用于更改此成员函数的行为:如果设置,则检索到的迭代器指向存储桶的第一个元素,否则它指向容器的第一个元素。

    返回值:返回指向容器的第一个元素或者桶的第一个元素。

    例子:

    #include <iostream>
    #include <unordered_map>
    int main()
    {
        std::unordered_map<std::string,std::string> mymap;
        mymap={ {""Australia","Canberra"},{"U.S.","Washington"},{"France","Paris"}};
        
        std::cout<<"mymap contains:";
        for(auto it=mymap.begin();it!=mymap.end();it++)
            {std::cout<<" "<<it->first<<" :"<<it->second;
        std::cout<<"mymap's buckets contains:";
        for(unsigned int i=0;i<mymap.bucket_count();i++){
            std::cout<<"bucket #"<<i<<"contains:";
            for(auto loacl_it=mymap.begin(i);it!=mymap.end(i);it++)
                std::cout<<" ”<<local_it->first<< ":"<<local_it->second;
            std::cout<<std::endl;
            }
        return 0;
    } 

    Possible output:

    mymap contains: France:Paris Australia:Canberra U.S.:Washington
    mymap's buckets contain:
    bucket #0 contains:
    bucket #1 contains:
    bucket #2 contains:
    bucket #3 contains:
    bucket #4 contains:
    bucket #5 contains: France:Paris
    bucket #6 contains:
    bucket #7 contains: Australia:Canberra
    bucket #8 contains: U.S.:Washington
    bucket #9 contains:
    bucket #10 contains:
    展开全文
  • 如果要在c++ 中使用这mapunordered_map 两个函数,需要分别引入下面的两个头文件 #include<map> #include<unordered_map> unordered_map 容器,直译过来就是"无序 map 容器"的意思。所谓“无序”,...
  • C++:map、hash_mapunordered_map

    千次阅读 2019-07-10 20:39:12
    另外也了解到还有C++11的unordered_map,所以这里一并介绍三个了。用法就不介绍了,主要介绍区别。 1. 三者的区别 map底层是用红黑树实现的,空间复杂度为O(n),是随着节点的增加才增加,而查找的时间时间复杂度...
  • C++ std::unordered_map

    2021-02-14 19:01:25
    unordered_map底层基于哈希表实现,拥有快速检索的功能。 unordered_map是STL中的一种关联容器。容器中元素element成对出现(std::pair),element.first是该元素的键-key,容器element.second是该元素的键的值-...
  • unordered_map详细介绍

    万次阅读 多人点赞 2019-07-21 15:50:21
    转载自关联容器:unordered_map详细介绍(附可运行代码) 介绍 1 特性 2 Hashtable和bucket 模版 1 迭代器 功能函数 1 构造函数 12示例代码 2 容量操作 21 size 22 empty 3 元素操作 31 find 32 ...
  • C++ STL unordered_map用法

    2020-08-19 12:10:19
    C++ STL unordered_map用法 在C++11中,unordered_map作为一种关联容器,替代了hash_mapunordered_map的底层实现是hash表,所以被称为无序关联容器。 不管是map还是unordered_map都是一种 key-map(value) 映射的...
  • 4.map问题+unordered_map问题 4.1 map 4.1.1 map的使用 4.1.2 构造map 4.1.3 往map中插入元素 4.1.4 在map中查找元素 4.1.5 删除与清空map中元素 4.1.6 查看map大小 4.1.7 map的基础操作函数总结 4.2...
  • unordered_map 简介2. unordered_map 使用3. unordered_multimap 简介4. unordered_multimap 使用 1. unordered_map 简介 unordered_map类基本功能与 STL map相似,都是存储的key-value的键值对,并且key值唯一,...
  • C++ mapunordered_map详解 官方文档链接 概述  C++中mapunordered_map提供的是一种键值对容器,在实际开发中会经常用到,它跟Python的字典很类似,所有的数据都是成对出现的,每一对中的第一个值称之为关键字...
  • 3.unordered_map 4.unordered_multimap map map特点 1.map支持下标访问符,即在[]中放入key,就可以找到与key对应的value 2.map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树) 3.键的值相同的...
  • unordered_map需要头文件#include <unordered_map> unordered_set需要头文件#include <unordered_set> 二者都是基于哈希实现的,无序,因此增删改查的时间复杂度是 O(1),比map和set快,它们是基于平衡...
  • map是STL里重要容器之一。 它的特性总结来讲就是:所有元素都会根据元素的键值key自动排序(也可根据自定义的仿函数进行自定义排序),其中的每个元素都是<key,value>的键值对,map中不允许有键值相同的元素...
  • unordered_map 简介

    2021-03-11 14:10:57
    在使用unordered_map时,需要引入头文件: #include < unordered_map > 内部实现 unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到...
  • C++ unordered_map

    2020-07-30 12:22:36
    转载自这里 目录 ...unordered_map是C++11正式加入的对hash_map的官方实现(之前标准C++没有hash_map的官方实现,我们使用的STL的hash_map并不是官方的)。从名字可以看出这个结构是无序的,底..
  • unordered_map 无序map容器,正常map容器是有序的会自动执行排序功能,由于 unordered_map 容器底层采用的是哈希表存储结构,该结构本身不具有对数据的排序功能,所以此容器内部不会自行对存储的键值对进行排序。...
  • unordered_map 位于头文件<unordered_map> unordered_map的定义 template< class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator ...
  • https://www.jianshu.com/p/56bb01df8ac7 unordered_map 使用 头文件: #include <unordered_map> 取得键和值: unordered_map<Key,T>::iterator it; it->first; // same as (*it).first ...
  • 多说不练假把戏,下面以一个例子进行说明:(在ordered_map中添加已经有的数据类型比较简单,Hash_Fun和Equal_to比较函数都可以缺省,所以不再多说,下面向unordered_map中添加自己定义的数据类型) 简单实例:有...
  • C++11 unordered_map详细介绍

    千次阅读 多人点赞 2020-02-18 21:14:13
    目录:1.介绍1.1 特性2. 模版2.1 迭代器3. 功能函数3.1 构造函数3.2 容量操作3.2.1 size3.2.2 empty3.3 元素操作3.3.1 find3.3.2 insert...C++11 unordered_map详细介绍 1.介绍 最近使用到一个c++的容器——unorde...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,631
精华内容 28,252
关键字:

unordered_map