当前位置：首页 > news >正文

unoredered_mapunordered_set封装

news 来源：原创 2024/9/12 11:38:56

各层封装关系

封装时细节/tips

Rfr Ptr用来constiterator

//HTIterator 模板
template<class K, class T, class Ptr, class Rfr, class KeyOfT, class Hash>
class HTIterator//普通Iterator类 & const_iterator类
typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

hashtable中必须写const Begin & const End ，因为cosntiterator和iterator是两个不同的类，不可自动转换

//错误， iterater & const_iterator不是同一类， 也没有强转函数， 不可转化
bit::HashTable<string, pair<string, string>>::ConstIterator it = ss.Begin();//正确， 类型匹配
bit::HashTable<string, pair<string, string>>::ConstIterator it = ss.cBegin();

因子比较记得转成小数

//错误， 两整数相除， 结果还是整数， 误差较大
if (_n / _tables.size() >= 1)//扩容//正确
if (double(_n) / _tables.size() >= 1)//扩容

HTIterator 构造函数， _ptr不可const， _pht 一定要const 为了 constiterator 初始化（传递 const this，要用 const hashtable类接收）

//iterator构造函数
HTIterator(HashNode<T>* p, const HashTable<K, T, KeyOfT, Hash>* pht):_ptr(p),_pht(pht)
{}//iterator成员类型
HashNode<T>* _ptr = nullptr;
const HashTable<K, T, KeyOfT, Hash>* _pht;

函数名后的const只修饰this指针

在类中，const成员函数只能调用const成员函数，因为this指针存在

但可以调用非成员函数的非const函数（在保证不权限放大情况下）

源代码：

代码库链接：daily-practice-code: 存放日常练习的代码，包括网课内容练习，各种容器/算法模拟实现， I/O好题等

main.cpp

#include "unordered_map.h"
#include "unordered_set.h"
using namespace std;void test_hash_bucket()
{bit::HashTable<string, pair<string, string>> ss;ss.Insert(make_pair("1", "one"));ss.Insert(make_pair("2", "two"));ss.Insert(make_pair("3", "three"));ss.Insert(make_pair("4", "four"));ss.Insert(make_pair("5", "five"));ss.Insert(make_pair("6", "six"));ss.Insert(make_pair("7", "sevent"));ss.Insert(make_pair("8", "eight"));ss.Insert(make_pair("9", "nine"));ss.Insert(make_pair("10 ", "ten"));ss.Insert(make_pair("11", "eleven"));ss.Insert(make_pair("12", "twelve"));ss.Insert(make_pair("13", "thirteen"));bit::HashTable<string, pair<string, string>>::ConstIterator it = ss.cBegin();while (it != ss.cEnd()){cout << it->first << ":" << it->second << endl;++it;}cout << "hello unordered" << endl;
}void test_unordered_map()
{bit::unordered_map<string, string> ss;ss["1"] = "one";ss["2"] = "two";ss["3"] = "three";ss.insert(make_pair("4", "four"));ss.insert(make_pair("5", "five"));ss.insert(make_pair("6", "six"));ss.insert(make_pair("7", "seven"));bit::unordered_map<string, string>::iterator it = ss.begin();cout << "before erase:" << endl;for (const auto& e: ss){cout << e.first << ":" << e.second << endl;}cout << "fine(\" 2\")" << ":" << ss.find("2")->second << endl;it = ss.erase(it);cout << "after erase" << endl;while (it != ss.end()){cout << it->first << ":" << it->second << endl;++it;}cout << "ss.bucket_count() == " << ss.bucket_count() << endl;cout << "bucket_size(2) == " << ss.bucket_size("2") << endl;cout << "hello unordered_map" << endl;
}void test_unordered_set()
{bit::unordered_set<int> ss;ss.insert(1);ss.insert(2);ss.insert(3);ss.insert(4);ss.insert(5);ss.insert(6);ss.insert(7);ss.insert(8);ss.insert(9);ss.insert(10);ss.insert(11);bit::unordered_set<int>::iterator it = ss.begin();cout << "before erase:" << endl;for (const auto& e : ss){cout << e << endl;}cout << "fine(\" 2\")" << ":" << *(ss.find(2)) << endl;it = ss.erase(it);cout << "after erase begin" << endl;while (it != ss.end()){cout<<(*it)<< endl;++it;}cout << "ss.bucket_count() == " << ss.bucket_count() << endl;cout << "bucket_size(2) == " << ss.bucket_size(2) << endl;cout << "successful, unordered_set" << endl;
}int main()
{//test_hash_bucket();//test_unordered_map();test_unordered_set();return 0;
}

