中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置： 首頁 > news >正文

網(wǎng)站圖片分辨率福州百度分公司

news 2025/7/6 6:08:18
網(wǎng)站圖片分辨率,福州百度分公司,dw網(wǎng)頁制作超鏈接,怎么免費(fèi)做網(wǎng)站前言： 前面我們學(xué)習(xí)了unordered_map和unordered_set容器，比較了他們和map、set的查找效率，我們發(fā)現(xiàn)他們的效率比map、set高，進(jìn)而我們研究他們的底層是由哈希實(shí)現(xiàn)。哈希是一種直接映射的方式，所以查找的效率很快…

前言：
? ? ? ?前面我們學(xué)習(xí)了unordered_map和unordered_set容器，比較了他們和map、set的查找效率，我們發(fā)現(xiàn)他們的效率比map、set高，進(jìn)而我們研究他們的底層是由哈希實(shí)現(xiàn)。哈希是一種直接映射的方式，所以查找的效率很快。與學(xué)習(xí)紅黑樹和map、set的思路一樣，我們現(xiàn)在學(xué)完了unordered_map和unordered_set，本章將模擬實(shí)現(xiàn)底層結(jié)構(gòu)來封裝該容器！

? ? 作者建議在閱讀本章前，可以先去看一下前面的紅黑樹封裝map和set——紅黑樹封裝map和set

這兩篇文章都重在強(qiáng)調(diào)泛型編程的思想，上一篇由于是初認(rèn)識，作者講解的會更詳細(xì)一點(diǎn)~

目錄

（一）如何復(fù)用一個哈希桶

1、結(jié)點(diǎn)的定義：

2、兩個容器各自的模板參數(shù)類型?編輯

3、改造哈希桶

（二）哈希桶的迭代器的模擬實(shí)現(xiàn)

1、begin()和end()的模擬實(shí)現(xiàn)

2、operator*和operator->及operator!=和operator==的模擬實(shí)現(xiàn)?

3、operator ++的模擬實(shí)現(xiàn)

（三）迭代器和改造哈希桶的總代碼

（四）封裝unordered_map和unordered_set

（一）如何復(fù)用一個哈希桶

我們學(xué)習(xí)過知道，unordered_map和unordered_set容器存放的結(jié)點(diǎn)并不一樣，為了讓它得到復(fù)用，我們就需要對哈希桶進(jìn)行改造，將哈希桶改造的更加泛型一點(diǎn)，既符合Key模型，也符合Key_Value模型。

1、結(jié)點(diǎn)的定義：

?所以我們這里還是和封裝map和set時(shí)一樣，無論是Key還是Key_Value，都用一個類型T來接收，這里高維度的泛型哈希表中，實(shí)現(xiàn)還是用的是Kye_Value模型，K是不能省略的，同樣的查找和刪除要用，故我們可以引出兩個容器各自模板參數(shù)類型。

2、兩個容器各自的模板參數(shù)類型

如何取到想要的數(shù)據(jù)：

  • 我們給每個容器配一個仿函數(shù)
  • 各傳不同的仿函數(shù)，拿到想要的不同的數(shù)據(jù)

同時(shí)我們再給每個容器配一個哈希函數(shù)。

3、改造哈希桶

通過上面1和2，我們可以把各自存放的數(shù)據(jù)泛化成data：

這樣我們哈希桶的模板參數(shù)算是完成了

  • 哈希函數(shù)我們可以自由選擇并傳
  • 仿函數(shù)在各自容器的封裝中實(shí)現(xiàn)，用于比較時(shí)我們可以取出各自容器想要的數(shù)據(jù)

我們把上一篇文章封裝的哈希桶拿來改造：

