当前位置： 首页 > article >正文

C++ unordered_map unordered_set 模拟实现

article 2025/3/17 14:00:38

1. 关于unordered_map 和 unordered_set

区别于C++的另外两个容器map和set，map和set的底层是红黑树；而unordered_map和unordered_set的底层是哈希

因为unordered_map和unordered_set的底层是哈希，因此他们存储的数据是没有顺序​​unordered​​的

下面，我们就通过之前写的基于开散列（哈希桶）的代码，来封装出一份简单的unordered_map和unordered_set

开散列哈希表的代码如下：

namespace open_hash
{
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		struct Node
		{
			std::pair<K, V> kv;
			Node* next;

			Node(const std::pair<K, V>& KV = std::pair<K, V>()) 
				: kv(KV),
				next(nullptr){}
		};


	public:
		HashTable()
			: _load_factor(1.0),
			_n(0) 
		{
			_hash.resize(10, nullptr);
		}

		~HashTable()
		{
			for (auto& node : _hash)
			{
				while (node)
				{
					Node* next = node->next;
					delete node;
					node = next;
				}
			}
		}

		size_t size() const
		{
			return _n;
		}

		Node* find(const K& key)
		{
			size_t hash_index = _hash_func(key) % _hash.capacity();
			Node* node = _hash[hash_index];
			while (node)
			{
				if (node->kv.first == key)
					return node;

				node = node->next;
			}

			return nullptr;
		}

		bool insert(std::pair<K, V> kv)
		{
			if (find(kv.first))
				return false;

			if (1.0 * _n / _hash.capacity() >= _load_factor)
			{
				size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();
				HashTable<K, V, Hash> new_hash;
				new_hash._hash.resize(capacity, nullptr);

				//将原来哈希桶中的节点转移到新的桶中
				for (auto& node : _hash)
				{
					while (node)
					{
						//从新计算映射关系
						size_t hash_index = _hash_func(node->kv.first) % new_hash._hash.capacity();
						Node* next = node->next;

						node->next = new_hash._hash[hash_index];
						new_hash._hash[hash_index] = node;

						node = next;
					}
				}

				_hash.swap(new_hash._hash);
			}

			Node* newnode = new Node(kv);
			size_t hash_index = _hash_func(kv.first) % _hash.capacity();

			//头插
			newnode->next = _hash[hash_index];
			_hash[hash_index] = newnode;

			++_n;
			return true;
		}

		bool erase(const K& key)
		{
			size_t hash_index = _hash_func(key) % _hash.capacity();
			Node* node = _hash[hash_index];
			Node* prev = nullptr;
			while (node)
			{
				if (node->kv.first == key)
				{
					if (prev == nullptr)
						_hash[hash_index] = _hash[hash_index]->next;
					else
						prev->next = node->next;

					delete node;
					--_n;

					return true;
				}

				prev = node;
				node = node->next;
			}

			return false;
		}

	private:
		std::vector<Node*> _hash;
		double _load_factor;
		Hash _hash_func;
		size_t _n;
	};
}

2. 模拟实现

2.1 修改哈希表的类模板参数

如果想要用同一份哈希表代码来模拟实现出unordered_map和unordered_set两份容器，就需要考虑一个问题：

  • unordered_set是Key结构的；而unordered_map是Key_Value结构的

  • 在上面的哈希表代码中，我们直接使用的就是KV模型，因此就需要想办法来屏蔽这种差异

可以通过这样的方式来解决：

将哈希表的模板参数改成这样：

template<class K, class T, class KeyOfT, class Hash>

K：Key值的类型

T：表示要存放什么类型的数据。

  • 对于unordered_set，填写的就是K
  • 对于unordered_set，填写的就是std::pair<K, V>
    在这里插入图片描述

Hash：计算哈希值的哈希函数

KeyOfT：获得键值Key的函数

  • 由于哈希表自己不知道存储的数据到底是Key模型的还是Key_Value模型的

  • 因此需要通过一个函数KeyOfT来获得数据的键值

  • 而这个KeyOfT由封装哈希表的unordered_map和unordered_set来提供

    类似这样：

    对于unordered_map，Key值是pair.first

    template <class K, class V, class Hash = HashFunc<const K>>
class unordered_map
{
	struct MapKeyOfT
	{
		const K operator()(const std::pair<const K, V>& p) const 
		{ 
			return p.first;
		}
	};
public:
	using HT = typename HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>;

private:
	HT _ht;
};

    对于unordered_set，Key值就是自己本身

    template <class K, class Hash = HashFunc<const K>>
class unordered_set
{
	struct SetKeyOfT
	{
		const K operator()(const K& key) const
		{
			return key;
		}
	};
public:
	using HT = typename HashTable<K, K, SetKeyOfT, Hash>;

private:
	HT _ht;
};

2.2 哈希表的迭代器实现

注：STL中的unordered_map(set)​只支持正向迭代器，不支持反向迭代器

规定：哈希表迭代器的begin()，为第一个不为空的哈希桶中的第一个节点；哈希表迭代器的end()，为nullptr

对于哈希表的迭代器，我们只需要关注operator++()即可

对于开散列哈希桶的哈希表，当其迭代器向后移动一位之后，可能出现两种情况：

  • 移动之后，不为空，说明这个哈希桶（单链表）还没有走完，那么直接返回这个节点即可

  • 移动之后，为空，说明这个哈希桶（单链表）已经走完了

    • 那么就找下一个不为空的哈希桶，并返回这个哈希桶的第一个节点
    • 如果找不到下一个不为空的哈希桶了，就返回end()

在这里插入图片描述

通过上面的分析我们发现，对于哈希表的迭代器类，其需要两个成员来完成迭代工作：

  • ​Node​​ ：用于迭代当前所在的哈希桶
  • ​HashTable​​ ：用于迭代所有的哈希桶

根据上面的分析，我么可以实现出哈希表迭代器：

//非const迭代器
template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>
struct __HashIterator
{
	using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;
	using HT = typename HashTable<K, T, KeyOfT, Hash>;
	using Self = typename  __HashIterator< K, T, KeyOfT, Hash>;

	Node* node;
	HT* ht;

	__HashIterator(Node* n, HT* h) : node(n), ht(h) {}

	//前置++
	Self& operator++()
	{
		//如果已经是end()，直接返回
		if (nullptr == node)
			return *this;

		Node* next = node->next;
		if (next != nullptr)	//如果哈希桶还没走完，就迭代到哈希桶的下一个
		{
			node = next;
			return *this;
		}

		//否则，找到下一个非空哈希桶
		size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();
		while (++hash_index < ht->_hash.capacity())
		{
			//找到了，就迭代到这个非空哈希桶的第一个节点
			if (ht->_hash[hash_index])
			{
				node = ht->_hash[hash_index];
				return *this;
			}
		}

		//走到这里，说明已经把哈希数组走完了（不需要往回走）
		//也就是把所有的哈希桶走完了
		//即走到end() nullptr
		node = nullptr;
		return *this;
	}

	//后置++
	Self operator++(int)
	{
		Self temp = *this;
		this->operator++();

		return temp;
	}

	bool operator==(const Self& it) const
	{
		return node == it.node;
	}

	bool operator!=(const Self& it) const
	{
		return node != it.node;
	}

	T& operator*() const
	{
		return node->data;
	}

	T* operator->() const
	{
		return &node->data;
	}
};

