【C++】unordered_set/unordered_multiset/unordered_map/unordered_multimap

发布时间:2023年12月24日

我们下面来学习C++的另外两个容器:unordered_set和unordered_map

目录

一、unordered系列关联式容器

二、unordered_map

2.1?unordered_map的介绍

2.2?unordered_map的接口说明

2.2.1 unordered_map的构造

2.2.2?unordered_map的容量

2.2.3?unordered_map的迭代器

2.2.4 unordered_map的元素访问

2.2.5?unordered_map的查询

2.2.6?unordered_map的修改操作

三、unordered_set

四、unordered_multiset和unordered_multimap

五、unordered系列关联式容器与普通树形结构存储容器的性能测试


一、unordered系列关联式容器

在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到㏒⑵N,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在C++11中,STL又提供了4个unordered系列的关联式容器,这四个容器与红黑树结构的关联式容器使用方式基本类似,只是其底层结构不同(unordered系列容器的底层为哈希表)

二、unordered_map

unordered_map的介绍文档:unordered_map - C++ Reference (cplusplus.com)

2.1?unordered_map的介绍

● unordered_map是存储键值对的关联式容器,其允许通过keys快速的索引到与 其对应的value

● 在unordered_map中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此 键关联。键和映射值的类型可能不同。

● 在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。

● unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭 代方面效率较低。

● unordered_maps实现了直接访问操作符(operator[]),它允许使用key作为参数直接访问 value。

● 它的迭代器是单向迭代器。

2.2?unordered_map的接口说明

unordered_map的接口和map是一模一样的,这里我们介绍一遍,就不再过多演示了:

2.2.1 unordered_map的构造

函数声明功能介绍
unordered_map构造不同格式的unordered_map对象

2.2.2?unordered_map的容量

函数声明功能介绍
empty检测unordered_map是否为空
size获取unordered_map的有效元素个数

2.2.3?unordered_map的迭代器

函数声明功能介绍
begin返回unordered_map第一个元素的迭代器
end返回unordered_map最后一个元素下一个位置的迭代器
cbegin返回unordered_map第一个元素的const迭代器
cend返回unordered_map最后一个元素下一个位置的const迭代器

2.2.4 unordered_map的元素访问

注意:该函数中实际调用哈希桶的插入操作,用参数key与V()构造一个默认值往底层哈希桶 中插入,如果key不在哈希桶中,插入成功,返回V(),插入失败,说明key已经在哈希桶中, 将key对应的value返回。

2.2.5?unordered_map的查询

函数声明功能介绍
find返回key在哈希桶中的位置
count

返回哈希桶中关键码为key的键值对的个数

2.2.6?unordered_map的修改操作

函数声明功能介绍
insert向容器中插入键值对
erase删除容器中的键值对
clear清空容器中有效元素个数
swap交换两个容器中的元素

三、unordered_set

unordered_set的介绍文档:unordered_set - C++ Reference (cplusplus.com)

对于其介绍和接口说明和set容器是一模一样的,下面不再说明了

四、unordered_multiset和unordered_multimap

unordered_multiset的介绍文档:unordered_multiset - C++ Reference (cplusplus.com)

unordered_multimap的介绍文档:unordered_multimap - C++ Reference (cplusplus.com)

unordered_multiset和unordered_multimap与unordered_set和unordered_map唯一的区别就是,其中存储的元素的key值是可以重复的

五、unordered系列关联式容器与普通树形结构存储容器的性能测试

测试代码:

#include<set>
#include<unordered_set>
using namespace std;

int main()
{
	const size_t N = 1000000;

	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系列关联式容器的性能是优于普通树形结构存储容器的性能的

文章来源:https://blog.csdn.net/m0_70811813/article/details/134983514
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。