//K --> 鍵值Key，T --> 數(shù)據(jù)
//unordered_map ->HashTable<K, pair<K, V>, MapKeyOfT> _ht;
//unordered_set ->HashTable<K, K, SetKeyOfT> _ht;
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{template<class K, class T, class KeyOfT, class HashFunc>friend class __HTIterator;typedef HashNode<T> Node;
public:typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}~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;}}size_t GetNextPrime(size_t prime){const int PRIMECOUNT = 28;static const size_t primeList[PRIMECOUNT] ={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};//獲取比prime大那一個素?cái)?shù)size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){if (primeList[i] > prime)return primeList[i];}return primeList[i];}pair<iterator, bool> Insert(const T& data){HashFunc hf;KeyOfT kot;iterator pos = Find(kot(data));if (pos != end()){return make_pair(pos, false);}//負(fù)載因子 == 1 擴(kuò)容 -- 平均每個桶掛一個結(jié)點(diǎn)if (_tables.size() == _n){//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newSize = GetNextPrime(_tables.size());if (newSize != _tables.size()){vector<Node*> newTable;newTable.resize(newSize, nullptr);//遍歷舊表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];//再對每個桶挨個遍歷while (cur){Node* next = cur->_next;size_t hashi = hf(kot(cur->_data)) % newSize;//轉(zhuǎn)移到新的表中cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}//將原表置空_tables[i] = nullptr;}newTable.swap(_tables);}}size_t hashi = hf(kot(data));hashi %= _tables.size();//頭插到對應(yīng)的桶即可Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;//有效數(shù)據(jù)加一_n++;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){if (_tables.size() == 0){return iterator(nullptr, this);}KeyOfT kot;HashFunc hf;size_t hashi = hf(key);//size_t hashi = HashFunc()(key);hashi %= _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){if (_tables.size() == 0){return false;}HashFunc hf;KeyOfT kot;size_t hashi = hf(key);hashi %= _tables.size();//單鏈表刪除結(jié)點(diǎn)Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){//頭刪if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}
private://指針數(shù)組vector<Node*> _tables;size_t _n = 0;
};

主要改造的地方就是上述所注意的地方：

  • 比較時(shí)需要調(diào)用各自的仿函數(shù)
  • 調(diào)用外部傳的哈希函數(shù)

還有對擴(kuò)容的二次思考：

研究表明：除留余數(shù)法，最好模一個素?cái)?shù)

  • 通過查STL官方庫我們也發(fā)現(xiàn)，其提供了一個取素?cái)?shù)的函數(shù)
  • 所以我們也提供了一個，直接拷貝過來
    • 這樣我們在擴(kuò)容時(shí)就可以每次給素?cái)?shù)個桶
    • 在擴(kuò)容時(shí)加了一條判斷語句是為了防止素?cái)?shù)值太大，過分?jǐn)U容容易直接把空間(堆)干崩了

（二）哈希桶的迭代器的模擬實(shí)現(xiàn)

1、begin()和end()的模擬實(shí)現(xiàn)

  • 以第一個桶中第一個不為空的結(jié)點(diǎn)為整個哈希桶的開始結(jié)點(diǎn)
  • 以空結(jié)點(diǎn)為哈希桶的結(jié)束結(jié)點(diǎn)

2、operator*和operator->及operator!=和operator==的模擬實(shí)現(xiàn)?

這兩組和之前實(shí)現(xiàn)的一模一樣，大家自行理解。

3、operator ++的模擬實(shí)現(xiàn)

注：

  • 這里要在哈希桶的類外面訪問其私有成員
  • 我們要搞一個友元類
  • 迭代器類是哈希桶類的朋友
  • 這樣就可以訪問了

?

思路：

  • 判斷一個桶中的數(shù)據(jù)是否遍歷完
  • 如果所在的桶沒有遍歷完，在該桶中返回下一個結(jié)點(diǎn)指針
  • 如果所在的桶遍歷完了，進(jìn)入下一個桶
  • 判斷下一個桶是否為空
  • 非空返回桶中第一個節(jié)點(diǎn)
  • 空的話就遍歷一個桶
  • 后置++和之前一眼老套路，不贅述

注意：

unordered_map和unordered_set是不支持反向迭代器的，從底層結(jié)構(gòu)我們也能很好的理解（單鏈表找不了前驅(qū)）所以不支持實(shí)現(xiàn)迭代器的operator- -

最后注意一點(diǎn)，我們需要知道哈希桶大小，所以不僅要傳結(jié)點(diǎn)地址，還要傳一個哈希桶，這樣才能知道其大小，除此，由于哈希桶改造在后面，所以我們要在前面聲明一下：

（三）迭代器和改造哈希桶的總代碼

