c++逆天改命进阶--unordered

文章目录

• 1.HashTable.h
• 2.UnorderedSet.h
• 3.UnorderedMap.h
• 4.test.cpp

1.HashTable.h

#pragma once
#include 
#include 
using namespace std;
namespace ls
{
	template <class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};
	template<>
	struct Hash<string>
	{
		size_t operator()(const string& s)
		{
			size_t value = 0;
			//BKDR Hash
			for (auto ch : s)
			{
				value += ch;
				value *= 131;
			}
			return value;
		}

	};
	template <class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	template <class K, class T, class KeyOfT, class HashFunc>
	class HashTable;//前置声明

	template <class K, class T, class KeyOfT, class HashFunc = Hash<K>>
	struct _HTIterator
	{
		typedef HashNode<T> Node;
		typedef _HTIterator<K, T, KeyOfT, HashFunc> Self;
		typedef HashTable<K, T, KeyOfT, HashFunc> HT;
		Node* _pNode;
		HT* _pht;
		_HTIterator(Node* pNode, HT* pht)
			:_pNode(pNode)
			,_pht(pht)
		{}
		
		Self& operator++()
		{
			KeyOfT kot;
			HashFunc hf;
			if (_pNode->_next)//当前桶没走完就往下走
			{
				_pNode = _pNode->_next;
				return *this;
			}
			else//当前桶走完了
			{
				//先计算当前桶在表中的index
				size_t index = hf(kot(_pNode->_data)) % _pht->_table.size();
				++index;
				while (index < _pht->_table.size())//index 没走到头就继续走
				{
					if (_pht->_table[index])//如果当前位置不为空走进这个桶
					{
						_pNode = _pht->_table[index];
						return *this;
					}
					else
					{
						++index;//为空index继续走
					}
				}
				_pNode = nullptr;//遍历结束走到空
				return *this;
			}
		}
		T& operator*()
		{
			return _pNode->_data;
		}
		T* operator->()
		{
			return &_pNode->_data;
		}

		bool operator != (const Self& s)const
		{
			return _pNode != s._pNode;
		}

		bool operator == (const Self& s)const
		{
			return _pNode == s._pNode;
		}

	};
	template <class K, class T, class KeyOfT, class HashFunc = Hash<K>>
	class HashTable
	{
		typedef HashNode<T> Node;
		template <class K, class T, class KeyOfT, class HashFunc>
		friend struct _HTIterator;

		

		
	public:
		typedef _HTIterator<K, T, KeyOfT, HashFunc> iterator;

		HashTable() = default;
		HashTable(const HashTable& ht)
		{
			_n = ht._n;
			_table.resize(ht._table.size(), nullptr);//先开出与拷贝对象同样大小的空间
			for (int i = 0;i < ht._table.size();++i)//遍历拷贝对象
			{
				Node* cur = ht._table[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);
					//将copy头插到新表中
					copy->_next = _table[i];
					_table[i] = copy;

					cur = cur->_next;
				}
			}
		}
		HashTable& operator=(const HashTable ht)
		{
			_table.swap(ht._table);
			swap(_n, ht._n);
			return *this;
		}
		~HashTable()
		{
			for (int i = 0;i < _table.size();++i)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}
		iterator begin()
		{
			size_t i = 0;
			while (i < _table.size())
			{
				if (_table[i])
				{
					return iterator(_table[i], this);
				}
				++i;
			}
			return end();
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}
		pair<iterator, bool> Insert(const T data)
		{
			KeyOfT kot;
			auto ret = Find(kot(data));
			if (ret != end())
			{
				return make_pair(ret, false);
			}
			HashFunc hf;
			if (_n == _table.size())//负载因子到1时开始扩容
			{
				vector<Node*> newtable;
				size_t newsize = _table.size() == 0 ? 8 : _table.size() * 2;
				newtable.resize(newsize, nullptr);
				//遍历旧表中非空节点，重新计算位置头插放到新表
				for (int i = 0;i < _table.size();++i)
				{
					if (_table[i])
					{
						Node* cur = _table[i];
						while (cur)
						{
							Node* next = cur->_next;
							size_t index = hf(kot(cur->_data)) % newtable.size();
							//头插
							cur->_next = newtable[index];
							newtable[index] = cur;
							cur = next;
						}
						_table[i] = nullptr;
					}
				}
				_table.swap(newtable);
			}
			size_t index = hf(kot(data)) % _table.size();
			Node* newNode = new Node(data);
			newNode->_next = _table[index];
			_table[index] = newNode;
			++_n;
			return make_pair(iterator(newNode, this), true);
		}
		iterator Find(const K& key)
		{

			if (_table.size() == 0)
			{
				return iterator(nullptr, this);
			}
			HashFunc hf;
			size_t index = hf(key) % _table.size();
			if (_table[index])
			{
				KeyOfT kot;
				Node* cur = _table[index];
				while (cur)
				{
					if (kot(cur->_data) == key)
					{
						return iterator(cur, this);
					}
					else
					{
						cur = cur->_next;
					}
				}
			}
			return iterator(nullptr, this);

		}
		bool Erase(const K& key)
		{
			if (_table.size() == 0)
			{
				return false;
			}
			HashFunc hf;
			size_t index = hf(key) % _table.size();
			Node* cur = _table[index];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (cur == _table[index])
					{
						_table[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->next;
					}
					delete cur;
					--_n;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
	private:
		vector<Node*> _table;
		size_t _n = 0;
	};
}

2.UnorderedSet.h

#pragma once
#include "HashTable.h"

namespace ls
{
	template <class K>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<K, K, SetKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

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

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

	private:
		HashTable< K, K, SetKeyOfT> _ht;
	};

	void test_unordered_set1()
	{
		unordered_set<int> us;
		us.insert(200);
		us.insert(1);
		us.insert(2);
		us.insert(33);
		us.insert(50);
		us.insert(60);
		us.insert(243);
		us.insert(6);

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

3.UnorderedMap.h

#pragma once
#include "HashTable.h"

namespace ls
{
	template <class K, class V>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

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

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
		V& operator[](const K& key)
		{
			auto ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		HashTable<K, pair<K, V>, MapKeyOfT> _ht;
	};
	void test_unordered_map1()
	{
		unordered_map<string, string> dict;
		dict.insert(make_pair("sort", "排序"));
		dict["left"] = "左边";
		dict["left"] = "剩余";
		dict["map"] = "映射";
		dict["string"] = "字符串";
		dict["set"] = "集合";

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

4.test.cpp

#include "HashTable.h"
#include "UnorderedMap.h"
#include "UnorderedSet.h"
int main()
{
	ls::test_unordered_set1();
	ls::test_unordered_map1();
	return 0;
}