文章目录
- 1.unordered系列关联式容器
- 2. unordered_map
- 3.unordered_set
1.unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，如map和set，它们在查询时效率可达logN，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率会降低。
因此在C++11中STL又提供了4个unordered系列的关联式容器，unordered_map，unordered_set和unordered_multimap，unordered_multiset，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。
在学习unordered_set和unordered_map之前最好先认识熟悉一下map和set，有关map和set的解释与用法，请移步至这篇文章：
map与set用法详解
那么在C++中unordered_map和map，unordered_set和set有什么区别呢？
最大的几个区别在于：底层结构，数据是否有序，在不同场景下的性能。
（C++98） set/map的底层结构是由红黑树（平衡二叉树搜索树）实现的，迭代器遍历（中序遍历），得到的数据是有序的,并且具有双向迭代器。在Java中，对它们的命名更直观，java中map和set，叫做TreeSet/TreeMap。
（C++11）unordered_set/unordered_map的底层结构是由哈希表实现的，迭代器遍历的结果是无序的，并且只有单向迭代器。关键点在于，unordered系列的关联式容器查找效率非常高，Hash表通过把关键码值映射到Hash表中的某个位置，来访问记录，查找的时间复杂度可达到O(1），在海量数据处理中有着广泛的应用。java中称之为HashSet/HashMap。
下面我们利用简单的代码，测试一下set与unordered_set的各个函数接口的性能。
#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <vector>
#include <time.h>
using namespace std;
int main()
{
const size_t N = 10000;
unordered_set<int> us;
set<int> s;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i)
{
//v.push_back(rand());//随机+大量重复值
v.push_back(rand()+i);//随机+部分重复
//v.push_back(i);//有序
}
size_t begin1 = clock();
for (auto e : v)
{
s.insert(e);
}
size_t end1 = clock();
cout << "set insert:" << end1 - begin1 << endl;
size_t begin2 = clock();
for (auto e : v)
{
us.insert(e);
}
size_t end2 = clock();
cout << "unordered_set insert:" << end2 - begin2 << endl;
size_t begin3 = clock();
for (auto e : v)
{
s.find(e);
}
size_t end3 = clock();
cout << "set find:" << end3 - begin3 << endl;
size_t begin4 = clock();
for (auto e : v)
{
us.find(e);
}
size_t end4 = clock();
cout << "unordered_set find:" << end4 - begin4 << endl << endl;
cout << s.size() << endl;
cout << us.size() << endl << endl;;
size_t begin5 = clock();
for (auto e : v)
{
s.erase(e);
}
size_t end5 = clock();
cout << "set erase:" << end5 - begin5 << endl;
size_t begin6 = clock();
for (auto e : v)
{
us.erase(e);
}
size_t end6 = clock();
cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
return 0;
}
测试结果：
总结一下：综合各种场景而言，unordered系列综合性能更好，尤其是find函数，查找效率一骑绝尘。在有序的情况下，set的插入和删除效率更好。
2. unordered_map
unordered_map官方文档
- unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
- 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
- 在内部,unordered_map没有对<key, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
- unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
- unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。
- 它的迭代器至少是前向迭代器。
简单使用：
void test_unordered_map()
{
string arr[] = { "西瓜","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉","梨" };
map<string, int> countMap;
for (auto& e : arr)
{
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
}
测试结果：是无序的。
3.unordered_set
unordered_set官方文档
简单使用：
void test_unordered_set()
{
unordered_set<int> s;
s.insert(1);
s.insert(3);
s.insert(2);
s.insert(7);
s.insert(2);
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//支持范围for
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
测试结果：是无序的。
在文章结尾再次说明：unordered_set，unordered_map,以及map，set的key值是不允许重复的，如果需要有重复的key值，就使用unordered_multiset，unordered_multimap，以及muiltiset,multimap。