#include<vector>
#include<string>
#include<iostream>
using namespace std;template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDRsize_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;}return hash;}
};namespace Bucket
{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class KeyOfT, class HashFunc>class HashTable;//哈希桶的迭代器template<class K, class T, class KeyOfT, class HashFunc>class __HTIterator{typedef HashNode<T> Node;typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;public:Node* _node;__HTIterator() {};//編譯器的原則是向上查找（定義必須在前面，否則必須先聲明）HashTable<K, T, KeyOfT, HashFunc>* _pht;__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node), _pht(pht){}Self& operator++(){if (_node->_next){_node = _node->_next;}else//當(dāng)前桶已經(jīng)走完了，要走下一個桶{KeyOfT kot;HashFunc hf;size_t hashi = hf(kot(_node->_data)) % _pht->_tables.size();hashi++;//找下一個不為空的桶 -- 訪問到了哈希表中私有的成員（友元）for (; hashi < _pht->_tables.size(); hashi++){if (_pht->_tables[hashi]){_node = _pht->_tables[hashi];break;}}//沒有找到不為空的桶，用nullptr去做end標(biāo)識if (hashi == _pht->_tables.size()){_node = nullptr;}}return *this;}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};//K --> 鍵值Key，T --> 數(shù)據(jù)//unordered_map ->HashTable<K, pair<K, V>, MapKeyOfT> _ht;//unordered_set ->HashTable<K, K, SetKeyOfT> _ht;template<class K, class T, class KeyOfT, class HashFunc>class HashTable{template<class K, class T, class KeyOfT, class HashFunc>friend class __HTIterator;typedef HashNode<T> Node;public:typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}~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;}}size_t GetNextPrime(size_t prime){const int PRIMECOUNT = 28;static const size_t primeList[PRIMECOUNT] ={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};//獲取比prime大那一個素?cái)?shù)size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){if (primeList[i] > prime)return primeList[i];}return primeList[i];}pair<iterator, bool> Insert(const T& data){HashFunc hf;KeyOfT kot;iterator pos = Find(kot(data));if (pos != end()){return make_pair(pos, false);}//負(fù)載因子 == 1 擴(kuò)容 -- 平均每個桶掛一個結(jié)點(diǎn)if (_tables.size() == _n){//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newSize = GetNextPrime(_tables.size());if (newSize != _tables.size()){vector<Node*> newTable;newTable.resize(newSize, nullptr);//遍歷舊表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];//再對每個桶挨個遍歷while (cur){Node* next = cur->_next;size_t hashi = hf(kot(cur->_data)) % newSize;//轉(zhuǎn)移到新的表中cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}//將原表置空_tables[i] = nullptr;}newTable.swap(_tables);}}size_t hashi = hf(kot(data));hashi %= _tables.size();//頭插到對應(yīng)的桶即可Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;//有效數(shù)據(jù)加一_n++;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){if (_tables.size() == 0){return iterator(nullptr, this);}KeyOfT kot;HashFunc hf;size_t hashi = hf(key);//size_t hashi = HashFunc()(key);hashi %= _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){if (_tables.size() == 0){return false;}HashFunc hf;KeyOfT kot;size_t hashi = hf(key);hashi %= _tables.size();//單鏈表刪除結(jié)點(diǎn)Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){//頭刪if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}private://指針數(shù)組vector<Node*> _tables;size_t _n = 0;};
}

（四）封裝unordered_map和unordered_set

有了上面的哈希桶的改裝，我們這里的對map和set的封裝就顯得很得心應(yīng)手了。

unordered_map的封裝：

#include "HashTable.h"namespace zc
{template<class K, class V, class HashFunc = DefaultHash<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> _ht;};void test_map(){unordered_map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("left", "左邊"));dict.insert(make_pair("left", "下面"));dict["string"];dict["left"] = "上面";dict["string"] = "字符串";unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << " " << it->second << endl;++it;}cout << endl;for (auto e : dict){cout << e.first << " " << e.second << endl;}}}

這里unordered_map中的operator[ ]我們知道其原理之后，模擬實(shí)現(xiàn)就非常方便，直接調(diào)用插入函數(shù)，控制好參數(shù)和返回值即可。

對unordered_set的封裝：

