当前位置: 首页> 房产> 家装 > c++进阶——unordered的封装

c++进阶——unordered的封装

时间:2025/7/11 23:54:10来源:https://blog.csdn.net/2401_83052144/article/details/141974288 浏览次数:0次

在这里插入图片描述

嗨喽大家好呀,今天阿鑫给大家带来的是c++进阶——unordered的封装,好久不见啦,下面让我们进入本节博客的内容吧!

c++进阶——unordered的封装

  1. unordered系列的基本架构
  2. unordered系列迭代器的封装
  3. unordered不支持修改key
  4. operator[]的实现
  5. 两个测试用例

在这里插入图片描述

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;
}

好啦,今天我们的学习就到这里哦,本节课内容还是有点难度的,希望大家能够好好吸收理解,期待我们的下一次再见

关键字:c++进阶——unordered的封装

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: