C++ 模拟实现 STL 中 unordered 系列的容器

2024-04-26 07:32:37

目录

一，改造 hash table

1，节点，数据结构，一些简单的辅助函数

2，迭代器

3，构造，析构，拷贝

4，插入，查找，删除

二，hash_set、hash_multiset 与 hash_map、hash_multimap

1，hash_set 与 hash_multiset

2，hash_map 与 hash_multimap

三，简单的测试

1，测试 hash_set 与 hash_multiset

2，测试 hash_map 与 hash_multimap

四，hash_table 完整代码

在C++标准模板库（STL）中，unordered 系列的容器包括 unordered_map、unordered_set、unordered_multimap 和 unordered_multiset。这些容器基于哈希表实现，提供平均常数时间复杂度的查找、插入和删除操作。与基于红黑树的有序容器（例如 set、map、multiset、multimap）相比，unordered 容器不会按特定顺序存储元素，而是按哈希表的特性进行组织。

如果不知道哈希表是什么或者是不清楚哈希表是怎么具体实现的可以看看我的另一篇博客~：

C++ 散列表（hash table）-****博客文章浏览阅读545次，点赞14次，收藏11次。散列表（也称为哈希表（hash table））是一种通过哈希函数来计算数据存储位置的数据结构，使得对数据的插入、删除和查找操作可以非常快速进行。哈希表可以说是一种专门用来查找的数据结构。在最理想的情况下，哈希表的这些操作的时间复杂度为O(1)。那么，它是怎么做到如此高效的呢？我们先来考虑一下这个：如果我们要查找的键都是小整数，我们可以用一个数组来实现无序的符号表，将键作为数组的索引而数组中下标 i 处储存的就是它对应的值。这样我们就可以快速访问任意键的值。https://blog.****.net/qq_41521068/article/details/137912859?spm=1001.2014.3001.5501

（STL 中 unordered 系列的容器与 set, map 这类的容器在功能上几乎完全相同，感兴趣的话还可以先看看这个：C++ 模拟实现 STL 中的 set、map 与 multiset、multimap-****博客）

接下来此文将基于上面卡片中的博客所实现的 hash table 来进行一点小小的改造，然后再基于改造后的 hash table 来模拟实现一下 STL 中 unordered 系列的容器。为了与 STL 区分开（也为了可以少些一点字母），这里不使用 unordered 来作为命名的前缀，而是使用 hash（例如：hash_set, hash_map, hash_multiset, hash_multimap）。

一，改造 hash table

1，节点，数据结构，一些简单的辅助函数

节点：

//哈希节点
template<class T>
struct hash_node {
	T data;
	hash_node* next;
	hash_node(const T& _data = T()) :data(_data), next(nullptr) {}
};

数据结构：

template<class Key, class T, class KeyOfT, class HashFunc = hash_func<Key>>
class hash_table {
private:
	typedef hash_node<T> Node;
	HashFunc _hf;
	KeyOfT _kot;

private:
	// 主要的成员变量
	size_t _size = 0;
	std::vector<Node*> _table;
}

这里来解释一下 KeyOfT：

  1. KeyOfT 的作用是从存储的元素中提取出键值。hash table 中存储的元素通常是键值对，它就是用来告诉 hash table 如何从这些元素中提取出键值，以便提供给哈希函数进行计算
  2. hash table 中存储的元素可能是键值对，也可能仅仅只是单键（例如 hash_set 中存的是单键， hash_map 中存的是键值对）。KeyOfT 就是为了统一单键与键值对这两种情况而设计的
  3. 在上面代码中的模板参数中，Key 表示键，T 表示储存的元素；如果是 hash_map，T 表示一个 pair<key,val>键值对， 如果是 hash_set，T 表示 Key。而 KeyOfT 就是从 T 中取出 Key

简单的辅助函数：

public:
	// 一些简单的功能
	bool empty()const { return _size == 0; }
	size_t size()const { return _size; }
	size_t table_size()const { return _table.size(); }
	// 为了便于扩展所设计的函数
	bool key_equal(Node* node,const Key& key)const { return  _kot(node->data) == key; }
	size_t next_size(size_t size)const { return prime(size); }
	// 为了方便找到索引而设计的函数
	size_t table_index(const Key& key)const { return _hf(key) % table_size(); }
	size_t table_index(const Key& key, size_t table_size)const { return _hf(key) % table_size; }

