In STL, the search of unordered_map and unordered_set is at the ceiling level. Their underlying logic is very simple, which is hash poke. The logic of hash poke is very simple, just different linked lists and arrays (in my opinion). But don’t insist on implementing unordered_map and unordered_set. It’s very simple. Just like cooking, each of us can make noodles, but the final feeling and taste when eaten in the mouth are different. There is a high probability that the chef will make them better than A novice cook can make delicious food, and unordered_map and unordered_set are just like cooking. It is not difficult to implement hashing, but it is really difficult to encapsulate the interface. Here is the code:
//unordered_map header file
#pragma once
#include"Hash.h"
namespace myunmap
{
template<class K,class V>
classmyunm
{
public:
struct map;
typedef Hash::HashNode<pair<K,V>> node;
typedef typename Hash::Iterator<K, pair<K,V>, map,pair<K,V> & amp;, pair<K,V>*, Hash::HashFunc<K>> iterator;
struct map
{
const K & amp; operator()(const pair<K,V> & amp; x)
{
return x.first;
}
};
pair<iterator,bool> insert(const pair<K, V> & amp; x)
{
return _Table.insert(x);
}
node* find(const K & x)
{
return _Table.find(x);
}
iterator begin()
{
return _Table.begin();
}
iterator end()
{
return _Table.end();
}
V & amp; operator[](const K & amp; data)
{
pair<iterator, bool> ret = _Table.insert(make_pair(data, V()));
return ret.first->second;
}
\t\t
private:
Hash::HashTable<K,pair<K,V>,map,Hash::HashFunc<K>> _Table;
};
}
//unordered_set header file
#pragma once
#include "Hash.h"
namespace myunset
{
template<class K>
class myset
{
public:
struct set;
typedef Hash::HashNode<K> node;
typedef typename Hash::Iterator<K, K, set, K &, K*, Hash::HashFunc<K>> iterator;
struct set
{
const K & amp; operator()(const K & amp; x)
{
return x;
}
};
pair<iterator,bool> insert(const K & amp; x)
{
return _Table.insert(x);
}
node* find(const K & x)
{
return _Table.find(x);
}
iterator begin()
{
return _Table.begin();
}
iterator end()
{
return _Table.end();
}
private:
Hash::HashTable<K,K,set,Hash::HashFunc<K>> _Table;
};
}
//Hash.h header file
#pragma once
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
using namespace std;
namespace Hash
{
template<class K>
struct HashFunc;
template<class T>
struct HashNode;
template<class K, class T, class KofT, class Hashf>
class HashTable;
template<class K ,class T,class KofT, class ref, class ptr,class Hashf = Hash::HashFunc<K>>
struct Iterator
{
typedef HashNode<T> node;
typedef HashTable<K, T, KofT, Hashf> HT;
node* ret;
HT* _ht;
Iterator(node* x,HT* ht)
:ret(x)
,_ht(ht)
{}
ref operator*()const
{
return ret->_data;
}
ptr operator->()const
{
return &ret->_data;
}
Iterator & operator + + ()
{
if (ret->_next)
ret = ret->_next;
else
{
KofT kot;
Hashf hsf;
size_t pp = hsf(kot(ret->_data)) % _ht->_table.size();
for (size_t i = pp + 1; i < _ht->_table.size(); i + + )
{
if (_ht->_table[i])
{
ret = _ht->_table[i];
return *this;
}
}
ret = nullptr;
}
return *this;
}
bool operator!=(const Iterator<K, T, KofT, ref, ptr, Hashf> & amp; x)const
{
return ret != x.ret;
}
};
template<class K>
struct HashFunc
{
const K & amp; operator()(const K & amp; key)
{
return key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string & amp; key)
{
size_t val = 0;
for (auto e : key)
{
val + = e;
val *= 131;
}
return val;
}
};
template<class T>
struct HashNode
{
T_data;
HashNode<T>* _next;
HashNode(const T & val)
:_data(val)
,_next(nullptr)
{}
};
template<class K ,class T , class KofT , class Hashf = Hash::HashFunc<K>>
classHashTable
{
typedef HashNode<T> node;
template<class K, class T, class KofT, class ref, class ptr, class Hashf>
friend struct Iterator;
typedef Iterator<K, T, KofT,T & amp;,T*,Hashf> iterator;
public:
HashTable()
{
_table.resize(3);
}
iterator begin()
{
for (size_t i = 0; i < _table.size(); i + + )
{
node* cur = _table[i];
if (cur)
return iterator(cur, this);
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
pair<iterator,bool> insert(const T & amp; x)
{
//remove duplication
if (find(_kot(x)))
return make_pair(iterator(find(_kot(x)),this), false);
if (_size != 0 & amp; & amp; _size / _table.size() == 1)
{
vector<node*> tmp;
tmp.resize(2 * _table.size(), nullptr);
for (size_t i = 0; i < _table.size(); i + + )
{
if (_table[i])
{
node* cur = _table[i];
while (cur)
{
node* next = cur->_next;
size_t ret = hsf(_kot(cur->_data))% tmp.size();
cur->_next = tmp[ret];
tmp[ret] = cur;
cur = next;
}
}
}
_table.swap(tmp);
}
int ret = hsf(_kot(x)) % _table.size();
node* cur = new node(x);
cur->_next = _table[ret];
_table[ret] = cur;
_size + + ;
return make_pair(iterator(cur, this), true);
}
node* find(const K & amp; key)
{
if (_table.size() == 0)
return nullptr;
size_t ret = hsf(key) % _table.size();
if (_table[ret])
{
node* cur = _table[ret];
while (cur)
{
if (_kot(cur->_data) == key)
return cur;
cur = cur->_next;
}
}
return nullptr;
}
private:
vector<node*> _table;
size_t _size = 0;
KofT_kot;
Hashf hsf;
};
}
//Test code
#include"Hash.h"
#include"unordered_map.h"
#include"unordered_set.h"
int main()
{
/*Hash::HashTable<int> s;
s.insert(1);
s.insert(1);
s.insert(1);
s.insert(1);*/
myunmap::myunm<int, int> s;
vector<int> v = { 1,1,1,1,1,1,1,1 };
//myunmap::myunm<int, int>::iterator sit = s.begin();
for (auto e : v)
{
s[e] + + ;
}
for (auto & e : s)
cout << e.first << endl;
/*myunset::myset<int> h;
h.insert(1);
h.insert(2);
h.insert(3);
h.insert(4);
h.insert(5);
h.insert(6);
h.insert(7);
myunset::myset<int>::iterator sit = h.begin();
while (sit != h.end())
{
cout << (*sit) << endl;
+ + sit;
}*/
return 0;
}
How can I put it this way? It took about an hour to implement hashing and about three hours to encapsulate the interface. How can I say that the process of encapsulating the code was uncomfortable. In fact, when encapsulating other things, I felt that it was okay, but When it comes to the iterator, it really feels confusing. Why is it said to be very confusing? In fact, it is also my fault that I wrote it at the very beginning, so I declared all the classes below. So it looks messy. Okay, let’s talk about how to achieve it.
I won’t talk about other parts, mainly the iterator.
The template of the iterator passes parameters. What I just wrote was K, K &, K*. But you will find a problem when writing this way, that is, there is no hash pointer, and to implement an iterator, the hash pointer is essential, so this is very contradictory. So you cannot set parameters like this. Because the hash pointer is used, the four template parameters of the hash point cannot be missing. In fact, if there is nothing, it can be implemented. But I added two more parameters, namely ref and ptr. This can be more convenient. Well, after the hash pointer problem is solved, it is equivalent to solving the complex problems in iterators. But the next question comes again, that is, what to do with operator[]? The parameter of this overloaded function should be K, but if you want to insert, the insertion of unordered_map is a pair. Therefore, at this time, you must call the insertion in the Hash file in the unordered_map file and pass it on.
The above are the two difficulties. Although it sounds simple, I think it is still a bit difficult to implement it by yourself. Implementing encapsulation is much more difficult than implementing hashing, especially the process of passing it down, which is particularly convoluted. I personally think that the encapsulation of map and set is simpler than unordered_map and unordered_set. Mainly unordered_map and unordered_set need to be mapped using hash functions, so they must support remainder, but what if it is a string? If it’s string, then you don’t have to implement it yourself? So a functor is needed at this time. Map and set are not needed. For red-black trees, I only need to know whether you are a pair or a K. So just one functor is enough.
Finally, I hope you all can support me! !