//const迭代器
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __HashConstIterator
{
	using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;
	using HT = typename HashTable<K, T, KeyOfT, Hash>;
	using Self = typename  __HashConstIterator< K, T, KeyOfT, Hash>;

	const Node* node;
	const HT* ht;

	__HashConstIterator(const Node* n, const HT* h) : node(n), ht(h) {}

	//前置++
	Self& operator++()
	{
		if (nullptr == node)
			return *this;

		Node* next = node->next;
		if (next != nullptr)
		{
			node = next;
			return *this;
		}

		size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();
		while (++hash_index < ht->_hash.capacity())
		{
			if (ht->_hash[hash_index])
			{
				node = ht->_hash[hash_index];
				return *this;
			}
		}

		//走到这里，说明已经把哈希数组走完了（不需要往回走）
		//也就是把所有的哈希桶走完了
		//即走到尾 nullptr
		node = nullptr;
		return *this;
	}

	//后置++
	Self operator++(int)
	{
		Self temp = *this;
		this->operator++();

		return temp;
	}

	bool operator==(const Self& it) const
	{
		return node == it.node;
	}

	bool operator!=(const Self& it) const
	{
		return node != it.node;
	}

	const T& operator*() const
	{
		return node->data;
	}

	const T* operator->() const
	{
		return &node->data;
	}
};

2.3 修改哈希表部分函数的返回值

后续我们模拟实现unordered_set和unordered_map的接口都是直接调用其内部封装的哈希表的接口

因此，为了符合规范，我们需要对原先哈希表部分函数的返回值进行修改

find()

以unordered_map的成员函数find()为例：

iterator find ( const key_type& k );
const_iterator find ( const key_type& k ) const;
  • 对于非const对象，返回非const迭代器
  • 对于const对象，返回const迭代器
iterator find(const K& key)
{
	size_t hash_index = _hash_func(key) % _hash.capacity();
	Node* node = _hash[hash_index];
	while (node)
	{
		if (_key_of_t(node->data) == key)
			return iterator(node, this);

		node = node->next;
	}

	return iterator(nullptr, this);
}

const_iterator find(const K& key) const 
{
	size_t hash_index = _hash_func(key) % _hash.capacity();
	Node* node = _hash[hash_index];
	while (node)
	{
		if (_key_of_t(node->data) == key)
			return const_iterator(node, this);

		node = node->next;
	}

	return const_iterator(nullptr, this);
}

insert()

以unordered_map的成员函数insert()为例：

pair<iterator,bool> insert ( const value_type& val );

可见，返回值是一个pair<iterator,bool>，其含义如下：

  • 如果哈希表中已经有相同关键字的元素，那么就表示插入失败，并返回指向这个相同关键字元素的迭代器
  • 如果哈希表中没有相同关键字的元素，那么就插入成功，并返回这个指向新插入的元素的迭代器
std::pair<iterator, bool> insert(const T& data)
{
	auto it = find(_key_of_t(data));
	if (it != end())
		return std::make_pair(it, false);

	if (1.0 * _n / _hash.capacity() >= _load_factor)
	{
		size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();
		HashTable<K, T, KeyOfT, Hash> new_hash;
		new_hash._hash.resize(capacity, nullptr);

		//将原来哈希桶中的节点转移到新的桶中
		for (auto& node : _hash)
		{
			while (node)
			{
				//从新计算映射关系
				size_t hash_index = _hash_func(_key_of_t(node->data)) % new_hash._hash.capacity();
				Node* next = node->next;

				node->next = new_hash._hash[hash_index];
				new_hash._hash[hash_index] = node;

				node = next;
			}
		}

		_hash.swap(new_hash._hash);
	}

	Node* newnode = new Node(data);
	size_t hash_index = _hash_func(_key_of_t(data)) % _hash.capacity();

	//头插
	newnode->next = _hash[hash_index];
	_hash[hash_index] = newnode;

	++_n;
	return std::make_pair(iterator(newnode, this), true);
}

erase()

以unordered_map的成员函数erase()为例：

by position (1)	iterator erase ( const_iterator position );

by key (2)	size_type erase ( const key_type& k );

  1. 通过迭代器删除

    • 如果删除成功，就返回指向被删除元素的下一个元素的迭代器
    • 如果删除失败，就返回end()

  2. 通过关键字Key删除

    • 如果删除成功，返回true
    • 如果删除失败，返回false
