C++ 模拟实现unordered_mapset

2024-03-01 05:12
文章标签 c++ 实现 模拟 unordered mapset

本文主要是介绍C++ 模拟实现unordered_mapset，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、原始哈希表 

二、改造哈希表 

1、模版特化 

2、适配数据类型

3、迭代器

4、哈希表引入迭代器

5、修改find函数 

6、修改insert函数 

三、set

隐式类型转换

四、map

完整版代码

哈希表

unordered_map

unordered_set 

一、原始哈希表 

原始哈希表代码如下：（使用拉链法）

namespace HashBucket1
{template<class K,class V>struct HashNode{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K,V>& kv):_next(nullptr),_kv(kv){}};template<class K>struct HashFunc{size_t operator()(const K& key){return key;}};template<>struct HashFunc<string>{//BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};template<class K,class V,class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;private:vector<Node*> _tables;size_t _n = 0;public:~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}Node* Find(const K& key){if (_tables.size() == 0)return nullptr;Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hash;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if(prev==nullptr)_tables[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;return true;}else {prev = cur;cur = cur->_next;}}return false;}// size_t newsize = GetNextPrime(_tables.size());size_t GetNextPrime(size_t prime){// SGIstatic const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kv.first) % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i < _tables.size(); i++){auto cur = _tables[i];size_t size = 0;while (cur){size++;cur = cur->_next;}if (size > max)max = size;}return max;}};
}

二、改造哈希表 

接下来，我们对哈希表代码进行改造。

1、模版特化 

模版的特化我们选择移动到命名空间外部， 方便后续调用。

template<class K>
struct HashFunc
{size_t operator()(const K& key){return key;}
};template<>
struct HashFunc<string>
{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};namespace HashBucket
{、、、、};
}

2、适配数据类型

由于unordered_map&set存储的数据类型不同，所以我们将数据类型的选择权交给unordered_map&set本身。

由此新增了template<class T>和template<class KeyOfT>，它们都是模板参数声明。它们声明了一个模板参数，第一个参数是一个类型，第二个参数是一个函数对象。

我们需要将节点结构体RBTreeNode中的数据成员_data的类型改为模板参数T。这样，每个节点就可以存储不同类型的数据，以适应map的节点存储pair结构、set的节点存储key。

namespace HashBucket
{template<class T>struct HashNode{HashNode<T>* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};
}

模板参数 KeyOfT 在 unordered_map 和 unordered_set 中被用作一个函数对象（仿函数），用于从存储的数据类型中提取键。通过提供一个自定义的函数对象类型，你可以指定如何从数据类型中提取键，以便在哈希表中进行存储和查找。

`KeyOfT`是一个辅助类也叫作仿函数，用于从值中提取键。在`set`中，键和值的类型相同，因此`KeyOfT`可以直接使用template<class K>。而在`map`中，键和值的类型不同，因此我们对于相应的仿函数做出针对性设计。

对于`map`类，我们需要将`KeyOfT`修改为适应`pair<const K, V>`类型的辅助类。我们可以定义一个新的辅助类（仿函数）`MapKeyOfT`，其内部使用重载了函数调用运算符 operator()，这个辅助类的作用是从`pair<const K, V>`类型的值中提取出键`K`，即仿函数返回值为 kv.first。同时，我们将`RBTree`的第三个模板参数修改为`MapKeyOfT`。

#pragma once#include "HashTable.h"namespace bit
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};private:HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};

 对于`set`类，我们需要将`KeyOfT`修改为配合map使用的辅助类。我们可以定义一个仿函数`SetKeyOfT`， 通过重载operator()直接返回key。同时，我们将第三个模板参数修改为’SetKeyOfT'。

#pragma once#include "HashTable.h"namespace bit
{template<class K, class Hash = HashFunc<K>>class unordered_set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};private:HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;};
}

