【C++深度探索】unordered_set、unordered_map封装

2024-08-29 08:36:08 浏览数 (1)

前言

  前面我们学习过红黑树实现map、set的封装，而unordered_set和unordered_map的功能与map和set类似，所不同的是其存储元素是无序的，底层是使用哈希表，所以今天我们就可以利用之前学习过的哈希表的实现，来对C STL库中的unordered_set和unordered_map进行模拟实现。

1. unordered_set和unordered_map介绍

  在C 98中，STL提供了底层为红黑树结构的一系列关联式容器，例如：map、set。在查询时效率可达到

log_2 N

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

✨unordered_map介绍

介绍文档，点击跳转

  1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过key快速的索引到与其对应的value。
  2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
  3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
  4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
  5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。

unordered_map和map核心功能重复90%，它们区别在于：

  1. 对键值对中key要求不同：
  • map：key要支持比较大小
  • unordered_map：key要支持转换成整型 比较相等
  1. map遍历有序，unordered_map遍历无序
  2. map有双向迭代器，unordered_map单向迭代器
  3. 它们之间性能有差异

unordered_map常见接口：

函数声明

功能介绍

unordered_map()

构造不同格式的unordered_map对象

bool empty() const

检测unordered_map是否为空

size_t size() const

获取unordered_map的有效元素个数

begin

返回unordered_map第一个元素的迭代器

end

返回unordered_map最后一个元素下一个位置的迭代器

cbegin

返回unordered_map第一个元素的const迭代器

cend

返回unordered_map最后一个元素下一个位置的const迭代器

operator[]

返回与key对应的value

iterator find(const K& key)

返回key在哈希桶中的位置

size_t count(const K& key)

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

insert

向容器中插入键值对

erase

删除容器中的键值对

void clear()

清空容器中有效元素个数

void swap(unordered_map&)

交换两个容器中的元素

size_t bucket_count()const

返回哈希桶中桶的总个数

size_t bucket_size(size_t n)const

返回n号桶中有效元素的总个数

size_t bucket(const K& key)

返回元素key所在的桶号

注意：operator[]函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。这与之前的map类似，插入函数返回一个键值对，键存放指针，对存放bool值，用来判断是否插入成功。

✨unordered_set介绍

文档介绍，点击跳转   unordered_set与unordered_map类似，不同在于前者储存单个数据，后者储存键值对，这里就不过多介绍。

2. 修改哈希表

  因为我们要使用哈希表来实现对unordered_set和unordered_map的封装，之前实现的哈希表都是插入键值对，是没办法很好封装unordered_set的，所以我们先得对哈希表进行改造，改造类似于使用红黑树封装map和set对红黑树的改造，具体实现如下：

我们之前模拟实现过哈希表，插入的节点是键值对pair类型，而如果要使用哈希表来对unordered_set和unordered_map封装的话，unordered_set存储的应该是单个值，而不是键值对，所以我们就需要对哈希表进行修改，使得unordered_set和unordered_map都能适用：

  1. 首先哈希表存储节点的类需要从只能存储键值对改为能够存储任意数据：
  • 修改前：
代码语言：javascript复制
template<class K,class V>
struct HashNode
{
	pair<K, V> _kv;
	HashNode<K, V>* _next;

	HashNode(const pair<K, V>& kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};
  • 修改后：
代码语言：javascript复制
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};
  1. 相应的，哈希表的模板参数也需要修改：
  • 修改前：
代码语言：javascript复制
//哈希表类
template<class K,class V, class Hash = HashFunc<K>>
class HashTable {
public:
	typedef HashNode<K,V> Node;
	Node* Find(const K& key);//查找函数
	
private:
	vector<Node*> _tables;
	size_t _n;//记录存储数据个数
};

 因为节点类只有一个模板参数了，所以哈希表前面两个模板参数有点多余，但是如果将哈希表的模板参数也改为一个，如下面代码所示：

代码语言：javascript复制
//哈希表
template<class T,class Hash = HashFunc<T>>
class HashTable 
{
public:
	typedef HashNode<T> Node;
	Node* Find(const T& key);//？查找函数
	
private:
	vector<Node*> _tables;
	size_t _n;//记录存储数据个数
};

 那么对于class Hash这个模板参数不可能也传入一个键值对，此外在实现查找上面代码中的Find函数时，对于unordered_map查找时Find函数参数就得传一个完整的键值对，我们不可能把完整的键值对全部传过去查找，这样查找就没有意义，我们只需要获得键值对的键查找到相应的键值对即可，所以我们还应该传一个模板参数用于传给class Hash、Find和Erase函数：

代码语言：javascript复制
//哈希表
template<class K,class T,class Hash = HashFunc<K>>//K存储键，T存储键值对
class HashTable 
{
public:
	typedef HashNode<T> Node;//传入键值对
	Node* Find(const K& key);//查找函数，只传键
	pair<Node*,bool> Insert(const T& data);//插入，传入T
	bool Erase(const K& key);//删除，只传键
private:
	vector<Node*> _tables;
	size_t _n;//记录存储数据个数
};

这样对于不同函数的需求就可以传入不同的模板参数了

函数 c++ 存储 map set

0 人点赞