c++进阶——unordered的封装
嗨喽大家好呀，今天阿鑫给大家带来的是c++进阶——unordered的封装，好久不见啦，下面让我们进入本节博客的内容吧！
c++进阶——unordered的封装
- unordered系列的基本架构
- unordered系列迭代器的封装
- unordered不支持修改key
- operator[]的实现
- 两个测试用例
1. unordered系列的基本架构
#pragma once
#include"HashTable.h"
namespace zj
{template<class K,class V>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool insert(const pair<K, V>& kv){return _ht.Insert(kv);}privete:hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;};}
#pragma once
#include"HashTable.h"
namespace zj
{template<class K>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _ht.Insert(key);}privete:hash_bucket::HashTable<K, K, SetKeyOfT> _ht;};}
KeyOfT用来获取不同data的key
2. unordered系列迭代器的封装
由于哈希表结构的特点，我们对迭代器的封装不能只局限于封装指向节点对象的指针，如果想遍历整个哈希表，我们需要同时将指向哈希表对象的指针进行封装
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){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_next){// 当前桶还有节点_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;}};
为了避免编译器向上找不到HashTable，需要加上HashTable的前置声明表面这是个类。
// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
HTIterator需要调用HashTable的私有成员变量_tables,类模板的友元声明需要加上模板
// 友元声明
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
friend struct HTIterator;
在Const_Iterator中的成员函数，由于this用const修饰，所以在构造迭代器时形参需要用const的哈希表指针
HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht):_node(node), _pht(pht)
{}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);
}
3. unordered不支持修改key
4. operator[]的实现
operator[]的实现,注意make_pair是构造一个pair对象，pair<x，y>是一个结构体类型
V& operator[](const K& key){//make_pair是用来构造一个pair的pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}
5. 两个测试用例
测试用例1
void test_set1()
{unordered_set<int> s = { 3,1,6,7,8,2 };/*unordered_set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;*/srand(time(0));for (size_t i = 0; i < 22000; ++i){s.insert(rand()); // N比较大时，重复值比较多//v.push_back(rand()+i); // 重复值相对少//v.push_back(i); // 没有重复，有序}/*for (auto e : s){cout << e << " ";}cout << endl;*/cout << s.bucket_count() << endl;//cout << s.max_bucket_count() << endl;cout << s.size() << endl;cout <<"负载因子：" << s.load_factor() << endl;cout <<"最大负载因子：" << s.max_load_factor() << endl;size_t len = 0;size_t nonEmptyBucketSize = 0;size_t maxLen = 0;for (size_t i = 0; i < s.bucket_count(); i++){if (s.bucket_size(i) > 0){if (s.bucket_size(i) > maxLen)maxLen = s.bucket_size(i);len += s.bucket_size(i);++nonEmptyBucketSize;}}cout << "平均每个桶的长度:" << (double)len / nonEmptyBucketSize << endl;cout << "最大的桶的长度:" << maxLen << endl;
}
测试用例2 ——红黑树和哈希表的对比
int test_set2()
{const size_t N = 1000000;unordered_set<int> us;set<int> s;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; ++i){//v.push_back(rand()); // N比较大时，重复值比较多v.push_back(rand()+i); // 重复值相对少//v.push_back(i); // 没有重复，有序}// 21:15size_t begin1 = clock();for (auto e : v){s.insert(e);}size_t end1 = clock();cout << "set insert:" << end1 - begin1 << endl;size_t begin2 = clock();us.reserve(N);for (auto e : v){us.insert(e);}size_t end2 = clock();cout << "unordered_set insert:" << end2 - begin2 << endl;int m1 = 0;size_t begin3 = clock();for (auto e : v){auto ret = s.find(e);if (ret != s.end()){++m1;}}size_t end3 = clock();cout << "set find:" << end3 - begin3 << "->" << m1 << endl;int m2 = 0;size_t begin4 = clock();for (auto e : v){auto ret = us.find(e);if (ret != us.end()){++m2;}}size_t end4 = clock();cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;cout << "插入数据个数：" << s.size() << endl;cout << "插入数据个数：" << us.size() << endl << endl;size_t begin5 = clock();for (auto e : v){s.erase(e);}size_t end5 = clock();cout << "set erase:" << end5 - begin5 << endl;size_t begin6 = clock();for (auto e : v){us.erase(e);}size_t end6 = clock();cout << "unordered_set erase:" << end6 - begin6 << endl << endl;return 0;
}