如何实现基于哈希表的STL无序容器封装？

本文共计1295个文字，预计阅读时间需要6分钟。

概述：本文以hash_table为基础进行封装，模拟SGI+STL对unordered系列容器进行简单实现，旨在加深对C++封装与泛型技术的体会。阅读本文前，建议先对哈希表进行学习。

正文：以下是对hash_table的简单封装实现，模拟unordered系列容器。

cpp#include #include #include

templateclass hash_table {private: std::vector data; std::function hash_func;

public: hash_table(std::function func) : hash_func(func) {}

void insert(const K& key, const V& value) { size_t index=hash_func(key) % data.size(); while (data[index].first !=K() && data[index].first !=key) { index=(index + 1) % data.size(); } if (data[index].first==K()) { data[index]={key, value}; } else { std::cout << Key already exists! <

V find(const K& key) const { size_t index=hash_func(key) % data.size(); while (data[index].first !=K() && data[index].first !=key) { index=(index + 1) % data.size(); } if (data[index].first==key) { return data[index].second; } return V(); }};

int main() { hash_table ht([](int key) { return key % 10; });

ht.insert(1, apple); ht.insert(2, banana); ht.insert(3, cherry);

std::cout << Find 1: <

return 0;}

以上代码展示了hash_table的基本功能，包括插入和查找。通过模拟unordered系列容器，我们可以加深对C++封装与泛型技术的理解。在实际应用中，可以进一步优化此代码，例如添加删除、更新等功能，以及使用更高效的哈希函数。

概述

本文对hash_table进行封装，以模仿SGI STL对unordered系列容器进行简单实现，旨在加深对C++封装与泛型技法的体会与理解。阅读本文之前，建议先对哈希表进行学习。本文是以hash_table的实现为基础的，建议与关联式数据结构_哈希表剖析 #C++进行结合阅读。

unordered_map

与map一样，unordered_map的所有元素类型都是pair，pair的第一个成员为Key，第二个成员为Value。因为Key在任何情况下都不允许被修改，所以Key在pair中其实是被const修饰的。使用unordered_map的目的是根据键值快速搜寻元素，unordered_map底层是散列表，不具有对元素自动排序的功能。总体上来说，unordered_map的期望搜索效率相比map更高。从使用方面来讲，unordered_map与map的用法完全相同。

template<class Key, class Value> class unordered_map { /*…………*/ private: hash_table<Key, pair<const Key, Value>, MapKeyOfT> _hash_table; };

MapKeyOfT

MapKeyOfT仿函数的设计目的与在map中的一样，均是为了拿到元素中的Key值，只不过在这里拿到Key值的目的是以Key计算元素的索引，将元素放到合适的桶中。

struct MapKeyOfT { const Key& operator()(const pair<const Key, Value>& kv) { return kv.first; } };

在hash_table层面，MapKeyOfT被视为模板参数KeyOfT，以同时兼容unordered_map和unordered_set，而不必关心hash_table的具体使用者及具体函数的内部实现细节。

迭代器

对于unordered_map，可以通过迭代器修改元素的Value，但不允许通过迭代器修改元素的Key，这是因为任意修改Key会破坏hash_table的组织。unordered_map的迭代器直接对hash_table进行复用即可。

public: typedef typename hash_table<Key, pair<const Key, Value>, MapKeyOfT>::iterator iterator; typedef typename hash_table<Key, pair<const Key, Value>, MapKeyOfT>::const_iterator const_iterator; iterator begin() { return _hash_table.begin(); } iterator end() { return _hash_table.end(); } const_iterator begin() const { return _hash_table.begin(); } const_iterator end() const { return _hash_table.end(); }

在对unordered_map进行插入操作时，不存在迭代器失效问题；进行删除操作时，被删除的元素的迭代器失效。

元素操作

unordered_map的大部分接口，直接对hash_table的接口进行复用即可。

//插入元素 pair<iterator, bool> insert(const pair<Key, Value>& kv) { return _hash_table.insert(std::make_pair(kv.first, kv.second)); } //删除元素 iterator erase(const Key& key) { return _hash_table.erase(key); } //查找元素 iterator find(const Key& key) const { return _hash_table.find(key); }

operator[]是unordered_map特有的接口，本质是对hash_table的insert接口的复用，支持用户方便地通过Key对对应元素的Value进行修改。

Value& operator[](const Key& key) { pair<iterator, bool> retInsert = insert(make_pair(key, Value())); return retInsert.first->second; } const Value& operator[](const Key& key) const { pair<iterator, bool> retInsert = insert(make_pair(key, Value())); return retInsert.first->second; }

unordered_set

unordered_set的元素不像unordered_map那样同时拥有Key和Value，可以认为，unordered_set的Key就是Value，Value就是Key。

template<class Key> class unordered_set { /*…………*/ private: hash_table<Key, Key, SetKeyOfT> _hash_table; };

SetKeyOfT

对于unordered_set的KeyOfT仿函数，只需要直接返回元素的Key值即可。unordered_set的KeyOfT的设计目的完全是为了迁就unordered_map，以进行兼容。

struct SetKeyOfT { const Key& operator()(const Key& key) { return key; } };

同理，不能通过unordered_set的迭代器修改键值，为了杜绝修改操作，可以直接将hash_table的const迭代器作为unordered_set的普通迭代器。unordered_set的迭代器是一种const iterators。

typedef typename hash_table<Key, Key, SetKeyOfT>::const_iterator iterator; typedef typename hash_table<Key, Key, SetKeyOfT>::const_iterator const_iterator; iterator begin() const { return _hash_table.begin(); } iterator end() const { return _hash_table.end(); }

在对unordered_set进行插入操作时，不存在迭代器失效问题；进行删除操作时，被删除的元素的迭代器失效。

unordered_set的大部分接口可以直接复用hash_table的接口。

iterator erase(const Key& key) { return _hash_table.erase(key); } iterator find(const Key& key) const { typename HashBucket::hash_table<Key, Key, SetKeyOfT>::iterator ret = _hash_table.find(key); return iterator(ret); }

对于insert接口，与set同理，由于返回值类型不一致，需要进行一层转换，支持转换的关键是，在__hash_table_iterator中额外搞一个构造函数。

template<class Key, class T, class Ref, class Ptr, class KeyOfT, class HashFunc> struct __hash_table_iterator { private: typedef __hash_table_iterator<Key, T, T&, T*, KeyOfT, HashFunc> iterator; public: //对于iterator，这个函数是拷贝构造 //对于const_iterator，这个函数是构造 //使用iterator构造const_iterator __hash_table_iterator(Node* node, const HashTable* hash_table) :_node(node), _hash_table(hash_table) { } /*…………*/ };

完成这个迭代器的构造函数之后，就可以对hash_table::insert的返回值进行转化，与unordered_set::insert进行匹配。

pair<iterator, bool> insert(const Key& key) { pair<typename HashBucket::hash_table<Key, Key, SetKeyOfT>::iterator, bool> ret = _hash_table.insert(key); return pair<iterator, bool>(ret.first, ret.second); }