大型營(yíng)銷型網(wǎng)站建設(shè),網(wǎng)站優(yōu)化 保定,論壇上怎么做網(wǎng)站優(yōu)化,建設(shè)廳投訴網(wǎng)站1. 源碼及框架分析SGI-STL30版本源代碼中沒有unordered_map和unordered_set#xff0c;SGI-STL30版本是C11之前的STL版本#xff0c;這兩個(gè)容器是C11之后才更新的。但是SGI-STL30實(shí)現(xiàn)了哈希表#xff0c;只容器的名字是hash_map和hash_set#xff0c;他是作為?標(biāo)準(zhǔn)的容器出…1. 源碼及框架分析SGI-STL30版本源代碼中沒有unordered_map和unordered_setSGI-STL30版本是C11之前的STL版本這兩個(gè)容器是C11之后才更新的。但是SGI-STL30實(shí)現(xiàn)了哈希表只容器的名字是hash_map和hash_set他是作為?標(biāo)準(zhǔn)的容器出現(xiàn)的非標(biāo)準(zhǔn)是指非C標(biāo)準(zhǔn)規(guī)定必須實(shí)現(xiàn)的源代碼在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中hash_map和hash_set的實(shí)現(xiàn)結(jié)構(gòu)框架核?部分截取出來(lái)如下stl_hash_settemplate class Value, class HashFcn hashValue, class EqualKey equal_toValue, class Alloc alloc class hash_set { private: typedef hashtableValue, Value, HashFcn, identityValue, EqualKey, Alloc ht; ht rep; public: typedef typename ht::key_type key_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::const_iterator iterator; typedef typename ht::const_iterator const_iterator; hasher hash_funct() const { return rep.hash_funct(); } key_equal key_eq() const { return rep.key_eq(); } };stl_hash_maptemplate class Key, class T, class HashFcn hashKey, class EqualKey equal_toKey, class Alloc alloc class hash_map { private: typedef hashtablepairconst Key, T, Key, HashFcn, select1stpairconst Key, T , EqualKey, Alloc ht; ht rep; public: typedef typename ht::key_type key_type; typedef T data_type; typedef T mapped_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::iterator iterator; typedef typename ht::const_iterator const_iterator; }; // stl_hashtable.h template class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc class hashtable { public: typedef Key key_type; typedef Value value_type; typedef HashFcn hasher; typedef EqualKey key_equal; private: hasher hash; key_equal equals; ExtractKey get_key; typedef __hashtable_nodeValue node; vectornode*, Alloc buckets; size_type num_elements; public: typedef __hashtable_iteratorValue, Key, HashFcn, ExtractKey, EqualKey, Alloc iterator; pairiterator, bool insert_unique(const value_type obj); const_iterator find(const key_type key) const; }; template class Value struct __hashtable_node { __hashtable_node* next; Value val; };這?我們就不再畫圖分析了通過源碼可以看到結(jié)構(gòu)上hash_map和hash_set跟map和set的完全類似復(fù)?同?個(gè)hashtable實(shí)現(xiàn)key和key/value結(jié)構(gòu)hash_set傳給hash_table的是兩個(gè)keyhash_map傳給hash_table的是pairconst key, value需要注意的是源碼??跟map/set源碼類似命名?格?較亂這?比map和set還亂hash_set模板參數(shù)居然?的Value命名hash_map?的是Key和T命名可??佬有時(shí)寫代碼也不規(guī)范亂彈琴。下?我們模擬?份自己的出來(lái)就按自己的風(fēng)格走了。2. 模擬實(shí)現(xiàn)unordered_map和unordered_set2.1 實(shí)現(xiàn)出復(fù)用哈希表的框架并支持insert參考源碼框架unordered_map和unordered_set復(fù)?之前我們實(shí)現(xiàn)的哈希表。我們這里相比源碼調(diào)整?下key參數(shù)就用Kvalue參數(shù)就?V哈希表中的數(shù)據(jù)類型我們使用T。其次跟map和set相比而言u(píng)nordered_map和unordered_set的模擬實(shí)現(xiàn)類結(jié)構(gòu)更復(fù)雜?點(diǎn)但是大框架和思路是完全類似的。因?yàn)镠ashTable實(shí)現(xiàn)了泛型不知道T參數(shù)導(dǎo)致是K還是pairK, V那么insert內(nèi)部進(jìn)?插?時(shí)要?K對(duì)象轉(zhuǎn)換成整形取模和K?較相等因?yàn)閜air的value不參與計(jì)算取模且默認(rèn)支持的是key和value?起比較相等我們需要時(shí)的任何時(shí)候只需要?較K對(duì)象所以我們?cè)趗nordered_map和unordered_set層分別實(shí)現(xiàn)?個(gè)MapKeyOfT和SetKeyOfT的仿函數(shù)傳給HashTable的KeyOfT然后HashTable中通過KeyOfT仿函數(shù)取出T類型對(duì)象中的K對(duì)象再轉(zhuǎn)換成整形取模和K比較相等具體細(xì)節(jié)參考如下代碼實(shí)現(xiàn)。實(shí)現(xiàn)步驟實(shí)現(xiàn)哈希表封裝unordered_map和unordered_set的框架 解決KeyOfTiteratorconst_iteratorkey不支持修改的問題perator[]UnorderedSet.h:#pragma once #includeHashTable.h namespace xiaohan { templateclass K, class Hash HashFuncK class unordered_map { // 仿函數(shù)set(K)和map(pair)比較大小時(shí)不一樣 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: bool insert(const K key) { return _ht.Insert(key); } private: hash_bucket::HashTableK, K, SetKeyOfT, Hash _ht; }; }UnorderedMap.h:#pragma once #includeHashTable.h namespace xiaohan { templateclass K, class Hash HashFuncK class unordered_map { // 仿函數(shù)set(K)和map(pair)比較大小時(shí)不一樣 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: bool insert(const K key) { return _ht.Insert(key); } private: hash_bucket::HashTableK, K, SetKeyOfT, Hash _ht; }; }HashTable.h:與上一章介紹的HashTable.h區(qū)別用T替代了KV解決了KeyOfT問題#pragma once #pragma once #includevector #includestring using namespace std; 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; // n const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; //特化 template struct HashFuncstring { /* 字符串轉(zhuǎn)換成整形可以把字符ascii碼相加即可 但是直接相加的話類似abcd和bcad這樣的字符串計(jì)算出是相同的 這?我們使?BKDR哈希的思路用上次的計(jì)算結(jié)果去乘以?個(gè)質(zhì)數(shù)這個(gè)質(zhì)數(shù)?般取31131 等效果會(huì)比較好*/ size_t operator()(const string key) { // abcd size_t hash 0; for (auto e : key) { hash hash e; hash hash * 131; } return hash; } }; namespace hash_bucket { templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) :_data(data) , _next(nullptr) {} }; // hash_bucket::HashTableK, pairK, V, MapKeyOfT _ht; // hash_bucket::HashTableK, K, SetKeyOfT _ht; templateclass K, class T, class KeyOfT, class Hash class HashTable { typedef HashNodeT Node; public: HashTable() :_tables(__stl_next_prime(1), nullptr) , _n(0) {} ~HashTable() { 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; } _n 0; } bool Insert(const T data) { KeyOfT kot; if (Find(kot(data))) return false; Hash hs; // 負(fù)載因子 1就開始擴(kuò)容 if (_n _tables.size()) { // 方法二, 只創(chuàng)建vector表直接將舊表的結(jié)點(diǎn)鏈接到新表中 vectorNode* newtables(__stl_next_prime(_tables.size() 1), nullptr); for (size_t i 0; i _tables.size(); i) { //遍歷舊表舊表結(jié)點(diǎn)重新映射挪動(dòng)到新表 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(); // 頭插法 Node* newnode new Node(kv); newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; return true; } Node* Find(const K key) { KeyofT kot; Hash hs; size_t hashi hs(key) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (kot(cur-_data) key) { return cur; } cur cur-_next; } return nullptr; } bool Erase(const K key) { KeyOfT kot; Hash hs; size_t hashi hs(key) % _tables.size(); Node* pre nullptr; Node* cur _tables[hashi]; while (cur) { // 刪除 if (kot(cur-_data) key) { // 桶中第一個(gè)結(jié)點(diǎn) if (pre nullptr) { _tables[hashi] cur-_next; } else { pre-_next cur-_next; } --_n; delete cur; return true; } pre cur; cur cur-_next; } return false; } private: vectorNode* _tables; // 指針數(shù)組 size_t _n; }; }2.2 支持iterator的實(shí)現(xiàn)iterator實(shí)現(xiàn)思路分析begin()返回第一個(gè)桶中第一個(gè)節(jié)點(diǎn)指針構(gòu)造的迭代器這里end()返回迭代器可以用空表示。由于HTIterator的類定義在HashTable之前而且兩者類內(nèi)都有對(duì)方所以HTIterator前面要添加前置聲明// 前置聲明 templateclass K, class T, class KeyOfT, class Hash class HashTable; templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash struct HTIterator { typedef HashNodeT Node; typedef HashTableK, T, KeyOfT, Hash HT; typedef HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self; Node* _node; const HT* _pht; // 哈希表的指針 HTIterator(Node* node, const HT* pht) :_node(node) , _pht(pht) {} Ref operator*() { return _node-_data; } Ptr operator-() { return _node-_data; } Self operator() { KeyOfT kot; Hash hs; if (_node-_next) // 當(dāng)前桶沒走完 { _node _node-_next; } else // 當(dāng)前桶走完了找到下一個(gè)桶的第一個(gè)節(jié)點(diǎn) { // 算出當(dāng)前桶的位置 size_t hashi hs(kot(_node-_data)) % _pht-_tables.size(); hashi; while(hashi _pht-_tables.size()) { if (_pht-_tables[hashi]) // 找到下一個(gè)不為空的桶 { _node _pht-_tables[hashi]; break; } else { hashi; } } if (hashi _pht-_tables.size()) // 最后一個(gè)桶走完了,要到end()位置 { // end()中_node是空 return nullptr; } } return *this; } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } };注意HashTable中的HTIterator也要有友元聲明class HashTable { // 友元聲明 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash friend struct HIIterator; typedef HashNodeT Node; public: typedef HTIteratorK, T, T, T*, KeyOfT, Hash Iterator; typedef HTIteratorK, T, const T, const T*, KeyOfT, Hash ConstIterator; Iterator Begin() { if (_n 0) { return End(); } 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 { if (_n 0) { return End(); } 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); } HashTable() :_tables(__stl_next_prime(1), nullptr) , _n(0) {} ...unordered_set的迭代器也不支持修改把unordered_set的第二個(gè)模板參數(shù)改成const K即可unordered_map的iterator不支持修改key但是可以修改value我們把unordered_map的第二個(gè)模板參數(shù)pair的第一個(gè)參數(shù)改成const K即可2.3 map支持[]2.4 unordered_map和unordered_set代碼實(shí)現(xiàn)UnorderedSet.h:#pragma once #includeHashTable.h namespace xiaohan { templateclass K, class Hash HashFuncK class unordered_set { // 仿函數(shù)set(K)和map(pair)比較大小時(shí)不一樣 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::Iterator iterator; typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::ConstIterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } pairiterator, bool insert(const K key) { return _ht.Insert(key); } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } private: hash_bucket::HashTableK, const K, SetKeyOfT, Hash _ht; }; }UnorderedMap.h:#pragma once #includeHashTable.h namespace xiaohan { templateclass K, class V, class Hash HashFuncK class unordered_map { struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; } }; public: typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::Iterator iterator; typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::ConstIterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } pairiterator, bool insert(const pairK, V kv) { return _ht.Insert(kv); } V operator[](const K key) { pairiterator, bool ret insert({ key, V() }); return ret.first-second; } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } private: hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht; }; }HashTable.h:#pragma once #pragma once #includevector #includestring using namespace std; 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; // n const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; //特化 template struct HashFuncstring { /* 字符串轉(zhuǎn)換成整形可以把字符ascii碼相加即可 但是直接相加的話類似abcd和bcad這樣的字符串計(jì)算出是相同的 這?我們使?BKDR哈希的思路用上次的計(jì)算結(jié)果去乘以?個(gè)質(zhì)數(shù)這個(gè)質(zhì)數(shù)?般取31131 等效果會(huì)比較好*/ size_t operator()(const string key) { // abcd size_t hash 0; for (auto e : key) { hash hash e; hash hash * 131; } return hash; } }; namespace hash_bucket { templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) :_data(data) , _next(nullptr) {} }; // 前置聲明 templateclass K, class T, class KeyOfT, class Hash class HashTable; templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash struct HTIterator { typedef HashNodeT Node; typedef HashTableK, T, KeyOfT, Hash HT; typedef HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self; Node* _node; const HT* _pht; // 哈希表的指針 HTIterator(Node* node, const HT* pht) :_node(node) , _pht(pht) {} Ref operator*() { return _node-_data; } Ptr operator-() { return _node-_data; } Self operator() { KeyOfT kot; Hash hs; if (_node-_next) // 當(dāng)前桶沒走完 { _node _node-_next; } else // 當(dāng)前桶走完了找到下一個(gè)桶的第一個(gè)節(jié)點(diǎn) { // 算出當(dāng)前桶的位置 size_t hashi hs(kot(_node-_data)) % _pht-_tables.size(); hashi; while(hashi _pht-_tables.size()) { if (_pht-_tables[hashi]) // 找到下一個(gè)不為空的桶 { _node _pht-_tables[hashi]; break; } else { hashi; } } if (hashi _pht-_tables.size()) // 最后一個(gè)桶走完了,要到end()位置 { // end()中_node是空 _node nullptr; } } return *this; } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } }; // hash_bucket::HashTableK, pairK, V, MapKeyOfT _ht; // hash_bucket::HashTableK, K, SetKeyOfT _ht; templateclass K, class T, class KeyOfT, class Hash class HashTable { // 友元聲明 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash friend struct HTIterator; typedef HashNodeT Node; public: typedef HTIteratorK, T, T, T*, KeyOfT, Hash Iterator; typedef HTIteratorK, T, const T, const T*, KeyOfT, Hash ConstIterator; Iterator Begin() { if (_n 0) { return End(); } 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 { if (_n 0) { return End(); } 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); } HashTable() :_tables(__stl_next_prime(1), nullptr) , _n(0) {} ~HashTable() { 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; } _n 0; } pairIterator, bool Insert(const T data) { KeyOfT kot; auto it Find(kot(data)); if (it ! End()) return { it, false }; Hash hs; // 負(fù)載因子 1就開始擴(kuò)容 if (_n _tables.size()) { // 方法二, 只創(chuàng)建vector表直接將舊表的結(jié)點(diǎn)鏈接到新表中 vectorNode* newtables(__stl_next_prime(_tables.size() 1), nullptr); for (size_t i 0; i _tables.size(); i) { //遍歷舊表舊表結(jié)點(diǎn)重新映射挪動(dòng)到新表 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(); // 頭插法 Node* newnode new Node(data); newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; return {Iterator(newnode, this), true}; } Iterator Find(const K key) { KeyOfT kot; Hash hs; size_t hashi hs(key) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (kot(cur-_data) key) { return {cur, this}; // {}初始化 } cur cur-_next; } return {nullptr, this}; } bool Erase(const K key) { KeyOfT kot; Hash hs; size_t hashi hs(key) % _tables.size(); Node* pre nullptr; Node* cur _tables[hashi]; while (cur) { // 刪除 if (kot(cur-_data) key) { // 桶中第一個(gè)結(jié)點(diǎn) if (pre nullptr) { _tables[hashi] cur-_next; } else { pre-_next cur-_next; } --_n; delete cur; return true; } pre cur; cur cur-_next; } return false; } private: vectorNode* _tables; // 指針數(shù)組 size_t _n; // std::vectorstd::listK, V _tables; }; }測(cè)試代碼#define _CRT_SECURE_NO_WARNINGS 1 #includeiostream #includeunordered_map using namespace std; #includeUnorderedSet.h #includeUnorderedMap.h void Print(const xiaohan::unordered_setint s) { xiaohan::unordered_setint::const_iterator it s.begin(); while (it ! s.end()) { // *it 1; cout *it ; it; } cout endl; } int main() { xiaohan::unordered_setint us; us.insert(3); us.insert(1000); us.insert(2); us.insert(102); us.insert(2111); us.insert(22); xiaohan::unordered_setint::iterator it us.begin(); while (it ! us.end()) { //*it 1; cout *it ; it; } cout endl; Print(us); xiaohan::unordered_mapstring, string dict; dict.insert({ string, ?字符串 }); dict.insert({ string, ?字符串1 }); dict.insert({ left, 左邊 }); dict.insert({ right, 右邊 }); // 可修改 dict[left] 左邊剩余; // dict[insert]; // dict[map] 地圖; for (auto [k, v] : dict) { //k x; //v x; cout k : v endl; } return 0; }結(jié)果