C++ 哈希

目录

1. 哈希概念

2. 哈希冲突

3. 哈希函数

4. 哈希冲突解决

4.1 闭散列

4.2 开散列

4.3 对于哈希表的补充

5. 开散列与闭散列比较

6. 哈希表的模拟实现以及unorder_set和unorder_map的封装

1. 哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数。

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

插入元素时： 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

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

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

2. 哈希冲突

在上面的例子中hash(4) = 4%10 = 4,hash(14) = 14%10 = 4,hash(4) == hash(14)。

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”

3. 哈希函数

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

哈希函数设计原则：

1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

2. 哈希函数计算出来的地址能均匀分布在整个空间中

3. 哈希函数应该比较简单

常见哈希函数

1.. 直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀         缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

2. 除留余数法

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

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

4. 哈希冲突解决

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

4.1 闭散列

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

1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入：

通过哈希函数获取待插入元素在哈希表中的位置

如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突， 使用线性探测找到下一个空位置，插入新元素

删除：

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，14查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

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

enum State{EMPTY, EXIST, DELETE};

扩容：散列表的载荷因子：e = 填入表中的元素个数 / 散列表的长度

e的值越大，发生哈希冲突的可能性越大

线性探测优点：实现非常简单

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

2. 二次探测：从发生冲突的位置开始，向后探测，但不是依次探测，而是每次向后找i^2(i = 1,2,3……)位置

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任 何一个位置都不会被探查两次。

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

闭散列的实现：

enum state
{
	EMPTY,
	EXITE,
	DELETE
};

template<class K, class V>
struct Hash_Ndoe
{
	//Hash_Ndoe(const pair<K, V>& kv)
	//	:_state(EMPTY),
	//	_kv(kv)
	//{}

	pair<K, V> _kv;
	state _state = EMPTY;

};

template<class K, class V>
class Hash
{
	typedef Hash_Ndoe<K, V> Node;
public:

	bool Insert(const pair<K, V>& kv)
	{
		//判断空间是否足够
		size_t _v_size = _v.size();
		if (_v_size == 0)
		{
			_v.resize(10);
		}
		else if (_n * 10 / _v_size > 7)
		{
			size_t newsize = _v_size * 2;
			Hash<K, V> newhash;
			newhash._v.resize(newsize);
			for (int i = 0; i < _v_size; ++i)
			{
				if (_v[i]._state == EXITE)
					newhash.Insert(_v[i]._kv);
			}
			_v.swap(newhash._v);
		}

		_v_size = _v.size();
		//找到对应位置
		size_t index = kv.first % _v_size;
		//线性探测
		int x = 1;
		while (_v[index]._state == EXITE)
		{
			if (_v[index]._kv.first == kv.first)
				return false;
			index = index + x;
			index %= _v_size;
		}
		_v[index]._kv = kv;
		_v[index]._state = EXITE;
		_n++;
		return true;

	}

	Node* Find(const K& key)
	{
		size_t _v_size = _v.size();
		if (_v_size == 0)
			return nullptr;
		size_t index = key % _v_size;
		size_t flag = index;
		int x = 1;
		while (_v[index]._state != EMPTY)
		{
			if (_v[index]._state == EXITE && _v[index]._kv.first == key)
				return &_v[index];
			index = index + x;
			index %= _v_size;
			if (flag == index)
				break;
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		Node* ret = Find(key);
		if (ret == nullptr)
			return false;

		ret->_state = DELETE;
		_n--;
		return true;
	}


private:
	vector<Node> _v;
	size_t _n = 0;
};

4.2 开散列

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

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

3. 开散列增容 桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可 能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希 表进行增容，那该条件怎么确认呢？

开散列最好的情况是：每个哈希桶中刚好挂一个节点， 再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。e == 1

4.3 对于哈希表的补充

1. key的类型只能是能被%的类型，那其他类型怎么办

开一个模板接口，传仿函数，仿函数的返回值为整形

2. 如果一个类型没有重载==，或者类型的==并不是你想要的，怎么找到对应的值

再开一个模板接口，传仿函数，仿函数的返回值为整形

3. 除留余数法，最好模一个素数

template<class K, class V>
struct HashTableNode
{
	pair<K, V> _kv;
	HashTableNode<K, V>* _next;