iterator erase(const_iterator pos)
{
	//不能删除end()
	if (pos == cend())
		return cend();

	size_t hash_index = _key_of_t(*pos) % _hash.capacity();
	Node* node = _hash[hash_index];
	Node* prev = nullptr;
	Node* next = nullptr;
	while (node)
	{
		if (_key_of_t(node->data) == _key_of_t(*pos))
		{
			if (prev == nullptr)
				_hash[hash_index] = _hash[hash_index]->next;
			else
				prev->next = node->next;

			delete node;
			--_n;

			//找到下一个节点
			next = (prev == nullptr) ? _hash[hash_index] : prev->next;
			if (next == nullptr)
			{
				while (++hash_index < _hash.capacity())
				{
					if (_hash[hash_index])
					{
						next = _hash[hash_index];
						break;
					}
				}
			}

			return iterator(next, this);
		}

		prev = node;
		node = node->next;
	}

	return end();
}

bool erase(const K& key)
{
	size_t hash_index = _hash_func(key) % _hash.capacity();
	Node* node = _hash[hash_index];
	Node* prev = nullptr;
	while (node)
	{
		if (_key_of_t(node->data) == key)
		{
			if (prev == nullptr)
				_hash[hash_index] = _hash[hash_index]->next;
			else
				prev->next = node->next;

			delete node;
			--_n;

			return true;
		}

		prev = node;
		node = node->next;
	}

	return false;
}

开散列哈希表实现代码

namespace open_hash
{
	template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>
	class HashTable;

	template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>
	struct __HashIterator
	{
		using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;
		using HT = typename HashTable<K, T, KeyOfT, Hash>;
		using Self = typename  __HashIterator< K, T, KeyOfT, Hash>;

		Node* node;
		HT* ht;

		__HashIterator(Node* n, HT* h) : node(n), ht(h) {}

		//前置++
		Self& operator++()
		{
			if (nullptr == node)
				return *this;

			Node* next = node->next;
			if (next != nullptr)
			{
				node = next;
				return *this;
			}

			size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();
			while (++hash_index < ht->_hash.capacity())
			{
				if (ht->_hash[hash_index])
				{
					node = ht->_hash[hash_index];
					return *this;
				}
			}

			//走到这里，说明已经把哈希数组走完了（不需要往回走）
			//也就是把所有的哈希桶走完了
			//即走到尾 nullptr
			node = nullptr;
			return *this;
		}

		//后置++
		Self operator++(int)
		{
			Self temp = *this;
			this->operator++();

			return temp;
		}

		bool operator==(const Self& it) const
		{
			return node == it.node;
		}

		bool operator!=(const Self& it) const
		{
			return node != it.node;
		}

		T& operator*() const
		{
			return node->data;
		}

		T* operator->() const
		{
			return &node->data;
		}
	};

	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
	struct __HashConstIterator
	{
		using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;
		using HT = typename HashTable<K, T, KeyOfT, Hash>;
		using Self = typename  __HashConstIterator< K, T, KeyOfT, Hash>;

		const Node* node;
		const HT* ht;

		__HashConstIterator(const Node* n, const HT* h) : node(n), ht(h) {}

		//支持非const迭代器到const迭代器的类型转换
		__HashConstIterator(const __HashIterator<K, T, KeyOfT>& it) : node(it.node), ht(it.ht) {}

		//前置++
		Self& operator++()
		{
			if (nullptr == node)
				return *this;

			Node* next = node->next;
			if (next != nullptr)
			{
				node = next;
				return *this;
			}

			size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();
			while (++hash_index < ht->_hash.capacity())
			{
				if (ht->_hash[hash_index])
				{
					node = ht->_hash[hash_index];
					return *this;
				}
			}

			//走到这里，说明已经把哈希数组走完了（不需要往回走）
			//也就是把所有的哈希桶走完了
			//即走到尾 nullptr
			node = nullptr;
			return *this;
		}

		//后置++
		Self operator++(int)
		{
			Self temp = *this;
			this->operator++();

			return temp;
		}

		bool operator==(const Self& it) const
		{
			return node == it.node;
		}

