1. AI技术聚合首页
  2. IT

【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装

心中带点小风骚 • • IT • 阅读 31

文章目录

  • 1. unordered系列关联式容器
      • 1.1 unordered_map
      • 1.2 unordered_set
      • 1.3.底层结构
  • 2.哈希
      • 2.1哈希概念
      • 2.2哈希冲突
      • 2.3 哈希函数
      • 2.4 哈希冲突解决
        • 2.4.1闭散列
        • 2.4.1开散列
        • 2.5开散列与闭散列比较
  • 3.哈希的模拟实现
      • 1. 模板参数列表
      • 2. 迭代器的实现
      • 3. 增加通过key获取value操作
      • 4. 哈希实现总代码：
  • 4.用实现的哈希封装unordered_map与unordered_set前的模板参数的梳理及相关联系的梳理
  • 5.unordered_map的封装实现
  • 6.unordered_set的封装实现

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🐵系列专栏：零基础学习C语言—– 数据结构的学习之路—-C++的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
————————————————

文章简介：

本篇博文主要会涉及到STL关联式容器，unordered系列关联式容器，unordered_set和unordered_map的底层数据结构，哈希表的底层及迭代器实现，以及在其上对unordered_set****和unordered_map的封装。

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，分别为：unordered_map与unordered_set和unordered_multimap与unordered_multiset 这四个容器，他们与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

  1. unordered_map和unordered_set与map与set类似，map与set是有序的，但是unordered系列都不是有序的，但是也不允许出现重复值。
  2. unordered_multimap和unordered_multiset与unordered_map和unordered_set类似，unordered_map和unordered_set不允许重复值出现，但是multi系列是允许重复值出现的。
  3. 只要是前缀带了unordered的就是无序，后缀带了multi的就是允许键值重复。
  4. 他们在使用方面上与set与map非常类似，这里不作详解。

1.1 unordered_map

unordered_map的文档介绍链接: link

文档说明：

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

1.2 unordered_set

unordered_mset的文档介绍链接: link

1.3.底层结构

STL关联式容器中：
set和map的底层数据结构为红黑树，因为map和set要求是自动排序的，红黑树能够实现这一功能，并且各个操作的时间复杂度都较低，而unordered_set和unordered_map的底层数据结构为哈希表，查找时间复杂度为常数级。

2.哈希

2.1哈希概念

顺序结构以及平衡树中，元素 关键码 与其 存储位置 之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的 存储位置 与它的 关键码 之间能够建立一一 映射 的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

例如有一个数组arr[ ]={ 4 , 9 , 17 , 28 , 16 , 22 , 13 , 10 };
哈希函数设置为：hash(key) = key % capacity（ capacity为存储元素底层空间总的大小）。

2.2哈希冲突

对于两个数据元素的关键字【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装和 【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装(i != j)，有【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装 != 【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装，但有：Hash(【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装) ==
Hash(【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

2.3 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：

  1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。
  2. 哈希函数计算出来的地址能均匀分布在整个空间中
  3. 哈希函数应该比较简单

常见哈希函数
这里只讲解常用的几种方法

  1. 直接定址法
    取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
    优点：简单、均匀
    缺点：需要事先知道关键字的分布情况
    使用场景：适合查找比较小且连续的情况
    面试题：字符串中第一个只出现一次字符

例如：数组arr[ ]={ 1 , 4 , 6 , 2 , 8 }; 假设线性函数我们取：Hash(key) = 2*key+1。
那么：Hash(6)=2 *1+1=13; 就把 6 存放到哈希表中对应映射位置为 13 的位置中，这样如果我们想要快速找元素6时，就可以直接利用该函数找到地址。

  1. 除留余数法
    设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

例如有一个数组arr[ ]={ 4 , 9 , 17 , 28 , 16 , 22 , 13 , 10 };
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

2.4 哈希冲突解决

解决哈希冲突两种常见的方法是： 闭散列 和 开散列

2.4.1闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置
呢？

  1. 线性探测
    现在需要插入元素44（如下图），先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
    线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};

线性探测优点：实现非常简单（就不实现了，重点实现后面的开散列）
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
如何缓解呢？

  1. 二次探测
    二次探测就是与线性探测寻找下一个位置的方法不同而已。
    线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题
    *找下一个空位置的方法为:【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装 = (【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装 + 【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装 )% m, 或者：【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装 = (【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装 – 【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装 )% m。其中：i = 1,2,3…， 【C++学习】哈希表的底层实现及其在unordered_set与unordered_map中的封装是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

研究表明：当表的长度为质数且表装载因子a（存放的数据个数/最多能存放的数据个数）不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：闭散列 最大的 缺陷 就是 空间利用率比较低，这也是哈希的缺陷。

