一：无序容器简介

Unordered Containers也是一种关联式容器。其中元素是分散，没有定性的排列（不是图中那样松散）。其中元素可能在某一次操作后改变原来的位置。

哈希表的链地址法，更能表现其内部实现结构。其中哈希表中表长可以改变，其实现用分配器实现，为了防止链表过程，效率减低，设置一个值，当链表长度过长时（大于等于表长），打散哈希表，重新设置表长，分配位置。

二：性能测试

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <stdio.h> #include <cstring> #if _MSC_VER #define snprintf _snprintf #endif using namespace std; long get_a_target_long() { /******变量声明********/ long target = 0; /**********************/ cout << "targer (0~" << RAND_MAX << "):"; cin >> target; return target; } string get_a_target_string() { /******变量声明********/ long target = 0; char buf[10]; /**********************/ cout << "targer (0~" << RAND_MAX << "):"; cin >> target; snprintf(buf, 10, "%d", target); return string(buf); } //与后面的比较函数中回调参数对应 int compareLongs(const void* l1, const void* l2) { return (*(long*)l1 - *(long*)l2); } int compareStrings(const void* s1, const void* s2) { if (*(string*)s1 > *(string*)s2) return 1; if (*(string*)s1 < *(string*)s2) return -1; return 0; } 公共函数

（一）unordered_multiset测试

#include <unordered_set> //测试unordered_multiset-->元素可以重复 namespace jj12 { void test_unordered_multiset(long& us_size) { cout << "\ntest_unordered_multiset()*******" << endl; /******变量声明:数组初始********/ char buf[10]; /******变量声明:unordered_multiset初始********/ unordered_multiset<string> ums; /******变量声明：记录时间********/ clock_t timeStart = clock(); //开始时间 for (long i = 0; i < us_size; i++) { try { snprintf(buf, 10, "%d", rand()); ums.insert(string(buf)); } catch (exception& e) { cout << e.what() << endl; cout << "Max_size:" << i << endl; abort(); //终止 } } cout << "inti unordered_multiset use milli-seconds:" << (clock() - timeStart) << endl; //获取初始化数组耗时 cout << "unordered_multiset.size:" << ums.size() << endl; //获取unordered_multiset大小 cout << "unordered_multiset.max_size:" << ums.max_size() << endl; //获取unordered_multiset允许最大长度 cout << "unordered_multiset.bucket_count:" << ums.bucket_count() << endl; //获取篮子数--表长 cout << "unordered_multiset.load_factor:" << ums.load_factor() << endl; //获取加载因子 cout << "unordered_multiset.max_load_factoe:" << ums.max_load_factor() << endl; //获取最大加载因子--1 cout << "unordered_multiset.max_bucket_count:" << ums.max_bucket_count() << endl; //获取存在最大篮子数--表长 //打印前20个篮子 for (int i = 0; i < 20; i++) cout << "Key #" << i << " has " << ums.bucket_size(i) //该篮子中有几个元素 << " elements" << endl; /******变量声明：获取我们要查询的数********/ string target = get_a_target_string(); //使用::find方法进行查找 timeStart = clock(); auto pI = find(ums.begin(), ums.end(), target); cout << "::find(),milli-seconds:" << clock() - timeStart << endl; if (pI != ums.end()) cout << "found:" << *pI << endl; else cout << "not found!" << endl; //使用unordered_multiset.find查找 timeStart = clock(); pI = ums.find(target); //比::find块得多，直接定位查询， cout << "unordered_multiset.find(),milli-seconds:" << clock() - timeStart << endl; if (pI != ums.end()) cout << "found:" << *pI << endl; else cout << "not found!" << endl; } }

（二）unordered_multimap测试

#include <unordered_map> //测试unordered_multimap-->元素可以重复 namespace jj13 { void test_unordered_multimap(long& mm_size) { cout << "\ntest_unordered_multimap()*******" << endl; /******变量声明:数组初始********/ char buf[10]; /******变量声明:unordered_multimap初始********/ unordered_multimap<long, string> umm; /******变量声明：记录时间********/ clock_t timeStart = clock(); //开始时间 for (long i = 0; i < mm_size; i++) { try { snprintf(buf, 10, "%d", rand()); umm.insert(pair<long, string>(i, string(buf))); } catch (exception& e) { cout << e.what() << endl; cout << "Max_size:" << i << endl; abort(); //终止 } } cout << "inti unordered_multimap use milli-seconds:" << (clock() - timeStart) << endl; //获取初始化数组耗时 cout << "unordered_multimap.size:" << umm.size() << endl; //获取unordered_multimap大小 cout << "unordered_multimap.max_size:" << umm.max_size() << endl; //获取unordered_multimap所允许最大 cout << "unordered_multimap.bucket_count:" << umm.bucket_count() << endl; //获取篮子数--表长 cout << "unordered_multimap.load_factor:" << umm.load_factor() << endl; //获取加载因子 cout << "unordered_multimap.max_load_factoe:" << umm.max_load_factor() << endl; //获取最大加载因子--1 cout << "unordered_multimap.max_bucket_count:" << umm.max_bucket_count() << endl; //获取存在最大篮子数--表长 //打印前20个篮子 for (int i = 0; i < 20; i++) cout << "Key #" << i << " has " << umm.bucket_size(i) //该篮子中有几个元素 << " elements" << endl; /******变量声明：获取我们要查询的数********/ long target = get_a_target_long(); //根据key查找 //unordered_multimap没有全局::find方法可用，::find找值，multimap找键，两者不同，不可以混用 //使用unordered_multimap.find查找 timeStart = clock(); auto pI = umm.find(target); cout << "unordered_multimap.find(),milli-seconds:" << clock() - timeStart << endl; if (pI != umm.end()) cout << "found:" << (*pI).first << ":" << (*pI).second << endl; else cout << "not found!" << endl; } }