		bool operator!=(const Self& it) const
		{
			return node != it.node;
		}

		const T& operator*() const
		{
			return node->data;
		}

		const T* operator->() const
		{
			return &node->data;
		}
	};

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		friend struct __HashIterator<K, T, KeyOfT, Hash>;;
		friend struct __HashConstIterator<K, T, KeyOfT, Hash>;

	public:
		struct Node
		{
			T data;
			Node* next;

			Node(const T& Data = T()) 
				: data(Data),
				next(nullptr){}
		};

	public:
		using iterator = __HashIterator<K, T, KeyOfT, Hash>;
		using const_iterator = __HashConstIterator<K, T, KeyOfT, Hash>;
		using HT = HashTable<K, T, KeyOfT, Hash>;

	public:
		HashTable()
			: _load_factor(1.0),
			_n(0) 
		{
			_hash.resize(10, nullptr);
		}

		//拷贝构造
		HashTable(const HT& ht)
			:_load_factor(ht._load_factor),
			_n(ht._n),
			_hash_func(ht._hash_func),
			_key_of_t(ht._key_of_t)
		{
			_hash.resize(ht._hash.capacity(), nullptr);

			for (auto& node : ht._hash)
			{
				Node* cur = node;
				while (cur)
				{
					size_t hash_index = _hash_func(_key_of_t(cur->data)) % _hash.capacity();
					Node* newnode = new Node(cur->data);

					newnode->next = _hash[hash_index];
					_hash[hash_index] = newnode;

					cur = cur->next;
				}
			}
		}

		//移动构造
		HashTable(HT&& ht)
		{
			swap(ht);
		}

		HT& operator=(const HT& ht)
		{
			HT temp(ht);
			swap(temp);

			return *this;
		}

		//移动赋值
		HT& operator=(HT&& ht)
		{
			swap(ht);

			return *this;
		}

		~HashTable()
		{
			for (auto& node : _hash)
			{
				while (node)
				{
					Node* next = node->next;
					delete node;
					node = next;
				}
			}
		}

		void swap(HT& ht)
		{
			std::swap(_hash, ht._hash);
			std::swap(_n, ht._n);
			std::swap(_hash_func, ht._hash_func);
			std::swap(_key_of_t, ht._key_of_t);
			std::swap(_load_factor, ht._load_factor);
		}

		iterator begin()
		{
			//找到第一个非空的哈希桶
			for (auto& node : _hash)
			{
				if (node)
					return iterator(node, this);
			}

			return iterator(nullptr, this);
		}

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

		const_iterator begin() const
		{
			//找到第一个非空的哈希桶
			for (auto& node : _hash)
			{
				if (node)
					return const_iterator(node, this);
			}

			return const_iterator(nullptr, this);
		}

		const_iterator cbegin() const
		{
			//找到第一个非空的哈希桶
			for (auto& node : _hash)
			{
				if (node)
					return const_iterator(node, this);
			}

			return const_iterator(nullptr, this);
		}

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

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

		size_t size() const
		{
			return _n;
		}

		iterator find(const K& key)
		{
			size_t hash_index = _hash_func(key) % _hash.capacity();
			Node* node = _hash[hash_index];
			while (node)
			{
				if (_key_of_t(node->data) == key)
					return iterator(node, this);

				node = node->next;
			}

			return iterator(nullptr, this);
		}

		const_iterator find(const K& key) const 
		{
			size_t hash_index = _hash_func(key) % _hash.capacity();
			Node* node = _hash[hash_index];
			while (node)
			{
				if (_key_of_t(node->data) == key)
					return const_iterator(node, this);

				node = node->next;
			}

			return const_iterator(nullptr, this);
		}