	HashTableNode(const pair<K, V>& kv)
		:_kv(kv),
		_next(nullptr)
	{}
};
	
template<class T>
struct HashFcn
{
	size_t operator()(const T& x)
	{
		return x;
	}
};

template<>
struct HashFcn<string>
{
	size_t operator()(const string& s)
	{
		size_t ret = 0;
		for (auto ch : s)
		{
			ret += ch;
			ret *= 31;
		}
		return ret;
	}
};

template<class K, class V, class HashFcn = HashFcn<K>>
class HashTable
{
	typedef HashTableNode<K, V> Node;
public:
	HashTable() {}

	HashTable(const HashTable<K, V>& hs)
		:_n(hs._n)
	{
		size_t _v_size = hs._v.size();
		_v.resize(_v_size);

		for (size_t i = 0; i < _v_size; ++i)
		{
			Node* cur1 = hs._v[i];
			Node* prev = nullptr;
			while (cur1)
			{
				Node* newnode = new Node(cur1->_kv);
				if (prev)
				{
					prev->_next = newnode;
				}
				else
				{
					_v[i] = newnode;
				}
					
				cur1 = cur1->_next;
				prev = newnode;
			}
		}
	}

	~HashTable()
	{
		for (auto& cur : _v)
		{
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
		}
	}

		

	size_t GetNextSize(size_t num)//质数
	{
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53,         97,         193,       389,       769,
			1543,       3079,       6151,      12289,     24593,
			49157,      98317,      196613,    393241,    786433,
			1572869,    3145739,    6291469,   12582917,  25165843,
			50331653,   100663319,  201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		size_t i = 0;
		for (; i < __stl_num_primes; ++i)
		{
			if (__stl_prime_list[i] > num)
				return __stl_prime_list[i];
		}

		return __stl_prime_list[i];
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
			return false;


		HashFcn hashfcn;
		//扩容
		size_t _v_size = _v.size();
		if (_v_size == _n)
		{
			size_t newsize = GetNextSize(_v_size);
			vector<Node*> newtable(newsize, nullptr);
				
			for (auto& cur : _v)//cur类型 Node*&
			{
				while (cur)
				{
					Node* next = cur->_next;//记录当前节点的下一个

					size_t newHashTablei = hashfcn(cur->_kv.first) % newsize;//计算新表的插入位置
					//头插
					cur->_next = newtable[newHashTablei];//连尾
					newtable[newHashTablei] = cur;//改头

					cur = next;//cur更新，连带更改cur的值****
				}
			}
			_v.swap(newtable);
		}


		//头插
		_v_size = _v.size();
		size_t HashTablei = hashfcn(kv.first) % _v_size;
		Node* newnode = new Node(kv);
		newnode->_next = _v[HashTablei];
		_v[HashTablei] = newnode;
		_n++;
		return true;
	}