（三）unordered_set测试

#include <unordered_set> //测试unordered_set-->元素不可以重复 namespace jj14 { void test_unordered_set(long& us_size) { cout << "\ntest_unordered_set()*******" << endl; /******变量声明:数组初始********/ char buf[10]; /******变量声明:unordered_set初始********/ unordered_set<string> us; /******变量声明：记录时间********/ clock_t timeStart = clock(); //开始时间 for (long i = 0; i < us_size; i++) { try { snprintf(buf, 10, "%d", rand()); us.insert(string(buf)); } catch (exception& e) { cout << e.what() << endl; cout << "Max_size:" << i << endl; abort(); //终止 } } cout << "inti unordered_multiset use milli-seconds:" << (clock() - timeStart) << endl; //获取初始化数组耗时 cout << "unordered_set.size:" << us.size() << endl; //获取unordered_set大小 cout << "unordered_set.max_size:" << us.max_size() << endl; //获取unordered_set允许最大 cout << "unordered_set.bucket_count:" << us.bucket_count() << endl; //获取篮子数--表长 cout << "unordered_set.load_factor:" << us.load_factor() << endl; //获取加载因子 cout << "unordered_set.max_load_factoe:" << us.max_load_factor() << endl; //获取最大加载因子--1 cout << "unordered_set.max_bucket_count:" << us.max_bucket_count() << endl; //获取存在最大篮子数--表长 //打印前20个篮子 for (int i = 0; i < 20; i++) cout << "Key #" << i << " has " << us.bucket_size(i) //该篮子中有几个元素 << " elements" << endl; /******变量声明：获取我们要查询的数********/ string target = get_a_target_string(); //使用::find方法进行查找 timeStart = clock(); auto pI = find(us.begin(), us.end(), target); cout << "::find(),milli-seconds:" << clock() - timeStart << endl; if (pI != us.end()) cout << "found:" << *pI << endl; else cout << "not found!" << endl; //使用unordered_set.find查找 timeStart = clock(); pI = us.find(target); //比::find块得多，直接定位查询， cout << "unordered_set.find(),milli-seconds:" << clock() - timeStart << endl; if (pI != us.end()) cout << "found:" << *pI << endl; else cout << "not found!" << endl; } }

（四）unordered_map测试

#include <unordered_map> //测试unordered_map-->元素不可以重复 namespace jj15 { void test_unordered_map(long& um_size) { cout << "\ntest_unordered_map()*******" << endl; /******变量声明:数组初始********/ char buf[10]; /******变量声明:unordered_multimap初始********/ unordered_map<long, string> um; /******变量声明：记录时间********/ clock_t timeStart = clock(); //开始时间 for (long i = 0; i < um_size; i++) { try { snprintf(buf, 10, "%d", rand()); um.insert(pair<long, string>(i, string(buf))); } catch (exception& e) { cout << e.what() << endl; cout << "Max_size:" << i << endl; abort(); //终止 } } cout << "inti unordered_map use milli-seconds:" << (clock() - timeStart) << endl; //获取初始化数组耗时 cout << "unordered_map.size:" << um.size() << endl; //获取unordered_map大小 cout << "unordered_map.max_size:" << um.max_size() << endl; //获取unordered_map允许最大 cout << "unordered_map.bucket_count:" << um.bucket_count() << endl; //获取篮子数--表长 cout << "unordered_map.load_factor:" << um.load_factor() << endl; //获取加载因子 cout << "unordered_map.max_load_factoe:" << um.max_load_factor() << endl; //获取最大加载因子--1 cout << "unordered_map.max_bucket_count:" << um.max_bucket_count() << endl; //获取存在最大篮子数--表长 //打印前20个篮子 for (int i = 0; i < 20; i++) cout << "Key #" << i << " has " << um.bucket_size(i) //该篮子中有几个元素 << " elements" << endl; /******变量声明：获取我们要查询的数********/ long target = get_a_target_long(); //根据key查找 //unordered_map没有全局::find方法可用，::find找值，unordered_map找键，两者不同，不可以混用 //使用unordered_map.find查找 timeStart = clock(); auto pI = um.find(target); cout << "unordered_map.find(),milli-seconds:" << clock() - timeStart << endl; if (pI != um.end()) cout << "found:" << (*pI).first << ":" << (*pI).second << endl; else cout << "not found!" << endl; } }

 

转载于:https://www.cnblogs.com/ssyfj/p/10797671.html