2，迭代器

如果不清楚迭代器是什么，或者是不知道要怎么为容器设计一个专属的迭代器可以看看我的另一篇博客：C++ 迭代器与反向迭代器-****博客

迭代器类：

// Ref 为引用类型，Ptr 为指针类型
template<class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
struct Hash_Iterator{
	typedef hash_node<T> Node;

	KeyOfT _kot;
	HashFunc _hf;

        // 我们在进行 ++ 时，迭代器可能会从 table[i] 跳转到 table[i+?]
        // 所以我们不仅需要节点 node ，还需要 node 所在的 table 对象
	Node* _node;
	const std::vector<Node*>* _table;    
        // 这里的 _table 一定要加 const 修饰，
	    // 不然在使用 const_iterator 时类型会无法转换    

	typedef T	value_type;
	typedef Ref reference;
	typedef Ptr pointer;

	typedef Hash_Iterator<T, T&, T*, KeyOfT, HashFunc> iterator; //普通迭代器类型
	typedef Hash_Iterator<T, Ref, Ptr, KeyOfT, HashFunc> self;   //当前迭代器类型

    // 用哈希节点构造当前迭代器
	Hash_Iterator(Node* node, const std::vector<Node*>* table) :_node(node), _table(table) {}
    // 用普通迭代器构造当前迭代器
	Hash_Iterator(const iterator& iter) :_node(iter._node), _table(iter._table) {}

	Ref operator*() { return _node->data; }
	Ptr operator->() { return &(operator*()); }
	bool operator==(const self& iter)const { return iter._node == _node; }
	bool operator!=(const self& iter)const { return iter._node != _node; }


	self operator++();
	self operator++(int);

};

这里要提一下：STL 中的 unordered 系列容器都没有 operator--() 操作，也就是说该系列容器并不支持反向迭代器。

现在我们来看看 operator++() 的实现：

self operator++() {
	if (_node->next) {
		//如果当前节点还有下一个节点
		_node = _node->next;
		return *this;
	}
	else {
		//从下一个桶开始往后找
		size_t idx = _hf(_kot(_node->data)) % _table->size();
		for (size_t i = idx + 1;i < _table->size();++i) {
			if ((*_table)[i]) {
				//取桶中的第一个元素
				_node = (*_table)[i];
				return *this;
			}
		}
	}
	_node = nullptr;
	_table = nullptr;
	return *this;
}

self operator++(int) {
	self res = *this;
	++(*this);
	return res;
}

hash_table 中的迭代器：

public:
	// 迭代器
	typedef Hash_Iterator<T, T&, T*, KeyOfT, HashFunc> iterator;
	typedef Hash_Iterator<T, const T&, const T*, KeyOfT, HashFunc> const_iterator;

	iterator begin() {
		if (empty()) return end();
		for (Node* node : _table) {
			if (node) return iterator(node, &_table);
		}
	}
	iterator end() { return iterator(nullptr, nullptr); }

	const_iterator begin()const {
		if (empty()) return end();
		for (Node* node : _table) {
			if (node) return const_iterator(node, &_table);
		}
	}
	const_iterator end()const { return const_iterator(nullptr, nullptr); }

3，构造，析构，拷贝

这里实现的 hash_table 允许表中有重复的元素存在，为了更好的适配 hash_set、hash_map 以及 hash_multiset、hash_multimap，所以 hash_table 只提供空构造（表中没有有效元素）以及拷贝构造，其他的构造方式就由它的上层容器来扩展。

首先来看辅助函数：

public:
	// 辅助拷贝与析构的函数
	// 交换
	void swap(hash_table& ht) {
		std::swap(_size, ht._size);
		_table.swap(ht._table);
	}

	// 清空
	void clear() {
		for (int i = 0;i < _table.size();++i) {
			Node* node = _table[i];
			while (node) {
				Node* next = node->next;
				delete node;
				node = next;
			}
			_table[i] = nullptr;
		}
		_size = 0;
	}

