精华内容
下载资源
问答
  • unordered_set unordered_multiset unordered_map unordered_multimap 特性 unordered_set/unordered_multiset性质和set/multiset一样,只是不支持lower_bound()操作,但是它的erase(), []的时间复杂度为O(1),即不...

    unordered_set unordered_multiset unordered_map unordered_multimap

    特性
    unordered_set/unordered_multiset性质和set/multiset一样,只是不支持lower_bound()操作,但是它的erase(), []的时间复杂度为O(1),即不能实现查找操作,但是增删改减的时间复杂度降低
    unorered_map/unordered_multimap也是类似,同上

    展开全文
  • 最近做编程题发现关联容器忘得多,翻翻...unordered_set unordered_map 具体成员函数API调用代码 priority_queue push_heap pop_heap sort_heap 参考: 基本概念 map multi_map map是标准的关联式容器,一个...

    最近做编程题发现关联容器忘得多,翻翻以前写的代码,mark一下,勉励自己

    目录

    基本概念

    map  multi_map

    unordered_set  unordered_map

    具体成员函数API调用代码

    priority_queue 

    push_heap pop_heap sort_heap  

    参考:



    基本概念

    map  multi_map

    • map是标准的关联式容器,一个map是一个键值对序列,即(key,value)对。它提供基于key的快速检索能力。
    • map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入,所以不能指定插入位置。
    • map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
    • map可以直接存取key所对应的value,支持[]操作符,如map[key]=value。
    • multimap与map的区别:map支持唯一键值,每个键只能出现一次;而multimap中相同键可以出现多次。multimap不支持[]操作符。

    unordered_set  unordered_map

    无序容器   使用hash函数和==运算
    桶管理:将具有相同hash值的元素保存在同一个桶中。无序容器的性能依赖于hash函数的性质和桶的大小和数量
    成员函数和map set差不多,关于有序的函数没有,多了桶管理函数

    具体成员函数API调用代码

    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<map>
    #include<unordered_set>
    #include<unordered_map>
    #include<functional>
    
    using namespace std;
    
    
    //定义关联容器
    void countre_init()
    {
    	vector<int>v = { 1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1 };
    	set<int>s(v.begin(), v.end());//不允许重复
    	multiset<int>multi_s(v.begin(), v.end());
    	//列表初始化
    	map < string, string >m = { {"zhangsan", "wangbadan"}, { "lisi","wangjiudan" }, { "zhangsan", "wangbadan" } };
    	multimap < string, string >multi_m = { { "zhangsan", "wangbadan" },{ "lisi","wangjiudan" },{ "zhangsan", "wangbadan" } };
    
    	cout << v.size() << " " << s.size() << " " << multi_s.size() << endl;
    	cout << m.size() << " " << multi_m.size() << endl;
    }
    //使用关键字类型的比较函数 自定义<
    bool compare(int a, int b)
    {return a < b ?  false:true;}//从大到小
    
    //仿函数::又叫函数对象,一种行为类似函数的对象。调用者可以向函数一样使用该对象。
    //实现:用户只需要实现一种新的类型,在类中进行重载(),参数根据用户索要进行的操作选择匹配
    class Greater//或struct
    {
    public:
    	bool operator()(const string str1, const string str2)
    	{
    		return str1.size() < str2.size() ? true : false;
    	}
    };
    void key_function()
    {
    	//set map 等有序集合 实现排序的时 默认使用<比较两个关键字
    	//自定义的操作类型在尖括号里紧跟元素类型
    	set<int, decltype(compare)*>s(compare);//必须指明指针类型  decltype推断函数类型
    	map<int, int,decltype(compare)*>m(compare);
    	for (int i = 0; i < 10; i++)
    	{
    		s.insert(i);
    		m.insert(make_pair(i+5, i));
    	}
    	for (auto c : s)
    		cout << c << " ";
    	cout << endl;
    
    	auto map_it = m.begin();
    	while (map_it != m.end())
    	{
    		cout << map_it->first << " " << map_it->second << endl;
    		map_it++;
    	}
    
    	//实现倒序  谓词  greater #include<functional>
    	//set<int,less<int> >  setIntA;  //该容器是按升序方式排列元素。
    	//set<int, greater<int>> setIntB;   //该容器是按降序方式排列元素。
    	set<string, greater<string>>s2 = { "zhangsan","lisi","wangwu","maliu","luqi","wangba" };
    	for (auto c : s2)
    		cout << c << " " << endl;
    	//实现倒序 仿函数
    	set<string, Greater>s3 = { "zhangsan","lisi","wangwu","maliu","luqi","wangba" };
    	for (auto c : s3)
    		cout << c << " " << endl;
    	
    }
    
    void pair_make()
    {
    	//pair类型 用于生成特定类型的模板,两个public成员first second  make_pair()函数 ==  !=等操作
    	//key_type (关键字类型)  mapped_type(值类型,只适用于map)  value_type(对于set为键值类型,map为pair类型) 
    	//每个pair的关键字key为const不可改变,但是value可以改变  set只有key值所以不可变
    	//采用作用域访问
    
     	pair<string, int>author("zhangsan", 33);
    	cout << author.first << author.second << endl;
    	author.second = 44;//合法 author.first = "lisi"  违法
    	set<int>s = { 1,2,3 };
    	set<int>::iterator it = s.begin();
    	cout << *it << endl;// *it = 2;//违法  只读
    	pair<string, int>t = make_pair("zhangsan", 44);//make_pair()函数
    	
    	vector<pair<string, int>>v;
    	vector<string>v2 = { "zhangsan","lisi","wangmazi" };
    	for(int i = 0;i<10;i++)
    		v.push_back(make_pair(v2[i%3], i + 30));
    	for (auto c : v)
    		cout << c.first << " " << c.second << endl;
    }
    
    //插入insert 删除erase
    void insert_function()
    {
    	vector<int>v = { 1,2,3,4,5,6,7,4,6,78,2,5 };
    	set<int>s;
    	s.insert(v.begin(), v.end());
    	s.insert(0);
    	for (auto c : s)
    		cout << c << " ";
    	cout << endl;
    	cout<<s.erase(5)<<endl;//erase(key)删除键值为key的元素,返回删除元素的个数,set01 multi 多个
    	cout << *(s.erase(s.begin())) << endl;//删除迭代器所指的元素,返回下一个迭代器
    	s.erase(++s.begin(), --s.end());//范围删除,+ - 不支持
    	for (auto c : s)
    		cout << c << " ";
    	cout << endl;
    	s.insert(v.begin() + 3, v.end() - 1);
    
    	map<string, int>m;
    	m.insert({ "zhangsan",22 });//最简单,常用花括号和make_pair()
    	m.insert(make_pair("lisi", 33));
    	m.insert(pair<string, int>("wangwu", 44));
    	m.insert(map<string, int>::value_type("maliu", 55));
    	//insert返回值w为pair(iterator,bool)iterator指向待插入元素的位置,bool表示插入是否成功,成功则true
        //对于map 和set返回pair 对于multimap和multiset插入总是成功,返回iterator
    	auto ret1 = s.insert(0);
    	if (ret1.second == false)
    		cout << "插入0失败" << endl;
    	auto ret2 = m.insert({ "zhangsan",22 });
    	if (ret2.second == false)
    		ret2.first->second += 11;
    	cout << ret2.first->first << " " << ret2.first->second << endl;//ret2.first指向待插入(重复)迭代器
    	//对于multi返回迭代器
    	multimap<string, int>m2 = { {"zhangsan",22} };
       auto it = m2.insert({ "zhangsan", 33 });
       m2.insert({ "lisi",44 });
       cout << it->first << " " << it->second << endl;
       cout << m2.erase("lisi") << endl;//返回1个
    
       //map的下标操作 set 和multiset multimap不存在下表操作,不存在值或者值不唯一
       //[]先检查有没有,没有则创建,有则返回value_type 与迭代器不同,迭代器解引用返回pair类型
       map<string, int>m3;//一个空map
       m3["zhangsan"] = 44;//1)首先查找"zhangsan",没找到 2) 插入关键字zhangsan 值默认为0  3)将4赋值给zhangsan 
       m3.at("zhangsan") = 55;//先查找,没有则抛出异常out_of_ranage否则返回value_type
    
       //访问元素
       cout<<*(s.find(1))<<endl;//返回一个迭代器,找不到返回s.end();
       cout << s.count(2) << endl;//返回一个数,key=2的个数
       //只有有序容器中可用
       cout << *s.lower_bound(3) << endl;//返回第一个不小于3的迭代器
       cout << *s.upper_bound(3) << endl;//返回第一个大于3的迭代器
       //multiset 和 multimap中查找,相同的key保存在相邻的位置
       cout << endl << endl << endl;
       auto it3 = m2.find("zhangsan");
       int count = m2.count("zhangsan");
       while (count)
       {
    	   cout << it3->first << " " << it3->second << endl;
    	   count--;
    	   it3++;
       }
       //upper_bound("zhangsan")找到则返回zhangsan下一个位置(尾后),未找到则返回一个可以插入zhangsan的位置
       //不影响序列有序,可能zhangsan最大,找到end==m2.end() 也可能没找到  同时最大end == m2.end(),所以
       //不能根据其返回值判断是否找到,但是返回一个范围,可以输出
    
       for (auto beg = m2.lower_bound("zhangsan"), end = m2.upper_bound("zhangsan"); beg != end; beg++)
    	   cout << beg->first << " " << beg->second << endl;
    
       //equal_ranage找到则返回pair(iterator1,iterator2);iterator1指向第一个,iterator2指向最后一个的尾后
       //如果没有找到则同时指向一个可以插入的位置
       for(auto pos = m2.equal_range("zhangsan"); pos.first!= pos.second; pos.first++)
    	  cout << pos.first->first << " " << pos.first->second << endl;
    }
    
    //无序容器   使用hash函数和==运算
    // 桶管理:将具有相同hash值的元素保存在同一个桶中。无序容器的性能依赖于hash函数的性质和桶的大小和数量
    //成员函数和map set差不多,关于有序的函数没有,多了桶管理函数
    
    void unordered_container()
    {
    	unordered_map<string, int>un_m = { {"ccc",3}, {"aaa",1},{"bbb",2 } };
    	un_m.insert({ "ddd",4 });
    	for (auto pos: un_m)
    	{
    		cout << pos.first << " " << pos.second << endl;
    	}
    	un_m.erase("ccc");
    	for (auto pos : un_m)
    	{
    		cout << pos.first << " " << pos.second << endl;
    	}
    	auto it = un_m.find("aaa");
    	cout << it->first << " " << it->second << endl;
    	cout << un_m.count("ddd") << endl;
    
    	//桶管理函数:允许我们查看桶的状态,必要时进行重组
    	cout<<un_m.bucket_count()<<endl;//正在使用的桶数量
    	cout << un_m.max_bucket_count()<<endl;//容器最多能容纳的桶的数量
    	cout << un_m.bucket_size(2) << endl;//第2个桶有几个元素
    	cout << un_m.bucket("ddd") << endl;//关键字为"ddd"在哪个桶里
    	cout << un_m.load_factor() << endl;//平均每个桶有几个元素
    
    
    }
    
    
    int main()
    {
    	
    	countre_init();
    	key_function();
    	pair_make();
    	insert_function();
    	unordered_container();
    	//调用函数对象,创建一个函数对象,调用它
    	Greater a;
    	cout<<a("zhangsan", "lisi")<<endl;
    	return 0;
    }
    

     


    priority_queue:

        //使用方法 priority(Type,Conteiner,Function)
        //std::priority_queue<T, std::vector<T>, greater<T>> pq;
        //不加后面两个参数的话默认为 container 默认为vector function默认为less  大顶堆 
        //小顶堆 基本类型 priority_queue<int, vector<int>, greater<int> >q3;
        //自定义型 则重载< 
        //函数greater在<functional>

     push_heap pop_heap sort_heap

        将[begin, end)范围进行堆排序,默认使用less<int>, 即最大元素放在第一个。
        make_heap(v.begin(), v.end());

        //将begin移动到end的前部,同时将剩下的元素堆排序为一个新的heap
        //配合vector的pop_back进行出堆操作
        pop_heap(v.begin(), v.end());  v.pop_back();

        //刚插入的(尾部)元素做堆排序
        v.push_back(100);  push_heap(v.begin(), v.end());

       //将一个堆做排序,最终成为一个有序的系列,可以看到sort_heap时,必须先是一个堆
        //(两个特性:1、最大元素在第一个 2、添加或者删除元素以对数时间),因此必须先做一次make_heap.
        sort_heap(v.begin(), v.end());

    push_heap pop_heap sort_heap的基本操作:

    void heap_opt()
    {
    	//include<algorithm> "functional"
    	int myints[] = { 10,20,30,5,15 };
    	vector<int> v(myints, myints + 5);
    	vector<int>::iterator it;
    
    	//将[begin, end)范围进行堆排序,默认使用less<int>, 即最大元素放在第一个。
    	make_heap(v.begin(), v.end());
    	cout << "初始堆堆顶 : " << v.front() << endl;
    
    	//将begin移动到end的前部,同时将剩下的元素堆排序为一个新的heap
    	//配合vector的pop_back进行出堆操作
    	pop_heap(v.begin(), v.end()); v.pop_back();
    	cout << "max heap after pop : " << v.front() << endl;
    
    	//刚插入的(尾部)元素做堆排序
    	v.push_back(100); push_heap(v.begin(), v.end());
    	cout << "max heap after push: " << v.front() << endl;
    
    	//将一个堆做排序,最终成为一个有序的系列,可以看到sort_heap时,必须先是一个堆
    	//(两个特性:1、最大元素在第一个 2、添加或者删除元素以对数时间),因此必须先做一次make_heap.
    	sort_heap(v.begin(), v.end());
    
    	cout << "最终堆顺序:";
    	for (unsigned i = 0; i<v.size(); i++) cout << " " << v[i];
    	cout << endl;
    }
    

    priority_queue的基本操作:

    void priority_queue_opt()
    {
    	//使用方法 priority(Type,Conteiner,Function)
    	//std::priority_queue<T, std::vector<T>, greater<T>> pq;
    	//不加后面两个参数的话默认为 container 默认为vector function默认为less  大顶堆 
    	//小顶堆 基本类型 priority_queue<int, vector<int>, greater<int> >q3;
    	//自定义型 则重载< 
    	//函数greater在<functional>
    	priority_queue<int> q1;
    	//默认是最大值优先队列 q1等价于q2
    	priority_queue<int, vector<int>, less<int>>q2;
    	priority_queue<int, vector<int>, greater<int> >q3;
    
    	q2.push(1);
    	q2.push(3);
    	q2.push(4);
    	q2.push(6);
    	cout << "q2.size" << q2.size() << endl;
    	while (!q2.empty())
    	{
    		cout << q2.top() << ' ';
    		q2.pop();
    	}
    	cout << endl;
    	q3.push(6);
    	q3.push(3);
    	q3.push(2);
    	q3.push(1);
    	while (!q3.empty())
    	{
    		cout << q3.top() << ' ';
    		q3.pop();
    	}
    	cout << endl;
    
    }

    利用大顶堆小顶堆进行取中位数:

    class MidNum {
    public:
    	void Insert(int num)
    	{
    		if (((min.size() + max.size()) & 1) == 0)//目前总共偶数个数字
    		{
    			if (max.size()>0 && num<max[0])//偶数个应该放在最小堆,但是数字比大顶堆最大值小
    			{
    				//vector.push_back  push_back() 数字进堆
    				//调整,先进大顶堆,将大顶堆最大放入最小堆保持元素差1
    				max.push_back(num);
    				//将front移动到end的前部,同时将剩下的元素重新构造成(堆排序)一个新的heap
    				push_heap(max.begin(), max.end(), less<int>());
    
    				num = max[0];
    
    				//pop_heap  vector.pop_back数字出堆
    				//将[first, last)范围进行堆排序,默认使用less<int>, 即最大元素放在第一个。
    				pop_heap(max.begin(), max.end(), less<int>());
    				max.pop_back();
    			}
    			min.push_back(num);
    			push_heap(min.begin(), min.end(), greater<int>());
    		}
    		else
    		{
    			if (min.size()>0 && min[0]<num)//本来要插入大顶堆,结果num小顶堆最小值小
    			{
    				min.push_back(num);
    				push_heap(min.begin(), min.end(), greater<int>());
    
    				num = min[0];
    
    				pop_heap(min.begin(), min.end(), greater<int>());
    				min.pop_back();
    			}
    			max.push_back(num);
    			push_heap(max.begin(), max.end(), less<int>());
    		}
    	}

    main测试函数

    int main()
    {
    
    	srand(time(0));
    	heap_opt();
    	priority_queue_opt();
    	MidNum m;
    	for (int i = 1; i < 10; ++i)
    		m.Insert(rand() % 100);
    	cout << m.GetMedian();
    	return 0;
    }

    结果:

     

    参考:

    primer

    C++Reference

    剑指offer 

    展开全文
  • map hash_map unordered_map 性能测试 2012-01-08 22:27:29 分类: C/C++ by zieckey 测试条件: gcc version 4.2.1 20070719 [FreeBSD] FreeBSD 7.2-RELEASE #0: Fri May 1 07:18:07 ...
    
    

    分类: C/C++

    by zieckey

    测试条件:
    gcc version 4.2.1 20070719  [FreeBSD]
    FreeBSD  7.2-RELEASE #0: Fri May  1 07:18:07 UTC 2009     root@driscoll.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC  amd64
    Intel(R) Xeon(R) CPU           E5620  @ 2.40GHz 16核

    测试程序说明:
    先准备好n个字符串随机的MD5字符串做为key,然后分别对3个容器进行插入、遍历、查找、删除操作。
    例如,n=100的时候,插入是指插入100个随机MD5 key;遍历是指对容器遍历一次;查找是指分别对这个100个随机的MD5 key做查找操作(即查找100次);删除是指挨个删除这个100个随机MD5 key。

    测试数据如下表:

    插入,单位us 100 1K 10K 100K 1M 10M
    std::map 241 2833 35888 381214 4439088 62233380
    std::ext/hash_map 97 1667 16466 146025 1788446 18512639
    std::tr1::unordered_map 77 772 8052 53094 658312 7429297


    遍历,单位us 100 1K 10K 100K 1M 10M
    std::map 11 76 842 11603 155700 1771906
    std::ext/hash_map 47 430 4218 39880 470344 4781575
    std::tr1::unordered_map 1 1 2 1 2 1

    查找,单位us 100 1K 10K 100K 1M 10M
    std::map 156 2111 30456 258709 4100260 59064394
    std::ext/hash_map 77 774 8056 56974 660231 7705527
    std::tr1::unordered_map 77 772 8051 54456 659537 7600263

    删除,单位us 100 1K 10K 100K 1M 10M
    std::map 291 3641 49584 472414 6675897 92491113
    std::ext/hash_map 89 869 9068 86524 964767 10372650
    std::tr1::unordered_map 49 480 4879 33087 395098 4369617

    结论:
    1. std::tr1::unordered_map 与 std::ext/hash_map 
         任何情况下,如果要在这两个容器之间选择的话,我们毫不犹豫应该选择 unordered_map。因为他的性能在上述4中操作中均优于 hash_map,甚至可以说远远优于 hash_map。

    2. std::tr1::unordered_map 与 std::map 
         map的性能总体来说是最差的。但是,当我们需要一个有序的关联容器的时候,我们必须选择std::map,因为 unordered_map 内部元素不是有序的,这一点从名字都可以看出来。除此之外都应该选择 unordered_map 。

    3. 上述测试中,unordered_map 的遍历性能几乎是常数级别的,与常识不太相符,需要再研究研究。

    附录:贴上源代码
    说明:与测试程序稍有区别,这里的源码里没有MD5相关的代码以确保其他人能比较方便的直接拿去编译运行。

    如有错误还请跟帖指出,非常感谢。


    1. #include <iostream>
    2. #include <string>
    3. #include <sstream>
    4. #include <list>
    5. #include <map>
    6. #include <sys/time.h>
    7. #include <ext/hash_map>
    8. #include <tr1/unordered_map>

    9. namespace zl
    10. { //{{{
    11.     struct equal_to
    12.     {
    13.         bool operator()(const char* s1, const char* s2) const
    14.         {
    15.             return strcmp(s1, s2) == 0;
    16.         }
    17.     };
    18.  
    19.     struct hash_string
    20.         : public std::unary_function<std::string, std::size_t>
    21.         {
    22.             std::size_t
    23.                 operator()(const std::string& __s) const
    24. #ifdef __linux__
    25.                 { return std::tr1::Fnv_hash<>::hash(__s.data(), __s.length()); }
    26. #else
    27.                 { return std::tr1::_Fnv_hash<>::hash(__s.data(), __s.length()); }
    28. #endif
    29.         };

    30.     
    31.     struct hash_charptr
    32.         : public std::unary_function<const char*, std::size_t>
    33.         {
    34.             std::size_t
    35.                 operator()(const char* __s) const
    36. #ifdef __linux__
    37.                 { return std::tr1::Fnv_hash<>::hash(__s, strlen(__s)); }
    38. #else
    39.                 { return std::tr1::_Fnv_hash<>::hash(__s, strlen(__s)); }
    40. #endif
    41.         };
    42. }//}}}

    43. typedef std::list<std::string> string_list;
    44. typedef std::map<std::string, int> string_map;
    45. typedef __gnu_cxx::hash_map<std::string, int, zl::hash_string> string_hash_map;
    46. typedef std::tr1::unordered_map<std::string, int> string_unordered_map;

    47. void fill_list(string_list& slist, size_t count);
    48. uint64_t current_usec();

    49. int main( int argc, char* argv[] )
    50. {
    51.     if (argc != 2 && argc != 3)
    52.     {
    53.         fprintf(stderr, "Usage:%s test_count rehash\n", argv[0]);
    54.         fprintf(stderr, "For example:%s 10000 rehash\n", argv[0]);
    55.         return -1;
    56.     }

    57.     size_t count = atoi(argv[1]);
    58.     bool rehash = false;
    59.     if (argc == 3)
    60.     {
    61.         rehash = true;
    62.     }

    63.     string_map smap;
    64.     string_hash_map shash_map;
    65.     string_unordered_map sunordered_map;

    66.     if (rehash)
    67.     {
    68.         sunordered_map.rehash(count);
    69.     }

    70.     string_list slist;
    71.     fill_list(slist, count);

    72.     uint64_t start = 0;
    73.     uint64_t end = 0;

    74.     uint64_t map_insert_us = 0;
    75.     uint64_t hash_map_insert_us = 0;
    76.     uint64_t unordered_map_insert_us = 0;

    77.     uint64_t map_traverse_us = 0;
    78.     uint64_t hash_map_traverse_us = 0;
    79.     uint64_t unordered_map_traverse_us = 0;

    80.     uint64_t map_find_us = 0;
    81.     uint64_t hash_map_find_us = 0;
    82.     uint64_t unordered_map_find_us = 0;

    83.     uint64_t map_delete_us = 0;
    84.     uint64_t hash_map_delete_us = 0;
    85.     uint64_t unordered_map_delete_us = 0;



    86.     // Insert test
    87.     {//{{{
    88.         string_list::iterator it(slist.begin());
    89.         string_list::iterator ite(slist.end());

    90.         //map insert
    91.         start = current_usec();
    92.         for (int i = 0; it != ite; ++it, ++i)
    93.         {
    94.             smap[*it] = i;
    95.         }
    96.         end = current_usec();
    97.         map_insert_us = end - start;

    98.         //hash_map insert
    99.         it = slist.begin();
    100.         start = current_usec();
    101.         for (int i = 0; it != ite; ++it, ++i)
    102.         {
    103.             shash_map[*it] = i;
    104.         }
    105.         end = current_usec();
    106.         hash_map_insert_us = end - start;

    107.         //unordered_map insert
    108.         it = slist.begin();
    109.         start = current_usec();
    110.         for (int i = 0; it != ite; ++it, ++i)
    111.         {
    112.             shash_map[*it] = i;
    113.         }
    114.         end = current_usec();
    115.         unordered_map_insert_us = end - start;
    116.     }//}}}

    117.     // Traverse test
    118.     {//{{{
    119.         //map traverse 
    120.         {
    121.             string_map::iterator it(smap.begin());
    122.             string_map::iterator ite(smap.end());
    123.             start = current_usec();
    124.             for (int i = 0; it != ite; ++it)
    125.             {
    126.                 i++;
    127.             }
    128.             end = current_usec();
    129.             map_traverse_us = end - start;
    130.         }

    131.         //hash_map traverse 
    132.         {
    133.             string_hash_map::iterator it(shash_map.begin());
    134.             string_hash_map::iterator ite(shash_map.end());
    135.             start = current_usec();
    136.             for (int i = 0; it != ite; ++it)
    137.             {
    138.                 i++;
    139.             }
    140.             end = current_usec();
    141.             hash_map_traverse_us = end - start;
    142.         }

    143.         //unordered_map traverse 
    144.         {
    145.             string_unordered_map::iterator it(sunordered_map.begin());
    146.             string_unordered_map::iterator ite(sunordered_map.end());
    147.             start = current_usec();
    148.             for (int i = 0; it != ite; ++it)
    149.             {
    150.                 i++;
    151.             }
    152.             end = current_usec();
    153.             unordered_map_traverse_us = end - start;
    154.         }
    155.     }//}}}

    156.     // Find test
    157.     {//{{{
    158.         string_list::iterator it(slist.begin());
    159.         string_list::iterator ite(slist.end());

    160.         //map find
    161.         start = current_usec();
    162.         for (int i = 0; it != ite; ++it, ++i)
    163.         {
    164.             smap[*it] = i;
    165.         }
    166.         end = current_usec();
    167.         map_find_us = end - start;

    168.         //hash_map find
    169.         it = slist.begin();
    170.         start = current_usec();
    171.         for (int i = 0; it != ite; ++it, ++i)
    172.         {
    173.             shash_map[*it] = i;
    174.         }
    175.         end = current_usec();
    176.         hash_map_find_us = end - start;

    177.         //unordered_map find
    178.         it = slist.begin();
    179.         start = current_usec();
    180.         for (int i = 0; it != ite; ++it, ++i)
    181.         {
    182.             shash_map[*it] = i;
    183.         }
    184.         end = current_usec();
    185.         unordered_map_find_us = end - start;
    186.     }//}}}

    187.     // Delete test
    188.     {//{{{
    189.         string_list::iterator it(slist.begin());
    190.         string_list::iterator ite(slist.end());

    191.         //map delete
    192.         start = current_usec();
    193.         for (int i = 0; it != ite; ++it, ++i)
    194.         {
    195.             smap.erase(*it);
    196.         }
    197.         end = current_usec();
    198.         map_delete_us = end - start;

    199.         //hash_map delete
    200.         it = slist.begin();
    201.         start = current_usec();
    202.         for (int i = 0; it != ite; ++it, ++i)
    203.         {
    204.             shash_map.erase(*it);
    205.         }
    206.         end = current_usec();
    207.         hash_map_delete_us = end - start;

    208.         //unordered_map delete
    209.         it = slist.begin();
    210.         start = current_usec();
    211.         for (int i = 0; it != ite; ++it, ++i)
    212.         {
    213.             shash_map.erase(*it);
    214.         }
    215.         end = current_usec();
    216.         unordered_map_delete_us = end - start;
    217.     }//}}}

    218.     //stat output
    219.     std::cout << " insert, count " << count << std::endl;
    220.     std::cout << " std::map " << map_insert_us << " us\n";
    221.     std::cout << " std::ext/hash_map " << hash_map_insert_us << " us\n";
    222.     std::cout << "std::tr1::unordered_map " << unordered_map_insert_us << " us\n";

    223.     std::cout << "\n";
    224.     std::cout << " traverse, count " << count << std::endl;
    225.     std::cout << " std::map " << map_traverse_us << " us\n";
    226.     std::cout << " std::ext/hash_map " << hash_map_traverse_us << " us\n";
    227.     std::cout << "std::tr1::unordered_map " << unordered_map_traverse_us << " us\n";

    228.     std::cout << "\n";
    229.     std::cout << " find, count " << count << std::endl;
    230.     std::cout << " std::map " << map_find_us << " us\n";
    231.     std::cout << " std::ext/hash_map " << hash_map_find_us << " us\n";
    232.     std::cout << "std::tr1::unordered_map " << unordered_map_find_us << " us\n";

    233.     std::cout << "\n";
    234.     std::cout << " delete, count " << count << std::endl;
    235.     std::cout << " std::map " << map_delete_us << " us\n";
    236.     std::cout << " std::ext/hash_map " << hash_map_delete_us << " us\n";
    237.     std::cout << "std::tr1::unordered_map " << unordered_map_delete_us << " us\n";

    238.      
    239.     return 0;
    240. }

    241. void fill_list(string_list& slist, size_t count)
    242. {
    243.     for (size_t i = 0; i < count; ++i)
    244.     {
    245.         std::ostringstream oss;
    246.         oss << i;
    247.         //slist.push_back(MD5::getHexMD5(oss.str().c_str(), oss.str().length()));
    248.         slist.push_back(oss.str());
    249.     }
    250. }


    251. uint64_t current_usec()
    252. {
    253.     struct timeval tv;
    254.     gettimeofday( &tv, NULL );
    255.     return tv.tv_sec * 1000 * 1000 + tv.tv_usec;
    256. }
    展开全文
  • c++ map hash_map unordered_map 比较

    千次阅读 2012-12-27 10:27:08
    map hash_map unordered_map 性能测试  by zieckey 测试条件: gcc version 4.2.1 20070719 [FreeBSD] FreeBSD 7.2-RELEASE #0: Fri May 1 07:18:07 UTC 2009 root@driscoll.cse....
    map hash_map unordered_map 性能测试 

    by zieckey


    测试条件:
    gcc version 4.2.1 20070719  [FreeBSD]
    FreeBSD  7.2-RELEASE #0: Fri May  1 07:18:07 UTC 2009     root@driscoll.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC  amd64
    Intel(R) Xeon(R) CPU           E5620  @ 2.40GHz 16核

    测试程序说明:
    先准备好n个字符串随机的MD5字符串做为key,然后分别对3个容器进行插入、遍历、查找、删除操作。
    例如,n=100的时候,插入是指插入100个随机MD5 key;遍历是指对容器遍历一次;查找是指分别对这个100个随机的MD5 key做查找操作(即查找100次);删除是指挨个删除这个100个随机MD5 key。

    测试数据如下表:

    插入,单位us 100 1K 10K 100K 1M 10M
    std::map 241 2833 35888 381214 4439088 62233380
    std::ext/hash_map 97 1667 16466 146025 1788446 18512639
    std::tr1::unordered_map 77 772 8052 53094 658312 7429297


    遍历,单位us 100 1K 10K 100K 1M 10M
    std::map 11 76 842 11603 155700 1771906
    std::ext/hash_map 47 430 4218 39880 470344 4781575
    std::tr1::unordered_map 1 1 2 1 2 1

    查找,单位us 100 1K 10K 100K 1M 10M
    std::map 156 2111 30456 258709 4100260 59064394
    std::ext/hash_map 77 774 8056 56974 660231 7705527
    std::tr1::unordered_map 77 772 8051 54456 659537 7600263

    删除,单位us 100 1K 10K 100K 1M 10M
    std::map 291 3641 49584 472414 6675897 92491113
    std::ext/hash_map 89 869 9068 86524 964767 10372650
    std::tr1::unordered_map 49 480 4879 33087 395098 4369617

    结论:
    1. std::tr1::unordered_map 与 std::ext/hash_map 
         任何情况下,如果要在这两个容器之间选择的话,我们毫不犹豫应该选择 unordered_map。因为他的性能在上述4中操作中均优于 hash_map,甚至可以说远远优于 hash_map。

    2. std::tr1::unordered_map 与 std::map 
         map的性能总体来说是最差的。但是,当我们需要一个有序的关联容器的时候,我们必须选择std::map,因为 unordered_map 内部元素不是有序的,这一点从名字都可以看出来。除此之外都应该选择 unordered_map 。

    3. 上述测试中,unordered_map 的遍历性能几乎是常数级别的,与常识不太相符,需要再研究研究。

    附录:贴上源代码
    说明:与测试程序稍有区别,这里的源码里没有MD5相关的代码以确保其他人能比较方便的直接拿去编译运行。

    如有错误还请跟帖指出,非常感谢。


    1. #include <iostream>
    2. #include <string>
    3. #include <sstream>
    4. #include <list>
    5. #include <map>
    6. #include <sys/time.h>
    7. #include <ext/hash_map>
    8. #include <tr1/unordered_map>

    9. namespace zl
    10. { //{{{
    11.     struct equal_to
    12.     {
    13.         bool operator()(const char* s1, const char* s2) const
    14.         {
    15.             return strcmp(s1, s2) == 0;
    16.         }
    17.     };
    18.  
    19.     struct hash_string
    20.         : public std::unary_function<std::string, std::size_t>
    21.         {
    22.             std::size_t
    23.                 operator()(const std::string& __s) const
    24. #ifdef __linux__
    25.                 { return std::tr1::Fnv_hash<>::hash(__s.data(), __s.length()); }
    26. #else
    27.                 { return std::tr1::_Fnv_hash<>::hash(__s.data(), __s.length()); }
    28. #endif
    29.         };

    30.     
    31.     struct hash_charptr
    32.         : public std::unary_function<const char*, std::size_t>
    33.         {
    34.             std::size_t
    35.                 operator()(const char* __s) const
    36. #ifdef __linux__
    37.                 { return std::tr1::Fnv_hash<>::hash(__s, strlen(__s)); }
    38. #else
    39.                 { return std::tr1::_Fnv_hash<>::hash(__s, strlen(__s)); }
    40. #endif
    41.         };
    42. }//}}}

    43. typedef std::list<std::string> string_list;
    44. typedef std::map<std::string, int> string_map;
    45. typedef __gnu_cxx::hash_map<std::string, int, zl::hash_string> string_hash_map;
    46. typedef std::tr1::unordered_map<std::string, int> string_unordered_map;

    47. void fill_list(string_list& slist, size_t count);
    48. uint64_t current_usec();

    49. int main( int argc, char* argv[] )
    50. {
    51.     if (argc != 2 && argc != 3)
    52.     {
    53.         fprintf(stderr, "Usage:%s test_count rehash\n", argv[0]);
    54.         fprintf(stderr, "For example:%s 10000 rehash\n", argv[0]);
    55.         return -1;
    56.     }

    57.     size_t count = atoi(argv[1]);
    58.     bool rehash = false;
    59.     if (argc == 3)
    60.     {
    61.         rehash = true;
    62.     }

    63.     string_map smap;
    64.     string_hash_map shash_map;
    65.     string_unordered_map sunordered_map;

    66.     if (rehash)
    67.     {
    68.         sunordered_map.rehash(count);
    69.     }

    70.     string_list slist;
    71.     fill_list(slist, count);

    72.     uint64_t start = 0;
    73.     uint64_t end = 0;

    74.     uint64_t map_insert_us = 0;
    75.     uint64_t hash_map_insert_us = 0;
    76.     uint64_t unordered_map_insert_us = 0;

    77.     uint64_t map_traverse_us = 0;
    78.     uint64_t hash_map_traverse_us = 0;
    79.     uint64_t unordered_map_traverse_us = 0;

    80.     uint64_t map_find_us = 0;
    81.     uint64_t hash_map_find_us = 0;
    82.     uint64_t unordered_map_find_us = 0;

    83.     uint64_t map_delete_us = 0;
    84.     uint64_t hash_map_delete_us = 0;
    85.     uint64_t unordered_map_delete_us = 0;



    86.     // Insert test
    87.     {//{{{
    88.         string_list::iterator it(slist.begin());
    89.         string_list::iterator ite(slist.end());

    90.         //map insert
    91.         start = current_usec();
    92.         for (int i = 0; it != ite; ++it, ++i)
    93.         {
    94.             smap[*it] = i;
    95.         }
    96.         end = current_usec();
    97.         map_insert_us = end - start;

    98.         //hash_map insert
    99.         it = slist.begin();
    100.         start = current_usec();
    101.         for (int i = 0; it != ite; ++it, ++i)
    102.         {
    103.             shash_map[*it] = i;
    104.         }
    105.         end = current_usec();
    106.         hash_map_insert_us = end - start;

    107.         //unordered_map insert
    108.         it = slist.begin();
    109.         start = current_usec();
    110.         for (int i = 0; it != ite; ++it, ++i)
    111.         {
    112.             shash_map[*it] = i;
    113.         }
    114.         end = current_usec();
    115.         unordered_map_insert_us = end - start;
    116.     }//}}}

    117.     // Traverse test
    118.     {//{{{
    119.         //map traverse 
    120.         {
    121.             string_map::iterator it(smap.begin());
    122.             string_map::iterator ite(smap.end());
    123.             start = current_usec();
    124.             for (int i = 0; it != ite; ++it)
    125.             {
    126.                 i++;
    127.             }
    128.             end = current_usec();
    129.             map_traverse_us = end - start;
    130.         }

    131.         //hash_map traverse 
    132.         {
    133.             string_hash_map::iterator it(shash_map.begin());
    134.             string_hash_map::iterator ite(shash_map.end());
    135.             start = current_usec();
    136.             for (int i = 0; it != ite; ++it)
    137.             {
    138.                 i++;
    139.             }
    140.             end = current_usec();
    141.             hash_map_traverse_us = end - start;
    142.         }

    143.         //unordered_map traverse 
    144.         {
    145.             string_unordered_map::iterator it(sunordered_map.begin());
    146.             string_unordered_map::iterator ite(sunordered_map.end());
    147.             start = current_usec();
    148.             for (int i = 0; it != ite; ++it)
    149.             {
    150.                 i++;
    151.             }
    152.             end = current_usec();
    153.             unordered_map_traverse_us = end - start;
    154.         }
    155.     }//}}}

    156.     // Find test
    157.     {//{{{
    158.         string_list::iterator it(slist.begin());
    159.         string_list::iterator ite(slist.end());

    160.         //map find
    161.         start = current_usec();
    162.         for (int i = 0; it != ite; ++it, ++i)
    163.         {
    164.             smap[*it] = i;
    165.         }
    166.         end = current_usec();
    167.         map_find_us = end - start;

    168.         //hash_map find
    169.         it = slist.begin();
    170.         start = current_usec();
    171.         for (int i = 0; it != ite; ++it, ++i)
    172.         {
    173.             shash_map[*it] = i;
    174.         }
    175.         end = current_usec();
    176.         hash_map_find_us = end - start;

    177.         //unordered_map find
    178.         it = slist.begin();
    179.         start = current_usec();
    180.         for (int i = 0; it != ite; ++it, ++i)
    181.         {
    182.             shash_map[*it] = i;
    183.         }
    184.         end = current_usec();
    185.         unordered_map_find_us = end - start;
    186.     }//}}}

    187.     // Delete test
    188.     {//{{{
    189.         string_list::iterator it(slist.begin());
    190.         string_list::iterator ite(slist.end());

    191.         //map delete
    192.         start = current_usec();
    193.         for (int i = 0; it != ite; ++it, ++i)
    194.         {
    195.             smap.erase(*it);
    196.         }
    197.         end = current_usec();
    198.         map_delete_us = end - start;

    199.         //hash_map delete
    200.         it = slist.begin();
    201.         start = current_usec();
    202.         for (int i = 0; it != ite; ++it, ++i)
    203.         {
    204.             shash_map.erase(*it);
    205.         }
    206.         end = current_usec();
    207.         hash_map_delete_us = end - start;

    208.         //unordered_map delete
    209.         it = slist.begin();
    210.         start = current_usec();
    211.         for (int i = 0; it != ite; ++it, ++i)
    212.         {
    213.             shash_map.erase(*it);
    214.         }
    215.         end = current_usec();
    216.         unordered_map_delete_us = end - start;
    217.     }//}}}

    218.     //stat output
    219.     std::cout << " insert, count " << count << std::endl;
    220.     std::cout << " std::map " << map_insert_us << " us\n";
    221.     std::cout << " std::ext/hash_map " << hash_map_insert_us << " us\n";
    222.     std::cout << "std::tr1::unordered_map " << unordered_map_insert_us << " us\n";

    223.     std::cout << "\n";
    224.     std::cout << " traverse, count " << count << std::endl;
    225.     std::cout << " std::map " << map_traverse_us << " us\n";
    226.     std::cout << " std::ext/hash_map " << hash_map_traverse_us << " us\n";
    227.     std::cout << "std::tr1::unordered_map " << unordered_map_traverse_us << " us\n";

    228.     std::cout << "\n";
    229.     std::cout << " find, count " << count << std::endl;
    230.     std::cout << " std::map " << map_find_us << " us\n";
    231.     std::cout << " std::ext/hash_map " << hash_map_find_us << " us\n";
    232.     std::cout << "std::tr1::unordered_map " << unordered_map_find_us << " us\n";

    233.     std::cout << "\n";
    234.     std::cout << " delete, count " << count << std::endl;
    235.     std::cout << " std::map " << map_delete_us << " us\n";
    236.     std::cout << " std::ext/hash_map " << hash_map_delete_us << " us\n";
    237.     std::cout << "std::tr1::unordered_map " << unordered_map_delete_us << " us\n";

    238.      
    239.     return 0;
    240. }

    241. void fill_list(string_list& slist, size_t count)
    242. {
    243.     for (size_t i = 0; i < count; ++i)
    244.     {
    245.         std::ostringstream oss;
    246.         oss << i;
    247.         //slist.push_back(MD5::getHexMD5(oss.str().c_str(), oss.str().length()));
    248.         slist.push_back(oss.str());
    249.     }
    250. }


    251. uint64_t current_usec()
    252. {
    253.     struct timeval tv;
    254.     gettimeofday( &tv, NULL );
    255.     return tv.tv_sec * 1000 * 1000 + tv.tv_usec;
    256. }

    展开全文
  • map hash_map unordered_map

    2019-04-06 14:20:53
    1. unordered_map, hash_map, map 概述 C++中,map(来自于 STL) ,底层实现采用红黑树。 hash_map(有很多种实现,底层实现均采用hashtable。目前普遍使用的来自 SGI 的 STL),还未成为C++标准,不过,在可预见的...
  •         ...map hash_map unordered_map 性能测试                                       【1】插入总数/ 总处理时间 单位us(微秒)
  • 简单对比mapunordered_map map内部是红黑树,在插入元素时会自动排序,map中的元素会自动保持从小到大(key)排序存储. 而无序容器unordered_map内部是散列表,通过哈希而不是排序来快速操作元素,使得效率更高...
  • 如果数据量小,并且没有顺序要求,强烈建议使用 unordered_map 如果数据量大,但查询次数不多,可以使用map 如果数据量大,查询次数多,建议使用hash_map map:红黑树 logn时间复杂度 有序 unordered_map内部是hash...
  • C++ 11中出现了两种新的关联容器:unordered_set和unordered_map,其内部实现与set和map大有不同, 哈希表是根据关键码值而进行直接访问的数据结构,通过相应的哈希函数(也称散列函数)处理关键字得到相应的关键...
  • 结论如下: Release模式下: ...2. 容量为100的时候,查找效率:map = unordered_map > hash_map 3. 容量为1000的时候,查找效率:unordered_map > hash_map > 4倍map 4. 容量为1万的时候,查...
  • mapunordered_map的区别见http://blog.csdn.net/orzlzro/article/details/7099231hash_mapunordered_map的区别Since there was no hash table defined in the C++ standard library, different implementors of ...
  • C++ 11+ 新容器 array数组 forward_list单向链表 unordered_map unordered_set无序容器 tuple元组 #include<iostream> #include<array> #include<tuple> #include<string> using namespace ...
  • 2012年1月8日 | by zieckey | 标签: hash_mapmap, STL, unordered_map, 关联容器, 性能比较, 用法示例 作者: zieckey 发表时间: 2012年1月8日 本文链接: ...
  • c++ map unordered_map

    2015-03-19 22:00:08
    在C++中最让我蛋疼的事情之一就是unordered_map千呼万唤才出来,在C++早期版本标准库里面只有map这个字典。 但是map的内部实现是采用的红黑树,众所周知,对于字典这类结构也可以用hash表来实现,也就是C++的标准...
  • string 求字符串的长度 在haystack字符串中找到needle字符串的位置,...unordered map (这就是hash table) 声明: unordered_map<int, int > m 向map中添加元素: m[nums[i]] = i; 在map中发现该元素: if(m....
  • map由于无序,速度比set最快。 unordered_set(注意会去重)速度大于map,所以判断存在时可以考虑使用unordered_set
  • 问题:C++无序容器的使用自定义类作为Key值 ...unordered_map> #include<unordered_set> using namespace std; class A { friend size_t hasher(const A& a); friend bool eqOp(co
  • map hash_map unordered_map 性能比较

    千次阅读 2016-07-13 15:26:06
    typedef std::tr1::unordered_map, int> string_unordered_map; void fill_list(string_list& slist, size_t count); uint64_t current_usec(); int main( int argc, char* argv[] ) { if (argc != 2 && argc != ...
  • 这种用map处理最简洁,key是输入的字符,value是字符的次数,寻找最大的数,然后遍历map,判断map的second参数是不是max,是就输出map的第一个参数。因为是多个string注意用auto类型表示迭代器it的类型,或者写<...
  • by zieckey 总结提前来了: unordered_map 类的调用比hash_map方便多了,看性能难怪stl 有前者,而后者调用需要 namespace__gnu_cxx。 结论: 1. std::tr1::unordered_map 与st...
  • c++11 无序map unordered_map

    千次阅读 2014-07-17 18:06:36
    #include #include ...typedef std::unordered_map Mymap; int main() { Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap
  • 后来把unordered_map换成map就过了。虽然在小数据集上hashmap和treemap区别不大,但数据量大的话,hashmap还是好些。所以最佳实践是,在不需要排序特性时,就用hashmap。 而且之前也从来没有遇到过hashmap比treemap...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,875
精华内容 3,150
关键字:

mapunordered