C++ unordered封装

C++ 哈希-CSDN博客

哈希表是unordered系列容器的底层逻辑，再实现了哈希的底层后，我们按照如下步骤封装unordered:

1. 改变数据类型，将HashTable中的所有的_kv都改成T

2. 因为map需要取key，写一个KeyOfT的仿函数并封装

3. iterator , ConstIterator的实现和封装

4. 解决set和map中的key不能修改（value应该设计成可以修改）

5. opereator[]

依照上述思路，我们来实现代码。

1. 调整数据类型

但是在改数据的过程中，会发现一些需要KeyOfT的内容（不明白什么是KeyOfT的可以先去看红黑树改造为set和map）

因为不确定data是单个数据或者是一个pair，不能直接这样用first。

2. KeyOfT

然后分别拿两个仿函数KeyOfMap和KeyOfSet：

对照着到HashTable中也去改变一下：

定义出仿函数对象：

然后要将刚刚写的"data.first"都改了：

有细心的读者可能会问，为什么HashTable需要既传Key，又传T，原因是Key是需要被当做一个类型去使用的，比如Find函数。

3. 迭代器

关于迭代器的遍历：

一个桶内很好动，一直it = it->_next即可；可是一个桶走完了如何找下一个桶？

因为每一条链都是独立的，因此迭代器中光有一个节点指针是不够的。

库中的实现方式：

直接传过来整个表对象，这样就能用_hst里的_table来遍历了。

因此，构造HSTIterator时需要多一个参数

利用哈希映射找到下一个该去的位置：

解决思路：通过_pnode重新找一个当前的hashi并遍历

这样就能根据迭代器指向的元素的data计算出一个hashi，但是需要先把将key转换成int的仿函数Hashfunc传入。

Self& operator++()
{
	if (_pnode->_next) {
		_pnode = _pnode->_next;
	}
	else {
		//去找下一条链
		KeyOfT kot;
		Hash _hs;
		size_t hashi = _hs(kot(_pnode->_data)) % _hst->_table.size();
		//找到了_pnode指向数据所对应的hashi，现在让hashi在vector<Node*>中往后找到有效位置
		while (hashi < _hst->_table.size())
		{
			++hashi;
			if (_hst->_table[hashi] != nullptr) {
				_pnode = _hst->_table[hashi];
				break;
			}
		}
		//走到这的时候，可能是hashi已经走到了末尾，也可能是找到了有效位置所以break了
		if (hashi == _hst->_table.size()) {
			_pnode = nullptr;
		}
	}
	return *this;
}

hashi和表中的vector的size一样大的时候，表明已经走完了vector但是没有遇到合适的桶。

再实现几个小接口：

然后就可以回到HashTable中去封装iterator了：

(为了让编译器检查通过，还要在最后加一个return)

End直接返回一个Iterator(nullptr,this)即可。

回到两个unordered中，封装迭代器:

模版类中拿内置类型，需要加一个typename说明是类型而不是static修饰的变量。

我们尝试对已经写好的代码进行纠错和更正，现在还有以下几个问题值得说明：

iterator中使用了HashTable，HashTable中的Begin()等函数使用了iterator。两个模块在互相使用、互相包，所以编译iterator的时候找不到hashtable

解决办法：前置声明。

在写iterato之前先声明HashTable。

友元：

现在存在的问题：

在迭代器(HSTIterator)的operator++中，我们访问了_table，但是_table是私有，是不能被访问的

_table是私有，但是我们要在iterator中访问他，因此需要友元。

普通类的友元直接frend即可，但是类模版的友元：

要在friend的声明前加上模版参数。

最后再封装constIterator

ConstIterator在构造时会有问题

错误出现在HashTable封装的这一层上：

这里的this是被const修饰了的，所以传进去构造ConstIterator的this也是被const修饰了的。

而红框中的pht是没有const修饰的，所以出现了权限的错误。

但是请注意：对于构造函数和析构函数的this添加const修饰是非法的，所以只修饰hst即可。

正确修改：

3. key不能修改

因为map和set都是不允许改变T（也就是value）的数值的，所以第二个K要改成const。

set:

map:

其他小接口直接套：

4.operator方括号

根据库中的逻辑改写insert，然后再利用Insert实现方括号访问。

pair<Iterator,bool> insert(const T& data) {
	HashFunc<K> hs;
	KeyOfT kot;
	if (Find(kot(data))!=End()) return make_pair(Find(kot(data)),false);//!!!!!data.first应该改成KeyOfT来控制

	//扩容
	if ((double)_n / _tables.size() >= 1) {
		/*HashTable newHT;
		newHT._tables.resize(2 * _tables.size());

		for (int i = 0; i < _tables.size(); i++) {
			Node* cur = _tables[i];
			while (cur) {
				newHT.insert(cur->_kv);
				cur = cur->_next;
			}
		}
		_tables.swap(newHT._tables);*/

		vector<Node*> newTable;
		newTable.resize(_tables.size() * 2);
		for (int i = 0; i < _tables.size(); i++) {
			Node* cur = _tables[i];
			while (cur) {
				Node* next = cur->_next;
				//找新表的下标
				size_t hashi = hs(kot(cur->_data)) % newTable.size();//!!!!!data.first应该改成KeyOfT来控制
				//头插到新表
				cur->_next = newTable[hashi];
				newTable[hashi] = cur;

				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newTable);
	}


	//头插
	Node* newnode = new Node(data);
	size_t hashi = hs(kot(data)) % _tables.size();
	if (_tables[hashi] == nullptr) {
		_tables[hashi] = newnode;
	}
	else {
		Node* cur = newnode;
		cur->_next = _tables[hashi];
		_tables[hashi] = cur;
	}
	++_n;
	return make_pair(Iterator(newnode,this), true);
}

利用insert :