private:
    // 拷贝哈希表
	void copy(const hash_table& ht){
		_size = ht.size();
		_table.resize(ht.table_size());
		Node* dummy = new Node;
		for (int i = 0;i < _table.size();++i) {
			Node* pre = dummy;
			Node* node = ht._table[i];
			while (node != nullptr) {
				pre->next = new Node(node->data);
				node = node->next;
				pre = pre->next;
			}
			_table[i] = dummy->next;
			dummy->next = nullptr;
		}
		delete dummy;
	}

接下来是真正的构造，析构与拷贝：

public:
	// 构造与析构
	hash_table() :_size(0), _table(11, nullptr) {}
	~hash_table() { if (not empty()) clear(); }

public:
	// 拷贝
	hash_table(const hash_table& ht) { copy(ht); }
	hash_table(hash_table&& ht) { swap(ht); }
	hash_table& operator=(hash_table ht) {
		swap(ht);
		return *this;
	}

4，插入，查找，删除

这里实现的 hash_table 提供两种不同的插入方式：一种是 insert_unique()，表示插入的元素必须是树中不存在的元素；另一种是 insert_equal()，这个操作可以将重复的元素插入树中。这两种插入方式分别会被 hash_set、hash_map 与 hash_multiset、hash_multimap 调用。

关于代码中的 resize （扩容逻辑）这里就不具体给出了，与文章开头中推荐的博客一样。

首先是插入：

public:
	pair<iterator, bool> insert_unique(const T& data){
		if (_size == _table.size()) resize(_size * 2);

		size_t idx = table_index(_kot(data));
		for (Node* node = _table[idx]; node;node = node->next) {
			if (key_equal(node, _kot(data))) {
				// key 已经存在就直接返回
				return make_pair(iterator(node, &_table), false);
			}
		}
		iterator res = insert_assist(data, idx);
		return make_pair(res, true);
	}

	iterator insert_equal(const T& data){
		if (_size == _table.size()) resize(_size * 2);
		
		size_t idx = table_index(_kot(data));
		return insert_assist(data, idx);
	}

private:
	iterator insert_assist(const T& data, size_t idx) {
		Node* node = new Node(data);
		// 头插新节点
		node->next = _table[idx];
		_table[idx] = node;
		++_size;
		return iterator(node, &_table);
	}

接下来是查找：

hash_table 的查找十分高效，不过 hash_table 中存放的元素并不是有序的，如果我们想按照范围来查找数据，我们因该选择 AVL 或者 RB_tree 来当作我们的容器。

private:
	template<class Iter_Type>
	Iter_Type find_impli(const Key& key)const{
		size_t idx = table_index(key);
		for (Node* node = _table[idx];node;node = node->next) {
			if (key_equal(node, key)) return Iter_Type(node, &_table);
		}
		return Iter_Type(nullptr, nullptr);
	}

public:
	// 查找，插入，删除
	iterator find(const Key& key) { return find_impli<iterator>(key); }
	const_iterator find(const Key& key)const { return find_impli<const_iterator>(key); }

	size_t count(const Key& key)const {
		size_t idx = table_index(key);
		size_t cnt = 0;
		for (Node* node = _table[idx];node;node = node->next) {
			if (key_equal(node, key)) ++cnt;
		}
		return cnt;
	}

最后是删除：

public:
	size_t erase(const Key& key) {
		size_t idx = table_index(key);
		size_t count = 0;
		Node* dummy = new Node;
		dummy->next = _table[idx];
		Node* pre = dummy, * cur = _table[idx];
		while (cur) {
			if (key_equal(cur, key)) {
				pre->next = cur->next;
				delete cur;
				cur = pre->next;
				--_size;
				++count;
			}
			else {
				pre = cur;
				cur = cur->next;
			}
		}
		_table[idx] = dummy->next;
		delete dummy;
		return count;
	}

哈希表示意图（开链法）：

二，hash_set、hash_multiset 与 hash_map、hash_multimap

