【C++】unordered系列容器的封装

template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
public:
	typedef HashNode<T> Node;
	iterator begin()
	{}
	iterator end()
	{}
	const_iterator begin() const 
	{}
	const_iterator end() const 
	{}
	
	HashTable()
		:hs(),
		kot()
	{
		_table.resize(10, nullptr);
		_n = 0;
	}
	//插入数据
	pair<iterator, bool> insert(const T kv)
	{}
	//删除
	bool erase(const K& key)
	{}
	//查找
	iterator find(const K& key)
	{}
private:
	//底层是一个指针数组
	vector<Node*> _table;
	//有效数量
	size_t _n;
	//仿函数
	Hash hs;
	KeyOfT kot;
};

//插入数据
pair<iterator, bool> insert(const T kv)
{
	iterator it = find(kot(kv));
	if (it != end())
		return make_pair(it, false);

	//扩容
	if (_n == _table.size() * 0.7)
	{
		//直接把原本的节点移动到新的table中即可
		vector<Node*> newtable(2 * _table.size());
		//遍历整个数组
		for (int i = 0; i < _table.size(); i++)
		{
			if (_table[i])
			{
				Node* cur = _table[i];
				while (cur)
				{
					//获取数据
					Node* next = cur->_next;
					//计算新的映射
					//kot(cur->_kv) 来获取 T 中的key
					size_t hashi = hs(kot(cur->_kv)) % newtable.size();
					//进行头插
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;

					cur = next;
				}

			}
		}
		_table.swap(newtable);
	}
	//首先寻找到合适下标
	size_t hashi = hs(kot(kv)) % _table.size();
	//进行头插
	Node* newnode = new Node(kv);

	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	++_n;

	return make_pair(iterator(newnode , this), true);
}

template<class Ref , class Ptr>
struct _HTIterator
{
	typedef _HTIterator<Ref, Ptr> Self;
	//成员
	Node* _node;
	//哈希表
	const HashTable* _pht;
	//构造函数
	_HTIterator(Node* node, const HashTable* ht)
		:_node(node),
		_pht(ht)
	{}
	//++
	Self& operator++()
	{
	}
	//判断很好写
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
	Ref operator*() const
	{
		return _node->_kv;
	}
	Ptr operator->() const
	{
		return &_node->_kv;
	}
};

//++
Self& operator++()
{
	Hash hs;
	KeyOfT kot;
	//++
	//当前桶没走完就移动到下一个 桶走完了就移动到下一个桶 
	if (_node->_next) _node = _node->_next;
	else
	{
		//桶走完了就移动到下一个桶
		size_t i = hs(kot(_node->_kv)) % _pht->_table.size();
		i++;

		for (; i < _pht->_table.size(); i++)
		{
			if (_pht->_table[i])
				break;
		}
		//走完循环有两种可能，要进行判断
		if (i == _pht->_table.size())
			_node = nullptr;
		else
		{
			_node = _pht->_table[i];
		}
	}

	return *this;
}

//迭代器
typedef _HTIterator<T&, T*> iterator;
//const 迭代器
typedef _HTIterator<const T&, const T*> const_iterator;

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

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

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

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

//仿函数
template<class K>
struct SetKeyOfT
{
	const K operator()(const K& k)
	{
		return k;
	}
};

template<class K ,class Hash = HashFunc<K>>
class my_unoerder_set
{
public:
	//迭代器
	typedef typename HashTable<K, const K, SetKeyOfT<K>, Hash >::iterator iterator;
	typedef typename HashTable<K, const K, SetKeyOfT<K>, Hash >::const_iterator const_iterator;

	pair<iterator , bool> insert(const K& k)
	{
		return _table.insert(k);
	}
	iterator find(const K& k)
	{
		return _table.find(k);
	}
	bool erase(const K& k)
	{
		return _table.erase(k);
	}
	iterator begin()
	{
		return _table.begin();
	}
	iterator end()
	{
		return _table.end();
	}
	const_iterator begin() const
	{
		return _table.begin();
	}
	const_iterator end() const 
	{
		return _table.end();
	}
private:
	HashTable<K,const K, SetKeyOfT<K> , Hash > _table;
};

void test_set1()
{
	my_unoerder_set<string> S;
	vector<string> arr = { "sort" , "hello" , "JLX" , "Hi" };
	for (auto e : arr)
	{
		S.insert(e);
	}
	my_unoerder_set<string>::iterator it = S.begin();
	cout << "-------while循环遍历--------" << endl;
	while (it != S.end())
	{
		//(*it)++;
		std::cout << *it << endl;
		++it;
	}
	cout << "-------基于范围的for循环--------" << endl;
	for (auto e : S)
	{
		//e++;
		cout << e << endl;
	}
	cout << "-------查找\"hello\"--------" << endl;
	cout << *(S.find("hello")) << endl;
}

//仿函数
template<class K , class V>
struct MapKeyOfT
{
	const K& operator()(const pair<K , V>& kv)
	{
		return kv.first;
	}
};

template<class K , class V, class Hash = HashFunc<K>>
class my_unoerder_map
{
public:
	//迭代器
	typedef typename HashTable< K, pair<const K, V>, MapKeyOfT<K, V> , Hash>::iterator iterator;
	typedef typename HashTable< K, pair<const K, V>, MapKeyOfT<K, V> , Hash>::const_iterator const_iterator;

	pair<iterator, bool> insert(pair<const K, V> kv)
	{
		return _table.insert(kv);
	}
	iterator find(const K& k)
	{
		return _table.find(k);
	}
	bool erase(const K& k)
	{
		return _table.erase(k);
	}
	iterator begin()
	{
		return _table.begin();
	}
	iterator end()
	{
		return _table.end();
	}
	//[]操作
	V& operator[](const K& k)
	{
		pair<iterator, bool> it = insert(make_pair( k , V() ));
		return it.first->second;
	}

private:
	HashTable<K, pair<const K , V>, MapKeyOfT<K , V> , Hash> _table;
};

void test_unordered_map()
{
	my_unoerder_map<string, int> countMap;
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
	"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };

	for (auto& e : arr)
	{
		countMap[e]++;
	}
	my_unoerder_map<string, int>::iterator it = countMap.begin();
	while (it != countMap.end())
	{
		//(*it).first += 2;
		cout << (*it).first << ':' << (*it).second << endl;
		++it;
	}
}