2.4.1开散列
  1. 开散列概念
    开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

  1. 开散列实现
template<class K>
struct Hashfunc       //整型数据不用转换
{ 
	size_t operator()(const K& key)
	{
		return (size_t)key;    //直接返回
	}
};
template<>                     //特化
struct Hashfunc<string>         //如果为字符串类型，需要将其转化为整形
{
	size_t operator()(const string& s)
	{
		size_t hashi = 0;
		for (auto e : s)
		{
			hashi += e;
			hashi *= 131;       //这里13 131 1313.....都可以
		}
		return hashi;          //转换为整型返回
	}
};
template<class K, class V>     //储存数据的节点
struct HashNode
{
	HashNode(const pair<K, V>& kv)
		:_next(nullptr)
		, _kv(kv)
	{}

	HashNode<K, V>* _next;    //指向写一个节点的指针
	pair<K, V> _kv;           //数据
};

template<class K,class V,class HFunc = Hashfunc<K>>
class HashTable
{
	typedef HashNode<K, V> Node;
public:
	HashTable(size_t size = 10)
	{
		_table.resize(size, nullptr);
		_n = 0;
	}
	插入函数的实现(这里只有插入函数，扩容与检查函数文章后面会有)
	bool insert(const pair<K,V>& kv)
	{
		//1.查重，如果已经存在，不用插入了
		
		//2.检查是否需要扩容
		
		//3.插入代码
		Hashfunc<K> HFunc;         //转换能取模的整型
		size_t hashi = HFunc(kv.first) % _table.size();
		if (_table[hashi])   //如果不为bullptr，则说明改位置已经有数据了，直接头插
		{                            //因为单链表的头插效率高
			//头插
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;

			++_n;
			return true;
		}
		else       //如果为nullptr，则说明该位置还没有数据，直接插入
		{
			Node* newnode = new Node(kv);
			_table[hashi] = newnode;

			++_n;
			return true;
		}
	}
      删除函数的实现
	bool Erase(const K& key)
	{
		Hashfunc<K> HFunc;          //转换能取模的整型
		size_t hashi = HFunc(key) % _table.size();   //找到该元素对应到哈希表中的位置
		if (_table[hashi])            //如果不为空，则说明有元素
		{
			Node* cur = _table[hashi];
			Node* parent = nullptr;     //保存上一个节点，因为如果不是第一个节点需要链接
			while (cur)                 //寻找要删除的元素的节点
			{
				if (cur->_kv.first == key)      //找到了
				{
					if (cur == _table[hashi]){   //如果是第一个节点，特殊处理
						delete cur;
						_table[hashi] = nullptr;
						_n--;
						return true;
					}
					else{                       //不是第一个节点
						if(parent)
							parent->_next = cur->_next;   //链接
						delete cur;
						_n--;
						return true;
					}
				}
				parent = cur;
				cur = cur->_next;
			}
			return false;
		}
		else{
			return false;
		}
	}
private:
	vector<Node*> _table;      ///表
	size_t _n;         //记录储存的有效数据个数
};

  1. 开散列增容
    桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

  2. 数据类型为非整型时的定址方法
    因为%取模的操作数只能是整型，那么当我们存储的数据类型为string或则Date(日期类)时，应该怎样去计算位置呢？
    这时，如果存储的数据不是整型的时候，就需要先转换为整型再定址；

2.5开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：
由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

3.哈希的模拟实现

1. 模板参数列表

// K:关键码类型
// T: 不同容器T的类型不同，如果是unordered_map，T代表一个键值对，如果是unordered_set,T为 K
// KeyOfValue: 因为T的类型不同，通过value取key的方式就不同，详见见unordered_map/set的实现
// HFunc : 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
template<class K, class T, class KeyofT, class HFunc = Hashfunc<K> >
class HashTable;

2. 迭代器的实现

解析：

  1. 因为我们实现的hashTable是开散列的，底层是一个数组，数组里面存储的一个一个的节点，节点下面有可能挂着一个哈希桶；迭代器的实现必须要实现 ++，*，!= 操作，++ 指向下一个节点的，这里如果迭代器里面我们只选择封装一个节点的指针的话，那么如果当这个节点是一个哈希桶里面的最后一个节点时，则没有办法找到下一个节点，所以需要加一个哈希表的地址，当然也可以是哈希表中存放节点指针的vector；
    其中下一个节点的寻找方法：

    1. 判断当前节点的下一个节点是否为空，如果不为空，则让其指向下一个节点即可，如果当前节点的下一个节点为空，则需要步骤二。
    2. 计算出当前节点所在哈希表中的下标（哈希地址），向后寻找数组中不为空的位置，让其指向该位置。

  2. 因为我们需要访问HashTable里面的私有成员（vector<Node*> ），所以需要将迭代器设置成HashTable的友元类。

