`unordered_map` 和 `unordered_set`

2024-05-14 09:44
文章标签 set map unordered

本文主要是介绍`unordered_map` 和 `unordered_set`，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

unordered —— 无序的，从表面上来看，与 map 和 set 不同之处就在于，unordered_map 和 unordered_set 无法保证插入数据是有序的；

尽管如此，由于这两种容器内部封装了“哈希桶”，可以实现快速查找数据 —— 这一优点与 map 和 set 相同。

其实，除了内部结构的不同外，其余与 map 和 set 没什么不同，一样的 insert、find、erase … … 在我们模拟过 map set 的基础上，再学习封装 无序map 和 无序set 实在简单。

因此，本文的重点在于迭代器的运行逻辑 —— operator++() ，和理解模板、仿函数等。

最后，补充一个概念：

哈希 是一种思想，将传入的数据映射成一个或多个整型；哈希表 / 哈希桶 则是一种实现哈希思想的结构。

一、改造哈希桶

1.1 初步搭建 HashTable
	// 改造 HashNodetemplate<class T> struct HashNode{HashNode<T>* _next; T _data;HashNode(const T& data):_next(nullptr),_data(data){}};// 改造 HashTable// 此处 HashFunc 与《开散列哈希桶》中提供的无异// KeyOfT 与 map set 中的无异，都是用于从 T 中取到键值 template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> class HashTable{public:typedef HashNode<T> Node;private:vector<Node*> _tables;size_t _n = 0;};
