`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。

相关文章

c++中的set容器介绍及操作大全

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》：本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方
阅读更多...
shell中set -u、set -x、set -e的使用

shell中set -u、set -x、set -e的使用

《shell中set-u、set-x、set-e的使用》本文主要介绍了shell中set-u、set-x、set-e的使用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录✅ 1. set -u：防止使用未定义变量 作用： 示例：❌ 报错示例输出：✅ 推荐使用场景：✅ 2. se
阅读更多...
Java中Map.Entry()含义及方法使用代码

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》：本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma
阅读更多...
Java中JSON格式反序列化为Map且保证存取顺序一致的问题

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》：本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时，需要提供方将Map类型的数据序列化为co
阅读更多...
Java使用Stream流的Lambda语法进行List转Map的操作方式

Java使用Stream流的Lambda语法进行List转Map的操作方式

《Java使用Stream流的Lambda语法进行List转Map的操作方式》：本文主要介绍Java使用Stream流的Lambda语法进行List转Map的操作方式,具有很好的参考价值,希望对大... 目录背景Stream流的Lambda语法应用实例1、定义要操作的UserDto2、ListChina编程转成M
阅读更多...
MySQL中FIND_IN_SET函数与INSTR函数用法解析

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》：本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分
阅读更多...
SpringBoot如何通过Map实现策略模式

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M
阅读更多...
Nginx指令add_header和proxy_set_header的区别及说明

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》：本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理？proxy
阅读更多...
C++ 各种map特点对比分析

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map（如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现：基于红黑
阅读更多...
JavaScript中的Map用法完全指南

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》：本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2