我们实现了 hash_table 之后，接下来的工作就十分简单了，基本上就是对 hash_table 的封装。

使用 set 或 map，我们的目的都是能够根据键值进行快速的查找。这一点不管是底层用 RB_tree 还是 hash_table 都能够很好的完成。但是我们需要注意的是：RB_tree 可以自动根据键值进行排序，而 hash_table 不行，所以 STL 中的 set，map 等容器都有自动排序的功能，而 unordered 系列的容器则没有。

1，hash_set 与 hash_multiset

hash_set 的使用方式与 set 完全相同

namespace mySTL {

	template<class Key>
	class hash_set {
	private:
		struct KeyOfT {
			Key operator()(const Key& key)const {
				return key;
			}
		};

		typedef hash_table<Key, Key, KeyOfT> hash_table;
		hash_table _hash_tab;

	public:
		typedef typename hash_table::const_iterator iterator;
		typedef typename hash_table::const_iterator const_iterator;
		iterator begin()const { return _hash_tab.begin(); }
		iterator end()const { return _hash_tab.end(); }

	public:
		// 构造与析构
		hash_set(){}
		hash_set(const std::initializer_list<Key>& lt) {
			for (const Key& key : lt) {
				insert(key);
			}
		}
		~hash_set() { if (not empty()) clear(); }

		// 拷贝
		hash_set(const hash_set& hs) { _hash_tab = hs._hash_tab; }
		hash_set(hash_set&& hs) { swap(hs); }
		hash_set& operator=(hash_set hs){
			swap(hs);
			return *this;
		}

	public:
		size_t size()const { return _hash_tab.size(); }
		bool empty()const { return _hash_tab.empty(); }
		void swap(hash_set& hs) { _hash_tab.swap(hs._hash_tab); }

		iterator find(const Key& key)const { return _hash_tab.find(key); }
		size_t count(const Key& key)const { return _hash_tab.count(key); }

		pair<iterator, bool> insert(const Key& key) { return _hash_tab.insert_unique(key); }
		size_t erase(const Key& key) { return _hash_tab.erase(key); }
		void clear() { _hash_tab.clear(); }

		void print()const { _hash_tab.print(); }
	};

}

hash_multiset 的特性与 hash_set 完全相同，实现上的唯一区别就在于插入，前者使用 insert_equal()，后者使用 insert_unique()。


namespace mySTL {

	template<class Key>
	class hash_multiset {
	private:
		struct KeyOfT {
			Key operator()(const Key& key)const {
				return key;
			}
		};

		typedef hash_table<Key, Key, KeyOfT> hash_table;
		hash_table _hash_tab;

	public:
		typedef typename hash_table::const_iterator iterator;
		typedef typename hash_table::const_iterator const_iterator;
		iterator begin()const { return _hash_tab.begin(); }
		iterator end()const { return _hash_tab.end(); }

	public:
		// 构造与析构
		hash_multiset() {}
		hash_multiset(const std::initializer_list<Key>& lt) {
			for (const Key& key : lt) {
				insert(key);
			}
		}
		~hash_multiset() { if (not empty()) clear(); }

		// 拷贝
		hash_multiset(const hash_multiset& hs) { _hash_tab = hs._hash_tab; }
		hash_multiset(hash_multiset&& hs) { swap(hs); }
		hash_multiset& operator=(hash_multiset hs) {
			swap(hs);
			return *this;
		}

	public:
		size_t size()const { return _hash_tab.size(); }
		bool empty()const { return _hash_tab.empty(); }
		void swap(hash_multiset& hs) { _hash_tab.swap(hs._hash_tab); }

		iterator find(const Key& key)const { return _hash_tab.find(key); }
		size_t count(const Key& key)const { return _hash_tab.count(key); }

		iterator insert(const Key& key) { return _hash_tab.insert_equal(key); }
		size_t erase(const Key& key) { return _hash_tab.erase(key); }
		void clear() { _hash_tab.clear(); }

		void print()const { _hash_tab.print(); }
	};

}

2，hash_map 与 hash_multimap

hash_map 的使用方式与 map 完全相同

namespace mySTL {

