[C++ unordered_set, unordered_map]

Directory

• 1. Hash
• • 1.1 Hash–open hashing
  • 1.2 Hash–Closed Hash
  • 1.3 Hash optimization
• 2. unordered_set, unordered_map
• • 2.1 Framework construction of unordered_set and unordered_map
  • 2.2 Iterators of unordered_set and unordered_map
  • • 2.2.1 Construction of ordinary iterators
    • 2.2.2 Encapsulation of ordinary iterators
    • 2.2.3 Unordered_set encapsulation of ordinary iterators
    • 2.2.4 Unordered_map encapsulation of ordinary iterators
  • 2.3 The Keys of unordered_set and unordered_map cannot be modified.
  • • 2.3.1Construction of const iterator
    • 2.3.2 Encapsulation of const iterator
    • 2.3.3 Encapsulation of const iterator of unordered_set
    • 2.3.4 Encapsulation of const iterator of unordered_map
  • 2.4 unordered_map’s [] overload

1. Hash

The idea of hashing is to establish a relationship between the stored data and the storage location, so that the element to be searched can be obtained directly from the table at one time without any comparison. Greatly improve the efficiency of search. The general idea is as follows:

Hash collision:
The above picture is just an ideal situation, in fact the following situation may occur. As shown in the picture:

In order to solve hash conflicts, many big guys have thought of many ways to solve hash conflicts. Below are two of the most commonly used methods to resolve hash conflicts:
Open hashing and closed hashing.

1.1 Hash – Open Hash

Code implementation:

#include<iostream>
using namespace std;
#include<vector>
//open address
namespace open_address
{<!-- -->
enum STATE
{<!-- -->
EXIST,
EMPTY,
DELETE
};

template<class K,class V>
struct HashDate
{<!-- -->
pair<K, V> _kv;
STATE _st=EMPTY;
};

template<class K,class V>
classHashTable
{<!-- -->
public:
HashTable()
{<!-- -->
_ht.resize(10);
}

bool insert(const pair<K, V> & amp; kv)
{<!-- -->
if (find(kv.first))
{<!-- -->
return false;
}

//Expansion with load factor greater than 0.7
if (_n * 10 / _ht.size() >= 7)
{<!-- -->
HashTable<K, V> newtable;
newtable._ht.resize(_ht.size() * 2);

for (size_t i = 0; i < _ht.size(); i + + )
{<!-- -->
newtable.insert(_ht[i]._kv);
}

_ht.swap(newtable._ht);
}

size_t hashi = kv.first % _ht.size();
while (_ht[hashi]._st == EXIST)
{<!-- -->
hashi + + ;
hashi %= _ht.size();
}

_ht[hashi]._kv = kv;
_ht[hashi]._st = EXIST;
_n + + ;

return true;
}

HashDate<const K,V>* find(const K & amp; key)
{<!-- -->
size_t hashi = key % _ht.size();
while (_ht[hashi]._st != EMPTY)
{<!-- -->
if (_ht[hashi]._kv.first == key)
{<!-- -->
return (HashDate<const K, V>*) & amp; _ht[hashi];
}
hashi + + ;
}
return nullptr;
}

bool erase(const K & amp; key)
{<!-- -->
HashDate<const K, V>* ret = find(key);
if (ret)
{<!-- -->
ret->_st = DELETE;
--_n;

return true;
}


return false;
}

private:
vector<HashDate<K,V>> _ht;
size_t _n = 0;//How many data are there
};
}

The above code does not process the string type, and will be optimized below

1.2 Hashing – Closed Hashing

Code implementation:

