1. 使用
unordered_map官方文檔
unordered_set 官方文檔
set / map與unordered_set / unordered_map 使用功能基本相同，但是兩者的底層結(jié)構(gòu)不同
set/map底層是紅黑樹
unordered_map/unordered_set 底層是 哈希表
紅黑樹是一種搜索二叉樹，搜索二叉樹又稱為排序二叉樹，所以迭代器遍歷是有序的
而哈希表對應(yīng)的迭代器遍歷是無序的
在map中存在rbegin以及rend的反向迭代器
在unordered_map中不存在rbegin以及rend的反向迭代器
1. unordered_set的使用
大部分功能與set基本相同，要注意的是使用unordered_set是無序的
插入數(shù)據(jù)，并使用迭代器打印，會按照插入的順序輸出，但若插入的數(shù)據(jù)已經(jīng)存在，則會插入失敗
2. unordered_map的使用
map統(tǒng)計時，會按照ASCII值排序
而unordered_map 中 元素是無序的
2. 封裝
對于 unordered_set 和 unordered_map 的封裝 是針對于 哈希桶HashBucket進行的，
即 在哈希開散列 的基礎(chǔ)上修改
點擊查看:哈希 開散列具體實現(xiàn)
修改結(jié)構(gòu)定義
哈希桶HashBucket中
需要將其內(nèi)部的HashNode 的參數(shù)進行修改
將原來的模板參數(shù) K，V 改為 T
同樣由于不知道傳入數(shù)據(jù)的是K還是K V類型的 ，所以 使用 T 類型的data代替
之前實現(xiàn)的模板參數(shù) K ，V分別代表 key 與value
修改后 ， 第一個參數(shù) 拿到單獨的K類型，是為了 使用 Find erase接口函數(shù)的參數(shù)為K
第二個參數(shù) T 決定了 拿到的是K類型 還是 K V 類型
針對insert參數(shù) data的兩種情況
創(chuàng)建 unordered_set.h頭文件，在其中創(chuàng)建命名空間unordered_set
在unordered_set中實現(xiàn)一個仿函數(shù)，
unordered_set 的第二個參數(shù) 為 K
unordered_set作為 K 模型 ，所以 T應(yīng)傳入K
創(chuàng)建 unordered_map.h頭文件，在其中創(chuàng)建命名空間unordered_map
unordered_map 的第二個參數(shù) 為 pair<cosnt K，V> 類型
K加入const ，是為了防止修改key
unordered_map 作為 KV 模型 ，所以 T應(yīng)傳入 pair<K,V>
復(fù)用 哈希桶的insert
在unordered_set中insert 是 復(fù)用HashTable中的insert
但實際上直接運行就會出現(xiàn)一大堆錯誤，哈希桶的insert 原本參數(shù)從kv變?yōu)?data，
由于data的類型為T，也就不知道 到底是unoreder_set 的K還是 unoreder_map 的KV類型的K
所以 insert中的 hashi的 key 不能夠直接求出
KeyOfT模板參數(shù)的作用
假設(shè)為unordered_set，則使用kot對象調(diào)用operator()，返回的是key
假設(shè)為unordered_map，則使用kot對象調(diào)用operator()，返回的是KV模型中的key
迭代器
在迭代器內(nèi)存存儲 節(jié)點的指針 以及 哈希表
在迭代器中使用哈希表，在哈希表中使用迭代器 ，存在互相引用，需要使用前置聲明
對于 operator * / operator-> / operator!= 跟 list 模擬實現(xiàn)基本類似
詳細(xì)點擊查看：list模擬實現(xiàn)
在自己實現(xiàn)的迭代器__HashIterator中，添加參數(shù) Ref 和 Ptr
當(dāng)為普通迭代器時，Ref作為T& ,Ptr作為T*
當(dāng)為const 迭代器時，Ref作為const T& ,Ptr作為const T*
operator++()
調(diào)用 hash調(diào)用對應(yīng)的仿函數(shù)HashFunc,若為普通類型(int)則輸出對應(yīng)key
若為 string類型，則調(diào)用特化，輸出對應(yīng)的各個字符累加的ASCII值
調(diào)用 KeyOfT ，主要區(qū)分unordered_map 與unordered_set ，
若為unordered_set ，則輸出 K類型的K
若為unordered_map ，則輸出 KV類型的K
hashi++，計算下一個桶的位置，判斷是否為空，若不為空則將其作為_node
若為空，需要繼續(xù)尋找不為空的桶
begin
在HashTable內(nèi)部實現(xiàn) begin，使用自己實現(xiàn)的_hashiterator 作為迭代器
返回第一個不為空的桶的第一個數(shù)據(jù)
c
end
在HashTable內(nèi)部實現(xiàn) end
返回最后一個桶的下一個位置 即nullptr
unordered_set對于 begin和end的復(fù)用
在unordered_set中，使用哈希桶中的HashTable的迭代器 來實現(xiàn)unordered_set的迭代器
加入typename 是因為編譯器無法識別HashBucket::HashTable<K, K, SetKeyOfT>是靜態(tài)變量還是類型
_ht作為哈希表，使其調(diào)用哈希表中的begin和end 來實現(xiàn) unordered_set的begin 和end
unordered_map對于 begin和end的復(fù)用
在 unordered_map中使用哈希桶中的HashTable的迭代器 來實現(xiàn)unordered_map的迭代器
unordered_map中operator[]的實現(xiàn)
將insert的返回值 變?yōu)閜air類型，第一個參數(shù)為迭代器 ，第二個參數(shù)為布爾值
若返回成功，則調(diào)用新插入位置的迭代器
通過尋找哈希桶中是否有相同的數(shù)據(jù)，若有則返回該迭代器以及false
在unordered_map中實現(xiàn)operator[]
詳細(xì)查看：operaor[]本質(zhì)理解
unordered_set修改迭代器數(shù)據(jù) 問題
在unordered_set中，借助 哈希桶中的普通迭代器 實現(xiàn) unordered_set的普通迭代器
在unordered_set中，借助 哈希桶中的const迭代器 實現(xiàn) unordered_set的const迭代器
在STL中，是不允許 unordered_set去 *it 修改數(shù)據(jù)的 ，但是在自己實現(xiàn)的迭代器中卻可以通過
在STL中將 unordered_set的普通迭代器也為哈希桶的const 迭代器
調(diào)用begin時，雖然看似返回普通迭代器，但是當(dāng)前普通迭代器是作為哈希桶的const迭代器存在的
而返回值依舊是 哈希桶的普通迭代器
在哈希桶自己實現(xiàn)的迭代器__HashIterator中
創(chuàng)建一個普通迭代器 ，當(dāng)傳入普通迭代器時，為拷貝構(gòu)造
當(dāng)傳入 const 迭代器時，就 發(fā)生隱式類型轉(zhuǎn)換，講普通迭代器轉(zhuǎn)換為const 迭代器文章來源：http://www.zghlxwxcb.cn/news/detail-461179.html
此時在unordered_set中 的普通迭代器無法被修改文章來源地址http://www.zghlxwxcb.cn/news/detail-461179.html
完整代碼
HashTable.h
#include<iostream>
#include<vector>
using namespace std;
template<class K>
struct HashFunc //仿函數(shù)
{
size_t operator()(const K& key)
{
return key;
}
};
//特化
template<>
struct HashFunc<string> //仿函數(shù)
{
//將字符串轉(zhuǎn)化為整形
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 31;//用上次的結(jié)果乘以31
}
return hash;
}
};
namespace HashBucket //哈希桶
{
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 Ref,class Ptr,class KeyOfT, class Hash >
struct __HashIterator
{
typedef HashNode<T> Node;
Node* _node;//節(jié)點的指針
typedef HashTable<K, T, KeyOfT, Hash> HT; //哈希表 typedef HT
HT* _ht; //哈希表
typedef __HashIterator<K, T, Ref,Ptr,KeyOfT, Hash> Self;
//定義一個普通迭代器
typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
__HashIterator(Node* node, HT* ht)
:_node(node),_ht(ht)
{
}
__HashIterator(const Iterator &it)
:_node(it._node),_ht(it._ht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self &s)
{
//使用節(jié)點的指針進行比較
return _node != s._node;
}
//前置++
Self& operator++()
{
//若不處于當(dāng)前桶的尾位置，則尋找桶的下一個位置
if (_node->_next != nullptr)
{
_node = _node->_next;
}
else
{
//若為空，則說明處于當(dāng)前桶的尾位置，則需尋找下一個不為空的桶
KeyOfT kot;
Hash hash;
//計算當(dāng)前桶位置
size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
hashi++;//下一個位置
//尋找下一個不為空的桶
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
else
{
//桶為空，需要繼續(xù)尋找
hashi++;
}
}
//沒有找到不為空的桶
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash >
friend struct __HashIterator;//友元 使 __HashIterator中可以調(diào)用HashTable的私有
typedef HashNode<T> Node;
public:
typedef __HashIterator<K, T,T&,T*, KeyOfT, Hash> iterator;
typedef __HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
iterator begin()
{
Node* cur = nullptr;
size_t i = 0;
//找到第一個不為空的桶
for (i = 0; i < _tables.size(); i++)
{
cur = _tables[i];
if (cur)
{
break;
}
}
//迭代器返回 第一個桶 和哈希表
//this 作為哈希表本身
return iterator(cur,this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin()const
{
Node* cur = nullptr;
size_t i = 0;
//找到第一個不為空的桶
for (i = 0; i < _tables.size(); i++)
{
cur = _tables[i];
if (cur)
{
break;
}
}
//迭代器返回 第一個桶 和哈希表
//this 作為哈希表本身
return const_iterator(cur, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
~HashTable()//析構(gòu)
{
for (auto& cur : _tables)
{
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
cur = nullptr;
}
}
iterator Find(const K& key)//查找
{
Hash hash;
KeyOfT kot;
//若表剛開始為空
if (_tables.size() == 0)
{
return end();
}
size_t hashi = hash(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)//刪除
{
Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _tables.size();
Node* prev = nullptr;//用于記錄前一個節(jié)點
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)//要刪除節(jié)點為頭節(jié)點時
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
pair<iterator,bool> insert(const T& data )//插入
{
KeyOfT kot;
//若對應(yīng)的數(shù)據(jù)已經(jīng)存在，則插入失敗
iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it, false);
}
Hash hash;
//負(fù)載因子==1時擴容
if (_n == _tables.size())
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*>newtables(newsize, nullptr);//創(chuàng)建 newsize個數(shù)據(jù)，每個數(shù)據(jù)都為空
for (auto& cur : _tables)
{
while (cur)
{
Node* next = cur->_next;//保存下一個舊表節(jié)點
size_t hashi = hash(kot(cur->_data)) % newtables.size();
//將舊表節(jié)點頭插到新表節(jié)點中
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
}
_tables.swap(newtables);
}
size_t hashi = hash(kot(data)) % _tables.size();
//頭插
Node* newnode = new Node(data);//新建節(jié)點
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(iterator(newnode,this), true);
}
private:
vector<Node*> _tables; //指針數(shù)組
size_t _n=0;//存儲數(shù)據(jù)有效個數(shù)
};
}
unordered_set.h
#include"HashTable.h"
namespace yzq
{
template<class K,class Hash=HashFunc<K>>
class unordered_set
{
public:
struct SetKeyOfT//仿函數(shù)
{
const K& operator()(const K&key)
{
return key;
}
};
public:
typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator 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();
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
HashBucket::HashTable<K,K, SetKeyOfT, Hash> _ht;
};
void test_set()
{
unordered_set<int> v;
v.insert(1);
v.insert(3);
v.insert(2);
v.insert(8);
v.insert(1000);
v.insert(5);
unordered_set<int>::iterator it = v.begin();
while (it != v.end())
{
//*it = 1;
cout << *it << " ";
++it;
}
}
}
unordered_map.h
#include"HashTable.h"
namespace yzq
{
template<class K,class V,class Hash=HashFunc<K>>
class unordered_map
{
public:
struct MapKeyOfT//仿函數(shù)
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashBucket::HashTable<K,
pair<const K, V>, MapKeyOfT,Hash>::iterator iterator;
typedef typename HashBucket::HashTable<K,
pair<const K, V>, MapKeyOfT, Hash>::constiterator const_iterator;
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;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.insert(kv);
}
iterator find(const K& key)
{
return _ht.Find();
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
HashBucket::HashTable<K, pair<const K ,V>, MapKeyOfT,Hash> _ht;
};
void test_map()
{
unordered_map<int,int> v;
v.insert(make_pair(1,1));
v.insert(make_pair(3, 3));
v.insert(make_pair(10, 10));
v.insert(make_pair(2, 2));
v.insert(make_pair(8, 8));
unordered_map<int, int>::iterator it = v.begin();
while (it != v.end())
{
cout << it->first<<":"<<it->second << " ";
++it;
}
cout << endl;
}
}
到了這里，關(guān)于【C++】unordered_set 和 unordered_map 使用 | 封裝的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
