【C++】20. unordered_set和unordered_map

发布于：2025-09-15 ⋅ 阅读:(14) ⋅ 点赞:(0)

文章目录

一、unordered_set的使⽤

1、参考文档

unordered_set参考文档
unordered_multiset参考文档

2、unordered_set类的介绍

template < class Key,                        // unordered_set::key_type/value_type
           class Hash = hash<Key>,           // unordered_set::hasher
           class Pred = equal_to<Key>,       // unordered_set::key_equal
           class Alloc = allocator<Key>      // unordered_set::allocator_type
           > class unordered_set;

  • unordered_set的声明如上，Key就是unordered_set底层关键字的类型。

  • unordered_set默认要求Key⽀持转换为整形，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key转成整形的仿函数传给第⼆个模板参数。

  • unordered_set默认要求Key⽀持⽐较相等，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key⽐较相等的仿函数传给第三个模板参数。

  • unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第四个参数。

  • unordered_set底层是⽤哈希桶实现的，增删查平均效率是O(1) ，迭代器遍历不再有序，为了跟set区分，所以取名unordered_set。

3、unordered_set的常用接口

1）constructor

和set一样，unordered_set也支持⽆参默认构造、迭代器区间构造、拷贝构造、列表初始化以及赋值重载。

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

int main()
{
	//默认去重+不排序
	unordered_set<int> us;//默认无参构造
	unordered_set<int> us1 = { 3,5,4,1,7,5,8,3,9,10 };//初始化列表
	unordered_set<int> us2(us1.begin(), us1.end());//迭代器区间构造
	unordered_set<int> us3(us1);//拷贝构造
	unordered_set<int> us4;
	us4 = us1;//赋值

	return 0;
}

2）Iterators

unordered_set的底层是哈希桶，是单向链表，因此只支持单向迭代器。

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

int main()
{
	unordered_set<int> us1 = { 3,5,4,1,7,5,8,3,9,10 };//初始化列表

	unordered_set<int>::iterator it = us1.begin();
	while (it != us1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	return 0;
}

运行结果：
在这里插入图片描述

3）Element lookup

unordered_set还支持find接口。

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

int main()
{
	unordered_set<int> us = { 5,6,1,2,4,5,3 };

	auto it = us.find(3);//查找
	cout << *it << endl;
		
	return 0;
}

运行结果：
在这里插入图片描述

4）Modifiers

unordered_set还支持插入、删除接口。

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

int main()
{
	unordered_set<int> us;
	us.insert(10);//插入
	us.insert(6);
	us.insert(20);
	us.insert(30);
	us.insert(15);
	us.erase(6);//删除
	for (auto e : us)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

运行结果：
在这里插入图片描述

5）Buckets

这里是有关哈希桶的相关接口。

函数声明 接口说明
bucket_count 返回桶的数量
max_bucket_count 返回桶的最大数量
bucket_size 返回桶的大小
bucket 定位元素所在的桶 
#include<iostream>
#include<unordered_set>
using namespace std;

int main()
{
	unordered_set<int> us = { 5,6,1,2,4,5,3,9 };

	cout << us.bucket_count() << endl;//桶的数量
	cout << us.max_bucket_count() << endl; //桶的最大数量
	cout << us.bucket_size(0) << endl;//桶0的大小
	cout << us.bucket(9) << endl;//9所在的桶

	return 0;
}

运行结果：
在这里插入图片描述

6）Hash policy

函数声明 接口说明
load_factor 返回负载因子
max_load_factor 获取或设置最大负载因子
rehash 设置桶的数量
reserve 更改容量，与rehash用法近似，都起到设置桶的数量的作用 
#include<iostream>
#include<unordered_set>
using namespace std;

int main()
{
	unordered_set<int> us = { 5,6,1,2,4,5,3,9 };
	cout << us.load_factor() << endl;//负载因子
	cout << us.max_load_factor() << endl;//最大的负载因子

	cout << us.bucket_count() << endl;
	us.rehash(20);//设置桶的数量
	cout << us.bucket_count() << endl;
	us.reserve(20);//更改容量
	cout << us.bucket_count() << endl;

	return 0;
}

运行结果：

4、unordered_set和set的差异

  • unordered_set和set的第⼀个差异是对key的要求不同，set要求Key⽀持⼩于⽐较，⽽unordered_set要求Key⽀持转成整形且⽀持等于⽐较，这本质是哈希表的要求。
  • unordered_set和set的第⼆个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set是单向迭代器，其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。
  • unordered_set和set的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_set的增删查改更快⼀些，因为红⿊树增删查改效率是O(logN) ，⽽哈希表增删查平均效率是O(1) ，具体可以参看下⾯代码的演⽰的对⽐差异。
#include<iostream>
#include<unordered_set>
#include<set>
#include<vector>
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);//无重复 有序
	}

	//插入N个数据
	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();
	cout << "set insert: " << end1 - begin1 << "ms" << endl;

	size_t begin2 = clock();
	us.reserve(N);
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert: " << end2 - begin2 << "ms" << endl << endl;;

	cout << "set插入数据个数: " << s.size() << endl;
	cout << "unordered_set插入数据个数: " << us.size() << endl << endl;

	//依次查找N个数据
	int m1 = 0;
	size_t begin3 = clock();
	for (auto e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	size_t end3 = clock();
	cout << "set find:" << m1 << "->" << end3 - begin3 << "ms" << endl;

	int m2 = 0;
	size_t begin4 = clock();
	for (auto e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	size_t end4 = clock();
	cout << "unordered_set find:" << m2 << "->" << end3 - begin3 << "ms" << endl << endl;

	//删除N个数据
	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();
	cout << "set erase: " << end5 - begin5 << "ms" << endl;

	size_t begin6 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end6 = clock();
	cout << "unordered_set erase: " << end6 - begin6 << "ms" << endl;

	return 0;
}

运行结果：

从上面的结果中可以发现unordered_set的插入与删除效率是要更高的。

二、unordered_map的使用

1、参考文档

unordered_map参考⽂档
unordered_multimap参考文档

2、unordered_map类的介绍

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

unordered_map类的定义与unordered_set类是一致的，只是多了一个模版参数T，用来表示映射值的数据类型。

3、unordered_map的常用接口

1）constructor

和map一样，unordered_map也支持⽆参默认构造、迭代器区间构造、拷贝构造、初始化列表以及赋值重载。

#include<iostream>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_map<string, string> um;//无参默认构造
	unordered_map<string, string> um1 = { {"left","左边"},{"right","右边"},{"insert","插入"} };//初始化列表
	unordered_map<string, string> um2(um1);//拷贝构造
	unordered_map<string, string> um3;
	um3 = um1;//赋值

	return 0;
}

