Table of Contents
1.Framework
2. Structure
unordered_map
unordered_set
3. Modifications to HashTable
Change template parameters
4. Add an iterator
a. Structure
b. Operator overloading
c.HashTable encapsulates iterator
d.Iterators of unordered_map and unordered_set
1.Frame
1. Reuse HashTable ~~> Add template parameter KeyOfT to obtain Key value
unordered_map passes K, V unordered_set passes K
2. Add iterator: HashNode + HashTable ~~> + + , implementation of [ ], ordinary iterator constructs const iterator
3. If you want to convert a custom type into an integer, write a functor outside and pass it to unordered_map or unordered_set
2. Structure
unordered_map
template<class K,class V,class Hash = HashFunc<V>>
class unordered_map
{
struct MapKeyOfT
{
const K & amp; operator()(const pair<K, V> & amp; kv)
{
return kv.first;
}
};
public:
bool insert(const pair<const K, V> & amp; kv)
{
return _ht.Insert(kv);
}
private:
HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT,Hash> _ht;
};
unordered_set
template<class K,class Hash = HashFunc<K>>
class unordered_Set
{
public:
//functor
struct SetKeyOfT
{
const K & amp; operator()(const K & amp; k)
{
return k;
}
};
//Interface: insert + erase + find
bool insert(const K & amp; key)
{
return _ht.Insert(key);
}
private:
HashBucket::HashTable<K, K, SetKeyOfT,Hash> _ht;
};
3. Modifications to HashTable
Change template parameters
1. Add KeyOfT functor –> let unordered_map and unordered_set reuse HashTable at the same time
2. Add template parameter K–>Difference between unordered_map (K,V) and unordered_set(K)
~~>Everything that involves getting the data value is changed to , and the functor KeyOfT is used to get it (insert + search + delete)
4. Add iterator
a.structure
//2.Iterator
//Overload: * -> + + == !=
template<class K,class T,class KeyOfT,class Hash>
struct __HashIterator
{
typedef HashNode<T> Node;
typedef HashTable< K, T, KeyOfT, Hash> HT;
typedef __HashIterator< K, T, KeyOfT, Hash> Self;
//node + hash table
Node* _node;
const HT* _ht;
\t\t//Constructor
__HashIterator(Node* node, const HT* ht)
:_node(node)
,_ht(ht)
{}
//Overloaded operator
};
b.Operator overloading
* -> == !=
//Overloaded operator
T & amp; operator*() { return _node->_data; }
T* operator->() { return & amp;(_node->_data); }
bool operator==(const Self & amp; it) { return _node == it._node; }
bool operator!=(const Self & amp; it) { return _node != it._node; }
+ +
Ideas: 1. If the next node is not nullptr, return the next node
2. If the next node is nullptr, find the next bucket
–First get the key value based on the data in the node to calculate the position of the current bucket
–Find the next bucket that is not empty
If the bucket is not empty, give it the node
If this bucket is empty, + + hash
Calculate the position of the current bucket: get the key + convert non-integer data to integer + get the number of hash buckets + hash table
~~> Functor + HashTable provides interface acquisition or friends
Self & amp; operator + + () { //1. If the next node is not nullptr, return the next node if (_node->_next) { _node = _node->_next; } //2. Find the next bucket that is not empty else { //Calculate the current bucket position Hash hash; KeyOfT kot; size_t hashi = hash(kot(_node->_data)) % _ht->GetCapacity(); vector<Node*> tables = _ht->GetTables(); + + hashi; //Find a bucket that is not empty while (hashi < _ht->GetCapacity()) { if (tables[hashi]) { _node = tables[hashi]; break; } else { + + hashi; } } //After finding the next node, return a null pointer if (hashi == _ht->GetCapacity()) _node = nullptr; } return *this; } };Effect:
c.HashTable encapsulated iterator
begin
Idea:
1. Find the first bucket with an element
iterator begin()
{
//Find the first hash bucket with elements
size_t hashi = 0;
while (hashi < GetCapacity())
{
if (_tables[hashi] != nullptr)
{
return iterator(_tables[hashi], this);
}
+ + hashi;
}
return iterator(nullptr,this);
}
end
iterator end()
{
return iterator(nullptr,this);
}
Iterator of d.unordered_map and unordered_set
Iterators of unordered_map and unordered_set~~>Call the iterator of HashTable
unordered_map~~> K, V type allows V to be modified~~>const iterator and ordinary iterator
unordered_set~~> K type is not allowed to be modified ~~>const iterators and ordinary iterators are both const iterators
Add const iterator and ordinary iterator~~> Modify the template parameters of the iterator + Modify the parameters of HashTable
Iterator template parameter modification
Modification of HashTable parameters
unordered_map
unordered_set
Provide ordinary iterators to construct const iterators
An ordinary object calls the begin function and returns an ordinary iterator. However, the ordinary iterator defined is a const iterator, and implicit type conversion will occur~~> Therefore, an ordinary iterator needs to be provided to construct a const iterator.
Implementation of []: The return type of a.insert is changed to pair
1. Call the insert function~~>If there is no K value, insert it into the hash table
2. Return to V
Effect:
