上篇文章我們講解了哈希表的實現，這節嘗試使用哈希表來封裝unordered_set/map
1. unordered_set/map的框架
封裝的過程實際上與set/map類似，在unordered_set/map層傳遞一個仿函數，用于取出key值
由于我們平常使用的都是unordered_set/map，因此哈希函數應在unordered_set/map層作為參數傳遞給哈希表
// unordered_set.h
template<typename K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t ans = 0;for (auto& e : s){ans *= 131;ans += e;}return ans;}
};namespace byh
{template<typename K, typename Hash = HashFunc<K>>class unordered_set{struct KeyOfSet{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _table.insert(key);}private:hash_bucket::HashTable<K, K, KeyOfSet, Hash> _table;};
}// unordered_map.h
namespace byh
{template<typename K, typename V, typename Hash = HashFunc<K>>class unordered_map{struct KeyOfMap{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool insert(const pair<K, V>& kv){return _table.insert(kv);}private:hash_bucket::HashTable<K, pair<K, V>, KeyOfMap, Hash> _table;};
}
2. 迭代器
在unordered_set/map這里，迭代器是對哈希節點指針的封裝
遍歷過程中，如果當前節點的next不為空，則直接迭代到下一節點；如果當前節點的next為空，則迭代到下一個不為空的桶
因此，迭代器中僅僅有節點的指針還不夠，還要有哈希表；迭代器在構造時將節點的指針和哈希表的指針作為參數傳遞
但由于table在哈希表中是私有成員，迭代器類中不能直接訪問table，這里有兩種解決方法
- 將迭代器類聲明為哈希表的友元類
- 在哈希表中使用內部類創建迭代器類，內部類天然就是外部類的友元類
// 友元的做法
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable;template<typename K, typename T, typename Ref, typename Ptr, typename KeyOfT, typename Hash>
class __Iterator
{using Node = HashNode<T>;using Self = __Iterator<K, T, Ref, Ptr, KeyOfT, Hash>;
public:__Iterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}Self& operator++(){if (_node->_next) _node = _node->_next;else{KeyOfT kot;Hash hash;size_t pos = hash(kot(_node->_data)) % _pht->_table.size();int i = 0;for (i = pos + 1; i < _pht->_table.size(); i++){Node* cur = _pht->_table[i];if (cur){_node = cur;break;}}if(i == _pht->_table.size()) _node = nullptr;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}private:Node* _node;HashTable<K, T, KeyOfT, Hash>* _pht;
};template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable
{friend __Iterator<K, T, T&, T*, KeyOfT, Hash>;
public:using Node = HashNode<T>;using iterator = __Iterator<K, T, T&, T*, KeyOfT, Hash>;// ......
}
// 內部類的做法
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable
{template<typename Ref, typename Ptr>class __Iterator{using Node = HashNode<T>;using Self = __Iterator<Ref, Ptr>;public:__Iterator(Node* node, HashTable* pht):_node(node), _pht(pht){}Self& operator++(){if (_node->_next) _node = _node->_next;else{KeyOfT kot;Hash hash;size_t pos = hash(kot(_node->_data)) % _pht->_table.size();int i = 0;for (i = pos + 1; i < _pht->_table.size(); i++){Node* cur = _pht->_table[i];if (cur){_node = cur;break;}}if (i == _pht->_table.size()) _node = nullptr;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}private:Node* _node;HashTable* _pht;};public:using Node = HashNode<T>;using iterator = __Iterator<T&, T*>;// ......
}
內部類做法的好處時，內部類能直接使用外部類的模板參數，不用向友元方式那樣傳遞很多模板參數，同時內部類能直接使用外部類而不用傳遞模板參數
哈希表的迭代器一旦設計好，unordered_set/map層無非就是封裝，這里不再敘述
3. const迭代器
const迭代器的整體思路沒難度，但有些細節地方需要注意
在哈希表層和unordered_set/map層添加完const迭代器后
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable
{template<typename Ref, typename Ptr>class __Iterator{using Node = HashNode<T>;using Self = __Iterator<Ref, Ptr>;public:__Iterator(Node* node, const HashTable* pht):_node(node), _pht(pht){}// ......private:Node* _node;const HashTable* _pht;};
關于unordered_map的operator[]，其設計思路與set/map相同
unordered_set/map層的插入、刪除、查找操作也同樣是簡單的封裝
4. 測試
void Print(const unordered_set<int>& s)
{unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;
}void Test_unordered_set()
{vector<int> v = { 1, 4, 2, 3, 5, 9, 11 };unordered_set<int> s;for (auto& e : v) s.insert(e);cout << "const迭代器: ";Print(s);cout << s.find(4) << endl;cout << s.find(54) << endl;s.erase(4);cout << s.find(4) << endl;
}
void Test_unordered_map()
{unordered_map<string, int> m;vector<string> v = { "apple", "apple", "banana", "watermelon", "banana" };for (auto& e : v) m[e] ++;unordered_map<string, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << " " << it->second << endl;++it;}cout << endl;cout << m.find("apple") << endl;cout << m.find("abdsaf") << endl;m.erase("apple");cout << m.find("apple") << endl;
}
)
)