		std::pair<iterator, bool> insert(const T& data)
		{
			auto it = find(_key_of_t(data));
			if (it != end())
				return std::make_pair(it, false);

			if (1.0 * _n / _hash.capacity() >= _load_factor)
			{
				size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();
				HashTable<K, T, KeyOfT, Hash> new_hash;
				new_hash._hash.resize(capacity, nullptr);

				//将原来哈希桶中的节点转移到新的桶中
				for (auto& node : _hash)
				{
					while (node)
					{
						//从新计算映射关系
						size_t hash_index = _hash_func(_key_of_t(node->data)) % new_hash._hash.capacity();
						Node* next = node->next;

						node->next = new_hash._hash[hash_index];
						new_hash._hash[hash_index] = node;

						node = next;
					}
				}

				_hash.swap(new_hash._hash);
			}

			Node* newnode = new Node(data);
			size_t hash_index = _hash_func(_key_of_t(data)) % _hash.capacity();

			//头插
			newnode->next = _hash[hash_index];
			_hash[hash_index] = newnode;

			++_n;
			return std::make_pair(iterator(newnode, this), true);
		}

		iterator erase(const_iterator pos)
		{
			//不能删除end()
			if (pos == cend())
				return cend();

			size_t hash_index = _key_of_t(*pos) % _hash.capacity();
			Node* node = _hash[hash_index];
			Node* prev = nullptr;
			Node* next = nullptr;
			while (node)
			{
				if (_key_of_t(node->data) == _key_of_t(*pos))
				{
					if (prev == nullptr)
						_hash[hash_index] = _hash[hash_index]->next;
					else
						prev->next = node->next;

					delete node;
					--_n;

					//找到下一个节点
					next = (prev == nullptr) ? _hash[hash_index] : prev->next;
					if (next == nullptr)
					{
						while (++hash_index < _hash.capacity())
						{
							if (_hash[hash_index])
							{
								next = _hash[hash_index];
								break;
							}
						}
					}

					return iterator(next, this);
				}

				prev = node;
				node = node->next;
			}

			return end();
		}

		bool erase(const K& key)
		{
			size_t hash_index = _hash_func(key) % _hash.capacity();
			Node* node = _hash[hash_index];
			Node* prev = nullptr;
			while (node)
			{
				if (_key_of_t(node->data) == key)
				{
					if (prev == nullptr)
						_hash[hash_index] = _hash[hash_index]->next;
					else
						prev->next = node->next;

					delete node;
					--_n;

					return true;
				}

				prev = node;
				node = node->next;
			}

			return false;
		}

	private:
		std::vector<Node*> _hash;
		double _load_factor;
		Hash _hash_func;
		KeyOfT _key_of_t;
		size_t _n;
	};
}

2.4 unordered_set 模拟实现

namespace lwj
{
	using namespace open_hash;

	template <class K, class Hash = HashFunc<const K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K operator()(const K& key) const
			{
				return key;
			}
		};
	public:
		using HT = typename HashTable<K, const K, SetKeyOfT, Hash>;
		using iterator = typename HT::iterator;
		using const_iterator = typename HT::const_iterator;
		using Self = typename unordered_set<K, Hash>;

		//支持默认构造
		unordered_set() = default;

		//拷贝构造
		unordered_set(const Self& set)
		{
			_ht = set._ht;
		}

		//移动构造
		unordered_set(Self&& set)
		{
			_ht.swap(set._ht);
		}

		//拷贝赋值
		Self& operator=(const Self& set)
		{
			_ht = set._ht;

			return *this;
		}

		//移动复赋值
		Self& operator=(Self&& set)
		{
			_ht.swap(set._ht);

			return *this;
		}

		bool count(const K& key) const
		{
			return find(key) != end();
		}

		iterator find(const K& key)
		{
			return _ht.find(key);
		}

		const_iterator find(const K& key) const
		{
			return _ht.find(key);
		}

		std::pair<iterator, bool> insert(const K& val)
		{
			return _ht.insert(val);
		}

		bool erase(const K& key)
		{
			return _ht.erase(key);
		}

		iterator erase(const_iterator pos)
		{
			return _ht.erase(pos);
		}

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

		const_iterator begin() const
		{
			return _ht.cbegin();
		}

		const_iterator cbegin() const
		{
			return _ht.cbegin();
		}

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

		const_iterator end() const
		{
			return _ht.cend();
		}

		const_iterator cend() const
		{
			return _ht.cend();
		}


	private:
		HT _ht;
	};
}