代码实现：

template<class K, class T, class KeyofT, class HFunc>        //前置声明，因为迭代器需要一HashTable的一个指针，需要使用到HashTable，编译器默认向上找，如果不加前置声明，则会找不到报错                            
class HashTable;                                                    

template<class K, class T, class KeyofT,class HFunc = Hashfunc<K>>
struct Iterator
{
	typedef HashTable<K, T, KeyofT, HFunc> HashTable;
	typedef Iterator<K, T, KeyofT,HFunc> Self;
	typedef HashNode<T> Node;       //存放数据的节点

	Node* _node;          //节点指针
	HashTable* _ht;        //哈希表

	Iterator(Node* node, HashTable* ht)
		:_node(node)
		,_ht(ht)
	{}

	T& operator*()
	{
		return _node->_date;
	}
	T* operator->()
	{
		return &_node->_date;
	}
	Self& operator++()
	{
		KeyofT kot;
		if (_node->_next)   //如果该节点的下一个节点存在
		{
			_node = _node->_next;
		}
		//找下一个桶
		else
		{
			Hashfunc<K> Hfunc;
			size_t hashi = Hfunc(kot(_node->_date)) % _ht->_table.size();
			hashi++;
			while (hashi < _ht->_table.size())
			{
				if (_ht->_table[hashi])
				{
					_node = _ht->_table[hashi];
					break;
				}
				hashi++;
			}
			if (hashi == _ht->_table.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}	
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};

3. 增加通过key获取value操作

//map
struct mapKeyofT
{
	const K& operator()(const pair<K, V>& kv)
	{
		return kv.first;
	}
};

///set
struct setKeyofT
{
	const K& operator()(const K& key)
	{
		return key;
	}
};

4. 哈希实现总代码：

#pragma once
#include<iostream>
#include<string>
#include<vector>

using namespace std;


template<class T>
struct HashNode
{
	HashNode(const T& date)
		:_next(nullptr)
		, _date(date)
	{}

	HashNode<T>* _next;
	T _date;
};

template<class K>
struct Hashfunc       //整型数据不用转换
{ 
	size_t operator()(const K& key)
	{
		return (size_t)key;    //直接返回
	}
};
template<>                     //特化
struct Hashfunc<string>         //如果为字符串类型，需要将其转化为整形
{
	size_t operator()(const string& s)
	{
		size_t hashi = 0;
		for (auto e : s)
		{
			hashi += e;
			hashi *= 131;       //这里13 131 1313.....都可以
		}
		return hashi;          //转换为整型返回
	}
};
///迭代器的实现
template<class K, class T, class KeyofT, class HFunc>        //前置声明
class HashTable;                                                    

template<class K, class T, class KeyofT,class HFunc = Hashfunc<K>>
struct Iterator
{
	typedef HashTable<K, T, KeyofT, HFunc> HashTable;
	typedef Iterator<K, T, KeyofT,HFunc> Self;
	typedef HashNode<T> Node;

	Node* _node;
	HashTable* _ht;

	Iterator(Node* node, HashTable* ht)
		:_node(node)
		,_ht(ht)
	{}

	T& operator*()
	{
		return _node->_date;
	}
	T* operator->()
	{
		return &_node->_date;
	}
	Self& operator++()
	{
		KeyofT kot;
		if (_node->_next)
		{
			_node = _node->_next;
		}
		//找下一个桶
		else
		{
			Hashfunc<K> Hfunc;
			size_t hashi = Hfunc(kot(_node->_date)) % _ht->_table.size();
			hashi++;
			while (hashi < _ht->_table.size())
			{
				if (_ht->_table[hashi])
				{
					_node = _ht->_table[hashi];
					break;
				}
				hashi++;
			}
			if (hashi == _ht->_table.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}	
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};
 
template<class K, class T, class KeyofT, class HFunc = Hashfunc<K>>
class HashTable
{
	typedef HashNode<T> Node;
public:
	template<class K, class T, class KeyofT, class HFunc>
	friend struct Iterator;
	typedef Iterator<K, T, KeyofT, HFunc> iterator;

	iterator begin()
	{
		for (int i = 0; i <_table.size(); i++)
		{
			if (_table[i])
			{
				return iterator(_table[i], this);
			}
		}
		return end();
	}
	iterator end()
	{
		return iterator(nullptr, this);
	}

	HashTable(size_t size = 10)
	{
		_table.resize(size, nullptr);
		_n = 0;
	}
	~HashTable()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i])
			{
				Node* cur = _table[i];
				Node* next = nullptr;
				while (cur)
				{
					next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}
	}

	pair<iterator,bool> insert(const T& date)
	{
		KeyofT kot;
		//查重，如果已经存在，不用插入了
		Node* ret = find(kot(date));
		if (ret)
		{
			return make_pair(iterator(ret,this), false);
		}
		//扩容   
		if (_n == _table.size())
		{
			vector<Node* > newtable(2 * _table.size(), nullptr);         //创建一个新的newtable
			Hashfunc<K> HFunc;
			for (size_t i = 0; i < _table.size(); i++)              //遍历原hashtable，将节点移到新的hastable里
			{
				if (_table[i])                                  //如果不为空，则移动节点到新表的对应位置上
				{
					Node* cur = _table[i];
					while (cur)
					{
						//头插到新表对应位置
						size_t hashi = HFunc(kot(cur->_date)) % newtable.size();

						Node* next = cur->_next;
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;

						cur = next;
					}
					_table[i] = nullptr;       //移动完后，将原表中映射位置置空
				}
			}               
			_table.swap(newtable);          //调用vector的的swap函数完成交换
		}
		//插入代码
		Hashfunc<K> HFunc;
		size_t hashi = HFunc(kot(date)) % _table.size();
		if (_table[hashi])
		{
			//头插
			Node* newnode = new Node(date);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;

			++_n;
			return make_pair(iterator(newnode,this),true);
		}
		else
		{
			Node* newnode = new Node(date);
			_table[hashi] = newnode;

			++_n;
			return make_pair(iterator(newnode, this), true);
		}
	}
	//查找
	Node* find(const K& key)
	{
		KeyofT kot;
		Hashfunc<K> HFunc;
		size_t hashi = HFunc(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (kot(cur->_date) == key)
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		Hashfunc<K> HFunc;
		size_t hashi = HFunc(key) % _table.size();
		if (_table[hashi])
		{
			Node* cur = _table[hashi];
			Node* parent = nullptr;
			while (cur)
			{
				KeyofT kot;
				if (kot(cur->_date) == key)      //找到了
				{
					if (cur == _table[hashi])   //是第一个节点
					{
						delete cur;
						_table[hashi] = nullptr;
						_n--;

						return true;
					}
					else                       //不是第一个节点
					{
						if(parent)
							parent->_next = cur->_next;
						delete cur;
						_n--;

						return true;
					}
				}
				parent = cur;
				cur = cur->_next;
			}
			return false;
		}
		else
		{
			return false;
		}
	}

private:
	vector<Node*> _table;           //表
	size_t _n;                     //记录储存的有效数据个数
};

4.用实现的哈希封装unordered_map与unordered_set前的模板参数的梳理及相关联系的梳理

我们是想要用同一个哈希表封装出不同的容器（unordered_map与unordered_set），所以就需要对相关操作参数及操作做出改变。

  1. unordered_map与unordered_set存储的数据类型不同，unordered_map存储的是pair<K,V> ，K为key的类型，V为value的类型而unordered_set，存储的是K，所以就需要对节点所存储的数据类型做出改变，如图：
  2. 因为unordered_map中的key为pair中的第一个数据，而unordered_set中存储的数据就是key，所以当在需要取出数据里面的key进行操作时，unordered_map与unordered_set取出的方法有差异，所以需要各自提供一个仿函数来实现：如图：

5.unordered_map的封装实现

#pragma once
#include"HashTable.h"
namespace map
{
	template<class K, class V, class HFunc = Hashfunc<K>>
	class unorderedmap
	{
		struct mapKeyofT              //取数据中的key，即pair<K,V>中的k
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<K, V>, mapKeyofT, HFunc>::iterator iterator;

		pair<iterator,bool> insert(const pair<K, V>& kv)
		{
			return _ht.insert(kv);
		}
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.insert(make_pair(key,V()));

			return (ret.first)->second;
		}
	private:
		HashTable<K, pair<K, V>, mapKeyofT, HFunc> _ht;    //需要用自己的mapKeyofT去实例化一个HashTable
	};

6.unordered_set的封装实现

#pragma once
#include"HashTable.h"
namespace set
{
	template<class K, class HFunc = Hashfunc<K>>
	class unorderedset
	{
		struct setKeyofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<K, K, setKeyofT, HFunc>::iterator iterator;

		pair<iterator, bool> insert(const K& key)
		{
			return _ht.insert(key);
		}

		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}

	private:
		HashTable<K, K, setKeyofT, HFunc> _ht;   //需要用自己的setKeyofT去实例化一个HashTable
	};

本章完~

版权声明：本文为博主作者：Jupiter·原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/2301_77509762/article/details/137358612

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
心中带点小风骚的头像心中带点小风骚普通用户
0
上一篇 2024年4月16日
下一篇 2024年4月16日

相关推荐