	template<class Key, class Val>
	class hash_map {
	private:
		struct KeyOfT {
			Key operator()(const pair<const Key, Val>& p)const {
				return p.first;
			}
		};

		typedef hash_table<Key, pair<const Key, Val>, KeyOfT> hash_table;
		hash_table _hash_tab;

	public:
		typedef typename hash_table::iterator iterator;
		typedef typename hash_table::const_iterator const_iterator;
		iterator begin() { return _hash_tab.begin(); }
		iterator end() { return _hash_tab.end(); }
		const_iterator begin()const { return _hash_tab.begin(); }
		const_iterator end()const { return _hash_tab.end(); }

	public:
		// 构造与析构
		hash_map(){}
		hash_map(const std::initializer_list<pair<Key, Val>>& lt) {
			for (const auto& data : lt) {
				insert(data);
			}
		}
		~hash_map() { if (not empty()) clear(); }

		// 拷贝
		hash_map(const hash_map& hm) { _hash_tab = hm._hash_tab; }
		hash_map(hash_map&& hm) { swap(hm); }
		hash_map& operator=(hash_map hm) {
			swap(hm);
			return *this;
		}

	public:
		size_t size()const { return _hash_tab.size(); }
		bool empty()const { return _hash_tab.empty(); }
		void swap(hash_map& hm) { _hash_tab.swap(hm._hash_tab); }

		iterator find(const Key& key) { return _hash_tab.find(key); }
		const_iterator find(const Key& key)const { return _hash_tab.find(key); }
		Val& operator[](const Key& key) { return insert(make_pair(key, Val())).first->second; }
		size_t count(const Key& key)const { return _hash_tab.count(key); }

		pair<iterator, bool> insert(const pair<Key, Val>& kv) { return _hash_tab.insert_unique(kv); }
		void erase(const Key& key) { _hash_tab.erase(key); }
		void clear() { _hash_tab.clear(); }

		void print()const { _hash_tab.print(); }
	};

}

hash_multimap 的特性与 hash_map 完全相同，实现上的唯一区别就在于插入，前者使用 insert_equal()，后者使用 insert_unique()。还有一点需要注意：hash_multimap 中没有重载 operator[]。

namespace mySTL {

	template<class Key, class Val>
	class hash_multimap {
	private:
		struct KeyOfT {
			Key operator()(const pair<const Key, Val>& p)const {
				return p.first;
			}
		};

		typedef hash_table<Key, pair<const Key, Val>, KeyOfT> hash_table;
		hash_table _hash_tab;

	public:
		typedef typename hash_table::iterator iterator;
		typedef typename hash_table::const_iterator const_iterator;
		iterator begin() { return _hash_tab.begin(); }
		iterator end() { return _hash_tab.end(); }
		const_iterator begin()const { return _hash_tab.begin(); }
		const_iterator end()const { return _hash_tab.end(); }

	public:
		// 构造与析构
		hash_multimap() {}
		hash_multimap(const std::initializer_list<pair<Key, Val>>& lt) {
			for (const auto& data : lt) {
				insert(data);
			}
		}
		~hash_multimap() { if (not empty()) clear(); }

		// 拷贝
		hash_multimap(const hash_multimap& hm) { _hash_tab = hm._hash_tab; }
		hash_multimap(hash_multimap&& hm) { swap(hm); }
		hash_multimap& operator=(hash_multimap hm) {
			swap(hm);
			return *this;
		}

	public:
		size_t size()const { return _hash_tab.size(); }
		bool empty()const { return _hash_tab.empty(); }
		void swap(hash_multimap& hm) { _hash_tab.swap(hm._hash_tab); }

		iterator find(const Key& key) { return _hash_tab.find(key); }
		const_iterator find(const Key& key)const { return _hash_tab.find(key); }
		size_t count(const Key& key)const { return _hash_tab.count(key); }

		iterator insert(const pair<Key, Val>& kv) { return _hash_tab.insert_equal(kv); }
		void erase(const Key& key) { _hash_tab.erase(key); }
		void clear() { _hash_tab.clear(); }

		void print()const { _hash_tab.print(); }
	};

}

三，简单的测试

