unordered_set、unordered_map的介绍+使用+比较
1.unordered系列关联式容器
在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时的效率可达到O(logN),即最差情况下需要比较红黑树的高度次,当树中的结点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在C++11中,STL又提供了4个unordered系列的关联式容器,这四个容器与红黑树结构的关联式容器使用方式基本类似,只是其底层结构不同。
2.unordered_set的介绍
- unordered_set是不按特定顺序存储键值的关联式容器,其允许通过键值快速的索引到对应的元素。
- 在unordered_set中,元素的值同时也是唯一地标识它的key。
- 在内部,unordered_set中的元素没有按照任何特定的顺序排序,为了能在常数范围内找到指定的key,unordered_set将相同哈希值的键值放在相同的桶中。
- unordered_set容器通过key访问单个元素要比set快,但它通常在遍历元素子集的范围迭代方面效率较低。
- 它的迭代器至少是前向迭代器。(单向)
3.unordered_multiset
unordered_multiset容器与unordered_set容器的底层数据结构是一样的,都是哈希表,其次,它们所提供的成员函数的接口都是基本一致的,这两种容器唯一的区别就是,unordered_multiset容器允许键值冗余,即unordered_multiset容器当中存储的元素是可以重复的。
4.unordered_map
- unordered_map是存储<key, value>键值对的关联式容器,其允许通过key值快速的索引到与其对应是value。
- 在unordered_map中,键值通常用于唯一地标识元素,而映射值是一个对象,其内容与此键关联。键和映射值的类型可能不同。
- 在内部,unordered_map没有对<key, value>按照任何特定的顺序排序,为了能在常数范围内找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。
- unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭代方面效率较低。
- unordered_map实现了直接访问操作符(operator[ ]),它允许使用key作为参数直接访问value。
- 它的迭代器至少是前向迭代器。(单向)
5.unordered_multimap
unordered_multimap容器与unordered_map容器的底层数据结构是一样的,都是哈希表,其次,它们所提供的成员函数的接口都是基本一致的,这两种容器唯一的区别就是,unordered_multimap容器允许键值冗余,即unordered_multimap容器当中存储的键值对的key值是可以重复的。
6.unordered_set、unordered_map的使用
7.map/set与unordered_map/unordered_set的区别
容器 | 底层数据结构 | 是否有序 | 实现版本 | 增删改查效率 | 迭代器类型 |
unordered_map/unordered_set | 哈希表/散列表 | 否 | C++98 | O(1) | 单向迭代器 |
map/set | 红黑树 | 是 | C++11 | O(logN) | 双向迭代器 |
8. 关于find查找算法
-- unordered_set专用查找算法。优点:使用哈希特性去查找,效率高 -- O(1)
-- 类似如果是set的,效率是O(logN)
auto pos = us.find(2); //unordered_set
auto pos = s.find(2); //set
-- 通用算法,优点:每个容器都可以使用,泛型算法。 缺点:暴力查找 -- O(N)
-- 复用
--auto pos = find(us.begin(), us.end(), 2); //find算法在 algorithm.h头文件中
if (pos != us.end())
{
cout << "找到了" << endl;
}
else
{
cout << "找不到" << endl;
}
9.map/set与unordered_map/unordered_set的性能测试
- map容器与unordered_map容器的差别和set容器与unordered_set容器的差别类似,下面我们以set容器和unordered_set容器的测试为例。
- 容器的性能,我们最关心的实际就是该容器增删查改的效率。我们可以通过下列代码测试set容器和unordered_set容器insert、find以及erase的效率。
#include <iostream>
#include <set>
#include <unordered_set>
#include <time.h>
using namespace std;
int main()
{
int N = 1000;
vector<int> v;
v.reserve(N);
srand((unsigned int)time(NULL));
//随机生成N个数字
for (int i = 0; i < N; i++)
{
v.push_back(rand());
}
/****************插入效率测试****************/
//将这N个数插入set容器
set<int> s;
clock_t begin1 = clock(); //记录开始时间
for (auto e : v)
{
s.insert(e);
}
clock_t end1 = clock(); //记录结束时间
//将这N个数插入unordered_set容器
unordered_set<int> us;
clock_t begin2 = clock();
for (auto e : v)
{
us.insert(e);
}
clock_t end2 = clock();
//分别输出插入set容器和unordered_set容器所用的时间
cout << "set insert: " << end1 - begin1 << endl;
cout << "unordered_set insert: " << end2 - begin2 << endl;
/****************查找效率测试****************/
//在set容器中查找这N个数
clock_t begin3 = clock();
for (auto e : v)
{
s.find(e);
}
clock_t end3 = clock();
//在unordered_set容器中查找这N个数
clock_t begin4 = clock();
for (auto e : v)
{
us.find(e);
}
clock_t end4 = clock();
//分别输出在set容器和unordered_set容器中查找这N个数所用的时间
cout << "set find: " << end3 - begin3 << endl;
cout << "unordered_set find: " << end4 - begin4 << endl;
/****************删除效率测试****************/
//将这N个数从set容器中删除
clock_t begin5 = clock();
for (auto e : v)
{
s.erase(e);
}
clock_t end5 = clock();
//将这N个数从unordered_set容器中删除
clock_t begin6 = clock();
for (auto e : v)
{
us.erase(e);
}
clock_t end6 = clock();
//分别输出将这N个数从set容器和unordered_set容器中删除所用的时间
cout << "set erase: " << end5 - begin5 << endl;
cout << "unordered_set erase: " << end6 - begin6 << endl;
return 0;
}
(1)对1000个数做增删查改操作
- 当N为1000时,set容器和unordered_set容器增删查改的效率差异并不大,在Debug版本下的测试结果如下:
- 在Release版本下,set容器和unordered_set容器对1000个数做增删查改操作所用的时间更是被优化到了接近0毫秒。
(2) 10000000个数做增删查改操作
- 10000000个数, set容器和unordered_set容器增删查改的效率的差异就很明显了,在Debug版本下的测试结果如下
- 经过Release版本优化后,unordered_set容器与set容器的差距更加明显了
(3)小结
- 当处理数据量小时,map/set容器与unordered_map/unordered_set容器增删查改的效率差异不大。
- 当处理数据量大时,map/set容器与unordered_map/unordered_set容器增删查改的效率相比,unordered系列容器的效率更高。
- 因此,当处理数据量较小时,选用xxx容器与unordered_xxx容器的差异不大;当处理数据量较大时,建议选用对应的unordered_xxx容器。
- 补充一点: 当需要存储的序列为有序时,应该选用map/set容器。