【C++】unordered

06-02 1176阅读

unordered系列map和set，与普通区别

用法几乎相同，键值唯一，区别unordered系列迭代器是单向的并且遍历出来不是有序的。unordered系列在数据规模大且无序的情况下性能更优

底层实现：

map 和 set ：基于平衡二叉树（通常是红黑树）实现，元素在树中按有序的方式存储。

unordered_map 和 unordered_set ：基于哈希表实现，元素存储在哈希桶中，存储顺序与插入顺序无关。是通过哈希函数将键（或元素）映射到哈希表的桶索引

有序性：

map和set:有序，可按自定义排序规则

unordered：无序，存储顺序取决于哈希函数和哈希桶的分配。

适用场景

map 和 set ：适用于需要元素有序的场景，如排序、范围查询等unordered_map 和 unordered_set ：适用于需要快速插入和查找的场景，对元素的顺序没有要求。

1.哈希表改造

按照以下思路进行模拟实现

1、改装哈希表(哈希桶)

2、封装map和set

3、实现普通迭代器

4、实现const迭代器

5、解决insert返回值问题 实现operator[]

6、解决key不能修改的问题

节点定义

【C++】unordered

用一个模板参数T来表示数据，unordered_set为key，map为pair，实现了泛型。

1.2增加迭代器

基本模板

【C++】unordered

总共有6个模板参数，K代表键值，T代表value值类型能实现map和set的泛型，Ptr是指针类型，Ref是引用类型，KeyOfT是用于从值中获取键值的函数，HashFunc是哈希函数将键值映射到地址上去

1.重定义一个self通用迭代器，模板参数为Ptr和Ref可以灵活地定义指针和引用类型，通常用于类的内部实现，引用或返回值。

2.重定义一个具体的迭代器iterator，其中指针类型和引用类型都被写死与T相同，是用于读写访问的迭代器，可以对容器中的元素进行修改。

3.需定义一个哈希表指针，因为自增操作时可以通过该指针方便遍历找到下一个哈希桶的位置。有如下作用：

a：提供对哈希表资源的访问。如哈希桶数组 _table、哈希函数 hf 和键提取函数 kot

b： 封装哈希表的实现细节。使哈希表的内部实现可以在不改变迭代器代码的情况下进行修改。

构造函数

【C++】unordered

1.将哈希表指针定义成const，因为在const迭代器begin和end函数中返回的this指针是const的，普通指针传进来也没问题，因为权限可以缩小不能放大，所以直接定义成const省略掉普通哈希表指针的迭代器构造

2.与set和map模拟实现中类似，一举两得，解决了返回值中非const的迭代器转化成const迭代器的过程。因为iterator的指针和引用参数写死了，就是常量。

自增++操作
self& operator++()
{
	if (_node->_next)
	{
		//当前桶还没完，继续往下遍历
		_node = _node->_next;
	}
	else
	{
		KeyOfT kot;
		HashFunc hf;
		size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
		//从下一个位置寻找
		hashi++;
		while (hashi _table.size())
		{
			if (_pht->_table[hashi])
			{
				_node = _pht->_table[hashi];
				return *this;
			}
			else
			{
				hashi++;
			}
		}
		//找完了没找到哈希桶
		_node = nullptr;
	}
	return *this;
}

1.返回对当前迭代器对象的引用（self&），以便支持连续的自增操作

2.分当前桶中继续往下遍历和查找下一个哈希桶中两种情况

3.查找下一个哈希桶时先用获取键kot函数拿到键值然后用哈希函数hf计算该键的映射哈希值。从下一个哈希桶的位置开始找不为空的哈希桶，循环条件为哈希值索引小于当前已存储桶的大小，若找到不为空哈希桶返回this指针，没找到对当前_node置空再返回this指针

前置声明

【C++】unordered

由于上图中存在相互包含问题，需要前置声明。

注意：编译器需要完整的类型定义来确定内存布局、调用成员函数和生成正确的机器码。前向声明只能用于指针和引用类型，因为这些类型不需要完整的类型信息。在需要直接实例化对象或调用成员函数时，必须包含完整的类型定义。

所以选择前向声明哈希表指针

  • 完整代码 
    //前置声明
