一首先学习一下STL库里的接口1.1unordered_set的相关接口1构造函数constructor1empty1默认构造函数空构造默认桶的数量为8后面显示传递size_type n桶的数量大于等于n。后面还有一个默认模版参数要注意const hasher hf hasher()这里可以传递自己实现的哈希函数如果容器里要存放自己实现的日期类可以实现一个将其转换为数字的仿函数。//empty(1)默认构造函数 unordered_setstring us1; //空构造默认桶的数量为8 unordered_setstring us11(11); //默认桶的数量大于112range2迭代区间构造可以传递一段其他容器的一段区间构造。//range(2)迭代区间构造 liststring l2{ ab,abc,abcd,a,axx,dse,uio,op}; unordered_setstring us2(l2.begin(), l2.end()); cout us2.bucket_count() endl; //8个桶 for (auto e2 : us2) cout e2 ;//op ab abc abcd uio axx a dse cout endl;3copy3拷贝构造//copy3拷贝构造 unordered_setstring us3{ aa,bb,cc,dd }; unordered_setstring us31(us3); //unordered_setstring us31 us3;//这也是拷贝构造 for (auto e3 : us31) cout e3 ;//aa bb dd cc cout endl;5initializer list (5)初始化器列表可以使用一个花括号构造初始化。//initializer list (5) 初始化器列表 unordered_setint us4{ 1,2,3,4,5,6,7,8,9,10 }; unordered_setint us41 { 1,2,3,4,5,6,7,8,9,10 };2迭代器和capacity接口unordered_setint us1{ 2,4,6,8,10,12,14,16 ,47,2,14,25 }; unordered_setint::iterator it1 us1.begin(); while (it1 ! us1.end()) { cout *it1 ; it1; } cout endl; //支持范围迭代器也就支持范围for for (auto e1 : us1) { cout e1 ; } cout endl; cout size us1.size() endl;//size103Element lookup(元素查找接口)1find根据关键字key查找找到了返回该元素的迭代器找不到返回end()。unordered_setint us1{ 2,4,6,8,10,12,14,16 ,47,2,14,25 }; unordered_setint::iterator f1 us1.find(47); if (f1 ! us1.end()) cout *f1 endl;//47 else cout 找不到 endl;2count根据关键字key查找找到了返回1找不到返回0。unordered_setint us2{ 2,4,6,8,10,12,14,16 ,47,2,14,25 }; size_t ret us2.count(99);//0 cout ret ret endl;3equal_range根据关键字key查找找到了返回这个元素的左右边界左边界等于key右边界大于key如果找不到或者容器中只有一个元素抛异常。unordered_setint us3{ 2,3,4,5,6 }; //pairunordered_setint::iterator, unordered_setint::iterator auto eq3 us3.equal_range(4); cout *(eq3.first) : *(eq3.second) endl;//4:5 [4 ,5)4Modifiers 修改接口1insert插入一个关键字key返回一个pair键值由于不能插入相同的key插入相同元素则插入失败返回key的迭代器false插入成功返回key的迭代器true 。//插入一个key unordered_setstring us1{ abc,www,kji }; pairunordered_setstring::iterator, bool pret1 us1.insert(arb); cout *(pret1.first) : pret1.second endl;//arb:1 pairunordered_setstring::iterator, bool pret2 us1.insert(arb); cout *(pret2.first) : pret2.second endl;//arb:0在一个迭代器位置插入一个关键字key。只会按照hash映射插入。//迭代器位置插入一个关键字key unordered_setstring us2{ abc,www,kji }; for (auto e1 : us2) cout e1 ;//kji abc www cout endl; unordered_setstring::iterator f2 us2.find(abc); us2.insert(f2, FFF); for (auto e1 : us2) cout e1 ;//kji abc www FFF cout endl;插入一段迭代区间和插入一个初始化器。//插入一段迭代区间和插入一个初始化器。 liststring l3{ ab,abc,aaa,cf,sdk }; unordered_setstring us3(l3.begin(), l3.end()); for (auto e3 : us3) cout e3 ;//aaa ab sdk abc cf cout endl;2erase版本 1 和 3 返回一个迭代器该迭代器指向被删除的元素的下一个位置。版本 2 返回了被删除的元素数量。unordered_setint us4{ 2,4,6,8,45,54,6,7,21,34,56,33 }; auto f4 us4.find(56); auto e4 us4.erase(f4); cout *e4 endl;//335Buckets 桶接口unordered_setint us4{ 2,4,6,8,10,12,14 }; cout us4.bucket_count() endl;//返回桶的个数 cout us4.bucket_size(7) endl;//返回桶内包含的元素个数 cout us4.bucket(2) endl; //返回key对应在哪个桶unordered_map和unordered_set的接口大部分都是一样的。unordered_map多了两个接口分别是 [ ] 的运算符重载和 at() 。#includeiostream #includeunordered_map #includestring using namespace std; int main() { unordered_mapstring, string um1{ {insert,插入},{sort,排序} }; pairunordered_mapstring, string::iterator, bool pret um1.insert({ erase,删除 }); cout pret.first-first : pret.first-second endl;//erase:删除 for (auto [x, y] : um1)//c17结构化绑定 cout x : y ; //insert:插入 sort : 排序 erase : 删除 cout endl; // [] //如果找不到就插入key并返回second的引用找到了直接返回second的引用 um1[fork];//插入second为空 string ret1 um1[getpid] 标示符;//插入 um1[fork] 创建;//修改 ret1 biaoshifu; // at //如果找不到会抛异常找到了返回second的引用 string ret2 um1.at(fork); ret2 xxx; for (auto [x, y] : um1)//c17结构化绑定 cout x : y ; //getpid:标示符biaoshifu insert : 插入 fork : 创建xxx sort : 排序 erase : 删除 }二现在咱们自己实现一个Mini版myunordered_set和myunordered_map1Hash_tables.h myunordered_set和myunordered_map共同的底层容器。#pragma once #includeiostream #includevector #includestring #includectime #includecstdlib #includealgorithm using std::cout; using std::endl; using std::pair; // Note: assumes long is at least 32 bits. static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos std::lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass T struct Hashtype { const size_t operator()(const T key) { return (const size_t)key; } }; template struct Hashtypestd::string { const size_t operator()(const std::string key) { size_t hash 0; for (auto h : key) { hash * 31; hash h; } return (const size_t)hash; } }; templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) :_data(data) ,_next(nullptr) { } }; templateclass key, class T, class Hash, class KeyOfValue class Hash_table; templateclass key, class T, class Ref, class Ptr, class Hash, class KeyOfValue struct Hash_table_Iterator { typedef HashNodeT node; typedef Hash_tablekey, T, Hash, KeyOfValue hashtable; typedef Hash_table_Iteratorkey, T, Ref, Ptr, Hash, KeyOfValue Self; const node* _node; const hashtable* _ht; Hash_table_Iterator(const node* n, const hashtable* h) :_node(n) ,_ht(h) { } const Ref operator*()const { return (const Ref)_node-_data; } const Ptr operator-() { return (const Ptr)(_node-_data); } bool operator!(const Self it)const { return _node ! it._node; } bool operator(const Self it)const { return _node it._node; } Self operator() { node* next _node-_next; if (next) { _node _node-_next; } else { KeyOfValue Kov; //取出数据 Hash hash; //转为整型 //计算出当前节点的hashi size_t hashi hash(Kov(_node-_data)) % _ht-_tables.size(); //找出下一个不为空的节点 size_t i hashi 1; for (; i _ht-_tables.size(); i) { if (_ht-_tables[i]) { _node _ht-_tables[i]; break; } } if (i _ht-_tables.size()) _node nullptr; } return *this; } Self operator(int) { Self tmp(*this); (*this); return tmp; } }; //Hash用来将一个字符转成整型 //KeyOfValue用来取出关键字key templateclass key, class T, class Hash, class KeyOfValue class Hash_table { templateclass key, class T, class Ref, class Ptr, class Hash, class KeyOfValue friend struct Hash_table_Iterator; public: typedef HashNodeT Node; typedef Hash_table_Iteratorkey, T, T, T*, Hash, KeyOfValue Iterator; typedef Hash_table_Iteratorkey, T, const T, const T*, Hash, KeyOfValue ConstIterator; Iterator Begin() { for (size_t i 0; i _tables.size(); i) if (_tables[i]) return Iterator(_tables[i], this); return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin()const { for (size_t i 0; i _tables.size(); i) if (_tables[i]) return ConstIterator(_tables[i], this); return End(); } ConstIterator End()const { return ConstIterator(nullptr, this); } Hash_table() :_tables(11)//_tables(__stl_next_prime(0)) ,_size(0) { } Hash_table(const Hash_table table) :Hash_table() { for (size_t i 0; i table._tables.size(); i) { Node* cur table._tables[i]; while (cur) { this-Insert(cur-_data); cur cur-_next; } } } Hash_table operator(const Hash_table table) { if (this ! table) { Hash_table tmp(table); _tables.swap(tmp._tables); _size tmp._size; } return *this; } pairIterator,bool Insert(const T data) { KeyOfValue Kov; //取出数据 Hash hash; //转为整型 Iterator ret Find(Kov(data)); if (ret ! End()) { return { ret,false }; } //判断是否扩容 if (_size _tables.size()) { std::vectorNode* tmp(__stl_next_prime((unsigned long)_tables.size() 1)); for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; size_t hashi hash(Kov(cur-_data)) % tmp.size(); cur-_next tmp[hashi]; tmp[hashi] cur; cur next; } _tables[i] nullptr; } _tables.swap(tmp); } size_t hashi hash(Kov(data)) % _tables.size(); Node* newNode new Node(data); newNode-_next _tables[hashi]; _tables[hashi] newNode; _size; return { Iterator(newNode,this),true }; } Iterator Find(const key k) { if (_size 0) { return End(); } KeyOfValue Kov; //取出数据 Hash hash; //转为整型 size_t hashi hash(k) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (Kov(cur-_data) k) return Iterator(cur, this); cur cur-_next; } return End(); } bool Erase(const key k) { if (_size 0) { return false; } KeyOfValue Kov; //取出数据 Hash hash; //转为整型 size_t hashi hash(k) % _tables.size(); Node* cur _tables[hashi]; Node* prev nullptr; while (cur) { if (Kov(cur-_data) k) { if (prev nullptr) { _tables[hashi] cur-_next; } else { prev-_next cur-_next; } delete cur; --_size; return true; } prev cur; cur cur-_next; } return false; } ~Hash_table() { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; delete cur; cur next; } _tables[i] nullptr; } } private: std::vectorNode* _tables; size_t _size; };2unordered_set#pragma once #includeHash_tables.h namespace zsw { templateclass key, class Hash Hashtypekey class unordered_set { struct identity { const key operator()(const key k) { return k; } }; typedef typename Hash_tablekey, const key, Hash, identity::Node node; public: typedef typename Hash_tablekey, const key, Hash, identity::Iterator iterator; typedef typename Hash_tablekey, const key, Hash, identity::ConstIterator const_iterator; iterator begin() { return _Htable.Begin(); } iterator end() { return _Htable.End(); } const_iterator begin()const { return _Htable.Begin(); } const_iterator end()const { return _Htable.End(); } unordered_set() default; pairiterator,bool insert(const key k) { return _Htable.Insert(k); } iterator find(const key k) { return _Htable.Find(k); } bool erase(const key k) { return _Htable.Erase(k); } private: Hash_tablekey, const key, Hash, identity _Htable; }; }3unordered_map#pragma once #includeHash_tables.h namespace zsw { templateclass key, class value, class Hash Hashtypekey class unordered_map { struct select1st { const key operator()(const pairconst key, value kv) { return kv.first; } }; typedef typename Hash_tablekey, pairconst key, value,Hash, select1st::Node node; public: typedef typename Hash_tablekey, pairconst key, value,Hash, select1st::Iterator iterator; typedef typename Hash_tablekey, pairconst key, value, Hash, select1st::ConstIterator const_iterator; iterator begin() { return _Htable.Begin(); } iterator end() { return _Htable.End(); } const_iterator begin()const { return _Htable.Begin(); } const_iterator end()const { return _Htable.End(); } unordered_map() default; pairiterator,bool insert(const pairkey, value kv) { return _Htable.Insert(kv); } iterator find(const key k) { return _Htable.Find(k); } bool erase(const key k) { return _Htable.Erase(k); } value operator[](const key k) { pairiterator, bool ret _Htable.Insert({ k,value() }); return ret.first-second; } private: Hash_tablekey, pairconst key, value, Hash, select1st _Htable; }; }以上就是unordered_set和unordered_map的简易实现。 
长河君 · 2026/8/29 4:20:21 · 阅读 1.2k 实现mini版myunordered_set和myunordered_map
一首先学习一下STL库里的接口1.1unordered_set的相关接口1构造函数constructor1empty1默认构造函数空构造默认桶的数量为8后面显示传递size_type n桶的数量大于等于n。后面还有一个默认模版参数要注意const hasher hf hasher()这里可以传递自己实现的哈希函数如果容器里要存放自己实现的日期类可以实现一个将其转换为数字的仿函数。//empty(1)默认构造函数 unordered_setstring us1; //空构造默认桶的数量为8 unordered_setstring us11(11); //默认桶的数量大于112range2迭代区间构造可以传递一段其他容器的一段区间构造。//range(2)迭代区间构造 liststring l2{ ab,abc,abcd,a,axx,dse,uio,op}; unordered_setstring us2(l2.begin(), l2.end()); cout us2.bucket_count() endl; //8个桶 for (auto e2 : us2) cout e2 ;//op ab abc abcd uio axx a dse cout endl;3copy3拷贝构造//copy3拷贝构造 unordered_setstring us3{ aa,bb,cc,dd }; unordered_setstring us31(us3); //unordered_setstring us31 us3;//这也是拷贝构造 for (auto e3 : us31) cout e3 ;//aa bb dd cc cout endl;5initializer list (5)初始化器列表可以使用一个花括号构造初始化。//initializer list (5) 初始化器列表 unordered_setint us4{ 1,2,3,4,5,6,7,8,9,10 }; unordered_setint us41 { 1,2,3,4,5,6,7,8,9,10 };2迭代器和capacity接口unordered_setint us1{ 2,4,6,8,10,12,14,16 ,47,2,14,25 }; unordered_setint::iterator it1 us1.begin(); while (it1 ! us1.end()) { cout *it1 ; it1; } cout endl; //支持范围迭代器也就支持范围for for (auto e1 : us1) { cout e1 ; } cout endl; cout size us1.size() endl;//size103Element lookup(元素查找接口)1find根据关键字key查找找到了返回该元素的迭代器找不到返回end()。unordered_setint us1{ 2,4,6,8,10,12,14,16 ,47,2,14,25 }; unordered_setint::iterator f1 us1.find(47); if (f1 ! us1.end()) cout *f1 endl;//47 else cout 找不到 endl;2count根据关键字key查找找到了返回1找不到返回0。unordered_setint us2{ 2,4,6,8,10,12,14,16 ,47,2,14,25 }; size_t ret us2.count(99);//0 cout ret ret endl;3equal_range根据关键字key查找找到了返回这个元素的左右边界左边界等于key右边界大于key如果找不到或者容器中只有一个元素抛异常。unordered_setint us3{ 2,3,4,5,6 }; //pairunordered_setint::iterator, unordered_setint::iterator auto eq3 us3.equal_range(4); cout *(eq3.first) : *(eq3.second) endl;//4:5 [4 ,5)4Modifiers 修改接口1insert插入一个关键字key返回一个pair键值由于不能插入相同的key插入相同元素则插入失败返回key的迭代器false插入成功返回key的迭代器true 。//插入一个key unordered_setstring us1{ abc,www,kji }; pairunordered_setstring::iterator, bool pret1 us1.insert(arb); cout *(pret1.first) : pret1.second endl;//arb:1 pairunordered_setstring::iterator, bool pret2 us1.insert(arb); cout *(pret2.first) : pret2.second endl;//arb:0在一个迭代器位置插入一个关键字key。只会按照hash映射插入。//迭代器位置插入一个关键字key unordered_setstring us2{ abc,www,kji }; for (auto e1 : us2) cout e1 ;//kji abc www cout endl; unordered_setstring::iterator f2 us2.find(abc); us2.insert(f2, FFF); for (auto e1 : us2) cout e1 ;//kji abc www FFF cout endl;插入一段迭代区间和插入一个初始化器。//插入一段迭代区间和插入一个初始化器。 liststring l3{ ab,abc,aaa,cf,sdk }; unordered_setstring us3(l3.begin(), l3.end()); for (auto e3 : us3) cout e3 ;//aaa ab sdk abc cf cout endl;2erase版本 1 和 3 返回一个迭代器该迭代器指向被删除的元素的下一个位置。版本 2 返回了被删除的元素数量。unordered_setint us4{ 2,4,6,8,45,54,6,7,21,34,56,33 }; auto f4 us4.find(56); auto e4 us4.erase(f4); cout *e4 endl;//335Buckets 桶接口unordered_setint us4{ 2,4,6,8,10,12,14 }; cout us4.bucket_count() endl;//返回桶的个数 cout us4.bucket_size(7) endl;//返回桶内包含的元素个数 cout us4.bucket(2) endl; //返回key对应在哪个桶unordered_map和unordered_set的接口大部分都是一样的。unordered_map多了两个接口分别是 [ ] 的运算符重载和 at() 。#includeiostream #includeunordered_map #includestring using namespace std; int main() { unordered_mapstring, string um1{ {insert,插入},{sort,排序} }; pairunordered_mapstring, string::iterator, bool pret um1.insert({ erase,删除 }); cout pret.first-first : pret.first-second endl;//erase:删除 for (auto [x, y] : um1)//c17结构化绑定 cout x : y ; //insert:插入 sort : 排序 erase : 删除 cout endl; // [] //如果找不到就插入key并返回second的引用找到了直接返回second的引用 um1[fork];//插入second为空 string ret1 um1[getpid] 标示符;//插入 um1[fork] 创建;//修改 ret1 biaoshifu; // at //如果找不到会抛异常找到了返回second的引用 string ret2 um1.at(fork); ret2 xxx; for (auto [x, y] : um1)//c17结构化绑定 cout x : y ; //getpid:标示符biaoshifu insert : 插入 fork : 创建xxx sort : 排序 erase : 删除 }二现在咱们自己实现一个Mini版myunordered_set和myunordered_map1Hash_tables.h myunordered_set和myunordered_map共同的底层容器。#pragma once #includeiostream #includevector #includestring #includectime #includecstdlib #includealgorithm using std::cout; using std::endl; using std::pair; // Note: assumes long is at least 32 bits. static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos std::lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass T struct Hashtype { const size_t operator()(const T key) { return (const size_t)key; } }; template struct Hashtypestd::string { const size_t operator()(const std::string key) { size_t hash 0; for (auto h : key) { hash * 31; hash h; } return (const size_t)hash; } }; templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) :_data(data) ,_next(nullptr) { } }; templateclass key, class T, class Hash, class KeyOfValue class Hash_table; templateclass key, class T, class Ref, class Ptr, class Hash, class KeyOfValue struct Hash_table_Iterator { typedef HashNodeT node; typedef Hash_tablekey, T, Hash, KeyOfValue hashtable; typedef Hash_table_Iteratorkey, T, Ref, Ptr, Hash, KeyOfValue Self; const node* _node; const hashtable* _ht; Hash_table_Iterator(const node* n, const hashtable* h) :_node(n) ,_ht(h) { } const Ref operator*()const { return (const Ref)_node-_data; } const Ptr operator-() { return (const Ptr)(_node-_data); } bool operator!(const Self it)const { return _node ! it._node; } bool operator(const Self it)const { return _node it._node; } Self operator() { node* next _node-_next; if (next) { _node _node-_next; } else { KeyOfValue Kov; //取出数据 Hash hash; //转为整型 //计算出当前节点的hashi size_t hashi hash(Kov(_node-_data)) % _ht-_tables.size(); //找出下一个不为空的节点 size_t i hashi 1; for (; i _ht-_tables.size(); i) { if (_ht-_tables[i]) { _node _ht-_tables[i]; break; } } if (i _ht-_tables.size()) _node nullptr; } return *this; } Self operator(int) { Self tmp(*this); (*this); return tmp; } }; //Hash用来将一个字符转成整型 //KeyOfValue用来取出关键字key templateclass key, class T, class Hash, class KeyOfValue class Hash_table { templateclass key, class T, class Ref, class Ptr, class Hash, class KeyOfValue friend struct Hash_table_Iterator; public: typedef HashNodeT Node; typedef Hash_table_Iteratorkey, T, T, T*, Hash, KeyOfValue Iterator; typedef Hash_table_Iteratorkey, T, const T, const T*, Hash, KeyOfValue ConstIterator; Iterator Begin() { for (size_t i 0; i _tables.size(); i) if (_tables[i]) return Iterator(_tables[i], this); return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin()const { for (size_t i 0; i _tables.size(); i) if (_tables[i]) return ConstIterator(_tables[i], this); return End(); } ConstIterator End()const { return ConstIterator(nullptr, this); } Hash_table() :_tables(11)//_tables(__stl_next_prime(0)) ,_size(0) { } Hash_table(const Hash_table table) :Hash_table() { for (size_t i 0; i table._tables.size(); i) { Node* cur table._tables[i]; while (cur) { this-Insert(cur-_data); cur cur-_next; } } } Hash_table operator(const Hash_table table) { if (this ! table) { Hash_table tmp(table); _tables.swap(tmp._tables); _size tmp._size; } return *this; } pairIterator,bool Insert(const T data) { KeyOfValue Kov; //取出数据 Hash hash; //转为整型 Iterator ret Find(Kov(data)); if (ret ! End()) { return { ret,false }; } //判断是否扩容 if (_size _tables.size()) { std::vectorNode* tmp(__stl_next_prime((unsigned long)_tables.size() 1)); for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; size_t hashi hash(Kov(cur-_data)) % tmp.size(); cur-_next tmp[hashi]; tmp[hashi] cur; cur next; } _tables[i] nullptr; } _tables.swap(tmp); } size_t hashi hash(Kov(data)) % _tables.size(); Node* newNode new Node(data); newNode-_next _tables[hashi]; _tables[hashi] newNode; _size; return { Iterator(newNode,this),true }; } Iterator Find(const key k) { if (_size 0) { return End(); } KeyOfValue Kov; //取出数据 Hash hash; //转为整型 size_t hashi hash(k) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (Kov(cur-_data) k) return Iterator(cur, this); cur cur-_next; } return End(); } bool Erase(const key k) { if (_size 0) { return false; } KeyOfValue Kov; //取出数据 Hash hash; //转为整型 size_t hashi hash(k) % _tables.size(); Node* cur _tables[hashi]; Node* prev nullptr; while (cur) { if (Kov(cur-_data) k) { if (prev nullptr) { _tables[hashi] cur-_next; } else { prev-_next cur-_next; } delete cur; --_size; return true; } prev cur; cur cur-_next; } return false; } ~Hash_table() { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; delete cur; cur next; } _tables[i] nullptr; } } private: std::vectorNode* _tables; size_t _size; };2unordered_set#pragma once #includeHash_tables.h namespace zsw { templateclass key, class Hash Hashtypekey class unordered_set { struct identity { const key operator()(const key k) { return k; } }; typedef typename Hash_tablekey, const key, Hash, identity::Node node; public: typedef typename Hash_tablekey, const key, Hash, identity::Iterator iterator; typedef typename Hash_tablekey, const key, Hash, identity::ConstIterator const_iterator; iterator begin() { return _Htable.Begin(); } iterator end() { return _Htable.End(); } const_iterator begin()const { return _Htable.Begin(); } const_iterator end()const { return _Htable.End(); } unordered_set() default; pairiterator,bool insert(const key k) { return _Htable.Insert(k); } iterator find(const key k) { return _Htable.Find(k); } bool erase(const key k) { return _Htable.Erase(k); } private: Hash_tablekey, const key, Hash, identity _Htable; }; }3unordered_map#pragma once #includeHash_tables.h namespace zsw { templateclass key, class value, class Hash Hashtypekey class unordered_map { struct select1st { const key operator()(const pairconst key, value kv) { return kv.first; } }; typedef typename Hash_tablekey, pairconst key, value,Hash, select1st::Node node; public: typedef typename Hash_tablekey, pairconst key, value,Hash, select1st::Iterator iterator; typedef typename Hash_tablekey, pairconst key, value, Hash, select1st::ConstIterator const_iterator; iterator begin() { return _Htable.Begin(); } iterator end() { return _Htable.End(); } const_iterator begin()const { return _Htable.Begin(); } const_iterator end()const { return _Htable.End(); } unordered_map() default; pairiterator,bool insert(const pairkey, value kv) { return _Htable.Insert(kv); } iterator find(const key k) { return _Htable.Find(k); } bool erase(const key k) { return _Htable.Erase(k); } value operator[](const key k) { pairiterator, bool ret _Htable.Insert({ k,value() }); return ret.first-second; } private: Hash_tablekey, pairconst key, value, Hash, select1st _Htable; }; }以上就是unordered_set和unordered_map的简易实现。