unordered_map.h

#include "hash_bucket.h"namespace bit
{// unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，HF哈希函数类型// unordered_map在实现时，只需将hashbucket中的接口重新封装即可template<class K, class V, class HF = HashFunc<K>>class unordered_map{// 通过key获取value的操作struct KeyOfValue{const K& operator()(const pair<K, V>& data){return data.first;}};typedef bit::HashTable<K, pair<K, V>, KeyOfValue, HF> HT;public:typedef typename HT::Iterator iterator;typedef typename HT::ConstIterator const_iterator;public:unordered_map() : _ht(){}iterator begin() { return _ht.Begin(); }iterator end() { return _ht.End(); }// capacitysize_t size()const { return _ht.size(); }bool empty()const { return _ht.empty(); }///// AcessV& operator[](const K& key){pair<iterator, bool> ret = _ht.InsertUnique(pair<K, V>(key, V()));return ret.first->second;}const V& operator[](const K& key)const{pair<iterator, bool> ret = _ht.InsertUnique(pair<K, V>(key, V()));return ret.fisrt->second;}//// lookupiterator find(const K& key) { return _ht.Find(key); }size_t count(const K& key) { return _ht.Count(key); }/// modifypair<iterator, bool> insert(const pair<K, V>& valye){return _ht.InsertUnique(valye);}iterator erase(iterator position){return _ht.Erase(position);}// bucketsize_t bucket_count() { return _ht.UnemptyBucketCount(); }size_t bucket_size(const K& key) { return _ht.BucketSize(key); }private:HT _ht;};
}

unoredered_set.h

#pragma once
#include "hash_bucket.h"namespace bit
{// unordered_set中存储的是K类型，HF哈希函数类型// unordered_set在实现时，只需将hashbucket中的接口重新封装即可template<class K, class HF = HashFunc<K>>class unordered_set{// 通过key获取value的操作struct KeyOfValue{const K& operator()(const K& data){return data;}};typedef bit::HashTable<K, K, KeyOfValue, HF> HT;public:typedef typename HT::Iterator iterator;typedef typename HT::ConstIterator const_iterator;public:unordered_set() : _ht(){}iterator begin() { return _ht.Begin(); }iterator end() { return _ht.End(); }// capacitysize_t size()const { return _ht.size(); }bool empty()const { return _ht.empty(); }///// lookupiterator find(const K& key) { return _ht.Find(key); }size_t count(const K& key) { return _ht.Count(key); }/// modifypair<iterator, bool> insert(const K& value){return _ht.InsertUnique(value);}iterator erase(iterator position){return _ht.Erase(position);}// bucketsize_t bucket_count() { return _ht.UnemptyBucketCount(); }size_t bucket_size(const K& key) { return _ht.BucketSize(key); }private:HT _ht;};
}

hash_bucket.h