template
class HashTable;
template
struct HTIterator
{
	typedef HashNode Node;
	typedef HTIterator self;
	typedef HTIterator iterator;
	Node* _node;
	const HashTable* _pht;
	HTIterator(Node* node,const HashTable* pht)
		:_node(node)
		, _pht(pht)
	{ }
	// 普通迭代器时，他是拷贝构造
	// const迭代器时，他是构造
	HTIterator(const iterator& it)
		:_node(it._node)
		, _pht(it._pht)
	{ }
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	self& operator++()
	{
		if (_node->_next)
		{
			//当前桶还没完，继续往下遍历
			_node = _node->_next;
		}
		else
		{
			KeyOfT kot;
			HashFunc hf;
			size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
			//从下一个位置寻找
			hashi++;
			while (hashi _table.size())
			{
				if (_pht->_table[hashi])
				{
					_node = _pht->_table[hashi];
					return *this;
				}
				else
				{
					hashi++;
				}
			}
			//找完了没找到哈希桶
			_node = nullptr;
		}
		return *this;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};

    1.3哈希表基本模板

    【C++】unordered

    模板参数与模板重定义和迭代器的相同，注意要加上迭代器的友元声明，在迭代器中会访问哈希表中的私有变量

    获取迭代器
    iterator begin()
{
	//找第一个桶
	for (size_t i = 0; i  
 
 
    注意迭代器是由当前节点和哈希表指针构成，末尾迭代器返回空指针和this指针。
     
 

    构造与析构函数
     

    HashTable()
{
	_table.resize(10, nullptr);
}
~HashTable()
{
	for (size_t i = 0; i _next;
			delete cur;
			cur = next;
		}
		_table[i] = nullptr;
	}
}

     
 
 
    resize开辟和初始化空间为空，由于vector数组中每个位置都存储着链表头指针，自定义类型需要手动释放空间
     
 

    插入
     

    pair Insert(const T&data)
{
	KeyOfT kot;
	iterator it=Find(kot(data));
	if(it!=end())
	{
		return make_pair(it,false);
	}
	HashFunc hf;
	//检查扩容，载荷因子到1就扩容
	if (_n == _table.size())
	{
		size_t newsize = _table.size() * 2;
		vector newtable;
		newtable.resize(newsize, nullptr);
		//遍历旧表，将节点转移挂到新表
		for (size_t i = 0; i _next;
				//头插
				cur->_next = newtable[hashi];
				newtable[hashi] = cur;
				//更新节点
				cur = next;
			}
			_table[i] = nullptr;
		}
		//交换新旧表
		_table.swap(newtable);
	}
	//插入新节点
	size_t hashi = hf(kot(data)) % _table.size();
	Node* newnode = new Node(data);
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	++_n;
	return make_pair(iterator(newnode,this),true);
}

     
 
 
    1.创建一个提取键对象，可以像函数一样调用
    2.检查待插入元素是否已存在
    3.定义一个哈希函数对象，重载了()也可以像函数一样被调用
    4.检查扩容，与原哈希表逻辑相同
    5.重新计算哈希值再创建新节点并插入，更新有效值元素，返回一个由迭代器和bool值构成的键值对
     
  
  
    由于unordered_map的[]重载需要通过insert实现，需要提供对指定键的值的访问，如果键不存在，则需要插入一个默认构造的值。所以insert的返回值要变成键值对
     
  
 

    查找
     

    iterator Find(const K& key)
{
	KeyOfT kot;
	HashFunc hf;
	size_t hashi = hf(key) % _table.size();
	//在该哈希桶中遍历寻找
	Node* cur = _table[hashi];
	while (cur)
	{
		if (kot(cur->_data) == key)
		{
			return iterator(cur,this);
		}
		cur = cur->_next;
	}
	return end();
}

     
 
 
    与原哈希表区别在于返回值变成迭代器
     
 

    删除
     

    bool Erase(const K& key)
{
	HashFunc hf;
	size_t hashi = hf(key) % _table.size();
	Node* cur = _table[hashi];
	Node* prev = nullptr;
	while (cur)
	{
		if (kot(cur->_data) == key)
		{
			//判断要删除节点为头节点情况
			if (prev == nullptr)
			{
				_table[hashi] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}
			--_n;
			delete cur;
			return true;
		}
		//更新节点继续遍历
		prev = cur;
		cur = cur->_next;
	}
	return false;
}

     
 
 
    与原哈希表相同
     
 