2.5 unordered_map 模拟实现

operator[] ()

mapped_type& operator[] ( const key_type& k );
mapped_type& operator[] ( key_type&& k );

这个函数的作用是：查找Key值所对应的Value，这分为两种情况：

  • Key值不存在，那么该函数就会直接向hash中以Key为键值插入一个新的键值对，然后返回这个键值对的Value
  • Key值存在，那么就返回该Key值对应的Value

我们可以直接利用​​insert​​的返回值来实现：

V& operator[](const K& key)
{
	//无论inset成功插入与否，其都会返回一个指向key值的迭代器
	std::pair<iterator, bool> p = insert({ key, V() });
	return p.first->second;
}

整体实现

namespace lwj
{
	using namespace open_hash;

	template <class K, class V, class Hash = HashFunc<const K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K operator()(const std::pair<const K, V>& p) const 
			{ 
				return p.first;
			}
		};
	public:
		using HT = typename HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>;
		using iterator = typename HT::iterator;
		using const_iterator = typename HT::const_iterator;
		using Self = typename unordered_map<K, V, Hash>;

		//支持默认构造
		unordered_map() = default;

		//拷贝构造
		unordered_map(const Self& map)
		{
			_ht = map._ht;
		}

		//移动构造
		unordered_map(Self&& map)
		{
			_ht.swap(map._ht);
		}

		//拷贝赋值
		Self& operator=(const Self& map)
		{
			_ht = map._ht;

			return *this;
		}

		//移动赋值
		Self& operator=(Self&& map)
		{
			_ht.swap(map._ht);

			return *this;
		}

		V& operator[](const K& key)
		{
			std::pair<iterator, bool> p = insert({ key, V() });
			return p.first->second;
		}

		bool count(const K& key) const
		{
			return find(key) != end();
		}

		iterator find(const K& key)
		{
			return _ht.find(key);
		}

		const_iterator find(const K& key) const
		{
			return _ht.find(key);
		}

		std::pair<iterator, bool> insert(const std::pair<const K, V>& val)
		{
			return _ht.insert(val);
		}

		bool erase(const K& key)
		{
			return _ht.erase(key);
		}

		iterator erase(const_iterator pos)
		{
			return _ht.erase(pos);
		}

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

		const_iterator begin() const
		{
			return _ht.cbegin();
		}

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

		const_iterator end() const
		{
			return _ht.cend();
		}

	private:
		HT _ht;
	};
}

http://www.kler.cn/a/587002.html

相关文章：

  • Certbot实现SSL免费证书自动续签（CentOS 7版 + Docker部署的nginx）
  • 测试工程师指南：基于需求文档构建本地安全知识库的完整实战
  • HarmonyOS第24天:鸿蒙应用安全秘籍：如何为用户数据筑牢防线？
  • 使用Python实现经典贪吃蛇游戏教程
  • python相关语法的学习文档1
  • 4.3 计算属性与watch的类型守卫实现
  • 软考高级《系统架构设计师》知识点（十三）
  • Day2 导论 之 「存储器，IO，微机工作原理」
  • 代码随想录二刷|图论6
  • 【.Net 9下使用Tensorflow.net---通过LSTM实现中文情感分析】
  • C++中std::count` 和 `std::count_if`的用法和示例
  • 数据结构-单链表专题
  • 【开源代码解读】AI检索系统R1-Searcher通过强化学习RL激励大模型LLM的搜索能力
  • DataEase：一款国产开源数据可视化分析工具
  • 蓝桥杯Python赛道备赛——Day5：算术（一）（数学问题）
  • 在Linux中安装Nginx
  • 机器学习之线性代数
  • 【蓝桥杯】24省赛：数字串个数
  • 使用 BookMarkHub 插件进行书签同步
  • 一文了解CAS