在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log_2 N log2N，即最差情 况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比 较次数就能够将元素找到， 因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，即unordered_map和unordered_set，unordered_multimap和unordered_multiset
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<string> #include<map> #include<set> #include<unordered_map> #include<unordered_set> #include<vector> #include<time.h> using namespace std; //无序+去重 void test_unordered_set() { unordered_set<int> us; us.insert(4); us.insert(8); us.insert(4); us.insert(3); us.insert(4); us.insert(2); us.insert(5); us.insert(1); unordered_set<int>::iterator it = us.begin(); while (it != us.end()) { cout << *it << " "; it++; } cout << endl; for (auto e : us) { cout << e << " "; } cout << endl; auto ret = us.find(5); if (ret != us.end()) { cout << "找到了"; } } void test_unordered_map() { unordered_map<string, string> um; um.insert(make_pair("sort", "排序")); um.insert(make_pair("string", "字符串")); um.insert(make_pair("left", "左边")); um.insert(make_pair("left", "剩余"));//这个插入失败，key不能重复 um["insert"]; um["insert"] = "插入"; unordered_map<string, string>::iterator it = um.begin(); while (it != um.end()) { cout << it->first << ": " << it->second << endl; it++; } cout << endl; for (const auto e : um) { cout << e.first << ": " << e.second << endl; } cout << endl; } void test_op()//性能分析 { set<int> s; unordered_set<int> us; srand(time(0)); vector<int> v; const size_t n = 10000000; v.reserve(n); for (size_t i = 0; i < 10000000; i++) { v.push_back(rand()); } //insert测性能 size_t begin1 = clock(); for (size_t i = 0; i < v.size(); i++) { s.insert(v[i]); } size_t end1 = clock(); size_t begin2 = clock(); for (size_t i = 0; i < v.size(); i++) { us.insert(v[i]); } size_t end2 = clock(); cout <<"set insert:" << end1 - begin1 << endl; cout << "unordered_set insert:" << end2 - begin2 << endl; //find测性能 begin1 = clock(); for (size_t i = 0; i < v.size(); i++) { s.find(rand()); } end1 = clock(); begin2 = clock(); for (size_t i = 0; i < v.size(); i++) { us.find(rand()); } end2 = clock(); cout << "set find:" << end1 - begin1 << endl; cout << "unordered_set find: "<< end2 - begin2 << endl; //erase测性能 begin1 = clock(); for (size_t i = 0; i < v.size(); i++) { s.erase(rand()); } end1 = clock(); begin2 = clock(); for (size_t i = 0; i < v.size(); i++) { us.erase(rand()); } end2 = clock(); cout << "set erase:" << end1 - begin1 << endl; cout << "unordered_set erase: " << end2 - begin2 << endl; } int main() { //test_unordered_set(); //test_unordered_map(); test_op(); system("pause"); return 0; }unordered_set删除数据的代价会大一点 其他都会比set好很多 所有unordered_set在性能效率方面会更胜一筹