为了方便测试，这里在 hash_table 中添加了一个函数：

public:
	void print()const {
		size_t idx = 0;
		for (Node* node : _table) {
			cout << idx++ << ": ";
			while (node) {
				cout << _kot(node->data) << " -> ";
				node = node->next;
			}
			cout << "null" << endl;
		}
		cout << endl;
	}

1，测试 hash_set 与 hash_multiset

下面这份代码是对 hash_set 进行简单的测试，我们只需要用一下编辑器自带的替换功能将下面代码中的 set 改为 multiset 就能够对 hash_multiset 也进行一下简单的测试了

class test_hash_set {
private:
	// 测试插入，迭代器，删除功能
	void test_insert_iter_erase() {
		mySTL::hash_set<int> hash;
		// 测试插入
		for (int i = 0;i < 50;++i) {
			hash.insert(rand() % 100);
		}
		hash.print();

		// 测试迭代器
		for (int data : hash) {
			cout << data << " ";
		}
		cout << endl << endl;

		// 测试删除
		for (int i = 0;i < 50;++i) {
			hash.erase(rand() % 100);
		}
		hash.print();
		hash.clear();
		hash.print();
	}

	// 测试构造，拷贝，查找
	void test_construct_copy_find() {
		// 测试构造与拷贝
		mySTL::hash_set<int> hash = { 1,5,5,5,3,6,9,67,71 };
		mySTL::hash_set<int> hash2(hash);
		mySTL::hash_set<int> hash3;
		hash3 = hash2;
		hash3.print();

		mySTL::hash_set<int> hash4 = move(hash3);
		hash4.print();

		// 测试查找
		cout << *hash4.find(5) << " " << hash4.count(5) << endl;

	}

public:
	void test() {
		test_insert_iter_erase();
		cout << endl;
		test_construct_copy_find();
	}

};

2，测试 hash_map 与 hash_multimap

class test_hash_map {
private:
	void test_insert_iter_erase() {
		//测试插入功能和迭代器
		mySTL::hash_map<std::string, std::string> hash;
		hash["test"] = "测试";
		hash["test"] = "测试2";
		hash["test"] = "测试3";
		hash["data_struct"] = "数据结构";
		hash["algorithm"] = "算法";
		hash["hash_table"] = "哈希表";

		hash.print();
		for (const auto& [key, val] : hash) {
			cout << key << " : " << val << endl;
		}
	}

	void test_construct_copy() {
		mySTL::hash_multimap<std::string, std::string> hash = { 
			{"test","测试"},{"test","测试2"},{"test","测试3"},
			{"data_struct","数据结构"},{"algorithm","算法"},{"hash_table","哈希表"}
		};
		mySTL::hash_multimap<std::string, std::string> hash2(hash);
		mySTL::hash_multimap<std::string, std::string> hash3;
		hash3 = hash2;

		hash3.print();
		for (const auto& [key, val] : hash3) {
			cout << key << " : " << val << endl;
		}
		cout << endl;

		mySTL::hash_multimap<std::string, std::string> hash4 = move(hash3);
		hash4.print();
		for (const auto& [key, val] : hash4) {
			cout << key << " : " << val << endl;
		}

	}

public:
	void test() {
		test_insert_iter_erase();
		test_construct_copy();
	}

};

四，hash_table 完整代码

namespace mySTL {

	//哈希节点
	template<class T>
	struct hash_node {
		T data;
		hash_node* next;
		hash_node(const T& _data = T()) :data(_data), next(nullptr) {}
	};

	// 哈希函数族
	template<class Key>
	struct hash_func {
		size_t operator()(const Key& key)const {
			return key;
		}
	};
	template<>
	struct hash_func<std::string> {
		size_t operator()(const std::string& str)const {
			size_t res = 0;
			int seed = 131;
			for (char ch : str) {
				res *= seed;
				res += ch;
			}
			return res;
		}
	};