    哈希函数
     

    template
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		//强转成返回值类型
		return (size_t)key;
	}
};
//模板特化
template
struct DefaultHashFunc
{
	size_t operator()(const string& str)
	{
		// BKDR,string的哈希算法
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};

     
 
 
    与原哈希表相同
    • 代码 
      template
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		//强转成返回值类型
		return (size_t)key;
	}
};
//模板特化
template
struct DefaultHashFunc
{
	size_t operator()(const string& str)
	{
		// BKDR,string的哈希算法
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};
namespace hash_bucket
{
	template
	struct HashNode
	{
		T _data;
		HashNode* _next;
		HashNode(const T&data)
			:_data(data)
			, _next(nullptr)
		{
		}
	};
	//前置声明
	template
	class HashTable;
	template
	struct HTIterator
	{
		typedef HashNode Node;
		typedef HTIterator self;
		typedef HTIterator iterator;
		Node* _node;
		const HashTable* _pht;
		HTIterator(Node* node,const HashTable* pht)
			:_node(node)
			, _pht(pht)
		{ }
		// 普通迭代器时，他是拷贝构造
		// const迭代器时，他是构造
		HTIterator(const iterator& it)
			:_node(it._node)
			, _pht(it._pht)
		{ }
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		self& operator++()
		{
			if (_node->_next)
			{
				//当前桶还没完，继续往下遍历
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				HashFunc hf;
				size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
				//从下一个位置寻找
				hashi++;
				while (hashi _table.size())
				{
					if (_pht->_table[hashi])
					{
						_node = _pht->_table[hashi];
						return *this;
					}
					else
					{
						hashi++;
					}
				}
				//找完了没找到哈希桶
				_node = nullptr;
			}
			return *this;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		bool operator==(const self& s)
		{
			return _node == s._node;
		}
	};
	// set -> hash_bucket::HashTable _ht;
	// map -> hash_bucket::HashTable _ht;
	template
	class HashTable
	{
		typedef HashNode Node;
		//友元声明
		template
		friend struct HTIterator;
	public:
		typedef HTIterator iterator;
		typedef HTIterator const_iterator;
		iterator begin()
		{
			//找第一个桶
			for (size_t i = 0; i _next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}
		pair Insert(const T&data)
		{
			KeyOfT kot;
			iterator it=Find(kot(data));
			if(it!=end())
			{
				return make_pair(it,false);
			}
			HashFunc hf;
			//检查扩容，载荷因子到1就扩容
			if (_n == _table.size())
			{
				size_t newsize = _table.size() * 2;
				vector newtable;
				newtable.resize(newsize, nullptr);
				//遍历旧表，将节点转移挂到新表
				for (size_t i = 0; i _next;
						//头插
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;
						//更新节点
						cur = next;
					}
					_table[i] = nullptr;
				}
				//交换新旧表
				_table.swap(newtable);
			}
			//插入新节点
			size_t hashi = hf(kot(data)) % _table.size();
			Node* newnode = new Node(data);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode,this),true);
		}
		iterator Find(const K& key)
		{
			KeyOfT kot;
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			//在该哈希桶中遍历寻找
			Node* cur = _table[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur,this);
				}
				cur = cur->_next;
			}
			return end();
		}
		bool Erase(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					//判断要删除节点为头节点情况
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				//更新节点继续遍历
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		void Print()
		{
			for (size_t i = 0; i ", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout _kv.first _next;
				}
				printf("NULL\n");
			}
			cout 
		ee::unordered_set
			//*it += 10;不能修改key
			cout 
			//不能修改key
			//dit-first += 'e';
			dit-second += 'e';
			cout 
			cout 
	template
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename hash_bucket::HashTable
			return _ht.begin();
		}
		const_iterator end()const
		{
			return _ht.end();
		}
		pair
			//return _ht.Insert(key);编译器严格检查下可能报错
			pair
	template
		struct MapKeyOfT
		{
			const K& operator()(const pair
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::HashTable
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		const_iterator begin()const
		{
			return _ht.begin();
		}
		const_iterator end()const
		{
			return _ht.end();
		}
		pair
			return _ht.Insert(kv);
		}
		V& operator[](const K&key)
		{
			pair
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。

相关阅读

目录[+]

取消
微信二维码
微信二维码
支付宝二维码