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

文章目录

  • 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提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2 N log2N,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在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( l o g 2 N log_2 N log2N),搜索的效率取决于搜索过程中元素的比较次数。

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

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

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

例如有一个数组arr[ ]={ 4 , 9 , 17 , 28 , 16 , 22 , 13 , 10 };
哈希函数设置为:hash(key) = key % capacity( capacity为存储元素底层空间总的大小)。
在这里插入图片描述
用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快,
但是如果我们再插入一个数7,就会和存放17的位置冲突,这个就引发了哈希冲突

2.2哈希冲突

对于两个数据元素的关键字 k i k_i ki k j k_j kj(i != j),有 k i k_i ki != k j k_j kj,但有:Hash( k i k_i ki) ==
Hash( k j k_j kj),即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

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的元素,即发生哈希冲突。
    线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素。
在这里插入图片描述
删除
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影
响。因此线性探测采用标记的伪删除法来删除一个元素。(例如使用枚举,列出三种状态(存在,不存在,已删除))

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

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

  1. 二次探测
    二次探测就是与线性探测寻找下一个位置的方法不同而已。
    线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题
    *找下一个空位置的方法为: H i H_i Hi = ( H 0 H_0 H0 + i 2 i^2 i2 )% m, 或者: H i H_i Hi = ( H 0 H_0 H0 - i 2 i^2 i2 )% m。其中:i = 1,2,3…, H 0 H_0 H0是通过散列函数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
	};

本章完~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515759.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

66toolkit终极网络工具系统:470+强大Web工具,助力您的网络运营与开发

一、产品介绍 66toolkit&#xff0c;被誉为“终极网络工具系统”&#xff08;SAAS&#xff09;&#xff0c;是一款功能强大的PHP脚本。它集合了超过470种快速且易用的Web工具&#xff0c;为日常任务处理和开发人员提供了极大的便利。作为一款综合性的网络工具系统&#xff0c;…

面试题目--fork

问题&#xff1a; (1)fork 以后&#xff0c;父进程打开的文件指针位置在子进程里面是否一样&#xff1f;(先open再fork) (2)能否用代码简单的验证一下? (3)先fork再打开文件父子进程是否共享偏移量?父进程打开的文件指针位置在子进程里面是否一样&#xff1f;能否用代码简…

武汉星起航:引领亚马逊孵化新篇章,助力合作伙伴共创商业辉煌

武汉星起航电子商务有限公司自2020年成立以来&#xff0c;凭借其敏锐的市场洞察和深度合作模式&#xff0c;在跨境电商领域取得了显著的成绩。为了进一步满足市场需求&#xff0c;公司决定推出亚马逊一站式孵化平台&#xff0c;为合作伙伴提供更全面的指导和支持。 该孵化平台…

【办公类-47-01】20240404 Word内部照片批量缩小长宽(课题资料系列)

作品展示 背景需求 最近在做《运用Python优化3-6岁幼儿学习操作材料的实践研究》的课题研究资料&#xff08;上半学期和下半学期&#xff09;。 将CSDN里面相关的研究照片文字贴入Word后&#xff0c;就发现一张图片就占了A4竖版一页&#xff0c;太大了。我想把word里面的所有…

数学结论在dsa中的应用

1. LC 3102 最小化曼哈顿距离 VP周赛391 T4。这是个结论题目。 首先曼哈顿距离是需要两个数对而不是两个数去进行比较的&#xff0c;两个数之间你很轻易就知道差的绝对值最大是多少了&#xff0c;只要挑最大和最小两个数一减就可以了。 但是两个数对之间各项差的绝对值之和最…

Spring的注入小技巧(接口前置处理,后置处理等优化写法)

目录 1.定一个公共&#xff08;前置、后置&#xff09;接口 2.添加接口的实现类&#xff08;就是不同的处理&#xff09; 3.测试小栗子 4.执行结果 接口的前置处理或是后置处理&#xff0c;这样写代码更优雅&#xff0c;可读性高&#xff0c;当然更有水平更装逼。前置处理或…

【信号处理】基于变分自编码器(VAE)的图片典型增强方法实现

关于 深度学习中&#xff0c;经常面临图片数据量较小的问题&#xff0c;此时&#xff0c;对数据进行增强&#xff0c;显得比较重要。传统的图片增强方法包括剪切&#xff0c;增加噪声&#xff0c;改变对比度等等方法&#xff0c;但是&#xff0c;对于后端任务的性能提升有限。…