	// 寻找并返回不小于 n 的最小素数的函数
	size_t prime(int n) {
		// 检查一个数是否为素数的函数
		std::function<bool(int)> is_prime = [](int num) {
			if (num <= 1) return false;  // 处理非正整数
			if (num <= 3) return true;   // 2和3是素数
			if (num % 2 == 0 || num % 3 == 0) return false; // 排除能被2或3整除的数
			for (int i = 5; i * i <= num; i += 6) {
				if (num % i == 0 || num % (i + 2) == 0) return false;
			}
			return true;
		};

		if (n <= 2) return 2;			// 特殊处理小于等于2的情况
		if ((n & 1) == 0) n++;			// 如果n是偶数，从下一个奇数开始检查
		while (not is_prime(n)) n += 2;	// 只检查奇数
		return n;
	}

	// Ref 为引用类型，Ptr 为指针类型
	template<class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
	struct Hash_Iterator{
		typedef hash_node<T> Node;

		KeyOfT _kot;
		HashFunc _hf;

		Node* _node;
		const std::vector<Node*>* _table;	// 这里的 _table 一定要加 const 修饰，
											// 不然在使用 const_iterator 时类型会无法转换

		typedef T	value_type;
		typedef Ref reference;
		typedef Ptr pointer;

		typedef Hash_Iterator<T, T&, T*, KeyOfT, HashFunc> iterator; //普通迭代器类型
		typedef Hash_Iterator<T, Ref, Ptr, KeyOfT, HashFunc> self;   //当前迭代器类型


		Hash_Iterator(Node* node, const std::vector<Node*>* table) :_node(node), _table(table) {}	//用哈希节点构造当前迭代器
		Hash_Iterator(const iterator& iter) :_node(iter._node), _table(iter._table) {}				//用普通迭代器构造当前迭代器

		Ref operator*() { return _node->data; }
		Ptr operator->() { return &(operator*()); }
		bool operator==(const self& iter)const { return iter._node == _node; }
		bool operator!=(const self& iter)const { return not(iter == *this); }


		self operator++() {
			if (_node->next) {
				//如果当前节点还有下一个节点
				_node = _node->next;
				return *this;
			}
			else {
				//从下一个桶开始往后找
				size_t idx = _hf(_kot(_node->data)) % _table->size();
				for (size_t i = idx + 1;i < _table->size();++i) {
					if ((*_table)[i]) {
						//取桶中的第一个元素
						_node = (*_table)[i];
						return *this;
					}
				}
			}
			_node = nullptr;
			_table = nullptr;
			return *this;
		}

		self operator++(int) {
			self res = *this;
			++(*this);
			return res;
		}

	};


	template<class Key, class T, class KeyOfT, class HashFunc = hash_func<Key>>
	class hash_table {
	private:
		typedef hash_node<T> Node;
		HashFunc _hf;
		KeyOfT _kot;

	private:
		// 主要的成员变量
		size_t _size = 0;
		std::vector<Node*> _table;

	public:
		// 迭代器
		typedef Hash_Iterator<T, T&, T*, KeyOfT, HashFunc> iterator;
		typedef Hash_Iterator<T, const T&, const T*, KeyOfT, HashFunc> const_iterator;

		iterator begin() {
			if (empty()) return end();
			for (Node* node : _table) {
				if (node) return iterator(node, &_table);
			}
		}
		iterator end() { return iterator(nullptr, nullptr); }

		const_iterator begin()const {
			if (empty()) return end();
			for (Node* node : _table) {
				if (node) return const_iterator(node, &_table);
			}
		}
		const_iterator end()const { return const_iterator(nullptr, nullptr); }



	public:
		// 一些简单的功能
		bool empty()const { return _size == 0; }
		size_t size()const { return _size; }
		size_t table_size()const { return _table.size(); }
		// 为了便于扩展所设计的函数
		bool key_equal(Node* node,const Key& key)const { return  _kot(node->data) == key; }
		size_t next_size(size_t size)const { return prime(size); }
		// 为了方便找到索引而设计的函数
		size_t table_index(const Key& key)const { return _hf(key) % table_size(); }
		size_t table_index(const Key& key, size_t table_size)const { return _hf(key) % table_size; }

	public:
		// 辅助拷贝与析构的函数
		// 交换
		void swap(hash_table& ht) {
			std::swap(_size, ht._size);
			_table.swap(ht._table);
		}