接着修改哈希表中的插入函数，定义KeyOfT kot;，通过kot获取节点元素的键 kot(cur->_data)。

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{typedef HashNode<T> Node;public:bool Insert(const T& data){KeyOfT kot;if (Find(kv.first)){return false;}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newtables.size();// 头插到新表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);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};
}

3、迭代器

namespace HashBucket
{// 前置声明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;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;Node* _node;const HT* _ht;__HashIterator(Node* node, const 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){return _node != s._node;}Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else{// 找下一个不为空的桶KeyOfT kot;Hash hash;// 算出我当前的桶位置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{++hashi;}}// 没有找到不为空的桶if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};
}

前置声明：
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable;

  • 前置声明：前置声明是一种声明方式，它允许我们在一个类、函数或者变量的定义实际出现之前就声明它。这在处理循环依赖或者提高编译速度的时候非常有用。例如，在这个代码中，HashTable 类在 __HashIterator 类之前被前置声明了，这样 __HashIterator 类就可以在 HashTable 类的定义出现之前就使用它。

 _HashIterator是一个模板结构体，它是一个迭代器，用于遍历哈希表中的元素。它的模板参数包括：

  • K：键的类型。
  • T：值的类型。
  • Ref：引用类型，通常为T&或const T&。
  • Ptr：指针类型，通常为T*或const T*。
  • KeyOfT：一个函数对象，用于从值中获取键。
  • Hash：一个函数对象，用于计算键的哈希值。

_HashIterator包含以下成员：

  • Node* _node;：这是一个指向当前迭代器所指向的节点的指针。节点的类型为HashNode<T>，其中T是模板参数。
  • const HT* _ht;：这是一个指向哈希表的指针。哈希表的类型为HashTable<K, T, KeyOfT, Hash>，其中K、T、KeyOfT和Hash都是模板参数。

  • 在这个设计中，_node 和 _ht 都被设计为指针类型，主要有以下几个原因：

    • 动态内存管理：使用指针可以动态地创建和销毁对象，这对于管理大量数据和实现复杂的数据结构（如链表、树、图等）非常有用。

    • 节省内存：如果 _node 和 _ht 是对象而不是指针，那么每个迭代器对象都会包含完整的 Node 和 HashTable 对象，这可能会消耗大量的内存。而使用指针，迭代器只需要存储对象的地址，这样可以大大节省内存。

    • 灵活性：指针可以被重新赋值，指向其他对象。这在实现一些复杂的操作（如迭代器的移动、复制等）时非常有用。

    • 访问原对象：在迭代器中，我们需要访问原 HashTable 对象和 Node 对象。通过指针，我们可以直接访问和操作原对象，而不是它们的副本。

_HashIterator还包含以下成员函数：

  • __HashIterator(Node* node, const HT* ht)：这是一个构造函数，用于初始化迭代器。它接受一个节点指针和一个哈希表指针作为参数。
  • __HashIterator(const Iterator& it)：这是一个拷贝构造函数，用于创建一个新的迭代器，它和参数it指向同一个节点。
  • Ref operator*()：这是一个解引用操作符，它返回当前迭代器所指向的节点的数据。返回类型为Ref，即模板参数中的引用类型。
  • Ptr operator->()：这是一个箭头操作符，它返回一个指向当前迭代器所指向的节点的数据的指针。返回类型为Ptr，即模板参数中的指针类型。
  • bool operator!=(const Self& s)：这是一个不等于操作符，它比较两个迭代器是否不相等。如果两个迭代器指向不同的节点，那么它们就不相等。
  • Self& operator++()：这是一个前置递增操作符，它将迭代器移动到下一个节点。如果当前节点的下一个节点为空，那么它将查找下一个非空的桶。

4、哈希表引入迭代器

namespace HashBucket
{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;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;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return iterator(cur, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end() const{return const_iterator(nullptr, this);}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};
}

在HashTable类中，迭代器的实现主要依赖于__HashIterator模板类。这个类接受6个模板参数，分别是K、T、Ref、Ptr、KeyOfT和Hash。

  • K：键的类型。
  • T：值的类型。
  • Ref：引用类型，通常为T&或const T&。
  • Ptr：指针类型，通常为T*或const T*。
  • KeyOfT：一个函数对象，用于从T类型的对象中提取键。
  • Hash：一个函数对象，用于计算键的哈希值。

友元：友元是 C++ 中的一个特性，它允许一个类或者函数访问另一个类的私有或者保护成员。

  • 在这个代码中，__HashIterator 类被声明为 HashTable 类的友元，这样 __HashIterator 就可以访问 HashTable 的私有成员 _tables 和 _n。这在实现一些需要访问私有成员的复杂操作时非常有用。例如，迭代器需要访问和操作容器的内部数据结构，所以通常会被声明为容器类的友元。

__HashIterator类中定义了一些基本的迭代器操作，包括解引用(operator*和operator->)和递增(operator++)。这些操作使得__HashIterator可以像普通的指针一样使用。

在HashTable类中，begin()和end()函数返回的是iterator类型的对象，这个类型实际上就是__HashIterator<K, T, T&, T*, KeyOfT, Hash>。这两个函数分别返回指向哈希表中第一个元素和最后一个元素之后位置的迭代器。

HashTable类还提供了const_iterator类型，这个类型实际上就是__HashIterator<K, T, const T&, const T*, KeyOfT, Hash>。const_iterator和iterator的区别在于，通过const_iterator不能修改它所指向的元素。

5、修改find函数 

HashTable类的Find函数返回一个iterator，表示找到的元素的位置。如果没有找到元素，就返回end()。

iterator Find(const K& key)
{if (_tables.size() == 0)return end();KeyOfT kot;Hash hash;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();
}

6、修改insert函数 

HashTable类的Insert函数返回一个pair，其中第一个元素是一个iterator，表示插入的元素的位置，第二个元素是一个bool，表示是否插入成功。

pair<iterator, bool> Insert(const T& data)
{KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newtables.size();// 头插到新表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);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), false);;
}

三、set

#pragma once#include "HashTable.h"namespace bit
{template<class K, class Hash = HashFunc<K>>class unordered_set{public:struct SetKeyOfT{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(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;};
}

unordered_set类的私有成员变量_ht是一个HashTable<K, K, SetKeyOfT, Hash>类型的对象，它是unordered_set的底层实现。 

在这段代码中，unordered_set是一个模板类，它接受两个模板参数：

  • K：元素的类型。
  • Hash：一个函数对象，用于计算元素的哈希值。默认值是HashFunc<K>。

unordered_set类中定义了一个内部的函数对象SetKeyOfT，它的作用是从元素中提取键。因为在unordered_set中，元素就是键，所以SetKeyOfT直接返回元素本身。

unordered_set类中还定义了两种迭代器类型：iterator和const_iterator。这两种迭代器都是HashTable<K, K, SetKeyOfT, Hash>::const_iterator类型的别名，表示指向元素的常量迭代器。

unordered_set类提供了一些基本的集合操作，包括：

  • begin()和end()：返回指向集合中第一个元素和最后一个元素之后位置的迭代器。
  • insert(const K& key)：插入一个元素，并返回一个pair，其中第一个元素是一个迭代器，表示插入的元素的位置，第二个元素是一个bool，表示是否插入成功。
  • find(const K& key)：查找一个元素，并返回一个迭代器，表示找到的元素的位置。如果没有找到元素，就返回end()。
  • erase(const K& key)：删除一个元素，并返回一个bool，表示是否删除成功。

隐式类型转换

class unordered_set
{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();}
}

 在这个代码中，`HashTable`的`begin()`函数返回的是一个非const迭代器，但在`unordered_set`中，`begin()`函数返回的是一个const迭代器。这是因为在`unordered_set`中，元素的值是不可变的，所以需要返回一个const迭代器来保证元素的值不会被修改。

这里的隐式类型转换是通过`__HashIterator`的构造函数实现的，单参数的构造函数支持隐式类型转换。`__HashIterator`有一个构造函数，它接受一个非const迭代器并将其转换为const迭代器：

struct __HashIterator
{typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;__HashIterator(const Iterator& it):_node(it._node), _ht(it._ht){}
}

当`_ht.begin()`返回一个非const迭代器时，这个迭代器会被传递给`__HashIterator`的这个构造函数，然后构造函数会返回一个新的const迭代器。这就是`_ht.begin()`如何进行隐式类型转换为const迭代器的。

四、map

#pragma once#include "HashTable.h"namespace testH
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{public:struct MapKeyOfT{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>::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 pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};
}

在这段代码中，unordered_map是一个模板类，它接受三个模板参数：

  • K：键的类型。
  • V：值的类型。
  • Hash：一个函数对象，用于计算键的哈希值。默认值是HashFunc<K>。

unordered_map类中定义了一个内部的函数对象MapKeyOfT，它的作用是从键值对中提取键。

unordered_map类中还定义了两种迭代器类型：iterator和const_iterator。这两种迭代器都是HashTable<K, pair<const K, V>, MapKeyOfT, Hash>的迭代器类型的别名。

unordered_map类提供了一些基本的映射操作，包括：

  • begin()和end()：返回指向映射中第一个元素和最后一个元素之后位置的迭代器。
  • insert(const pair<K, V>& kv)：插入一个键值对，并返回一个pair，其中第一个元素是一个迭代器，表示插入的元素的位置，第二个元素是一个bool，表示是否插入成功。
  • operator[](const K& key)：返回与给定键关联的值。如果映射中不存在这个键，就插入一个与这个键关联的默认值。
  • find(const K& key)：查找一个键，并返回一个迭代器，表示找到的元素的位置。如果没有找到元素，就返回end()。
  • erase(const K& key)：删除一个键值对，并返回一个bool，表示是否删除成功。

unordered_map类的私有成员变量_ht是一个HashTable<K, pair<const K, V>, MapKeyOfT, Hash>类型的对象，它是unordered_map的底层实现。

完整版代码

哈希表

template<class K>
struct HashFunc
{size_t operator()(const K& key){return key;}
};// 特化
template<>
struct HashFunc<string>
{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 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;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;Node* _node;const HT* _ht;__HashIterator(Node* node, const 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){return _node != s._node;}Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else{// 找下一个不为空的桶KeyOfT kot;Hash hash;// 算出我当前的桶位置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{++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;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;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return iterator(cur, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end() const{return const_iterator(nullptr, this);}~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}iterator Find(const K& key){if (_tables.size() == 0)return end();KeyOfT kot;Hash hash;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;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}// size_t newsize = GetNextPrime(_tables.size());size_t GetNextPrime(size_t prime){// SGIstatic const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];}pair<iterator, bool> Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newtables.size();// 头插到新表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);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), false);;}size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i < _tables.size(); ++i){auto cur = _tables[i];size_t size = 0;while (cur){++size;cur = cur->_next;}//printf("[%d]->%d\n", i, size);if (size > max){max = size;}}return max;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};
}

unordered_map

#pragma once#include "HashTable.h"namespace testH
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{public:struct MapKeyOfT{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>::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 pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_unordered_map1(){unordered_map<int, int> m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));unordered_map<int, int>::iterator it = m.begin();while (it != m.end()){//it->first = 1;//it->second = 1;cout << it->first << ":" << it->second << endl;++it;}cout << endl;}void test_unordered_map2(){string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}class Date{friend struct HashDate;public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}bool operator==(const Date& d) const{return _year == d._year&& _month == d._month && _day == d._day;}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}struct HashDate{size_t operator()(const Date& d){size_t hash = 0;hash += d._year;hash *= 31;hash += d._month;hash *= 31;hash += d._day;hash *= 31;return hash;}};// 一个类型要做unordered_map/unordered_set的key，要满足支持转换成取模的整形 和 ==比较// 一个类型要做map/set的key，要满足支持<比较/*if (cur->key < key){}else if (key < cur->key){}else{}*/void test_unordered_map4(){Date d1(2023, 3, 13);Date d2(2023, 3, 13);Date d3(2023, 3, 12);Date d4(2023, 3, 11);Date d5(2023, 3, 12);Date d6(2023, 3, 13);Date a[] = { d1, d2, d3, d4, d5, d6};unordered_map<Date, int, HashDate> countMap;for (auto e : a){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}
}

unordered_set 

#pragma once#include "HashTable.h"namespace testH
{template<class K, class Hash = HashFunc<K>>class unordered_set{public:struct SetKeyOfT{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(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;};void print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;}void test_unordered_set1(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };unordered_set<int> s;for (auto e : a){s.insert(e);}s.insert(54);s.insert(107);unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;print(s);}
}

这篇关于C++ 模拟实现unordered_mapset的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/761315。

相关文章

windos server2022里的DFS配置的实现

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS？优势：应用场景：DFS配置步骤什么是DFS？DFS指的是分布式文件系统（Distr
阅读更多...
NFS实现多服务器文件的共享的方法步骤

NFS实现多服务器文件的共享的方法步骤

《NFS实现多服务器文件的共享的方法步骤》NFS允许网络中的计算机之间共享资源,客户端可以透明地读写远端NFS服务器上的文件,本文就来介绍一下NFS实现多服务器文件的共享的方法步骤,感兴趣的可以了解一... 目录一、简介二、部署1、准备1、服务端和客户端：安装nfs-utils2、服务端：创建共享目录3、服
阅读更多...
C#使用yield关键字实现提升迭代性能与效率

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭
阅读更多...
Python实现高效地读写大型文件

Python实现高效地读写大型文件

《Python实现高效地读写大型文件》Python如何读写的是大型文件,有没有什么方法来提高效率呢,这篇文章就来和大家聊聊如何在Python中高效地读写大型文件,需要的可以了解下... 目录一、逐行读取大型文件二、分块读取大型文件三、使用 mmap 模块进行内存映射文件操作（适用于大文件）四、使用 pand
阅读更多...
python实现pdf转word和excel的示例代码

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1，PDF转Word2，PDF转Excel三、前端页面效果展示总结一
阅读更多...
Python xmltodict实现简化XML数据处理

Python xmltodict实现简化XML数据处理

《Pythonxmltodict实现简化XML数据处理》Python社区为提供了xmltodict库,它专为简化XML与Python数据结构的转换而设计,本文主要来为大家介绍一下如何使用xmltod... 目录一、引言二、XMLtodict介绍设计理念适用场景三、功能参数与属性1、parse函数2、unpa
阅读更多...
C#实现获得某个枚举的所有名称

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi
阅读更多...
Go语言实现将中文转化为拼音功能

Go语言实现将中文转化为拼音功能

《Go语言实现将中文转化为拼音功能》这篇文章主要为大家详细介绍了Go语言中如何实现将中文转化为拼音功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 有这么一个需求：新用户入职 创建一系列账号比较麻烦，打算通过接口传入姓名进行初始化。想把姓名转化成拼音。因为有些账号即需要中文也需要英
阅读更多...
C# 读写ini文件操作实现

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中，常将INI文件作为配置文件，用于存储应用程序的
阅读更多...
C#实现获取电脑中的端口号和硬件信息

C#实现获取电脑中的端口号和硬件信息

《C#实现获取电脑中的端口号和硬件信息》这篇文章主要为大家详细介绍了C#实现获取电脑中的端口号和硬件信息的相关方法,文中的示例代码讲解详细,有需要的小伙伴可以参考一下... 我们经常在使用一个串口软件的时候，发现软件中的端口号并不是普通的COM1，而是带有硬件信息的。那么如果我们使用C#编写软件时候，如
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2