C++ unordered_map unordered_set 模拟实现
1. 关于unordered_map 和 unordered_set
区别于C++的另外两个容器map
和set
,map
和set
的底层是红黑树;而unordered_map
和unordered_set
的底层是哈希
因为unordered_map
和unordered_set
的底层是哈希,因此他们存储的数据是没有顺序unordered
的
下面,我们就通过之前写的基于开散列(哈希桶)的代码,来封装出一份简单的unordered_map
和unordered_set
开散列哈希表的代码如下:
namespace open_hash
{
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
struct Node
{
std::pair<K, V> kv;
Node* next;
Node(const std::pair<K, V>& KV = std::pair<K, V>())
: kv(KV),
next(nullptr){}
};
public:
HashTable()
: _load_factor(1.0),
_n(0)
{
_hash.resize(10, nullptr);
}
~HashTable()
{
for (auto& node : _hash)
{
while (node)
{
Node* next = node->next;
delete node;
node = next;
}
}
}
size_t size() const
{
return _n;
}
Node* find(const K& key)
{
size_t hash_index = _hash_func(key) % _hash.capacity();
Node* node = _hash[hash_index];
while (node)
{
if (node->kv.first == key)
return node;
node = node->next;
}
return nullptr;
}
bool insert(std::pair<K, V> kv)
{
if (find(kv.first))
return false;
if (1.0 * _n / _hash.capacity() >= _load_factor)
{
size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();
HashTable<K, V, Hash> new_hash;
new_hash._hash.resize(capacity, nullptr);
//将原来哈希桶中的节点转移到新的桶中
for (auto& node : _hash)
{
while (node)
{
//从新计算映射关系
size_t hash_index = _hash_func(node->kv.first) % new_hash._hash.capacity();
Node* next = node->next;
node->next = new_hash._hash[hash_index];
new_hash._hash[hash_index] = node;
node = next;
}
}
_hash.swap(new_hash._hash);
}
Node* newnode = new Node(kv);
size_t hash_index = _hash_func(kv.first) % _hash.capacity();
//头插
newnode->next = _hash[hash_index];
_hash[hash_index] = newnode;
++_n;
return true;
}
bool erase(const K& key)
{
size_t hash_index = _hash_func(key) % _hash.capacity();
Node* node = _hash[hash_index];
Node* prev = nullptr;
while (node)
{
if (node->kv.first == key)
{
if (prev == nullptr)
_hash[hash_index] = _hash[hash_index]->next;
else
prev->next = node->next;
delete node;
--_n;
return true;
}
prev = node;
node = node->next;
}
return false;
}
private:
std::vector<Node*> _hash;
double _load_factor;
Hash _hash_func;
size_t _n;
};
}
2. 模拟实现
2.1 修改哈希表的类模板参数
如果想要用同一份哈希表代码来模拟实现出unordered_map
和unordered_set
两份容器,就需要考虑一个问题:
-
unordered_set
是Key
结构的;而unordered_map
是Key_Value
结构的 -
在上面的哈希表代码中,我们直接使用的就是
KV
模型,因此就需要想办法来屏蔽这种差异
可以通过这样的方式来解决:
将哈希表的模板参数改成这样:
template<class K, class T, class KeyOfT, class Hash>
K
:Key
值的类型
T
:表示要存放什么类型的数据。
- 对于
unordered_set
,填写的就是K
- 对于
unordered_set
,填写的就是std::pair<K, V>
Hash
:计算哈希值的哈希函数
KeyOfT
:获得键值Key
的函数
由于哈希表自己不知道存储的数据到底是
Key
模型的还是Key_Value
模型的因此需要通过一个函数
KeyOfT
来获得数据的键值而这个
KeyOfT
由封装哈希表的unordered_map
和unordered_set
来提供类似这样:
对于
unordered_map
,Key
值是pair.first
template <class K, class V, class Hash = HashFunc<const K>> class unordered_map { struct MapKeyOfT { const K operator()(const std::pair<const K, V>& p) const { return p.first; } }; public: using HT = typename HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>; private: HT _ht; };
对于
unordered_set
,Key
值就是自己本身template <class K, class Hash = HashFunc<const K>> class unordered_set { struct SetKeyOfT { const K operator()(const K& key) const { return key; } }; public: using HT = typename HashTable<K, K, SetKeyOfT, Hash>; private: HT _ht; };
2.2 哈希表的迭代器实现
注:
STL
中的unordered_map(set)
只支持正向迭代器,不支持反向迭代器规定:哈希表迭代器的
begin()
,为第一个不为空的哈希桶中的第一个节点;哈希表迭代器的end()
,为nullptr
对于哈希表的迭代器,我们只需要关注operator++()
即可
对于开散列哈希桶的哈希表,当其迭代器向后移动一位之后,可能出现两种情况:
-
移动之后,不为空,说明这个哈希桶(单链表)还没有走完,那么直接返回这个节点即可
-
移动之后,为空,说明这个哈希桶(单链表)已经走完了
- 那么就找下一个不为空的哈希桶,并返回这个哈希桶的第一个节点
- 如果找不到下一个不为空的哈希桶了,就返回
end()
通过上面的分析我们发现,对于哈希表的迭代器类,其需要两个成员来完成迭代工作:
-
Node
:用于迭代当前所在的哈希桶 -
HashTable
:用于迭代所有的哈希桶
根据上面的分析,我么可以实现出哈希表迭代器:
//非const迭代器
template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>
struct __HashIterator
{
using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;
using HT = typename HashTable<K, T, KeyOfT, Hash>;
using Self = typename __HashIterator< K, T, KeyOfT, Hash>;
Node* node;
HT* ht;
__HashIterator(Node* n, HT* h) : node(n), ht(h) {}
//前置++
Self& operator++()
{
//如果已经是end(),直接返回
if (nullptr == node)
return *this;
Node* next = node->next;
if (next != nullptr) //如果哈希桶还没走完,就迭代到哈希桶的下一个
{
node = next;
return *this;
}
//否则,找到下一个非空哈希桶
size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();
while (++hash_index < ht->_hash.capacity())
{
//找到了,就迭代到这个非空哈希桶的第一个节点
if (ht->_hash[hash_index])
{
node = ht->_hash[hash_index];
return *this;
}
}
//走到这里,说明已经把哈希数组走完了(不需要往回走)
//也就是把所有的哈希桶走完了
//即走到end() nullptr
node = nullptr;
return *this;
}
//后置++
Self operator++(int)
{
Self temp = *this;
this->operator++();
return temp;
}
bool operator==(const Self& it) const
{
return node == it.node;
}
bool operator!=(const Self& it) const
{
return node != it.node;
}
T& operator*() const
{
return node->data;
}
T* operator->() const
{
return &node->data;
}
};
//const迭代器
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __HashConstIterator
{
using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;
using HT = typename HashTable<K, T, KeyOfT, Hash>;
using Self = typename __HashConstIterator< K, T, KeyOfT, Hash>;
const Node* node;
const HT* ht;
__HashConstIterator(const Node* n, const HT* h) : node(n), ht(h) {}
//前置++
Self& operator++()
{
if (nullptr == node)
return *this;
Node* next = node->next;
if (next != nullptr)
{
node = next;
return *this;
}
size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();
while (++hash_index < ht->_hash.capacity())
{
if (ht->_hash[hash_index])
{
node = ht->_hash[hash_index];
return *this;
}
}
//走到这里,说明已经把哈希数组走完了(不需要往回走)
//也就是把所有的哈希桶走完了
//即走到尾 nullptr
node = nullptr;
return *this;
}
//后置++
Self operator++(int)
{
Self temp = *this;
this->operator++();
return temp;
}
bool operator==(const Self& it) const
{
return node == it.node;
}
bool operator!=(const Self& it) const
{
return node != it.node;
}
const T& operator*() const
{
return node->data;
}
const T* operator->() const
{
return &node->data;
}
};
2.3 修改哈希表部分函数的返回值
后续我们模拟实现unordered_set
和unordered_map
的接口都是直接调用其内部封装的哈希表的接口
因此,为了符合规范,我们需要对原先哈希表部分函数的返回值进行修改
find()
以unordered_map
的成员函数find()
为例:
iterator find ( const key_type& k );
const_iterator find ( const key_type& k ) const;
- 对于非
const
对象,返回非const
迭代器 - 对于
const
对象,返回const
迭代器
iterator find(const K& key)
{
size_t hash_index = _hash_func(key) % _hash.capacity();
Node* node = _hash[hash_index];
while (node)
{
if (_key_of_t(node->data) == key)
return iterator(node, this);
node = node->next;
}
return iterator(nullptr, this);
}
const_iterator find(const K& key) const
{
size_t hash_index = _hash_func(key) % _hash.capacity();
Node* node = _hash[hash_index];
while (node)
{
if (_key_of_t(node->data) == key)
return const_iterator(node, this);
node = node->next;
}
return const_iterator(nullptr, this);
}
insert()
以unordered_map
的成员函数insert()
为例:
pair<iterator,bool> insert ( const value_type& val );
可见,返回值是一个pair<iterator,bool>
,其含义如下:
- 如果哈希表中已经有相同关键字的元素,那么就表示插入失败,并返回指向这个相同关键字元素的迭代器
- 如果哈希表中没有相同关键字的元素,那么就插入成功,并返回这个指向新插入的元素的迭代器
std::pair<iterator, bool> insert(const T& data)
{
auto it = find(_key_of_t(data));
if (it != end())
return std::make_pair(it, false);
if (1.0 * _n / _hash.capacity() >= _load_factor)
{
size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();
HashTable<K, T, KeyOfT, Hash> new_hash;
new_hash._hash.resize(capacity, nullptr);
//将原来哈希桶中的节点转移到新的桶中
for (auto& node : _hash)
{
while (node)
{
//从新计算映射关系
size_t hash_index = _hash_func(_key_of_t(node->data)) % new_hash._hash.capacity();
Node* next = node->next;
node->next = new_hash._hash[hash_index];
new_hash._hash[hash_index] = node;
node = next;
}
}
_hash.swap(new_hash._hash);
}
Node* newnode = new Node(data);
size_t hash_index = _hash_func(_key_of_t(data)) % _hash.capacity();
//头插
newnode->next = _hash[hash_index];
_hash[hash_index] = newnode;
++_n;
return std::make_pair(iterator(newnode, this), true);
}
erase()
以unordered_map
的成员函数erase()
为例:
by position (1) iterator erase ( const_iterator position );
by key (2) size_type erase ( const key_type& k );
-
通过迭代器删除
- 如果删除成功,就返回指向被删除元素的下一个元素的迭代器
- 如果删除失败,就返回
end()
-
通过关键字
Key
删除- 如果删除成功,返回
true
- 如果删除失败,返回
false
- 如果删除成功,返回
iterator erase(const_iterator pos)
{
//不能删除end()
if (pos == cend())
return cend();
size_t hash_index = _key_of_t(*pos) % _hash.capacity();
Node* node = _hash[hash_index];
Node* prev = nullptr;
Node* next = nullptr;
while (node)
{
if (_key_of_t(node->data) == _key_of_t(*pos))
{
if (prev == nullptr)
_hash[hash_index] = _hash[hash_index]->next;
else
prev->next = node->next;
delete node;
--_n;
//找到下一个节点
next = (prev == nullptr) ? _hash[hash_index] : prev->next;
if (next == nullptr)
{
while (++hash_index < _hash.capacity())
{
if (_hash[hash_index])
{
next = _hash[hash_index];
break;
}
}
}
return iterator(next, this);
}
prev = node;
node = node->next;
}
return end();
}
bool erase(const K& key)
{
size_t hash_index = _hash_func(key) % _hash.capacity();
Node* node = _hash[hash_index];
Node* prev = nullptr;
while (node)
{
if (_key_of_t(node->data) == key)
{
if (prev == nullptr)
_hash[hash_index] = _hash[hash_index]->next;
else
prev->next = node->next;
delete node;
--_n;
return true;
}
prev = node;
node = node->next;
}
return false;
}
开散列哈希表实现代码
namespace open_hash
{
template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>
class HashTable;
template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>
struct __HashIterator
{
using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;
using HT = typename HashTable<K, T, KeyOfT, Hash>;
using Self = typename __HashIterator< K, T, KeyOfT, Hash>;
Node* node;
HT* ht;
__HashIterator(Node* n, HT* h) : node(n), ht(h) {}
//前置++
Self& operator++()
{
if (nullptr == node)
return *this;
Node* next = node->next;
if (next != nullptr)
{
node = next;
return *this;
}
size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();
while (++hash_index < ht->_hash.capacity())
{
if (ht->_hash[hash_index])
{
node = ht->_hash[hash_index];
return *this;
}
}
//走到这里,说明已经把哈希数组走完了(不需要往回走)
//也就是把所有的哈希桶走完了
//即走到尾 nullptr
node = nullptr;
return *this;
}
//后置++
Self operator++(int)
{
Self temp = *this;
this->operator++();
return temp;
}
bool operator==(const Self& it) const
{
return node == it.node;
}
bool operator!=(const Self& it) const
{
return node != it.node;
}
T& operator*() const
{
return node->data;
}
T* operator->() const
{
return &node->data;
}
};
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __HashConstIterator
{
using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;
using HT = typename HashTable<K, T, KeyOfT, Hash>;
using Self = typename __HashConstIterator< K, T, KeyOfT, Hash>;
const Node* node;
const HT* ht;
__HashConstIterator(const Node* n, const HT* h) : node(n), ht(h) {}
//支持非const迭代器到const迭代器的类型转换
__HashConstIterator(const __HashIterator<K, T, KeyOfT>& it) : node(it.node), ht(it.ht) {}
//前置++
Self& operator++()
{
if (nullptr == node)
return *this;
Node* next = node->next;
if (next != nullptr)
{
node = next;
return *this;
}
size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();
while (++hash_index < ht->_hash.capacity())
{
if (ht->_hash[hash_index])
{
node = ht->_hash[hash_index];
return *this;
}
}
//走到这里,说明已经把哈希数组走完了(不需要往回走)
//也就是把所有的哈希桶走完了
//即走到尾 nullptr
node = nullptr;
return *this;
}
//后置++
Self operator++(int)
{
Self temp = *this;
this->operator++();
return temp;
}
bool operator==(const Self& it) const
{
return node == it.node;
}
bool operator!=(const Self& it) const
{
return node != it.node;
}
const T& operator*() const
{
return node->data;
}
const T* operator->() const
{
return &node->data;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
friend struct __HashIterator<K, T, KeyOfT, Hash>;;
friend struct __HashConstIterator<K, T, KeyOfT, Hash>;
public:
struct Node
{
T data;
Node* next;
Node(const T& Data = T())
: data(Data),
next(nullptr){}
};
public:
using iterator = __HashIterator<K, T, KeyOfT, Hash>;
using const_iterator = __HashConstIterator<K, T, KeyOfT, Hash>;
using HT = HashTable<K, T, KeyOfT, Hash>;
public:
HashTable()
: _load_factor(1.0),
_n(0)
{
_hash.resize(10, nullptr);
}
//拷贝构造
HashTable(const HT& ht)
:_load_factor(ht._load_factor),
_n(ht._n),
_hash_func(ht._hash_func),
_key_of_t(ht._key_of_t)
{
_hash.resize(ht._hash.capacity(), nullptr);
for (auto& node : ht._hash)
{
Node* cur = node;
while (cur)
{
size_t hash_index = _hash_func(_key_of_t(cur->data)) % _hash.capacity();
Node* newnode = new Node(cur->data);
newnode->next = _hash[hash_index];
_hash[hash_index] = newnode;
cur = cur->next;
}
}
}
//移动构造
HashTable(HT&& ht)
{
swap(ht);
}
HT& operator=(const HT& ht)
{
HT temp(ht);
swap(temp);
return *this;
}
//移动赋值
HT& operator=(HT&& ht)
{
swap(ht);
return *this;
}
~HashTable()
{
for (auto& node : _hash)
{
while (node)
{
Node* next = node->next;
delete node;
node = next;
}
}
}
void swap(HT& ht)
{
std::swap(_hash, ht._hash);
std::swap(_n, ht._n);
std::swap(_hash_func, ht._hash_func);
std::swap(_key_of_t, ht._key_of_t);
std::swap(_load_factor, ht._load_factor);
}
iterator begin()
{
//找到第一个非空的哈希桶
for (auto& node : _hash)
{
if (node)
return iterator(node, this);
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin() const
{
//找到第一个非空的哈希桶
for (auto& node : _hash)
{
if (node)
return const_iterator(node, this);
}
return const_iterator(nullptr, this);
}
const_iterator cbegin() const
{
//找到第一个非空的哈希桶
for (auto& node : _hash)
{
if (node)
return const_iterator(node, this);
}
return const_iterator(nullptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
const_iterator cend() const
{
return const_iterator(nullptr, this);
}
size_t size() const
{
return _n;
}
iterator find(const K& key)
{
size_t hash_index = _hash_func(key) % _hash.capacity();
Node* node = _hash[hash_index];
while (node)
{
if (_key_of_t(node->data) == key)
return iterator(node, this);
node = node->next;
}
return iterator(nullptr, this);
}
const_iterator find(const K& key) const
{
size_t hash_index = _hash_func(key) % _hash.capacity();
Node* node = _hash[hash_index];
while (node)
{
if (_key_of_t(node->data) == key)
return const_iterator(node, this);
node = node->next;
}
return const_iterator(nullptr, this);
}
std::pair<iterator, bool> insert(const T& data)
{
auto it = find(_key_of_t(data));
if (it != end())
return std::make_pair(it, false);
if (1.0 * _n / _hash.capacity() >= _load_factor)
{
size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();
HashTable<K, T, KeyOfT, Hash> new_hash;
new_hash._hash.resize(capacity, nullptr);
//将原来哈希桶中的节点转移到新的桶中
for (auto& node : _hash)
{
while (node)
{
//从新计算映射关系
size_t hash_index = _hash_func(_key_of_t(node->data)) % new_hash._hash.capacity();
Node* next = node->next;
node->next = new_hash._hash[hash_index];
new_hash._hash[hash_index] = node;
node = next;
}
}
_hash.swap(new_hash._hash);
}
Node* newnode = new Node(data);
size_t hash_index = _hash_func(_key_of_t(data)) % _hash.capacity();
//头插
newnode->next = _hash[hash_index];
_hash[hash_index] = newnode;
++_n;
return std::make_pair(iterator(newnode, this), true);
}
iterator erase(const_iterator pos)
{
//不能删除end()
if (pos == cend())
return cend();
size_t hash_index = _key_of_t(*pos) % _hash.capacity();
Node* node = _hash[hash_index];
Node* prev = nullptr;
Node* next = nullptr;
while (node)
{
if (_key_of_t(node->data) == _key_of_t(*pos))
{
if (prev == nullptr)
_hash[hash_index] = _hash[hash_index]->next;
else
prev->next = node->next;
delete node;
--_n;
//找到下一个节点
next = (prev == nullptr) ? _hash[hash_index] : prev->next;
if (next == nullptr)
{
while (++hash_index < _hash.capacity())
{
if (_hash[hash_index])
{
next = _hash[hash_index];
break;
}
}
}
return iterator(next, this);
}
prev = node;
node = node->next;
}
return end();
}
bool erase(const K& key)
{
size_t hash_index = _hash_func(key) % _hash.capacity();
Node* node = _hash[hash_index];
Node* prev = nullptr;
while (node)
{
if (_key_of_t(node->data) == key)
{
if (prev == nullptr)
_hash[hash_index] = _hash[hash_index]->next;
else
prev->next = node->next;
delete node;
--_n;
return true;
}
prev = node;
node = node->next;
}
return false;
}
private:
std::vector<Node*> _hash;
double _load_factor;
Hash _hash_func;
KeyOfT _key_of_t;
size_t _n;
};
}
2.4 unordered_set 模拟实现
namespace lwj
{
using namespace open_hash;
template <class K, class Hash = HashFunc<const K>>
class unordered_set
{
struct SetKeyOfT
{
const K operator()(const K& key) const
{
return key;
}
};
public:
using HT = typename HashTable<K, const K, SetKeyOfT, Hash>;
using iterator = typename HT::iterator;
using const_iterator = typename HT::const_iterator;
using Self = typename unordered_set<K, Hash>;
//支持默认构造
unordered_set() = default;
//拷贝构造
unordered_set(const Self& set)
{
_ht = set._ht;
}
//移动构造
unordered_set(Self&& set)
{
_ht.swap(set._ht);
}
//拷贝赋值
Self& operator=(const Self& set)
{
_ht = set._ht;
return *this;
}
//移动复赋值
Self& operator=(Self&& set)
{
_ht.swap(set._ht);
return *this;
}
bool count(const K& key) const
{
return find(key) != end();
}
iterator find(const K& key)
{
return _ht.find(key);
}
const_iterator find(const K& key) const
{
return _ht.find(key);
}
std::pair<iterator, bool> insert(const K& val)
{
return _ht.insert(val);
}
bool erase(const K& key)
{
return _ht.erase(key);
}
iterator erase(const_iterator pos)
{
return _ht.erase(pos);
}
iterator begin()
{
return _ht.begin();
}
const_iterator begin() const
{
return _ht.cbegin();
}
const_iterator cbegin() const
{
return _ht.cbegin();
}
iterator end()
{
return _ht.end();
}
const_iterator end() const
{
return _ht.cend();
}
const_iterator cend() const
{
return _ht.cend();
}
private:
HT _ht;
};
}
2.5 unordered_map 模拟实现
operator[] ()
mapped_type& operator[] ( const key_type& k );
mapped_type& operator[] ( key_type&& k );
这个函数的作用是:查找Key
值所对应的Value
,这分为两种情况:
Key
值不存在,那么该函数就会直接向hash
中以Key
为键值插入一个新的键值对,然后返回这个键值对的Value
Key
值存在,那么就返回该Key
值对应的Value
我们可以直接利用insert
的返回值来实现:
V& operator[](const K& key)
{
//无论inset成功插入与否,其都会返回一个指向key值的迭代器
std::pair<iterator, bool> p = insert({ key, V() });
return p.first->second;
}
整体实现
namespace lwj
{
using namespace open_hash;
template <class K, class V, class Hash = HashFunc<const K>>
class unordered_map
{
struct MapKeyOfT
{
const K operator()(const std::pair<const K, V>& p) const
{
return p.first;
}
};
public:
using HT = typename HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>;
using iterator = typename HT::iterator;
using const_iterator = typename HT::const_iterator;
using Self = typename unordered_map<K, V, Hash>;
//支持默认构造
unordered_map() = default;
//拷贝构造
unordered_map(const Self& map)
{
_ht = map._ht;
}
//移动构造
unordered_map(Self&& map)
{
_ht.swap(map._ht);
}
//拷贝赋值
Self& operator=(const Self& map)
{
_ht = map._ht;
return *this;
}
//移动赋值
Self& operator=(Self&& map)
{
_ht.swap(map._ht);
return *this;
}
V& operator[](const K& key)
{
std::pair<iterator, bool> p = insert({ key, V() });
return p.first->second;
}
bool count(const K& key) const
{
return find(key) != end();
}
iterator find(const K& key)
{
return _ht.find(key);
}
const_iterator find(const K& key) const
{
return _ht.find(key);
}
std::pair<iterator, bool> insert(const std::pair<const K, V>& val)
{
return _ht.insert(val);
}
bool erase(const K& key)
{
return _ht.erase(key);
}
iterator erase(const_iterator pos)
{
return _ht.erase(pos);
}
iterator begin()
{
return _ht.begin();
}
const_iterator begin() const
{
return _ht.cbegin();
}
iterator end()
{
return _ht.end();
}
const_iterator end() const
{
return _ht.cend();
}
private:
HT _ht;
};
}