C++之unordered封裝的實現(xiàn)
更新時間：2025年05月06日 09:00:27 作者：孞?￥
本文主要介紹了C++之unordered封裝的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
一、哈希表的修改
注意：這里我們使用哈希桶來封裝unordered_map和unordered_set。
1.1、哈希表節(jié)點結(jié)構(gòu)
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};因為我們要復(fù)用哈希表，即使用同一份哈希表代碼來封裝unordered_map和unordered_set，所以這里將模版參數(shù)改為T，T即要存儲的數(shù)據(jù)類型，對于unordered_set而言，T直接就是要存儲的數(shù)據(jù)類型；對于unordered_map而言，T是pair類型的。
在插入方法中，我們使用有參構(gòu)造，在創(chuàng)建節(jié)點時直接將數(shù)據(jù)通過構(gòu)造函數(shù)賦值進去，所以這里還實現(xiàn)了一個構(gòu)造函數(shù)。
1.2、迭代器
iterator核心源碼：
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
node* cur;
hashtable* ht;
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};
template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
const node* old = cur;
cur = cur->next;
if (!cur) {
size_type bucket = ht->bkt_num(old->val);
while (!cur && ++bucket < ht->buckets.size())
cur = ht->buckets[bucket];
}
return *this;
}
iterator實現(xiàn)思路分析：
- iterator實現(xiàn)的?框架跟list的iterator思路是?致的，??個類型封裝結(jié)點的指針，再通過重載運算 符實現(xiàn)，迭代器像指針?樣訪問的?為，要注意的是哈希表的迭代器是單向迭代器。
- 這?的難點是operator++的實現(xiàn)。iterator中有?個指向結(jié)點的指針，如果當前桶下?還有結(jié)點， 則結(jié)點的指針指向下?個結(jié)點即可。如果當前桶?完了，則需要想辦法計算找到下?個桶。這?的難點是反?是結(jié)構(gòu)設(shè)計的問題，參考上面源碼，我們可以知道iterator中除了有結(jié)點的指針，還有哈希表對象的指針，這樣當前桶?完了，要計算下?個桶就相對容易多了，?key值計算出當前桶位置，依次往后找下?個不為空的桶即可。
- begin()返回第?個不為空的桶中第?個節(jié)點指針構(gòu)造的迭代器，這?end()返回迭代器可以?空指針表?。
- unordered_map的iterator不?持修改key但是可以修改value，我們把unordered_map的第?個模板參數(shù)pair的第?個參數(shù)改成const K即可，HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;（不允許修改Key是因為數(shù)據(jù)在哈希表中存儲的地址是通過Key映射的，如果修改Key，破壞了哈希表的結(jié)構(gòu)）。
- unordered_set的iterator也不?持修改，我們把unordered_set的第?個模板參數(shù)改成const K即可，HashTable<K, const K, SetKeyOfT, Hash> _ht;（和unordered_map同理）。
具體代碼：
// 前置聲明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
:_node(node)
,_pht(pht)
{}
Self& operator++()
{
if (_node->_next)
{
//當前桶還有節(jié)點
_node = _node->_next;
}
else
{
//當前桶走完了，找下一個不為空的桶
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
++hashi;
while (hashi < _pht->_tables.size())
{
if (_pht->_tables[hashi])
{
break;
}
++hashi;
}
if (hashi == _pht->_tables.size())
{
_node = nullptr; //end()
}
else
{
_node = _pht->_tables[hashi];
}
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};注意：這里需要對哈希表進行前置聲明，因為在迭代器中用到了哈希表，但是編譯器編譯時是向上查找，而哈希表在下面，會因為找不到而報錯，將哈希表放到上面也不行，因為哈希表里也會封裝迭代器，如果哈希表在上面向上查找時就會找不到迭代器，總之必須有一個進行前置聲明。另外，迭代器中重載++運算符時為了確定當前節(jié)點的位置訪問了哈希表的私有成員，所以后面在哈希表中還需要進行友元聲明。
1.3、哈希表結(jié)構(gòu)
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
// 友元聲明
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
friend struct HTIterator;
typedef HashNode<T> Node; //節(jié)點不想讓外界訪問
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; //迭代器需要讓外界訪問
typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;
Iterator Begin()
{
if (_n == 0) //沒有有效數(shù)據(jù)
{
return End();
}
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);
}
ConstIterator Begin() const
{
if (_n == 0)
return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
{
_tables.resize(10, nullptr);
}
~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;
}
}
pair<Iterator,bool> Insert(const T& data)
{
KeyOfT kot;
Iterator it = Find(kot(data));
//去重
if (it != End())
{
return make_pair(it,false);
}
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size();
//負載因子==1 擴容
if (_n == _tables.size())
{
// 需要新建節(jié)點和釋放舊節(jié)點，效率較低
// HashTable<K, V, Hash> newHT;
// for (size_t i = 0; i < _tables.size(); i++)
// {
// Node* cur = _tables[i];
// while (cur)
// {
// newHT.Insert(cur->_kv);
// cur = cur->_next;
// }
// }
// _tables.swap(newHT._tables);
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;
//舊表中的節(jié)點重新映射在新表中的位置
size_t hashi = hs(kot(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
//節(jié)點都挪到新表上了，舊表置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
//頭插
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)
{
KeyOfT kot;
Hash hs;
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 End();
}
bool Erase(const K& key)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
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;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables; //指針數(shù)組
size_t _n; //表中存儲數(shù)據(jù)個數(shù)
};
}為什么需要KeyOfT模版參數(shù)：
跟map和set相???unordered_map和unordered_set的模擬實現(xiàn)類結(jié)構(gòu)更復(fù)雜?點，但是?框架和思路是完全類似的。因為HashTable實現(xiàn)了泛型不知道T參數(shù)是K，還是pair， 那么insert內(nèi)部進?插?時要?K對象轉(zhuǎn)換成整形取模和K?較相等(去重)，因為pair的value不需要參與計算取模，且pair默認?持的是key和value?起?較相等，但實際上我們需要的是任何時候只需要?較K對象，所以我們在unordered_map和unordered_set層分別實現(xiàn)?個MapKeyOfT和SetKeyOfT的仿函數(shù)傳給 HashTable的KeyOfT，然后HashTable中通過KeyOfT仿函數(shù)取出T類型對象中的K對象，再轉(zhuǎn)換成整形取模和K?較相等。
返回值的修改：
這里為了符合unordered_map和unordered_set的使用將Find方法的返回值改為迭代器，為了實現(xiàn)unordered_map的 [ ] 運算符重載，將Insert方法的返回值該為pair類型，其中返回的pair對象的first屬性的值是新插入節(jié)點/原有節(jié)點的迭代器，second屬性的值是bool類型，代表是否插入成功。
1.4、完整代碼
namespace hash_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 Hash>
class HashTable;
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
:_node(node)
,_pht(pht)
{}
Self& operator++()
{
if (_node->_next)
{
//當前桶還有節(jié)點
_node = _node->_next;
}
else
{
//當前桶走完了，找下一個不為空的桶
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
++hashi;
while (hashi < _pht->_tables.size())
{
if (_pht->_tables[hashi])
{
break;
}
++hashi;
}
if (hashi == _pht->_tables.size())
{
_node = nullptr; //end()
}
else
{
_node = _pht->_tables[hashi];
}
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
// 友元聲明
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
friend struct HTIterator;
typedef HashNode<T> Node; //節(jié)點不想讓外界訪問
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; //迭代器需要讓外界訪問
typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;
Iterator Begin()
{
if (_n == 0) //沒有有效數(shù)據(jù)
{
return End();
}
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);
}
ConstIterator Begin() const
{
if (_n == 0)
return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
{
_tables.resize(10, nullptr);
}
~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;
}
}
pair<Iterator,bool> Insert(const T& data)
{
KeyOfT kot;
Iterator it = Find(kot(data));
//去重
if (it != End())
{
return make_pair(it,false);
}
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size();
//負載因子==1 擴容
if (_n == _tables.size())
{
// 需要新建節(jié)點和釋放舊節(jié)點，效率較低
// HashTable<K, V, Hash> newHT;
// for (size_t i = 0; i < _tables.size(); i++)
// {
// Node* cur = _tables[i];
// while (cur)
// {
// newHT.Insert(cur->_kv);
// cur = cur->_next;
// }
// }
// _tables.swap(newHT._tables);
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;
//舊表中的節(jié)點重新映射在新表中的位置
size_t hashi = hs(kot(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
//節(jié)點都挪到新表上了，舊表置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
//頭插
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)
{
KeyOfT kot;
Hash hs;
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 End();
}
bool Erase(const K& key)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
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;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables; //指針數(shù)組
size_t _n; //表中存儲數(shù)據(jù)個數(shù)
};
}二、unordered_map的實現(xiàn)
這里的實現(xiàn)沒有什么困難，就是直接套一層殼，所有的調(diào)用最終還是去調(diào)哈希表的方法，所以這里就不在贅述了，直接上代碼。
#include"HashTable.h"
namespace bit
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const 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();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
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);
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
void test_map()
{
unordered_map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左邊" });
dict.insert({ "right", "右邊" });
dict["left"] = "左邊，剩余";
dict["insert"] = "插入";
dict["string"];
unordered_map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
// 不能修改first，可以修改second
//it->first += 'x';
it->second += 'x';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
}
三、unordered_set的實現(xiàn)
這里和unordered_map一樣，就是直接套一層殼，所有的調(diào)用最終還是去調(diào)哈希表的方法，所以這里就不在贅述了，直接上代碼。
#include"HashTable.h"
namespace bit
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, 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();
}
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:
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
void Print(const unordered_set<int>& s)
{
unordered_set<int>::const_iterator it = s.begin();
while (it != s.end())
{
// *it += 1;
cout << *it << " ";
++it;
}
cout << endl;
}
struct Date
{
int _year;
int _month;
int _day;
bool operator==(const Date& d) const
{
return _year == d._year
&& _month == d._month
&& _day == d._day;
}
};
struct HashDate
{
size_t operator()(const Date& key)
{
// 112
// 121
return (key._year * 31 + key._month) * 31 + key._day;
}
};
void test_set()
{
unordered_set<int> s;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };
for (auto e : a)
{
s.insert(e);
}
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
//*it += 1;
cout << *it << " ";
++it;
}
cout << endl;
unordered_set<Date, HashDate> us;
us.insert({ 2024, 7, 25 });
us.insert({ 2024, 7, 26 });
Print(s);
}
}到此這篇關(guān)于C++之unordered封裝的實現(xiàn)的文章就介紹到這了,更多相關(guān)C++ unordered封裝內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言詳解如何實現(xiàn)堆及堆的結(jié)構(gòu)與接口
堆是計算機科學中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱，通常是一個可以被看做一棵完全二叉樹的數(shù)組對象。而堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。本文將詳細介紹堆的結(jié)構(gòu)與接口，需要的可以參考一下2022-04-04
這篇文章主要為大家詳細介紹了C++實現(xiàn)bmp格式圖像讀寫，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
c++實現(xiàn)一個簡易的網(wǎng)絡(luò)緩沖區(qū)的實踐
這篇文章主要介紹了c++實現(xiàn)一個簡易的網(wǎng)絡(luò)緩沖區(qū)的實踐，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
在C語言中,有時候我們遇到這樣的考題,將c語言大寫字母轉(zhuǎn)化為小寫字母,下面這篇文章主要給大家介紹了關(guān)于C語言中字母大小寫轉(zhuǎn)化的相關(guān)資料,文中介紹的非常詳細,需要的朋友可以參考下2022-11-11
預(yù)處理程序提供了條件編譯的功能?？梢园床煌臈l件去編譯不同的程序部分，因而產(chǎn)生不同的目標代碼文件。這對于程序的移植和調(diào)試是很有用的。條件編譯有三種形式，下面分別介紹。2017-05-05
這篇文章主要介紹了C++中引用&與取地址&的區(qū)別,有助于C++初學者更好的掌握指針的概念及用法,需要的朋友可以參考下2014-09-09
C語言數(shù)據(jù)結(jié)構(gòu)算法之實現(xiàn)快速傅立葉變換
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)算法之實現(xiàn)快速傅立葉變換的相關(guān)資料,需要的朋友可以參考下2017-06-06
C++中memcpy函數(shù)的使用以及模擬實現(xiàn)
memcpy是c和c++使用的內(nèi)存拷貝函數(shù)，本文主要介紹了C++中memcpy函數(shù)的使用以及模擬實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
Qt利用QState狀態(tài)機實現(xiàn)控件互斥操作詳解
這篇文章主要為大家詳細介紹了Qt如何利用QState狀態(tài)機實現(xiàn)控件互斥操作，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下2022-12-12
數(shù)據(jù)結(jié)構(gòu)用兩個棧實現(xiàn)一個隊列的實例
這篇文章主要介紹了C++語言數(shù)據(jù)結(jié)構(gòu)用兩個棧實現(xiàn)一個隊列的實例的相關(guān)資料,需要的朋友可以參考下2017-06-06