运算符规则

console.log(null undefined) null和undefined都是原始类型&#xff0c;然后把这两个转换为数字。是0NaN.看规则有一个NaN的话就得到NaN. console.log({} []); 把{}和[]转换为原始类型分别为和[Object Object]。然后特殊情况有字符串&#xff0c;那就拼接字符串返回[Object…

Redis数据库——群集(主从、哨兵)

目录 前言 一、主从复制 1.基本原理 2.作用 3.流程 4.搭建主动复制 4.1环境准备 4.2修改主服务器配置 4.3从服务器配置&#xff08;Slave1和Slave2&#xff09; 4.4查看主从复制信息 4.5验证主从复制 二、哨兵模式——Sentinel 1.定义 2.原理 3.作用 4.组成 5.…

【Java多线程(3)】线程安全问题和解决方案

目录 一、线程安全问题 1. 线程不安全的示例 2. 线程安全的概念 3. 线程不安全的原因 二、线程不安全的解决方案 1. synchronized 关键字 1.1 synchronized 的互斥特性 1.2 synchronized 的可重入特性 1.3 死锁的进一步讨论 1.4 死锁的四个必要条件&#xff08;重点&…

Golang 内存管理和垃圾回收底层原理(一)

一、这篇文章我们来聊聊Golang内存管理和垃圾回收&#xff0c;主要注重基本底层原理讲解&#xff0c;进一步实战待后续文章 1、这篇我们来讨论一下Golang的内存管理 先上结构图 从图我们来讲Golang的基本内存结构&#xff0c;内存结构可以分为&#xff1a;协程缓存、中央缓存…

vue3+eachrts饼图轮流切换显示高亮数据

<template><div class"charts-box"><div class"charts-instance" ref"chartRef"></div>// 自定义legend 样式<div class"charts-note"><span v-for"(items, index) in data.dataList" cla…

jdbc连SQL server,显示1433端口连接失败解决方法

Exception in thread "main" com.microsoft.sqlserver.jdbc.SQLServerException: 通过端口 1433 连接到主机 localhost 的 TCP/IP 连接失败。错误:“connect timed out。请验证连接属性。确保 SQL Server 的实例正在主机上运行&#xff0c;且在此端口接受 TCP/IP 连接…

移动WEB开发之rem适配布局

一、rem 基础 rem 单位 rem (root em)是一个相对单位&#xff0c;类似于em&#xff0c;em是父元素字体大小。不同的是rem的基准是相对于html元素的字体大小。比如&#xff0c;根元素&#xff08;html&#xff09;设置font-size12px; 非根元素设置width:2rem; 则换成px表示就是2…

页面自适应

后续整理下自适应的集中方法 地址

【数据库】MySQL InnoDB存储引擎详解 - 读书笔记

MySQL InnoDB存储引擎详解 - 读书笔记 InnoDB 存储引擎概述InnoDB 存储引擎的版本InnoDB 体系架构内存缓冲池LRU List、Free List 和 Flush List重做日志缓冲&#xff08;redo log buffer&#xff09;额外的内存池 存储结构表空间系统表空间独立表空间通用表空间undo表空间临时…

如何彻底删除node和npm

如何彻底删除node和npm 前言&#xff1a; 最近做个项目把本地的node更新了&#xff0c;之前是v10.14.2更新至v16.14.0 &#xff0c;想着把之前的项目起来下&#xff0c;执行npm install 结果启动不了&#xff0c;一直报npm版本不匹配需要更新本地库异常… 找了几天发现是npm 和…

基于JAVA的汽车售票网站论文

摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对汽车售票信息管理混乱&#xff0c;出错率高&#xff0c;信息安全性差…

从零到百万富翁:ChatGPT + Pinterest

原文&#xff1a;Zero to Millionaire Online: ChatGPT Pinterest 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 在社交媒体上赚取百万美元 - 逐步指南&#xff0c;如何在线赚钱版权 献给&#xff1a; 我将这本书&#xff0c;“从零到百万富翁在线&#xff1a;Chat…

Netty经典32连问

文章目录 1、Netty是什么&#xff0c;它的主要特点是什么&#xff1f;2、Netty 应用场景了解么&#xff1f;3、Netty 核心组件有哪些&#xff1f;分别有什么作用&#xff1f;4、Netty的线程模型是怎样的&#xff1f;如何优化性能&#xff1f;5、EventloopGroup了解么?和 Event…