		// 拷贝哈希表
		void copy(const hash_table& ht){
			_size = ht.size();
			_table.resize(ht.table_size());
			Node* dummy = new Node;
			for (int i = 0;i < _table.size();++i) {
				Node* pre = dummy;
				Node* node = ht._table[i];
				while (node != nullptr) {
					pre->next = new Node(node->data);
					node = node->next;
					pre = pre->next;
				}
				_table[i] = dummy->next;
				dummy->next = nullptr;
			}
			delete dummy;
		}

		// 清空
		void clear() {
			for (int i = 0;i < _table.size();++i) {
				Node* node = _table[i];
				while (node) {
					Node* next = node->next;
					delete node;
					node = next;
				}
				_table[i] = nullptr;
			}
			_size = 0;
		}

	public:
		// 构造与析构
		hash_table() :_size(0), _table(11, nullptr) {}
		~hash_table() { if (not empty()) clear(); }

	public:
		// 拷贝
		hash_table(const hash_table& ht) { copy(ht); }
		hash_table(hash_table&& ht) { swap(ht); }
		hash_table& operator=(hash_table ht) {
			swap(ht);
			return *this;
		}

	public:
		// 扩容
		void resize(size_t size) {
			size = next_size(size);
			if (size <= _size) return;
			std::vector<Node*> newTable(size, nullptr);
			for (Node* node : _table) {
				while (node) {
					size_t idx = table_index(_kot(node->data), newTable.size());
					Node* next = node->next;
					node->next = newTable[idx];
					newTable[idx] = node;
					node = next;
				}
			}
			// _table = std::move(newTable);
			_table.swap(newTable);
		}

	private:
		template<class Iter_Type>
		Iter_Type find_impli(const Key& key)const{
			size_t idx = table_index(key);
			for (Node* node = _table[idx];node;node = node->next) {
				if (key_equal(node, key)) return Iter_Type(node, &_table);
			}
			return Iter_Type(nullptr, nullptr);
		}

	public:
		// 查找，插入，删除
		iterator find(const Key& key) { return find_impli<iterator>(key); }
		const_iterator find(const Key& key)const { return find_impli<const_iterator>(key); }

		size_t count(const Key& key)const {
			size_t idx = table_index(key);
			size_t cnt = 0;
			for (Node* node = _table[idx];node;node = node->next) {
				if (key_equal(node, key)) ++cnt;
			}
			return cnt;
		}

		pair<iterator, bool> insert_unique(const T& data){
			size_t idx = table_index(_kot(data));
			for (Node* node = _table[idx]; node;node = node->next) {
				if (key_equal(node, _kot(data))) {
					// key 已经存在就直接返回
					return make_pair(iterator(node, &_table), false);
				}
			}
			iterator res = insert_equal(data);
			return make_pair(res, true);
		}

		iterator insert_equal(const T& data){
			if (_size == _table.size()) {
				// 扩容 table
				resize(_size * 2);
			}
			size_t idx = table_index(_kot(data));
			Node* node = new Node(data);
			// 头插新节点
			node->next = _table[idx];
			_table[idx] = node;
			++_size;
			return iterator(node, &_table);
		}

	public:
		size_t erase(const Key& key) {
			size_t idx = table_index(key);
			size_t count = 0;
			Node* dummy = new Node;
			dummy->next = _table[idx];
			Node* pre = dummy, * cur = _table[idx];
			while (cur) {
				if (key_equal(cur, key)) {
					pre->next = cur->next;
					delete cur;
					cur = pre->next;
					--_size;
					++count;
				}
				else {
					pre = cur;
					cur = cur->next;
				}
			}
			_table[idx] = dummy->next;
			delete dummy;
			return count;
		}

	public:
		void print()const {
			size_t idx = 0;
			for (Node* node : _table) {
				cout << idx++ << ": ";
				while (node) {
					cout << _kot(node->data) << " -> ";
					node = node->next;
				}
				cout << "null" << endl;
			}
			cout << endl;
		}

	};

}

上一篇：easyexcel的使用


下一篇：Docker的数据管理、网络通信和dockerfile