namespace hash_bucket
{<!-- -->
template<class K,class V>
struct HashNode
{<!-- -->
HashNode(const pair<K, V> & amp; kv)
:_kv(kv)
{<!-- -->}

pair<K, V> _kv;
HashNode<K, V>* _next=nullptr;
};

template<class K,class V>
classHashTable
{<!-- -->
typedef HashNode<K, V> Node;
public:
HashTable()
{<!-- -->
_ht.resize(10, nullptr);
}

bool insert(const pair<K, V> & amp; kv)
{<!-- -->
//Expand the capacity when the load factor reaches 1
if (_n == _ht.size())
{<!-- -->
size_t newsize = _ht.size() * 2;
HashTable<K, V> newtable;
newtable._ht.resize(newsize);

for (size_t i = 0; i < _ht.size(); i + + )
{<!-- -->
Node* cur = _ht[i];
while (cur)
{<!-- -->
Node* next = cur->_next;
size_t hashi = cur->_kv.first % newsize;

//cur header inserts into the new linked list
cur->_next = newtable._ht[hashi];
newtable._ht[hashi] = cur;

cur = next;
}
}
_ht.swap(newtable._ht);
}


size_t hashi = kv.first % _ht.size();
Node* newnode = new Node(kv);

newnode->_next = _ht[hashi];
_ht[hashi] = newnode;

+ + _n;
return true;
}

Node* find(const K & amp; key)
{<!-- -->
size_t hashi = key % _ht.size();
Node* cur = _ht[hashi];
while (cur)
{<!-- -->
if (cur->_kv.first == key)
{<!-- -->
return cur;
}
cur = cur->_next;
}
return nullptr;
}

bool erase(const K & amp; key)
{<!-- -->
Node* pre = nullptr;
if (find(key) == nullptr)
{<!-- -->
return false;
}

size_t hashi = key % _ht.size();
Node* cur = _ht[hashi];
while (cur)
{<!-- -->
if (cur->_kv.first == key)
{<!-- -->
if (pre == nullptr)
{<!-- -->
//Delete header
delete cur;
_ht[hashi] = nullptr;
}
else
{<!-- -->
Node* next = cur->_next;
pre->_next = next;
delete cur;
}
return true;
}
pre = cur;
cur = cur->_next;
}
\t\t\t
}

void Print()
{<!-- -->
for (size_t i = 0; i < _ht.size(); i + + )
{<!-- -->
cout << "[" << i << "]"<< "->";
Node* cur = _ht[i];
while (cur)
{<!-- -->
cout << cur->_kv.first<<"->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}

private:
vector<Node*> _ht;
size_t_n;
};
}

The above code does not process the string type, and will be optimized below

1.3 Hash optimization

None of the above codes can realize the search for strings, but in many cases in real life, string searches are performed. So this problem needs to be solved below.
Just add a HashFunc to the template parameter.

template<class K>
struct DefaultHashFunc
{<!-- -->
//Prevent negative numbers from taking modulo
size_t operator()(const K & amp; key)
{<!-- -->
return (size_t)key;
}
};

//template specialization
template<>
struct DefaultHashFunc<string>
{<!-- -->
//For string
size_t operator()(const string & amp; str)
{<!-- -->
size_t ret = 0;
for (auto ch : str)
{<!-- -->
ret *= 131;
ret + = ch;
}
return ret;
}
};

2. unordered_set, unordered_map

Note: The bottom layers of unordered_set and unordered_map below all use the hash_bucket above.

2.1 Framework construction of unordered_set and unordered_map

The first problem to be solved first is the problem of key and Val. Because unordered_set has only one template parameter, while unordered_map has two. Therefore, the hash bucket needs to be modified. The K,V form cannot be used, but the K,T form must be used. When T is passed as K, it is unordered_set, and when T is passed as pair, it is unordered_map. For this purpose, you need to write a functor for KeyOfT.

unordered_set.h code

#pragma once
#include"hashtable.h"

namespace Ting
{<!-- -->
template<class K>
class unordered_set
{<!-- -->
public:
struct SetKeyOfT
{<!-- -->
const K & amp; operator()(const K & amp; key)
{<!-- -->
return key;
}
};

bool insert(const K & amp; key)
{<!-- -->
return _ht.insert(key);
}

void Print()
{<!-- -->
_ht.Print();
}
private:
hash_bucket::HashTable<K, K,SetKeyOfT> _ht;
};
}

unordered_map.h code

#pragma once
#include"hashtable.h"

namespace Ting
{<!-- -->
template<class K,class V>
class unordered_map
{<!-- -->
public:
struct MapKeyOfT
{<!-- -->
const K & amp; operator()(const pair<K,V> & amp; kv)
{<!-- -->
return kv.first;
}
};

bool insert(const pair<K, V> & amp; kv)
{<!-- -->
return _ht.insert(kv);
}

void Print()
{<!-- -->
_ht.Print();
}
private:
hash_bucket::HashTable<K, pair<K,V>, MapKeyOfT> _ht;
};
}

2.2 Iterators of unordered_set and unordered_map

2.2.1 Construction of ordinary iterator

According to the normal writing method, we find that we can no longer write at this point. As shown in the picture:

It’s best to pass a hashtable pointer, so you can play like this.

template<class K, class T, class KeyOfT, class HashFunc>
struct HashIterator
{<!-- -->
typedef HashNode<T> Node;
typedef HashIterator<K,T,KeyOfT,HashFunc> Self;
typedef HashTable<K, T, KeyOfT, HashFunc> HashTable;

HashIterator(Node* node, HashTable* hptr)
:_node(node)
, _hptr(hptr)
{<!-- -->}

Self operator + + ()
{<!-- -->
if (_node->_next)
{<!-- -->
_node = _node->_next;
}
else
{<!-- -->
//It’s hard to write the following
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(kot(_node->_date)) % _hptr->_ht.size();
hashi + + ;

while (hashi < _hptr->_ht.size() & amp; & amp; _hptr->_ht[hashi] == nullptr)
{<!-- -->
+ + hashi;
}
if (hashi == _hptr->_ht.size())
{<!-- -->
_node = nullptr;
}
else
{<!-- -->
_node = _hptr->_ht[hashi];
}
}
return *this;
}

T* operator->()
{<!-- -->
return &(_node->_date);
}

T & operator*()
{<!-- -->
return _node->_date;
}

bool operator!=(Node* node)
{<!-- -->
return _node != node;
}

Node* _node;
HashTable* _hptr;
};

But writing this way will fail the compilation. The reason is that we passed a HashTable pointer, and the compiler compiles from top to bottom when compiling. The compiler does not know what a Hashtable is, so it must be declared in advance.

2.2.2 Encapsulation of ordinary iterators

template<class K,class T,class KeyOfT,class HashFunc=DefaultHashFunc<K>>
classHashTable
{<!-- -->
typedef HashNode<T> Node;
public:
typedef HashIterator<K, T, KeyOfT, HashFunc> iterator;

iterator begin()
{<!-- -->
size_t i = 0;
while (i < _ht.size() & amp; & amp; _ht[i] == nullptr)
{<!-- -->
+ + i;
}
if (i == _ht.size())
{<!-- -->
return iterator(nullptr, this);
}
return iterator(_ht[i], this);
}

iterator end()
{<!-- -->
return iterator(nullptr, this);
}


HashTable()
{<!-- -->
_ht.resize(10, nullptr);
}

bool insert(const T & date)
{<!-- -->
HashFunc hf;
KeyOfT kot;
if (find(kot(date)))
{<!-- -->
return false;
}

//Expand the capacity when the load factor reaches 1
if (_n == _ht.size())
{<!-- -->
size_t newsize = _ht.size() * 2;
HashTable<K,T,KeyOfT,HashFunc> newtable;
newtable._ht.resize(newsize);

for (size_t i = 0; i < _ht.size(); i + + )
{<!-- -->
Node* cur = _ht[i];
while (cur)
{<!-- -->
Node* next = cur->_next;
size_t hashi = hf(kot(cur->_date)) % newsize;

//cur header inserts into the new linked list
cur->_next = newtable._ht[hashi];
newtable._ht[hashi] = cur;

cur = next;
}
}
_ht.swap(newtable._ht);
}


size_t hashi = hf(kot(date)) % _ht.size();
Node* newnode = new Node(date);

newnode->_next = _ht[hashi];
_ht[hashi] = newnode;

+ + _n;
return true;
}

Node* find(const K & amp; key)
{<!-- -->
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _ht.size();
Node* cur = _ht[hashi];
while (cur)
{<!-- -->
if (kot(cur->_date) == key)
{<!-- -->
return cur;
}
cur = cur->_next;
}
return nullptr;
}

bool erase(const K & amp; key)
{<!-- -->
HashFunc hf;
KeyOfT kot;
Node* pre = nullptr;
if (find(hf(key)) == nullptr)
{<!-- -->
return false;
}

size_t hashi = hf(key) % _ht.size();
Node* cur = _ht[hashi];
while (cur)
{<!-- -->
if (kot(cur->_date) == key)
{<!-- -->
if (pre == nullptr)
{<!-- -->
//Delete header
delete cur;
_ht[hashi] = nullptr;
}
else
{<!-- -->
Node* next = cur->_next;
pre->_next = next;
delete cur;
}
return true;
}
pre = cur;
cur = cur->_next;
}
\t\t\t
}

void Print()
{<!-- -->
KeyOfT kot;
for (size_t i = 0; i < _ht.size(); i + + )
{<!-- -->
cout << "[" << i << "]"<< "->";
Node* cur = _ht[i];
while (cur)
{<!-- -->
cout << kot(cur->_date) << "->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}

//private:
vector<Node*> _ht;
size_t_n;
};

}

2.2.3 Unordered_set encapsulation of ordinary iterators

#include"hashtable.h"

namespace Ting
{<!-- -->
template<class K>
class unordered_set
{<!-- -->
public:
struct SetKeyOfT
{<!-- -->
const K & amp; operator()(const K & amp; key)
{<!-- -->
return key;
}
};

typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator iterator;


bool insert(const K & amp; key)
{<!-- -->
return _ht.insert(key);
}

iterator begin()
{<!-- -->
return _ht.begin();
}

iterator end()
{<!-- -->
return _ht.end();
}

void Print()
{<!-- -->
_ht.Print();
}
private:
hash_bucket::HashTable<K, K,SetKeyOfT> _ht;
};
}

2.2.4unordered_map ordinary iterator encapsulation

#include"hashtable.h"

namespace Ting
{<!-- -->
template<class K,class V>
class unordered_map
{<!-- -->
public:
struct MapKeyOfT
{<!-- -->
const K & amp; operator()(const pair<K,V> & amp; kv)
{<!-- -->
return kv.first;
}
};

bool insert(const pair<K, V> & amp; kv)
{<!-- -->
return _ht.insert(kv);
}

typedef typename hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;


bool insert(const K & amp; key)
{<!-- -->
return _ht.insert(key);
}

iterator begin()
{<!-- -->
return _ht.begin();
}

iterator end()
{<!-- -->
return _ht.end();
}

void Print()
{<!-- -->
_ht.Print();
}
private:
hash_bucket::HashTable<K, pair<K,V>, MapKeyOfT> _ht;
};
}

2.3 The keys of unordered_set and unordered_map cannot be modified

At this time, const iterators are needed, and the encapsulation of const iterators must be considered

2.3.1Construction of const iterator

This is normal operation, no different from what I wrote before.
The code is as follows:

//Advanced declaration of template
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;

template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HashIterator
{<!-- -->
typedef HashNode<T> Node;
typedef HashIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HashTable<K, T, KeyOfT, HashFunc> HashTable;

HashIterator(Node* node, HashTable* hptr)
:_node(node)
, _hptr(hptr)
{<!-- -->}

Self operator + + ()
{<!-- -->
if (_node->_next)
{<!-- -->
_node = _node->_next;
}
else
{<!-- -->
//It’s hard to write the following
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(kot(_node->_date)) % _hptr->_ht.size();
hashi + + ;

while (hashi < _hptr->_ht.size() & amp; & amp; _hptr->_ht[hashi] == nullptr)
{<!-- -->
+ + hashi;
}
if (hashi == _hptr->_ht.size())
{<!-- -->
_node = nullptr;
}
else
{<!-- -->
_node = _hptr->_ht[hashi];
}
}
return *this;
}

Ptr operator->()
{<!-- -->
return &(_node->_date);
}

Ref operator*()
{<!-- -->
return _node->_date;
}

bool operator!=(const Self & amp; it)
{<!-- -->
return _node != it._node;
}

Node* _node;
HashTable* _hptr;
};

2.3.2 Encapsulation of const iterator

 template<class K,class T,class KeyOfT,class HashFunc=DefaultHashFunc<K>>
classHashTable
{<!-- -->
typedef HashNode<T> Node;
public:
typedef HashIterator<K, T, T*, T & amp;, KeyOfT, HashFunc> iterator;
typedef HashIterator<K, T, const T*, const T & amp;, KeyOfT, HashFunc> const_iterator;


iterator begin()
{<!-- -->
size_t i = 0;
while (i < _ht.size() & amp; & amp; _ht[i] == nullptr)
{<!-- -->
+ + i;
}
if (i == _ht.size())
{<!-- -->
return iterator(nullptr, this);
}
return iterator(_ht[i], this);
}

iterator end()
{<!-- -->
return iterator(nullptr, this);
}

const_iterator begin() const
{<!-- -->
size_t i = 0;
while (i < _ht.size() & amp; & amp; _ht[i] == nullptr)
{<!-- -->
+ + i;
}
if (i == _ht.size())
{<!-- -->
return const_iterator(nullptr, this);
}
return const_iterator(_ht[i], this);
}

const_iterator end() const
{<!-- -->
return const_iterator(nullptr, this);
}

HashTable()
{<!-- -->
_ht.resize(10, nullptr);
}

bool insert(const T & date)
{<!-- -->
HashFunc hf;
KeyOfT kot;
if (find(kot(date)))
{<!-- -->
return false;
}

//Expand the capacity when the load factor reaches 1
if (_n == _ht.size())
{<!-- -->
size_t newsize = _ht.size() * 2;
HashTable<K,T,KeyOfT,HashFunc> newtable;
newtable._ht.resize(newsize);

for (size_t i = 0; i < _ht.size(); i + + )
{<!-- -->
Node* cur = _ht[i];
while (cur)
{<!-- -->
Node* next = cur->_next;
size_t hashi = hf(kot(cur->_date)) % newsize;

//cur header inserts into the new linked list
cur->_next = newtable._ht[hashi];
newtable._ht[hashi] = cur;

cur = next;
}
}
_ht.swap(newtable._ht);
}


size_t hashi = hf(kot(date)) % _ht.size();
Node* newnode = new Node(date);

newnode->_next = _ht[hashi];
_ht[hashi] = newnode;

+ + _n;
return true;
}

Node* find(const K & amp; key)
{<!-- -->
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _ht.size();
Node* cur = _ht[hashi];
while (cur)
{<!-- -->
if (kot(cur->_date) == key)
{<!-- -->
return cur;
}
cur = cur->_next;
}
return nullptr;
}

bool erase(const K & amp; key)
{<!-- -->
HashFunc hf;
KeyOfT kot;
Node* pre = nullptr;
if (find(hf(key)) == nullptr)
{<!-- -->
return false;
}

size_t hashi = hf(key) % _ht.size();
Node* cur = _ht[hashi];
while (cur)
{<!-- -->
if (kot(cur->_date) == key)
{<!-- -->
if (pre == nullptr)
{<!-- -->
//Delete header
delete cur;
_ht[hashi] = nullptr;
}
else
{<!-- -->
Node* next = cur->_next;
pre->_next = next;
delete cur;
}
return true;
}
pre = cur;
cur = cur->_next;
}
\t\t\t
}

void Print()
{<!-- -->
KeyOfT kot;
for (size_t i = 0; i < _ht.size(); i + + )
{<!-- -->
cout << "[" << i << "]"<< "->";
Node* cur = _ht[i];
while (cur)
{<!-- -->
cout << kot(cur->_date) << "->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}

//private:
vector<Node*> _ht;
size_t_n;
};

}

But the above code will fail to compile. The reason is as follows:

Therefore, we need to rewrite the iterator, add an overload of the constructor, and then change the hashtable pointer to a const type. like:

2.3.3 Encapsulation of const iterator of unordered_set

This is handled in the same way as set.

#pragma once
#include"hashtable.h"

namespace Ting
{<!-- -->
template<class K>
class unordered_set
{<!-- -->
public:
struct SetKeyOfT
{<!-- -->
const K & amp; operator()(const K & amp; key)
{<!-- -->
return key;
}
};

typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;

bool insert(const K & amp; key)
{<!-- -->
return _ht.insert(key);
}

iterator begin() const
{<!-- -->
return _ht.begin();
}

iterator end() const
{<!-- -->
return _ht.end();
}

void Print()
{<!-- -->
_ht.Print();
}
private:
hash_bucket::HashTable<K, K,SetKeyOfT> _ht;
};
}

2.3.4 Encapsulation of const iterator of unordered_map

This is handled in the same way as map.

#pragma once
#include"hashtable.h"

namespace Ting
{<!-- -->
template<class K,class V>
class unordered_map
{<!-- -->
public:
struct MapKeyOfT
{<!-- -->
const K & amp; operator()(const pair<K,V> & amp; kv)
{<!-- -->
return kv.first;
}
};

bool insert(const pair<K, V> & amp; kv)
{<!-- -->
return _ht.insert(kv);
}

typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;


bool insert(const K & amp; key)
{<!-- -->
return _ht.insert(key);
}

iterator begin()
{<!-- -->
return _ht.begin();
}

iterator end()
{<!-- -->
return _ht.end();
}

const_iterator end() const
{<!-- -->
return _ht.end();
}

const_iterator begin() const
{<!-- -->
return _ht.begin();
}

void Print()
{<!-- -->
_ht.Print();
}
private:
hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT> _ht;
};
}

[] overload of 2.4unordered_map

Step 1: Rewrite the return value of the insert function in the hashtable to the type of pair

pair<iterator,bool> insert(const T & amp; date)
{<!-- -->
HashFunc hf;
KeyOfT kot;
if (find(kot(date)))
{<!-- -->
return make_pair(iterator(nullptr,this),false);
}

//Expand the capacity when the load factor reaches 1
if (_n == _ht.size())
{<!-- -->
size_t newsize = _ht.size() * 2;
HashTable<K,T,KeyOfT,HashFunc> newtable;
newtable._ht.resize(newsize);

for (size_t i = 0; i < _ht.size(); i + + )
{<!-- -->
Node* cur = _ht[i];
while (cur)
{<!-- -->
Node* next = cur->_next;
size_t hashi = hf(kot(cur->_date)) % newsize;

//cur header inserts into the new linked list
cur->_next = newtable._ht[hashi];
newtable._ht[hashi] = cur;

cur = next;
}
}
_ht.swap(newtable._ht);
}


size_t hashi = hf(kot(date)) % _ht.size();
Node* newnode = new Node(date);

newnode->_next = _ht[hashi];
_ht[hashi] = newnode;

+ + _n;
return make_pair(iterator(newnode,this),true);
}

Then I compiled it and found that another compilation error was reported. The reason is actually the same as set. As shown in the picture:

Step 2: Add a constructor to the iterator

//Advanced declaration of template
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;

template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HashIterator
{<!-- -->
typedef HashNode<T> Node;
typedef HashIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HashTable<K, T, KeyOfT, HashFunc> HashTable;
typedef HashIterator<K, T, T*, T & amp;, KeyOfT, HashFunc> Iterator;

HashIterator(Node* node, HashTable* hptr)
:_node(node)
, _hptr(hptr)
{<!-- -->}

HashIterator(Node* node, const HashTable* hptr)
:_node(node)
, _hptr(hptr)
{<!-- -->}

HashIterator(const Iterator & amp; it)
:_node(it._node)
, _hptr(it._hptr)
{<!-- -->}

Self operator + + ()
{<!-- -->
if (_node->_next)
{<!-- -->
_node = _node->_next;
}
else
{<!-- -->
//It’s hard to write the following
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(kot(_node->_date)) % _hptr->_ht.size();
hashi + + ;

while (hashi < _hptr->_ht.size() & amp; & amp; _hptr->_ht[hashi] == nullptr)
{<!-- -->
+ + hashi;
}
if (hashi == _hptr->_ht.size())
{<!-- -->
_node = nullptr;
}
else
{<!-- -->
_node = _hptr->_ht[hashi];
}
}
return *this;
}

Ptr operator->()
{<!-- -->
return &(_node->_date);
}

Ref operator*()
{<!-- -->
return _node->_date;
}

bool operator!=(const Self & amp; it)
{<!-- -->
return _node != it._node;
}

Node* _node;
const HashTable* _hptr;
};

Step 3: Complete operator[]

#pragma once
#include"hashtable.h"

namespace Ting
{<!-- -->
template<class K,class V>
class unordered_map
{<!-- -->
public:
struct MapKeyOfT
{<!-- -->
const K & amp; operator()(const pair<K,V> & amp; kv)
{<!-- -->
return kv.first;
}
};

typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

pair<iterator,bool> insert(const pair<K, V> & amp; kv)
{<!-- -->
return _ht.insert(kv);
}


bool insert(const K & amp; key)
{<!-- -->
return _ht.insert(key);
}

iterator begin()
{<!-- -->
return _ht.begin();
}

iterator end()
{<!-- -->
return _ht.end();
}

const_iterator end() const
{<!-- -->
return _ht.end();
}

const_iterator begin() const
{<!-- -->
return _ht.begin();
}

void Print()
{<!-- -->
_ht.Print();
}

V & amp; operator[](const K & amp; key)
{<!-- -->
pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));
return ret.first->second;
}
private:
hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT> _ht;
};
}