	Node* Find(const K& key)
	{
		HashFcn hashfcn;
		size_t _v_size = _v.size();
		if (_v_size == 0 || _n == 0)
			return nullptr;

		size_t HashTablei = hashfcn(key) % _v_size;
		Node* cur = _v[HashTablei];
		while (cur)
		{
			if (cur->_kv.first == key)
				return cur;
			else
				cur = cur->_next;
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		HashFcn hashfcn;
		size_t _v_size = _v.size();
		if (_v_size == 0 || _n == 0)
			return false;

		size_t HashTablei = hashfcn(key) % _v_size;
		Node* cur = _v[HashTablei];
		Node* prev = nullptr;
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				if (prev == nullptr)
				{
					_v[HashTablei] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				_n--;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;

	}


private:
	vector<Node*> _v;
	size_t _n = 0;
};

5. 开散列与闭散列比较

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

6. 哈希表的模拟实现以及unorder_set和unorder_map的封装

hashtable.h

#pragma once
#include<assert.h>

template<class T>
struct HashFcn
{
	size_t operator()(const T& x)
	{
		return x;
	}
};

template<>
struct HashFcn<string>
{
	size_t operator()(const string& s)
	{
		size_t ret = 0;
		for (auto ch : s)
		{
			ret += ch;
			ret *= 31;
		}
		return ret;
	}
};

template<class T>
struct Equal_Key
{
	bool operator()(const T& key1, const T& key2)
	{
		return key1 == key2;
	}
};

namespace HashOpen
{
	template<class V>
	struct HashTableNode
	{
		typedef V value_type;

		value_type _data;
		HashTableNode<V>* _next;

		HashTableNode(const value_type& data)
			:_data(data),
			_next(nullptr)
		{}
	};

	template<class K, class V, class KeyOfValue, class HashFcn, class Pred>
	class HashTable;

	template<class K, class V, class Ptr, class Ref, class KeyOfValue, class HashFcn, class Pred>
	struct __hash_iterator
	{
		typedef HashTableNode<V> Node;
		typedef HashTable<K, V, KeyOfValue, HashFcn, Pred> Hash;
		typedef __hash_iterator<K, V, Ptr, Ref, KeyOfValue, HashFcn, Pred> Self;
		typedef __hash_iterator<K, V, V*, V&, KeyOfValue, HashFcn, Pred> iterator;

		Node* _cur;
		const Hash* _hs;

		__hash_iterator(Node* cur, const Hash* hs)
			:_cur(cur),
			_hs(hs)
		{}

		__hash_iterator(const iterator& it)
			:_cur(it._cur),
			_hs(it._hs)
		{}

		Ref operator*()
		{
			return _cur->_data;
		}
		Ptr operator->()
		{
			return &operator*();
		}
		bool operator!=(const Self& t)
		{
			return _cur != t._cur;
		}

		Self& operator++()
		{
			KeyOfValue kov;
			HashFcn hash;
			if (_cur == nullptr)
			{
				assert(1);
				return *this;
			}

			Node* next = _cur->_next;
			if (next == nullptr)
			{
				size_t _v_size = _hs->_v.size();
				size_t hashi = hash(kov(_cur->_data)) % _v_size;
				++hashi;
				_cur = nullptr;
				for (size_t i = hashi; hashi < _v_size; ++hashi)
				{
					if (_hs->_v[hashi])
					{
						_cur = _hs->_v[hashi];
						break;
					}
				}
			}
			else
			{
				_cur = next;
			}
			return *this;
		}

	};

	template<class K, class V, class KeyOfValue, class HashFcn, class Pred>
	class HashTable
	{
		template<class K, class V, class Ptr, class Ref, class KeyOfValue, class HashFcn, class Pred>
		friend struct __hash_iterator;
		typedef HashTableNode<V> Node;
		typedef HashTable<K, V, KeyOfValue, HashFcn, Pred> Self;
		typedef K key_type;
		typedef V value_type;
	public:
		typedef __hash_iterator<K, V, V*, V&, KeyOfValue, HashFcn, Pred> iterator;
		typedef __hash_iterator<K, V, const V*, const V&, KeyOfValue, HashFcn, Pred> const_iterator;

		HashTable() {}

		HashTable(const Self& hs)
			:_n(hs._n)
		{
			size_t _v_size = hs._v.size();
			_v.resize(_v_size);

			for (size_t i = 0; i < _v_size; ++i)
			{
				Node* cur1 = hs._v[i];
				Node* prev = nullptr;
				while (cur1)
				{
					Node* newnode = new Node(cur1->_data);
					if (prev)
					{
						prev->_next = newnode;
					}
					else
					{
						_v[i] = newnode;
					}
					
					cur1 = cur1->_next;
					prev = newnode;
				}
			}
		}

		~HashTable()
		{
			for (auto& cur : _v)
			{
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
			}
		}

		iterator begin()
		{
			size_t _v_size = _v.size();
			for (size_t i = 0; i < _v_size; ++i)
			{
				if (_v[i])
					return iterator(_v[i], this);
			}
			return end();
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		const_iterator begin() const
		{
			size_t _v_size = _v.size();
			for (size_t i = 0; i < _v_size; ++i)
			{
				if (_v[i])
					return const_iterator(_v[i], this);
			}
			return end();
		}

		const_iterator end() const
		{
			return const_iterator(nullptr, this);//const this
		}

		size_t GetNextSize(size_t num)//质数
		{
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
			  53,         97,         193,       389,       769,
			  1543,       3079,       6151,      12289,     24593,
			  49157,      98317,      196613,    393241,    786433,
			  1572869,    3145739,    6291469,   12582917,  25165843,
			  50331653,   100663319,  201326611, 402653189, 805306457,
			  1610612741, 3221225473, 4294967291
			};
			size_t i = 0;
			for (; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > num)
					return __stl_prime_list[i];
			}

			return __stl_prime_list[i];
		}

		pair<iterator, bool> Insert(const value_type& data)
		{
			KeyOfValue kov;
			iterator it = Find(kov(data));
			if (it._cur)
				return make_pair(it, false);


			HashFcn hashfcn;
			//扩容
			size_t _v_size = _v.size();
			if (_v_size == _n)
			{
				//size_t newsize = GetNextSize(_v_size);
				size_t newsize = _v_size == 0 ? 10 : _v_size * 2;
				vector<Node*> newtable(newsize, nullptr);
				
				for (auto& cur : _v)//cur类型 Node*&
				{
					while (cur)
					{
						Node* next = cur->_next;//记录当前节点的下一个

						size_t newHashTablei = hashfcn(kov(cur->_data)) % newsize;//计算新表的插入位置
						//头插
						cur->_next = newtable[newHashTablei];//连尾
						newtable[newHashTablei] = cur;//改头

						cur = next;//cur更新，连带更改cur的值****
					}
				}
				_v.swap(newtable);
			}


			//头插
			_v_size = _v.size();
			size_t HashTablei = hashfcn(kov(data)) % _v_size;
			Node* newnode = new Node(data);
			newnode->_next = _v[HashTablei];
			_v[HashTablei] = newnode;
			_n++;
			return make_pair(iterator(newnode, this), true);
		}

		iterator Find(const key_type& key)
		{
			KeyOfValue kov;
			HashFcn hashfcn;
			Pred pred;
			size_t _v_size = _v.size();
			if (_v_size == 0 || _n == 0)
				return iterator(nullptr, this);

			size_t HashTablei = hashfcn(key) % _v_size;
			Node* cur = _v[HashTablei];
			while (cur)
			{
				if (pred(kov(cur->_data), key))
					return iterator(cur, this);
				else
					cur = cur->_next;
			}
			return iterator(nullptr, this);
		}

		bool Erase(const key_type& key)
		{
			HashFcn hashfcn;
			KeyOfValue kov;
			size_t _v_size = _v.size();
			if (_v_size == 0 || _n == 0)
				return false;

			size_t HashTablei = hashfcn(key) % _v_size;
			Node* cur = _v[HashTablei];
			Node* prev = nullptr;
			while (cur)
			{
				if (pred(kov(cur->_data), key))
				{
					if (prev == nullptr)
					{
						_v[HashTablei] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					_n--;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;

		}


	private:
		vector<Node*> _v;
		size_t _n = 0;
	};
}

unorder_set

#pragma once

#include"hashtable.h"

namespace kele
{

	template<class K, class Hash = HashFcn<K>, class Pred = Equal_Key<K>>
	class unorder_set
	{
		typedef K key_type;
		typedef K value_type;
	public:

		struct _keyofvalue
		{
			const key_type& operator()(const value_type& value)
			{
				return value;
			}
		};

		typedef typename HashOpen::HashTable<key_type, value_type, _keyofvalue, Hash, Pred>::const_iterator iterator;
		typedef typename HashOpen::HashTable<key_type, value_type, _keyofvalue, Hash, Pred>::const_iterator const_iterator;

		iterator begin()
		{
			return ht.begin();
		}

		iterator end()
		{
			return ht.end();
		}

		const_iterator begin() const
		{
			return ht.begin();
		}

		const_iterator end() const
		{
			return ht.end();
		}

		pair<iterator, bool> insert(const value_type& value)
		{
			return ht.Insert(value);
		}

		iterator find(const key_type& key)
		{
			return ht.Find(key);
		}

		bool erase(const key_type& key)
		{
			return ht.Erase(key);
		}


	private:
		HashOpen::HashTable<key_type, value_type, _keyofvalue, Hash, Pred> ht;
	};
}

unorder_map

#pragma once

#include"hashtable.h"

namespace kele
{

	template<class K, class V, class Hash = HashFcn<K>, class Pred = Equal_Key<K>>
	class unorder_map
	{
		typedef K key_type;
		typedef V data_type;
		typedef pair<const K, V> value_type;
	public:
		struct _keyofvalue
		{
			const key_type& operator()(const value_type& value)
			{
				return value.first;
			}
		};

		typedef typename HashOpen::HashTable<key_type, value_type, _keyofvalue, Hash, Pred>::iterator iterator;
		typedef typename HashOpen::HashTable<key_type, value_type, _keyofvalue, Hash, Pred>::const_iterator const_iterator;

		iterator begin()
		{
			return ht.begin();
		}

		iterator end()
		{
			return ht.end();
		}

		const_iterator begin() const
		{
			return ht.begin();
		}

		const_iterator end() const
		{
			return ht.end();
		}

		pair<iterator, bool> insert(const value_type& value)
		{
			return ht.Insert(value);
		}

		iterator find(const key_type& key)
		{
			return ht.Find(key);
		}

		bool erase(const key_type& key)
		{
			return ht.Erase(key);
		}

		data_type& operator[](const key_type& key)
		{
			return (ht.Insert(make_pair(key, data_type())).first)->second;
		}

	private:
		HashOpen::HashTable<key_type, value_type, _keyofvalue, Hash, Pred> ht;
	};
}

test.cpp

#include<iostream>
#include<vector>
#include<string>
using namespace std;
#include"hashtable.h"
#include"unorderedset.h"
#include"unorderedmap.h"


void test_map1()
{
	kele::unorder_map<int, int> m;
	int arr[] = { 1, 2, 3, 4,5,55,15,46,66 ,1,22,2,2,55};
	for (auto e : arr)
	{
		//m.insert(make_pair(e,e));
		m[e]++;
	}

	//kele::unorder_map<int, int>::iterator it = m.begin();
	//while (it != m.end())
	//{
	//	cout << it->first << ":" << it->second << endl;
	//	++it;
	//}

	for (auto it : m)
	{
		cout << it.first << ":" << it.second << endl;
	}

}

class Date
{
	friend struct HashFunc;
	friend ostream& operator<<(ostream& out, const Date& x);
public:

	Date(int year, int month, int day)
		:_year(year),
		_month(month),
		_day(day)
	{}

	bool operator==(const Date x) const
	{
		return _year == x._year
			&& _month == x._month
			&& _day == x._day;
	}


private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& out, const Date& x)
{
	out << x._year << "/" << x._month << "/" << x._day;
	return out;
}

struct HashFunc
{
	size_t operator()(const Date* date)
	{
		size_t ret = 0;
		ret = (ret + date->_year) * 31;
		ret = (ret + date->_month) * 31;
		ret = (ret + date->_day) * 31;

		return ret;
	}
};

struct Equal
{
	bool operator()(const Date* date1, const Date* date2)
	{
		return *date1 == *date2;
	}
};

void test_map2()
{
	kele::unorder_map<Date*, int, HashFunc, Equal> m;
	Date d1(2024, 3, 10);
	Date d2(2024, 3, 11);
	Date d3(2024, 3, 10);
	Date d4(2024, 3, 12);
	Date d5(2024, 3, 12);

	Date* a[] = { &d1,&d2,&d3,&d4,&d5 };
	for (auto e : a)
	{
		m[e]++;
	}

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

template<class K>
void print(const kele::unorder_set<int>& s)
{
	for (auto& e : s)
	{
		//e++;
		cout << e << " ";
	}
}

void test_set1()
{
	kele::unorder_set<int> s;
	int arr[] = { 1, 2, 3, 4,5,55,15,46,66 ,1,22,2,2,55 };
	for (auto e : arr)
	{
		s.insert(e);
	}
	print<int>(s);
}

template<class K, class V>
void print(const kele::unorder_map<int, int>& m)
{
	for (auto& e : m)
	{
		//e.second++;
		cout << e.first << ":" << e.second << " ";
	}
}

int main()
{
	//test_map1();
	//test_map2();
	test_set1();
	return 0;
}

完

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

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

相关文章

谷粒商城——分布式基础（全栈开发篇第一部分）

谷粒商城——分布式基础（全栈开发篇第一部分）

文章目录 一、服务治理网路数据支撑日志处理ELK应用监控集成工具开发工具 二、环境创建1、虚拟机创建2、虚拟机安装docker等1. 安装docker1. 配置阿里docker3.docker安装mysql错误 4、docker安装redis 3、软件1.Maven 阿里云镜像1.8jdk2、idea lombokmybatisX &#xff0c;3、 …
阅读更多...
算法之滑动窗口

算法之滑动窗口

题目1:209. 长度最小的子数组 - 力扣&#xff08;LeetCode&#xff09; 解法⼀(暴力求解): 思路&#xff1a; 从前往后, 枚举数组中的任意⼀个元素, 把它当成起始位置, 然后从这个起始位置开始, 然 后寻找⼀段最短的区间, 使得这段区间的和「⼤于等于」⽬标值. 将所有元素作为…
阅读更多...
Docker容器化技术（数据卷的管理）

Docker容器化技术（数据卷的管理）

数据卷 是一个可供容器使用的特殊目录&#xff0c;它将主机操作系统目录直接 映射进容器&#xff0c;类似于 Linux 中的 mount 行为 。 数据卷&#xff1a;可以提供很多有用的特性 数据卷可以在容器之间共事和重用&#xff0c;容器间传递数据将变得高效与方便&#xff1b;对数…
阅读更多...
二分查找【详解】

二分查找【详解】

本期介绍&#x1f356; 主要介绍&#xff1a;二分查找的简单思路&#xff0c;为什么必须在有序的前提下才能使用二分查找&#xff0c;该怎么用C程序来实现二分查找&#xff0c;二分查找的局限性&#x1f440;。 文章目录 1. 题目2. 思路3. 前提条件4. 编写程序 1. 题目 在一个有…
阅读更多...
详解mfc140.dll文件，修复mfc140.dll缺失的多种方法

详解mfc140.dll文件，修复mfc140.dll缺失的多种方法

mfc140.dll文件是Windows操作系统中的一个非常重要的动态链接库文件。它不仅被广泛用于操作系统本身的正常运行&#xff0c;还被许多应用程序所依赖。 一、详解mfc140.dll文件 mfc140.dll是Microsoft Foundation Classes&#xff08;MFC&#xff09;库中的一个动态链接库&…
阅读更多...
SpringBoot整合阿里云文件上传OSS以及获取oss临时访问url

SpringBoot整合阿里云文件上传OSS以及获取oss临时访问url

SpringBoot整合阿里云文件上传OSS 1. 引入相关依赖<!--阿里云 OSS依赖--><dependency><groupId>com.aliyun.oss</groupId><artifactId>aliyun-sdk-oss</artifactId><version>3.10.2</version></dependency><dependen…
阅读更多...
106. Dockerfile通过多阶段构建减小Golang镜像的大小

106. Dockerfile通过多阶段构建减小Golang镜像的大小

我们如何通过引入具有多阶段构建过程的Dockerfiles来减小Golang镜像的大小&#xff1f; 让我们从一个通用的Dockerfile开始&#xff0c;它负责处理基本的事务&#xff0c;如依赖项、构建二进制文件、声明暴露的端口等&#xff0c;以便为Go中的一个非常基础的REST API提供服务。…
阅读更多...
常见的排序算法的时间复杂度

常见的排序算法的时间复杂度

常见的排序算法的时间复杂度 排序算法的时间复杂度通常取决于输入数据的规模&#xff08;通常表示为n&#xff09;。以下是一些常见排序算法及其平均、最好和最坏情况下的时间复杂度&#xff1a; 1、冒泡排序&#xff08;Bubble Sort&#xff09; 平均时间复杂度&#xff1a;…
阅读更多...
进程打开文件

进程打开文件

目录 一、预备知识 二、操作文件函数 三、操作文件系统调用 四、理解进程打开文件 函数 vs 系统调用 open的返回值 fd 如何理解一切皆文件&#xff1f; 理解struct file 内核对象 fd的分配规则 && 重定向 理解标准错误流&#xff08;2号文件描述符&#xff0…
阅读更多...
得帆助力大族激光主数据平台建设，用数据为企业生产力赋能

得帆助力大族激光主数据平台建设，用数据为企业生产力赋能

本期客户 大族激光科技产业集团股份有限公司&#xff08;以下简称“大族激光”&#xff09;是一家从事工业激光加工设备与自动化等配套设备及其关键器件的研发、生产、销售&#xff0c;激光、机器人及自动化技术在智能制造领域的系统解决方案的优质提供商&#xff0c;是国内激光…
阅读更多...
如何通过四维轻云SDK开发打造智慧景区管理平台？

如何通过四维轻云SDK开发打造智慧景区管理平台？

智慧景区管理平台通常是基于GIS技术&#xff0c;在三维实景地图的基础上&#xff0c;接入景区各类传感设备、第三方系统数据&#xff0c;进行业务功能的梳理及开发。但对于没有GIS开发经验的团队而言&#xff0c;地图开发具有一定的技术门槛&#xff0c;尤其是需要在前端解决好…
阅读更多...
VR全景在智慧园区中的应用

VR全景在智慧园区中的应用

VR全景如今以及广泛的应用于生产制造业、零售、展厅、房产等领域&#xff0c;如今720云VR全景更是在智慧园区的建设中&#xff0c;以其独特的优势&#xff0c;发挥着越来越重要的作用。VR全景作为打造智慧园区的重要角色和呈现方式已经受到了越来越多智慧园区企业的选择和应用。…
阅读更多...
记事小本本

记事小本本

记事小本本 实现效果 相关代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</titl…
阅读更多...
Zookeeper详解

Zookeeper详解

1.Zookeeper概述 1.Zookeeper概念 Zookeeper是 Apache Hadoop 项目下的一个子项目&#xff0c;是一个树形目录服务 Zookeeper 翻译过来就是动物园管理员&#xff0c;他是用来管 Hadoop&#xff08;大象&#xff09;、Hive(蜜蜂)、Pig(小猪)的管理员。简称zk Hadoop: 存储海…
阅读更多...
Java项目：46 ssm005基于SSM框架的购物商城系统+jsp（含文档）

Java项目：46 ssm005基于SSM框架的购物商城系统+jsp（含文档）

作者主页&#xff1a;源码空间codegym 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 项目是单体ssm电商水果平台&#xff0c;包括前台商城平台及后台管理系统 前台商城系统包含首页门户、商品推荐、商品搜索、商品展示、购物车、…
阅读更多...
Buuctf-Web-[极客大挑战 2019]EasySQL 1 题解及思路总结

Buuctf-Web-[极客大挑战 2019]EasySQL 1 题解及思路总结

​ 启动靶机 目录 题要做题过程第一步——找到页面与数据库产生交互的地方第二步——查看SQL语句闭合方式判断SQL注入闭合方式&#xff1a;方法一&#xff1a;使用\(转义字符)来判断SQL注入的闭合方式方法二&#xff1a;输入1、1、1"判断SQL语句闭合方式 第三步——进行SQ…
阅读更多...
代理IP如何应对自动化测试和爬虫检测

代理IP如何应对自动化测试和爬虫检测

目录 一、代理IP在自动化测试和爬虫中的作用 二、代理IP的优缺点分析 1.优点 2.缺点 三、应对自动化测试和爬虫检测的策略 1.选择合适的代理IP 2.设置合理的请求频率和间隔 3.模拟人类行为模式 4.结合其他技术手段 四、案例与代码示例 五、总结 在自动化测试和爬虫开…
阅读更多...
Alpha突触核蛋白神经退行性疾病介绍

Alpha突触核蛋白神经退行性疾病介绍

StressMarq——Alpha突触核蛋白&神经退行性疾病 Alpha突触核蛋白科研背景 • Alpha突触核蛋白约 15kDa, 140个氨基酸 • StressMarq/欣博盛生物在E. coli中过表达人源基因然后将蛋白从细胞质基质中纯化出来 • 未折叠的alpha突触核蛋白单体在12% SDS-PAGE上为~15 kDa的条…
阅读更多...
CentOS本地部署Tale博客并结合内网穿透实现公网访问本地网站

CentOS本地部署Tale博客并结合内网穿透实现公网访问本地网站

文章目录 前言1. Tale网站搭建1.1 检查本地环境1.2 部署Tale个人博客系统1.3 启动Tale服务1.4 访问博客地址 2. Linux安装Cpolar内网穿透3. 创建Tale博客公网地址4. 使用公网地址访问Tale 前言 今天给大家带来一款基于 Java 语言的轻量级博客开源项目——Tale&#xff0c;Tale…
阅读更多...
2022年吉林省大学生电子设计竞赛(D题)

2022年吉林省大学生电子设计竞赛(D题)

一. 使用技术 PWM调速&#xff0c;PID&#xff0c;串口通信&#xff0c;陀螺仪测角度&#xff0c;蓝牙 二. 项目描述 大学的第一个比赛&#xff0c;项目采用主控stm32&#xff0c;车体采用一个四路电机驱动来驱动减速电机&#xff0c;小车依靠8路灰度循迹模块&#xff0c;实…
阅读更多...
最新文章

Copyright @ 2022~2023