C++进阶——封装哈希表实现unordered_map/set
与红黑树封装map/set基本相似，只是unordered_map/set是单向迭代器，模板多传一个HashFunc。
目录
1、源码及框架分析
2、模拟实现unordered_map/set
2.1 复用的哈希表框架及Insert
2.2 iterator的实现
2.2.1 iteartor的核心源码
2.2.2 iterator的实现思路
2.3 map支持[ ]
2.4 UnorderedMap/Set的代码实现
2.4.1 UnorderedMap.h
2.4.2 UnorderedSet.h
2.4.3 HashTable.h
2.4.4 Test.cpp
1、源码及框架分析
SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，只是容器的名字是hash_map和hash_set，它们是作为非标准的容器出现的，非标准是指非C++标准规定必须实现的，源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中。hash_map和hash_set的实现结构框架核心部分截取出来如下：
// stl_hash_set
template <class Value, class HashFcn = hash<Value>,
class EqualKey = equal_to<Value>,
class Alloc = alloc>
class hash_set
{
private:
typedef hashtable<Value, Value, HashFcn, identity<Value>,
EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::const_iterator iterator;
typedef typename ht::const_iterator const_iterator;
hasher hash_funct() const { return rep.hash_funct(); }
key_equal key_eq() const { return rep.key_eq(); }
};
// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>,
class EqualKey = equal_to<Key>,
class Alloc = alloc>
class hash_map
{
private:
typedef hashtable<pair<const Key, T>, Key, HashFcn,
select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef T data_type;
typedef T mapped_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::iterator iterator;
typedef typename ht::const_iterator const_iterator;
};
// stl_hashtable.h
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc>
class hashtable {
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher;
typedef EqualKey key_equal;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node;
vector<node*,Alloc> buckets;
size_type num_elements;
public:
typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
Alloc> iterator;
pair<iterator, bool> insert_unique(const value_type& obj);
const_iterator find(const key_type& key) const;
};
template <class Value>
struct __hashtable_node
{
__hashtable_node* next;
Value val;
};
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc>
class hashtable {}；
插入用Value，删除查找用Key，ExtractKey是一个仿函数，取Value中的Key值。
2、模拟实现unordered_map/set
2.1 复用的哈希表框架及Insert
1. 这里相比源码调整一下，key参数就用K，value参数就用V，哈希表中的数据类型，我们使用T。
2. 哈希表只需要比较key，那么UnorderedMap和UnorderedSet各自传一个仿函数KfromT，UnorderedSet是为了兼容UnorderedMap，所以也要实现。
3. const保证了不能修改key。Hash是传给哈希表的哈希函数。
HashTable<K, pair<const K, V>, MapKfromT,Hash> _t;
HashTable<K, const K, SetKfromT,Hash> _t;
template<class K, class T, class KfromT,class Hash>
class HashTable{}；
#include "HashTable.h"
namespace Lzc
{
// class Hash = HashFunc<K>，要通过封装的一层去控制底层的逻辑，
template<class K, class V, class Hash = HashFunc<K>>
class UnorderedMap
{
struct MapKfromT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
private:
HashTable<K, pair<const K, V>, MapKfromT, Hash> _ht;
};
}
#include "HashTable.h"
namespace Lzc
{
template<class K, class Hash = HashFunc<K>>
class UnorderedSet
{
struct SetKfromT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
private:
HashTable<K, const K, SetKfromT, Hash> _ht;
};
}
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
// hash_bucket
namespace Lzc
{
inline size_t __stl_next_prime(size_t n) {
static const int __stl_num_primes = 28;
static const size_t __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const size_t* first = __stl_prime_list;
const size_t* last = __stl_prime_list + __stl_num_primes;
const size_t* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFunc<string>
{
// 字符串转换成整形，可以把字符ASCII码相加即可
// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
// 这里使用BKDR哈希，用上次的计算结果去乘以一个质数，
// 这个质数一般取31, 131等效果会比较好
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto& ch : key)
{
hash = hash * 131 + ch;
}
return hash;
}
};
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
template<class K, class T, class KfromT, class Hash>
class HashTable
{
typedef HashNode<T> Node;
public:
KfromT KfT;
Hash hash;
HashTable()
:_table(__stl_next_prime(0), nullptr)
, _n(0)
{
}
HashTable(const HashTable& ht)
:_table(ht._table.size(), nullptr)
, _n(0)
{
for (int i = 0; i < ht._table.size(); ++i)
{
Node* cur = ht._table[i];
while (cur)
{
Insert(cur->_data);
cur = cur->_next;
}
}
}
HashTable& operator=(const HashTable& ht)
{
if (this != &ht)
{
HashTable tmp(ht);
swap(_table, tmp._table);
swap(_n, tmp._n);
}
return *this;
}
~HashTable()
{
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
_n = 0;
}
bool Insert(const T& data)
{
if (Find(KfT(data)))
return false;
// 负载因子>=1扩容
if (_n >= _table.size())
{
vector<Node*> newtable(__stl_next_prime(_table.size() + 1), nullptr);
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t hash0 = hash(KfT(cur->_data)) % newtable.size();
cur->_next = newtable[hash0]; // 头插
newtable[hash0] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable);
}
size_t hashi = hash(KfT(data)) % _table.size();
Node* newnode = new Node(data);
newnode->_next = _table[hashi];// 头插
_table[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key)
{
size_t hashi = hash(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (KfT(cur->_data) == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
size_t hashi = hash(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (KfT(cur->_data) == key)
{
if (prev)
prev->_next = cur->_next;
else
_table[hashi] = cur->_next;
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _table;
size_t _n;
};
}
2.2 iterator的实现
2.2.1 iteartor的核心源码
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
node* cur;
hashtable* ht;
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};
template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
const node* old = cur;
cur = cur->next;
if (!cur) {
size_type bucket = ht->bkt_num(old->val);
while (!cur && ++bucket < ht->buckets.size())
cur = ht->buckets[bucket];
}
return *this;
}2.2.2 iterator的实现思路
1. 整体思路与list的iterator一致，封装节点的指针，迭代器类模板多传Ref和Ptr两个参数，一份模板实现iterator和const_iterator。
2. iterator是一个单向迭代器，只能++(因为是哈希桶，桶中是单链表)，如果++，这个桶遍历完了，如何找到下一个桶呢？
源码是传一个HashTable的指针，可是，只用传vector<Node*>，继续向后找就行了，
所以我们传vector<Node*>。const vector<Node*>，是不允许改变vector中的指针。
3. begin()就是最左非空节点，end()是nullptr。
4. const 对象的const迭代器不能修改数据，所以
typedef HTIterator<T, T&, T*, Node*, KfromT, Hash> Iterator;
typedef HTIterator<T, const T&, const T*, const Node*, KfromT, Hash> ConstIterator;
template<class T, class Ref, class Ptr, class NodePtr, class KfromT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<T, Ref, Ptr, NodePtr, KfromT, Hash> Self;
typedef HTIterator<T, T&, T*, Node*, KfromT, Hash> Iterator;
KfromT KfT;
Hash hash;
HTIterator(NodePtr node, const vector<NodePtr>& table)
:_node(node)
, _table(table)
{
}
HTIterator(const Iterator& it)
:_node(it._node)
, _table(it._table)
{
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
// 找下一个不为空的桶
size_t hashi = hash(KfT(_node->_data)) % _table.size();
++hashi;
while (hashi < _table.size() && _table[hashi] == nullptr)
{
++hashi;
}
if (hashi == _table.size())
_node = nullptr;
else
_node = _table[hashi];
}
return *this;
}
Ref operator*()
{
assert(_node);
return _node->_data;
}
Ptr operator->()
{
assert(_node);
return &(_node->_data);
}
bool operator==(const HTIterator& htit) const
{
return _node == htit._node;
}
bool operator!=(const HTIterator& htit) const
{
return _node != htit._node;
}
NodePtr _node;
// 找下一个桶，普通迭代器可以修改元素值但不能修改容器结构(增删元素)。
const vector<NodePtr>& _table;
};
2.3 map支持[ ]
UnorderedMap要支持[ ]主要需要修改Insert返回值，
修改HashTable中的insert返回值为pair<Iterator,bool> Insert(const T& data)，
插入失败，就返回相同的key的value的引用。
插入成功，就返回key的value(默认值)的引用。
2.4 UnorderedMap/Set的代码实现
2.4.1 UnorderedMap.h
#pragma once
#include "HashTable.h"
namespace Lzc
{
// class Hash = HashFunc<K>，要通过封装的一层去控制底层的逻辑，
template<class K, class V, class Hash = HashFunc<K>>
class UnorderedMap
{
struct MapKfromT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKfromT, Hash>::Iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKfromT, Hash>::ConstIterator const_iterator;
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
iterator ret = _ht.Insert({ key, V() }).first;
return ret->second;
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
const_iterator find(const K& key) const
{
return _ht.Find(key);
}
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
const_iterator begin() const
{
return _ht.Begin();
}
const_iterator end() const
{
return _ht.End();
}
private:
HashTable<K, pair<const K, V>, MapKfromT, Hash> _ht;
};
}2.4.2 UnorderedSet.h
#pragma once
#include "HashTable.h"
namespace Lzc
{
template<class K, class Hash = HashFunc<K>>
class UnorderedSet
{
struct SetKfromT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, const K, SetKfromT, Hash>::Iterator iterator;
typedef typename HashTable<K, const K, SetKfromT, Hash>::ConstIterator const_iterator;
pair<iterator, bool> insert(const K& kv)
{
return _ht.Insert(kv);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
const_iterator find(const K& key) const
{
return _ht.Find(key);
}
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
const_iterator begin() const
{
return _ht.Begin();
}
const_iterator end() const
{
return _ht.End();
}
private:
HashTable<K, const K, SetKfromT, Hash> _ht;
};
}2.4.3 HashTable.h
#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
// hash_bucket
namespace Lzc
{
inline size_t __stl_next_prime(size_t n) {
static const int __stl_num_primes = 28;
static const size_t __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const size_t* first = __stl_prime_list;
const size_t* last = __stl_prime_list + __stl_num_primes;
const size_t* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFunc<string>
{
// 字符串转换成整形，可以把字符ASCII码相加即可
// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
// 这里使用BKDR哈希，用上次的计算结果去乘以一个质数，
// 这个质数一般取31, 131等效果会比较好
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto& ch : key)
{
hash = hash * 131 + ch;
}
return hash;
}
};
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
template<class T, class Ref, class Ptr, class NodePtr, class KfromT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<T, Ref, Ptr, NodePtr, KfromT, Hash> Self;
typedef HTIterator<T, T&, T*, Node*, KfromT, Hash> Iterator;
KfromT KfT;
Hash hash;
HTIterator(NodePtr node, const vector<NodePtr>& table)
:_node(node)
, _table(table)
{
}
HTIterator(const Iterator& it)
:_node(it._node)
, _table(it._table)
{
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
// 找下一个不为空的桶
size_t hashi = hash(KfT(_node->_data)) % _table.size();
++hashi;
while (hashi < _table.size() && _table[hashi] == nullptr)
{
++hashi;
}
if (hashi == _table.size())
_node = nullptr;
else
_node = _table[hashi];
}
return *this;
}
Ref operator*()
{
assert(_node);
return _node->_data;
}
Ptr operator->()
{
assert(_node);
return &(_node->_data);
}
bool operator==(const HTIterator& htit) const
{
return _node == htit._node;
}
bool operator!=(const HTIterator& htit) const
{
return _node != htit._node;
}
NodePtr _node;
// 找下一个桶，普通迭代器可以修改元素值但不能修改容器结构(增删元素)。
const vector<NodePtr>& _table;
};
template<class K, class T, class KfromT, class Hash>
class HashTable
{
typedef HashNode<T> Node;
public:
typedef HTIterator<T, T&, T*, Node*, KfromT, Hash> Iterator;
typedef HTIterator<T, const T&, const T*, const Node*, KfromT, Hash> ConstIterator;
KfromT KfT;
Hash hash;
HashTable()
:_table(__stl_next_prime(0), nullptr)
, _n(0)
{
}
HashTable(const HashTable& ht)
:_table(ht._table.size(), nullptr)
, _n(0)
{
for (int i = 0; i < ht._table.size(); ++i)
{
Node* cur = ht._table[i];
while (cur)
{
Insert(cur->_data);
cur = cur->_next;
}
}
}
HashTable& operator=(const HashTable& ht)
{
if (this != &ht)
{
HashTable tmp(ht);
swap(_table, tmp._table);
swap(_n, tmp._n);
}
return *this;
}
~HashTable()
{
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
_n = 0;
}
Iterator Begin()
{
for (int i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
if (cur)
return Iterator(cur, _table);
}
return Iterator(nullptr, _table);
}
Iterator End()
{
return Iterator(nullptr, _table);
}
ConstIterator Begin() const
{
for (int i = 0; i < _table.size(); ++i)
{
const Node* cur = _table[i];
if (cur)
return ConstIterator(cur, _table);
}
return ConstIterator(nullptr, _table);
}
ConstIterator End() const
{
return ConstIterator(nullptr, _table);
}
pair<Iterator, bool> Insert(const T& data)
{
Iterator it = Find(KfT(data));
if (it != End())
return { it,false };
// 负载因子>=1扩容
if (_n >= _table.size())
{
vector<Node*> newtable(__stl_next_prime(_table.size() + 1), nullptr);
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t hash0 = hash(KfT(cur->_data)) % newtable.size();
cur->_next = newtable[hash0]; // 头插
newtable[hash0] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable);
}
size_t hashi = hash(KfT(data)) % _table.size();
Node* newnode = new Node(data);
newnode->_next = _table[hashi];// 头插
_table[hashi] = newnode;
++_n;
return { Iterator(newnode,_table),true };
}
Iterator Find(const K& key)
{
size_t hashi = hash(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (KfT(cur->_data) == key)
return Iterator(cur, _table);
cur = cur->_next;
}
return Iterator(nullptr, _table);
}
ConstIterator Find(const K& key) const
{
size_t hashi = hash(key) % _table.size();
const Node* cur = _table[hashi];
while (cur)
{
if (KfT(cur->_data) == key)
return ConstIterator(cur, _table);
cur = cur->_next;
}
return ConstIterator(nullptr, _table);
}
bool Erase(const K& key)
{
size_t hashi = hash(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (KfT(cur->_data) == key)
{
if (prev)
prev->_next = cur->_next;
else
_table[hashi] = cur->_next;
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _table;
size_t _n;
};
}
2.4.4 Test.cpp
//#include "HashTable.h"
#include "UnorderedMap.h"
#include "UnorderedSet.h"
struct SetKfromT
{
const int& operator()(const int& key)
{
return key;
}
};
void TestHashTableBasic() {
Lzc::HashTable<int, int, SetKfromT, Lzc::HashFunc<int>> ht;
// 插入测试
assert(ht.Insert(1).second == true); // 首次插入成功
assert(ht.Insert(1).second == false); // 重复插入失败
// 查找测试
auto it = ht.Find(1);
assert(it != ht.End() && *it == 1); // 能找到已插入的值
assert(ht.Find(2) == ht.End()); // 找不到未插入的值
}
void TestHashTableRehash() {
Lzc::HashTable<int, int, SetKfromT, Lzc::HashFunc<int>> ht;
// 插入足够多的数据触发扩容
for (int i = 0; i < 100; ++i) {
ht.Insert(i);
}
// 验证所有数据仍可找到
for (int i = 0; i < 100; ++i) {
assert(ht.Find(i) != ht.End());
}
}
void TestHashTableErase() {
Lzc::HashTable<int, int, SetKfromT, Lzc::HashFunc<int>> ht;
ht.Insert(1);
ht.Insert(2);
assert(ht.Erase(1) == true); // 删除存在的键
assert(ht.Find(1) == ht.End()); // 确认删除成功
assert(ht.Erase(3) == false); // 删除不存在的键
}
void TestUnorderedMapInsert() {
Lzc::UnorderedMap<int, string> map;
// 插入测试
auto it1 = map.insert({ 1, "one" });
assert(it1.second == true && (it1.first)->second == "one");
auto it2 = map.insert({ 1, "uno" });
assert(it2.second == false && (it2.first)->second == "one"); // 重复插入失败
// operator[] 测试
map[2] = "two";
assert(map[2] == "two"); // 修改值
assert(map[3] == ""); // 自动插入默认值
}
void TestUnorderedMapIteration() {
Lzc::UnorderedMap<int, string> map;
map.insert({ 1, "one" });
map.insert({ 2, "two" });
// 范围for遍历
for (const auto& e : map) {
assert((e.first == 1 && e.second == "one") || (e.first == 2 && e.second == "two"));
}
}
void TestUnorderedMapCopy() {
Lzc::UnorderedMap<int, string> map1;
map1.insert({ 1, "one" });
// 拷贝构造
auto map2 = map1;
assert(map2.find(1)->second == "one");
// 赋值操作
Lzc::UnorderedMap<int, string> map3;
map3 = map1;
assert(map3.find(1) != map3.end());
}
void TestUnorderedSetInsert() {
Lzc::UnorderedSet<int> set;
assert(set.insert(1).second == true); // 首次插入成功
assert(set.insert(1).second == false); // 重复插入失败
assert(set.find(1) != set.end());
}
void TestUnorderedSetErase() {
Lzc::UnorderedSet<int> set;
set.insert(1);
set.insert(2);
assert(set.erase(1) == true); // 删除存在的键
assert(set.find(1) == set.end());
assert(set.erase(3) == false); // 删除不存在的键
}
void TestUnorderedSetEdgeCases() {
Lzc::UnorderedSet<int> empty_set;
// 空表测试
assert(empty_set.find(1) == empty_set.end());
assert(empty_set.erase(1) == false);
// 插入大量数据
for (int i = 0; i < 1000; ++i) {
empty_set.insert(i);
}
assert(empty_set.find(999) != empty_set.end());
}
int main() {
TestHashTableBasic();
TestHashTableRehash();
TestHashTableErase();
TestUnorderedMapInsert();
TestUnorderedMapIteration();
TestUnorderedMapCopy();
TestUnorderedSetInsert();
TestUnorderedSetErase();
TestUnorderedSetEdgeCases();
cout << "All tests passed!" << endl;
return 0;
}