1.2 数据插入 数据查找
  • 数据插入 —— Insert()
	pair<iterator, bool> Insert(const T& data){KeyOfT kot;iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iteratorif (ret != end())// 找到了{return make_pair(ret, false);}// 扩容 // ... // 插入Hash hs;size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;_n++;return make_pair(new_iterator, true); // 此处为伪代码！}

与普通哈希桶不同的地方在于此： size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值 ，多套了一层仿函数。

PS：

  1. 扩容逻辑与哈希桶完全一致。

  2. return make_pair(new_iterator, true); 为伪代码，用 new_iterator 代表插入节点的迭代器 —— 后面介绍迭代器时，会将这里的坑填上！

  • 数据查找 —— Find()

很多新手不理解为什么在封装 map set 要这样构造 —— 好像传入了两个 Key ：

map: RBTree<K, pair<const K, V>, ... > _t;

set: RBTree<K, const K, ...> _t;

我们通常是 t.find(key1); t,erase(key2); 这种方式使用 find() 和 erase() ，无论 t 是 map 还是 set。

意思就是，第一个模板参数 K 是为了解决 map 的查找和删除等的问题。

	iterator Find(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator_cur; // 这里同样是伪代码！}cur = cur->_next;}return iterator_nullptr;// 伪代码}

iterator_cur 代表 cur 位置的迭代器； iterator_nullptr 代表 空迭代器，这两个迭代器的空白会在后面填补。

二、迭代器封装 __Hash_Iterator

__Hash_Iterator 内部应该传入什么呢？节点的指针吗？哈希桶的指针吗？

我们希望可以通过迭代器遍历整个哈希桶，同时要能取到当前迭代器所在节点的数据，因此，迭代器内部应有节点的指针和哈希桶的指针。

	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> struct __Hash_Iterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HashTable;typedef __Hash_Iterator<K, T, KeyOfT, Hash> Self;Node* _node;HashTable* _ht;__Hash_Iterator(Node* node, HashTable* ht):_node(node),_ht(ht){}};
2.1 operator++()

operator++() 需要考虑两种情形：

  1. _node->_next 不为空，++ 后，_node = _node->_next
  2. _node->_next 为空，则往后遍历 HashTable，直到找到下一个不为空的位置，或者遍历完整个 HashTable 。
	Self& operator++(){if (_node->_next){_node = _node->_next;}else {Hash hs;KeyOfT kot;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();hashi++; // 从当前位置的后一个位置开始查找while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){// 找到下一个位置，跳出循环_node = _ht->_tables[hashi]; break;}++hashi;}if (hashi == _ht->_tables.size()) // 遍历结束，没有下一个节点{_node = nullptr;}}return *this;}
2.2 operator!=() operator*() operator->()
	bool operator!=(const Self& s){return _node != s._node;}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}
2.3 完善 HashTable

针对第一部分中迭代器遗留问题，在这里将其完善。

	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> class HashTable{public:typedef HashNode<T> Node;typedef __Hash_Iterator<K, T, KeyOfT, Hash> iterator;pair<iterator, bool> Insert(const T& data){KeyOfT kot;Hash hs;iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iteratorif (ret != end())// 找到了{return make_pair(ret, false);}// 扩容 if (_n == _tables.size()){vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}// 插入size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;_n++;return make_pair(iterator(newNode, this), true); // }iterator Find(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this); }cur = cur->_next;}return iterator(nullptr, this);}bool Erase(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev == nullptr) // cur == _tables[hashi]{_tables[hashi]->_next = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables;size_t _n = 0;};
2.4 begin() end()
	iterator begin(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return iterator(_tables[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}

三、unordered_map unordered_set 封装

unordered_map

	template<class K, class V, class Hash = HashFunc<K>>class unordered_map{public:struct MapKeyOfT{K operator()(const pair<K, V>& kv){return kv.first;}};typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};

unordered_set

	template<class K, class Hash = HashFunc<K>>class unordered_set{public:struct SetKeyOfT{K operator()(const K& key){return key;}};typedef typename HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}iterator find(const K& key){return _ht.Find(key);}private:HashTable<K, const K, SetKeyOfT, Hash> _ht;};
注意：

如果直接将以上代码在 VS 中运行，会出现以下几个错误：

该问题的原因是，在 __Hash_Iterator 之前并未声明 HashTable 。

	template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值class HashTable; // 声明template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>struct __Hash_Iterator{// ...};

该问题在于，__Hash_Iterator 无法访问 HashTable 的 private 成员变量，解决办法是将 __Hash_Iterator 写成 HashTable 的友元类。

	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>class HashTable{public:template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值friend struct __Hash_Iterator; // 友元// ...};

四、完整代码

My_Unordered_Map.h
#include "HashTable.h"namespace MY_Test
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{public:struct MapKeyOfT{K operator()(const pair<K, V>& kv){return kv.first;}};typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_map1(){unordered_map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("right", "右边"));for (auto& kv : dict){//kv.first += 'x';kv.second += 'y';cout << kv.first << ":" << kv.second << endl;}}void test_map2(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };unordered_map<string, int> countMap;for (auto& e : arr){/*if (e == "ݮ"){int i = 0;}*/countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}
My_Unordered_Set.h
#include "HashTable.h"namespace MY_Test
{template<class K, class Hash = HashFunc<K>>class unordered_set{public:struct SetKeyOfT{K operator()(const K& key){return key;}};typedef typename HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}iterator find(const K& key){return _ht.Find(key);}private:HashTable<K, const K, SetKeyOfT, Hash> _ht;};void test_set1(){unordered_set<int> us;us.insert(3);us.insert(1);us.insert(5);us.insert(15);us.insert(45);us.insert(7);unordered_set<int>::iterator it = us.begin();while (it != us.end()){//*it += 100;cout << *it << " ";++it;}cout << endl;for (auto e : us){cout << e << " ";}cout << endl;}
}
HashTable.h
#include <vector>template<class K>
struct HashFunc
{size_t operator()(const K& key){size_t hash = key;return hash;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash = hash * 131 + e;}return hash;}
};template<class T>
struct HashNode
{HashNode<T>* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}
};template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
class HashTable; // 声明template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __Hash_Iterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HashTable;typedef __Hash_Iterator<K, T, KeyOfT, Hash> Self;Node* _node;HashTable* _ht;__Hash_Iterator(Node* node, HashTable* ht):_node(node), _ht(ht){}Self& operator++(){if (_node->_next){_node = _node->_next;}else{Hash hs;KeyOfT kot;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();hashi++; // 从当前位置的后一个位置开始查找while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){// 找到下一个位置，跳出循环_node = _ht->_tables[hashi];break;}++hashi;}if (hashi == _ht->_tables.size()) // 遍历结束，没有下一个节点{_node = nullptr;}}return *this;}bool operator!=(const Self& s){return _node != s._node;}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}
};template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
public:typedef HashNode<T> Node;typedef __Hash_Iterator<K, T, KeyOfT, Hash> iterator;template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值friend struct __Hash_Iterator; // 友元HashTable(){_tables.resize(10);}pair<iterator, bool> Insert(const T& data){KeyOfT kot;Hash hs;iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iteratorif (ret != end())// 找到了{return make_pair(ret, false);}// 扩容 if (_n == _tables.size()){vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}// 插入size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;_n++;return make_pair(iterator(newNode, this), true); // }iterator Find(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return iterator(nullptr, this);}bool Erase(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev == nullptr) // cur == _tables[hashi]{_tables[hashi]->_next = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}iterator begin(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return iterator(_tables[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}private:vector<Node*> _tables;size_t _n = 0;
};

这篇关于`unordered_map` 和 `unordered_set`的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/988420。

相关文章

poj 3050 dfs + set的妙用

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵，求由多少个由连续6个元素组成的不一样的字符的个数。 解析： dfs + set去重搞定。 代码： #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm
阅读更多...
Collection List Set Map的区别和联系

Collection List Set Map的区别和联系

Collection List Set Map的区别和联系 这些都代表了Java中的集合，这里主要从其元素是否有序，是否可重复来进行区别记忆，以便恰当地使用，当然还存在同步方面的差异，见上一篇相关文章。 有序否 允许元素重复否 Collection 否 是 List 是 是 Set AbstractSet 否
阅读更多...
论文翻译：ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

论文翻译：ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的，这引发了人们的担忧和猜测，即它们可能已
阅读更多...
多路转接之select(fd_set介绍,参数详细介绍),实现非阻塞式网络通信

多路转接之select(fd_set介绍,参数详细介绍),实现非阻塞式网络通信

目录 多路转接之select 引入 介绍 fd_set 函数原型 nfds readfds / writefds / exceptfds readfds  总结  fd_set操作接口  timeout timevalue 结构体 传入值 返回值 代码 注意点 -- 调用函数 select的参数填充  获取新连接 注意点 -- 通信时的调用函数 添加新fd到
阅读更多...
Android set Tag, findViewWithTag使用

Android set Tag, findViewWithTag使用

设置了tag为“principal”的view ImageView principal = (ImageView) findViewById(R.id.imagen_home_0);principal.setTag("principal"); 在其它地方获取，获取已经设置了tag为“principal”的view LayoutInflater inflater = LayoutInflate
阅读更多...
C++ STL关联容器Set与集合论入门

C++ STL关联容器Set与集合论入门

1. 简介 Set（集合）属于关联式容器，也是STL中最实用的容器，关联式容器依据特定的排序准则，自动为其元素排序。Set集合的底层使用一颗红黑树，其属于一种非线性的数据结构，每一次插入数据都会自动进行排序，注意，不是需要排序时再排序，而是每一次插入数据的时候其都会自动进行排序。因此，Set中的元素总是顺序的。 Set的性质有：数据自动进行排序且数据唯一，是一种集合元素，允许进行数学上的集合相
阅读更多...
Eclipse或MyEclipse中Java Working Set管理项目

Eclipse或MyEclipse中Java Working Set管理项目

随着学习JAVA的时间的越来越久，项目也越来越多，Eclipse或MyEclipse界面中显示一堆！ 每次工作使用到的项目肯定不会太多...... 每次从这么大数量的工程当中找到自己要使用的, 必须大规模的滚动滚动条...... 图片一   Project Explorer中：    图片二:Package Explorer中： 这样就好找很多了，分类放！
阅读更多...
Map

Map

Map 是 Java 中用于存储键值对的集合接口。以下是对 Map 的详细介绍： 特点 键值对存储：每个元素包含一个键和一个值。 键唯一：键不能重复，但值可以重复。 无序/有序：根据具体实现，键值对的顺序可能无序（如 HashMap）或有序（如 TreeMap、LinkedHashMap）。 主要实现类 HashMap 基于哈希表，无序存储。 允许一个 null 键和多个 null 值。
阅读更多...
STL set整理

STL set整理

#include<set>#include<cstdio>#include<iterator>#include<iostream>#include<algorithm>using namespace std;//set 集合的操作//multisetset<int>Set1;set<int>Set2;set<int>Set3;/*begin() 返回指向第一个元素的迭代器
阅读更多...
解决PHP Warning: strftime(): It is not safe to rely on the system's timezone set

解决PHP Warning: strftime(): It is not safe to rely on the system's timezone set

当运行一些程序时，在httpd日志中会有如下警告日志： PHP Warning:  strftime(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2