#include "HashTable.h"#include "HashTable.h"namespace zc
{template<class K, class HashFunc = DefaultHash<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://2.48typedef typename Bucket::HashTable<K, K, SetKeyOfT, HashFunc>::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);}bool erase(const K& key){return _ht.Erase(key);}private:Bucket::HashTable<K, K, SetKeyOfT, HashFunc> _ht;};struct Date{Date(int year = 1, int month = 1, int day = 1):_year(year), _month(month), _day(day){}bool operator==(const Date& d) const{return _year == d._year&& _month == d._month&& _day == d._day;}int _year;int _month;int _day;};struct DateHash{size_t operator()(const Date& d){//return d._year + d._month + d._day;size_t hash = 0;hash += d._year;hash *= 131;hash += d._month;hash *= 1313;hash += d._day;//cout << hash << endl;return hash;}};void test_set(){unordered_set<int> s;//set<int> s;s.insert(2);s.insert(3);s.insert(1);s.insert(2);s.insert(5);s.insert(12);unordered_set<int>::iterator it = s.begin();//auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;unordered_set<Date, DateHash> sd;sd.insert(Date(2022, 3, 4));sd.insert(Date(2022, 4, 3));}
}

最后大家可以利用代碼中給的測試函數(shù)進(jìn)行測試！

感謝你的閱讀！

http://www.risenshineclean.com/news/42185.html

相關(guān)文章：

  • 佛山新網(wǎng)站制作特色網(wǎng)站推廣排名
  • 沒有網(wǎng)站怎么做淘客視頻號怎么推廣流量
  • 臨沂做網(wǎng)站電話信息發(fā)布平臺推廣有哪些
  • 編程課有必要學(xué)嗎丈哥seo博客工具
  • 武漢網(wǎng)站設(shè)計(jì)站建設(shè)seo課程
  • 政務(wù)網(wǎng)站的建設(shè)時(shí)期的概述品牌策劃公司哪家好
  • 多語言網(wǎng)站實(shí)現(xiàn)微信引流推廣怎么做
  • 張家港網(wǎng)站建設(shè)做網(wǎng)站免費(fèi)的網(wǎng)絡(luò)營銷方式
  • 網(wǎng)站怎么做別名專門搜索知乎內(nèi)容的搜索引擎
  • 網(wǎng)站圖片怎么做超鏈接百家號關(guān)鍵詞排名
  • 萬能造假截圖生成器上海外貿(mào)seo
  • 做的好的購物網(wǎng)站佛山網(wǎng)站設(shè)計(jì)實(shí)力樂云seo
  • 學(xué)校網(wǎng)站制作方案我對網(wǎng)絡(luò)營銷的理解
  • 購物網(wǎng)站的基本功能營銷網(wǎng)絡(luò)是什么
  • 網(wǎng)站開發(fā)外包報(bào)價(jià)建設(shè)網(wǎng)站
  • 推薦常州網(wǎng)站建設(shè)seo技術(shù)員
  • 可以做宣傳海報(bào)的網(wǎng)站信息流優(yōu)化師簡歷怎么寫
  • 網(wǎng)站目錄怎么做推廣專員是做什么的
  • 最新國際新聞頭條今日國際大事件seo計(jì)費(fèi)系統(tǒng)登錄
  • 做網(wǎng)站濱州市最近的時(shí)事新聞
  • 杭州手機(jī)申請網(wǎng)站登錄谷歌chrome
  • 哪個網(wǎng)站的圖片可以做素材永久觀看不收費(fèi)的直播
  • 魏縣做網(wǎng)站網(wǎng)站排名推廣工具
  • 普象工業(yè)設(shè)計(jì)網(wǎng)站上海最新事件
  • 上海制作網(wǎng)頁宣傳seo發(fā)展前景怎么樣啊
  • 如何知道網(wǎng)站開發(fā)語言軟文營銷的成功案例
  • wordpress計(jì)算器主題優(yōu)化站點(diǎn)
  • 怎么做淘寶客的跳轉(zhuǎn)網(wǎng)站免費(fèi)的網(wǎng)頁入口
  • 上海企業(yè)網(wǎng)站建設(shè)谷歌關(guān)鍵詞挖掘工具
  • 重慶網(wǎng)站推廣轉(zhuǎn)化率鄭州seo聯(lián)系搜點(diǎn)網(wǎng)絡(luò)效果好