2）Iterators

unordered_map的底层是哈希桶，是单向链表，因此只支持单向迭代器。

#include<iostream>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_map<string, string> um1 = { {"left","左边"},{"right","右边"},{"insert","插入"} };

	unordered_map<string, string>::iterator it = um1.begin();
	while (it != um1.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}

	return 0;
}

运行结果：

3）Element access

相较于unordered_set，unordered_map还重载了[ ]，可以通过[ ]实现插入、修改、查找等等作用。

函数声明 接口说明
operator[ ] 访问元素 
#include<iostream>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_map<string, string> um1 = { {"left","左边"},{"right","右边"},{"insert","插入"} };
	um1["front"] = "前面";//插入
	um1["insert"] = "插入元素";//修改
	cout << um1["front"] << endl;//访问

	for (auto e : um1)
	{
		cout << e.first << ":" << e.second << endl;
	}

	return 0;
}

运行结果：

4）Element lookup

unordered_map还支持find接口。

#include<iostream>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_map<string, string> um = { {"left","左边"},{"right","右边"},{"insert","插入"} };

	auto it = um.find("left");//查找
	cout << it->first << ":" << it->second << endl;

	return 0;
}

运行结果：
在这里插入图片描述

5）Modifiers

unordered_map还支持插入、删除接口。

#include<iostream>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_map<string, string> um = { {"left","左边"},{"right","右边"},{"insert","插入"} };
	um.insert({ "back","后面" });//插入
	um.erase("right");//删除

	for (auto e : um)
	{
		cout << e.first << ":" << e.second << endl;
	}
	
	return 0;
}

运行结果：

6）Buckets

函数声明 接口说明
bucket_count 返回桶的数量
max_bucket_count 返回桶的最大数量
bucket_size 返回桶的大小
bucket 定位元素所在的桶 
#include<iostream>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_map<string, string> um = { {"left","左边"},{"right","右边"},{"insert","插入"} };
	cout << um.bucket_count() << endl;//桶的数量
	cout << um.max_bucket_count() << endl;//桶的最大数量
	cout << um.bucket_size(0) << endl;//桶0的大小
	cout << um.bucket("left") << endl;//"left"所在的桶

	return 0;
}

运行结果：

7）Hash policy

函数声明 接口说明
load_factor 返回负载因子
max_load_factor 获取或设置最大负载因子
rehash 设置桶的数量
reserve 更改容量，与rehash用法近似，都起到设置桶的数量的作用 
#include<iostream>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_map<string, string> um = { {"left","左边"},{"right","右边"},{"insert","插入"} };
	cout << um.load_factor() << endl;//负载因子
	cout << um.max_load_factor() << endl;//最大的负载因子

	cout << um.bucket_count() << endl;

	um.rehash(20);//设置桶的数量
	cout << um.bucket_count() << endl;

	um.reserve(20);//更改容量
	cout << um.bucket_count() << endl;

	return 0;
}

运行结果：

4、unordered_map和map的差异

  • unordered_map和map的第⼀个差异是对key的要求不同，map要求Key⽀持⼩于⽐较，而unordered_map要求Key⽀持转成整形且⽀持等于⽐较，这本质是哈希表的要求。
  • unordered_map和map的第⼆个差异是迭代器的差异，map的iterator是双向迭代器，unordered_map是单向迭代器，其次map底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以map迭代器遍历是Key有序+去重。⽽unordered_map底层是哈希表，迭代器遍历是Key⽆序+去重。
  • unordered_map和map的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_map的增删查改更快⼀些，因为红⿊树增删查改效率是O(logN) ，⽽哈希表增删查平均效率是O(1)。

5、 unordered_multimap/unordered_multiset

  • unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，⽀持Key冗余。
  • unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个⽅⾯的差异，key的要求的差异，iterator及遍历顺序的差异，性能的差异。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布