#pragma once
#pragma once
#include <iostream>
#include <string>
#include <assert.h>
#include <vector>
using namespace std;template <class T, class K>//默认pair
struct KOT
{K operator()(const T& kv){return kv.first;}
};template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{size_t operator()(const string& key){return stoi(key);size_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};namespace bit
{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 Rfr, class KeyOfT, class Hash>class HTIterator{typedef HTIterator<K, T, Ptr, Rfr, KeyOfT, Hash> Self;public:HTIterator(HashNode<T>* p, const HashTable<K, T, KeyOfT, Hash>* pht):_ptr(p),_pht(pht){}Rfr operator*(){return _ptr->_data;}Self operator++(){decltype(_ptr) cur = _ptr->_next;if (cur)//cur不为空{_ptr = cur;return Self(_ptr, _pht);}//cur为空size_t int_key = hash(kot(_ptr->_data));int_key %= _pht->_tables.size();int_key++;while (int_key < _pht->_tables.size()){if (_pht->_tables[int_key])//不为空{_ptr = _pht->_tables[int_key];return Self(_ptr, _pht);}int_key++;}_ptr = nullptr;return Self(nullptr, _pht);}Ptr operator->(){return &(_ptr->_data);}bool operator==(const Self& other) const{return _ptr == other._ptr;}bool operator!=(const Self other) const{return _ptr != other._ptr;}private:HashNode<T>* _ptr = nullptr;const HashTable<K, T, KeyOfT, Hash>* _pht;Hash hash;KeyOfT kot;};// K 为 T 中key的类型// T 可能是键值对，也可能是K// KeyOfT: 从T中提取key// Hash将key转化为整形，因为哈市函数使用除留余数法template<class K, class T, class KeyOfT = KOT<T, K>, class Hash = HashFunc<K>>class HashTable{template<class K, class T,class Ptr, class Rfr, class KeyOfT, class Hash >friend class HTIterator;typedef HashNode<T> Node;public:typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;HashTable(){_tables.resize(10, nullptr);}// 哈希桶的销毁~HashTable(){for (auto e : _tables){while (e){auto next = e->_next;delete e;e = next;}}}// 插入值为data的元素，如果data存在则不插入bool Insert(const T& data){if (Find(kot(data))!= Iterator(nullptr, this)) return false;if (double(_n) / _tables.size() >= 1)//扩容{HashTable<K, T, KeyOfT, Hash> new_hash;new_hash._tables.resize(_tables.size() * 2);for (auto e : _tables){while (e){new_hash.Insert(e->_data);e = e->_next;}}_tables.swap(new_hash._tables);Insert(data);return true;}Node* ptr = new Node(data);int key = hash(kot(data));key %= _tables.size();ptr->_next = _tables[key];_tables[key] = ptr;_n++;return true;}pair<Iterator, bool> InsertUnique(const T& data){if (Find(kot(data)) != Iterator(nullptr, this)) return make_pair(Find(kot(data)),false);if (double(_n) / _tables.size() >= 1)//扩容{HashTable<K, T, KeyOfT, Hash> new_hash;new_hash._tables.resize(_tables.size() * 2);for (auto e : _tables){while (e){new_hash.Insert(e->_data);e = e->_next;}}_tables.swap(new_hash._tables);return make_pair(InsertUnique(data).first, true);}Node* ptr = new Node(data);int key = hash(kot(data));key %= _tables.size();ptr->_next = _tables[key];_tables[key] = ptr;_n++;return make_pair(Iterator(ptr, this), true);}// 在哈希桶中查找值为key的元素，存在返回true否则返回falseIterator Find(const K& key){int int_key = hash(key);int_key %= _tables.size();auto ptr = _tables[int_key];while (ptr){if (kot(ptr->_data) == key) return Iterator(ptr, this);ptr = ptr->_next;}return Iterator(nullptr, this);}// 哈希桶中删除key的元素，删除成功返回true，否则返回falsepair<Iterator, bool> Erase(const K& key){if (Find(key)== End()) return make_pair(Iterator(nullptr, this), false);//找不到key//存在keyint int_key = hash(key);int_key %= _tables.size();auto ptr = _tables[int_key];Node* prev = ptr;while (ptr){if (kot(ptr->_data) == key){//ptr为要删除结点if (prev == ptr)//ptr为头节点{_tables[int_key] = ptr->_next;}else prev->_next = ptr->_next;Iterator it(ptr, this);++it;delete ptr;_n--;return make_pair(it, true);}prev = ptr;ptr = ptr->_next;}//找不到删除节点return make_pair(Iterator(nullptr, this), false);}Iterator Erase(Iterator it){return Erase(kot(*it)).first;}size_t size() const{return size_t(_n);}bool empty() const{return _n == 0;}size_t Count(const K& key) {size_t ret = 0;Iterator it = Begin();while (it != End()){if (it->first == key){ret++;}++it;}return ret;}size_t TotalBucketCount(){return _tables.size();}size_t UnemptyBucketCount(){size_t ret = 0;for (const auto& e : _tables){if (e) ++ret;}return ret;}size_t BucketSize(const K& key){int int_key = hash(key);Node* cur = _tables[int_key];size_t ret = 0;while (cur){ret++;cur = cur->_next;}return ret;}Iterator Begin(){int cur = 0;while (cur < this->_tables.size()){if (_tables[cur]){return Iterator(_tables[cur], this);}cur++;}return End();}ConstIterator cBegin() const{int cur = 0;while (cur < this->_tables.size()){if (_tables[cur]){return ConstIterator(_tables[cur], this);}cur++;}return cEnd();}Iterator End(){return Iterator(nullptr, this);}ConstIterator cEnd() const{return ConstIterator(nullptr, this);}void Print(const string& str = ""){cout << str << endl;for (auto e : _tables){while (e){cout << e->_data.first << ":" << e->_data.second << endl;e = e->_next;}}}private:vector<Node*> _tables;  // 指针数组size_t _n = 0;			// 表中存储数据个数KeyOfT kot;Hash hash;};
}