嗨喽大家好呀，今天阿鑫给大家带来的是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:15
size_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;
}
![[Linux]：进程(下)](https://img-blog.csdnimg.cn/img_convert/f0c07e46c07b79a5f64d43840d99e37d.png)
