前言
看这篇博客之前请先看：
C++ | 哈希表-CSDN博客💓 个人主页：普通young man-CSDN博客
⏩ 文章专栏：C++_普通young man的博客-CSDN博客
⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
————————————————
目录
模拟实现unordered_map和unordered_set
insert方法的实现
Hashtable类中的Insert方法
unordered_map和unordered_set中的insert方法
迭代器iterator的实现
HTIterator类
unordered_map和unordered_set中的迭代器
map支持[]运算符
unordered_map中的[]运算符
完整代码实现
Hashtable.h
unordered_map
unordered_set
本篇博客需要讲解的比较少，主要是配合上文写的
模拟实现unordered_map和unordered_set
insert方法的实现
Hashtable类中的Insert方法
Hashtable类的Insert方法用于向哈希表中插入一个新元素。其实现步骤如下：
pair<Iterator,bool> Insert(const T& data) {
// 利用仿函数比较
Hash hash;
KeyOfT koft;
// 判断是否存在
Iterator it = Find(koft(data));
if (it != End()) {
return { it, false };
}
// 扩容
if (_tables.size() == _n) {
// 创建一个哈希表
vector<Node*> new_tables(__stl_next_prime(_tables.size() + 1));
// 遍历旧哈希表
for (int i = 0; i < _tables.size(); i++) {
// cur指向每一个元素，方便遍历哈希桶
Node* cur = _tables[i];
// 遍历桶
while (cur) {
// 计算新表的哈希值
size_t new_hashi = hash(koft(cur->_data)) % new_tables.size();
// 存储下一个节点
Node* next = cur->_next;
// 插入节点
cur->_next = new_tables[new_hashi];
new_tables[new_hashi] = cur;
// 将下一个节点给cur,持续插入
cur = next;
}
}
// 交换指针
_tables.swap(new_tables);
}
// 计算哈希值
size_t hashi = hash(koft(data)) % _tables.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
// 增加个数
++_n;
return { Iterator(newnode, this), true };
}- 检查元素是否已存在：使用
Find方法查找要插入的元素是否已经存在于哈希表中。如果存在，则直接返回该元素的迭代器和false。 - 扩容操作：当哈希表的负载因子（元素个数
_n与哈希桶数量_tables.size()之比）达到 1 时，需要进行扩容。扩容步骤如下：- 创建一个新的更大的哈希表
new_tables。 - 遍历旧哈希表中的每个元素，将其重新插入到新哈希表中。
- 交换旧哈希表和新哈希表的指针。
- 创建一个新的更大的哈希表
- 插入新元素：计算新元素的哈希值，使用头插法将新元素插入到对应的哈希桶中。
- 返回结果：返回新插入元素的迭代器和
true。
unordered_map和unordered_set中的insert方法
unordered_map和unordered_set中的insert方法只是简单地调用了Hashtable类的Insert方法：
// unordered_map
pair<iterator, bool> insert(const pair<K,V>& key) {
return _ht.Insert(key);
}
// unordered_set
pair<iterator, bool> insert(const K& key) {
return _ht.Insert(key);
}迭代器iterator的实现
HTIterator类
HTIterator类是哈希表的迭代器类，用于遍历哈希表中的元素。其实现步骤如下：
// 模板参数说明：
// K 表示键的类型
// T 表示存储在哈希表中的数据类型
// Ref 表示对数据的引用类型（例如 T& 或 const T&）
// Ptr 表示指向数据的指针类型（例如 T* 或 const T*）
// Hash 是一个哈希函数对象类型，用于计算键的哈希值
// KeyOfT 是一个函数对象类型，用于从存储的数据中提取键
template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
struct HTIterator {
// 定义哈希表类型，方便后续使用
typedef Hashtable<K, T, Hash, KeyOfT> HT;
// 定义节点类型，方便后续使用
typedef Hashnode<T> Node;
// 定义迭代器自身类型，方便后续使用
typedef HTIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
// 指向哈希表的指针，用于访问哈希表的成员（如哈希桶数组等）
const HT* _ht;
// 指向当前节点的指针，用于操作当前节点的数据
Node* _node;
// 构造函数，用于初始化迭代器
// 参数 node 是当前节点的指针
// 参数 ht 是指向哈希表的指针
HTIterator(Node* node, const HT* ht) :
_node(node),
_ht(ht)
{}
// 重载解引用运算符 *，用于获取当前节点的数据的引用
// 当使用 *it（it 是迭代器对象）时，返回当前节点存储的数据的引用
Ref operator*() {
return _node->_data;
}
// 重载箭头运算符 ->，用于获取当前节点的数据的指针
// 当使用 it->（it 是迭代器对象）时，返回当前节点存储的数据的指针
Ptr operator->() {
return &_node->_data;
}
// 重载不等运算符 !=，用于比较两个迭代器是否指向不同的节点
// 参数 s 是另一个迭代器对象
// 如果两个迭代器指向的节点不同，返回 true，否则返回 false
bool operator!=(const Self& s) {
return _node != s._node;
}
// 重载前置自增运算符 ++，用于将迭代器移动到下一个元素
// 返回移动后的迭代器自身
Self operator++() {
// 如果当前节点有下一个节点，将迭代器移动到下一个节点
if (_node->_next) {
_node = _node->_next;
}
else {
// 计算当前节点数据的键的哈希值
Hash hash;
KeyOfT koft;
size_t hashi = hash(koft(_node->_data)) % _ht->_tables.size();
// 从下一个哈希桶位置开始查找
hashi++;
// 遍历哈希桶，直到找到一个有数据的桶或者遍历完所有桶
while (hashi < _ht->_tables.size()) {
_node = _ht->_tables[hashi];
if (_node)
break;
else
hashi++;
}
// 如果遍历完所有桶都没有找到有数据的桶，将节点指针置为 nullptr
if (hashi == _ht->_tables.size()) {
_node = nullptr;
}
}
return *this;
}
};- 构造函数：初始化迭代器的节点指针
_node和哈希表指针_ht。 - 解引用运算符
*：返回当前节点的数据引用。 - 箭头运算符
->：返回当前节点的数据指针。 - 不等运算符
!=：比较两个迭代器是否指向不同的节点。 - 前置自增运算符
++：将迭代器移动到下一个元素。如果当前桶还有数据，则移动到当前桶的下一个节点；否则，从下一个桶开始查找，直到找到有数据的桶或遍历完所有桶。
unordered_map和unordered_set中的迭代器
unordered_map和unordered_set中的迭代器是通过Hashtable类的迭代器实现的：
// unordered_map
typedef typename hash_bucket::Hashtable<K, pair<const K,V>, Hash, MapKeyOfT>::Iterator iterator;
typedef typename hash_bucket::Hashtable<K, pair<const K, V>, Hash, MapKeyOfT >::ConstIterator const_iterator;
// unordered_set
typedef typename hash_bucket::Hashtable<K, const K,Hash,SetKeyOfT>::Iterator iterator;
typedef typename hash_bucket::Hashtable<K, const K,Hash ,SetKeyOfT >::ConstIterator const_iterator;map支持[]运算符
unordered_map中的[]运算符
unordered_map中的[]运算符用于通过键访问或插入元素。其实现步骤如下：
V& operator[](const K& key) {
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}- 入元素：调用
insert方法插入一个键值对{ key, V() }。如果键已经存在，则insert方法会返回该元素的迭代器和false；否则，会插入一个新元素并返回该元素的迭代器和true。 - 返回值：返回插入元素的值的引用。
通过这种方式，[]运算符可以实现以下功能：
- 如果键已经存在，则返回该键对应的值的引用。
- 如果键不存在，则插入一个新的键值对，值为默认构造的
V()，并返回该值的引用。
完整代码实现
Hashtable.h
// 防止头文件被重复包含
#pragma once
#include<iostream>
#include<vector>
// 使用标准命名空间，方便使用标准库中的类和函数
using namespace std;
// 该函数用于获取大于等于给定值 n 的下一个质数
// 质数常用于哈希表的容量设置，可减少哈希冲突
inline unsigned long __stl_next_prime(unsigned long n)
{
// 假设 long 至少为 32 位
// 定义质数列表中质数的数量
static const int __stl_num_primes = 28;
// 预定义的质数列表，这些质数会作为哈希表扩容时的容量选择
static const unsigned long __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
};
// first 指向质数列表的起始位置
const unsigned long* first = __stl_prime_list;
// last 指向质数列表的结束位置
const unsigned long* last = __stl_prime_list + __stl_num_primes;
// 使用 lower_bound 函数在质数列表中查找第一个不小于 n 的质数
// lower_bound 是标准库函数，采用二分查找，效率较高
const unsigned long* pos = lower_bound(first, last, n);
// 如果没有找到比 n 大的质数，返回列表中最后一个质数；否则返回找到的质数
return pos == last ? *(last - 1) : *pos;
}
// 仿函数模板，用于将键 k 转换为无符号整数类型，默认实现是直接转换
// 这个仿函数在计算哈希值时会用到
template<class k>
struct HashFun
{
// 重载 () 运算符，将键转换为 size_t 类型
size_t operator()(const k& key) {
return (size_t)key;
}
};
// 针对 string 类型的 HashFun 特化版本
// 使用 BKDR 哈希算法将字符串转换为哈希值，减少哈希冲突
template<>
struct HashFun<string>
{
size_t operator()(const string& key) {
size_t hash = 0;
// 利用 BKDR 算法计算字符串的哈希值
for (auto it : key)
{
hash += it;
hash *= 131;
}
return hash;
}
};
// 链地址法实现的哈希表命名空间
namespace hash_bucket {
// 哈希表节点结构体，存储数据和指向下一个节点的指针
template<class T>
struct Hashnode
{
T _data;
Hashnode<T>* _next;
// 构造函数，初始化节点数据，指向下一个节点的指针置为 nullptr
Hashnode(const T& data)
:
_data(data),
_next(nullptr)
{}
};
// 前置声明 Hashtable 类，以便在迭代器类中使用
template<class K, class T, class Hash, class KeyOfT>
class Hashtable;
// 哈希表迭代器结构体，用于遍历哈希表中的元素
template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
struct HTIterator
{
// 定义哈希表类型，方便后续使用
typedef Hashtable<K, T, Hash, KeyOfT> HT;
// 定义节点类型，方便后续使用
typedef Hashnode<T> Node;
// 定义迭代器自身类型，方便后续使用
typedef HTIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
// 指向哈希表的指针，用于访问哈希表的成员（如哈希桶数组等）
const HT* _ht;
// 指向当前节点的指针，用于操作当前节点的数据
Node* _node;
// 构造函数，初始化迭代器的节点指针和哈希表指针
HTIterator(Node* node, const HT* ht) :
_node(node),
_ht(ht)
{}
// 重载解引用运算符 *，用于获取当前节点的数据的引用
Ref operator*() {
return _node->_data;
}
// 重载箭头运算符 ->，用于获取当前节点的数据的指针
Ptr operator->() {
return &_node->_data;
}
// 重载不等运算符 !=，用于比较两个迭代器是否指向不同的节点
bool operator!=(const Self& s) {
return _node != s._node;
}
// 重载前置自增运算符 ++，用于将迭代器移动到下一个元素
Self operator++() {
// 如果当前节点有下一个节点，将迭代器移动到下一个节点
if (_node->_next) {
_node = _node->_next;
}
else {
// 计算当前节点数据的键的哈希值
Hash hash;
KeyOfT koft;
size_t hashi = hash(koft(_node->_data)) % _ht->_tables.size();
// 从下一个哈希桶位置开始查找
hashi++;
// 遍历哈希桶，直到找到一个有数据的桶或者遍历完所有桶
while (hashi < _ht->_tables.size()) {
_node = _ht->_tables[hashi];
// 如果找到有数据的桶，跳出循环
if (_node)
break;
else
// 不断增加哈希桶位置，继续查找
hashi++;
}
// 如果遍历完所有桶都没有找到有数据的桶，将节点指针置为 nullptr
if (hashi == _ht->_tables.size()) {
_node = nullptr;
}
}
return *this;
}
};
// 哈希表类，使用链地址法解决哈希冲突
template<class K, class T, class Hash, class KeyOfT>
class Hashtable
{
// 友元声明，允许迭代器类访问 Hashtable 的私有成员
template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
friend struct HTIterator;
// 定义节点类型，方便后续使用
typedef Hashnode<T> Node;
public:
// 定义普通迭代器类型
typedef HTIterator<K, T, T&, T*, Hash, KeyOfT> Iterator;
// 定义常量迭代器类型
typedef HTIterator<K, T, const T&, const T*, Hash, KeyOfT> ConstIterator;
// 返回指向哈希表第一个元素的迭代器
Iterator Begin() {
// 如果哈希表中没有元素，直接返回 End 迭代器
if (_n == 0) return End();
// 遍历哈希桶数组，找到第一个有数据的桶
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
if (cur) {
return Iterator(cur, this);
}
}
// 如果没有找到有数据的桶，返回 End 迭代器
return End();
}
// 返回指向哈希表末尾的迭代器
Iterator End() {
return Iterator(nullptr, this);
}
// 常量版本的 Begin 方法，返回常量迭代器
ConstIterator Begin() const {
// 如果哈希表中没有元素，直接返回 End 迭代器
if (_n == 0) return End();
// 遍历哈希桶数组，找到第一个有数据的桶
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
if (cur) {
return ConstIterator(cur, this);
}
}
// 如果没有找到有数据的桶，返回 End 迭代器
return End();
}
// 常量版本的 End 方法，返回常量迭代器
ConstIterator End() const {
return ConstIterator(nullptr, this);
}
// 构造函数，初始化哈希表，使用下一个质数作为初始大小
Hashtable() :
_tables(__stl_next_prime(0)),
_n(0)
{};
// 析构函数，释放哈希表中所有节点的内存
~Hashtable() {
// 遍历哈希桶数组
for (int i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 遍历当前桶中的所有节点
while (cur)
{
// 存储下一个节点
Node* next = cur->_next;
// 释放当前节点的内存
delete cur;
// 将下一个节点赋值给 cur，继续释放
cur = next;
}
// 将当前桶的指针置为 nullptr
_tables[i] = nullptr;
}
// 将元素个数置为 0
_n = 0;
}
// 拷贝构造函数，复制另一个哈希表的内容
Hashtable(const Hashtable& m1) :
_n(m1._n),
_tables(m1._tables.size())
{
// 循环遍历每一个桶
for (int i = 0; i < m1._tables.size(); i++)
{
Node* cur = m1._tables[i];
// 遍历当前桶中的所有节点
while (cur)
{
// 创建一个新节点，复制当前节点的数据
Node* newnode = new Node(cur->_data);
// 使用头插法将新节点插入到当前桶中
newnode->_next = _tables[i];
_tables[i] = newnode;
// 移动到下一个节点
cur = cur->_next;
}
}
}
// 赋值运算符重载，使用拷贝交换技术实现赋值操作
Hashtable& operator=(Hashtable tmp)
{
// 交换哈希桶数组
_tables.swap(tmp._tables);
// 交换元素个数
std::swap(_n, tmp._n);
return *this;
}
// 向哈希表中插入一个元素
pair<Iterator, bool> Insert(const T& data) {
// 创建哈希函数对象
Hash hash;
// 创建从数据中提取键的函数对象
KeyOfT koft;
// 判断要插入的元素是否已经存在于哈希表中
Iterator it = Find(koft(data));
if (it != End()) {
// 如果元素已经存在，返回该元素的迭代器和 false
return { it, false };
}
// 扩容判断
// 当哈希表的负载因子（元素个数与哈希桶数量之比）达到 1 时，需要扩容
if (_tables.size() == _n) {
// 创建一个新的哈希表，容量为下一个质数
vector<Node*> new_tables(__stl_next_prime(_tables.size() + 1));
// 遍历旧哈希表的每个桶
for (int i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 遍历当前桶中的所有节点
while (cur)
{
// 计算节点在新哈希表中的哈希值
size_t new_hashi = hash(koft(cur->_data)) % new_tables.size();
// 存储下一个节点
Node* next = cur->_next;
// 使用头插法将节点插入到新哈希表的对应桶中
cur->_next = new_tables[new_hashi];
new_tables[new_hashi] = cur;
// 移动到下一个节点
cur = next;
}
}
// 交换旧哈希表和新哈希表的指针
_tables.swap(new_tables);
}
// 计算要插入元素在当前哈希表中的哈希值
size_t hashi = hash(koft(data)) % _tables.size();
// 创建一个新节点，存储要插入的元素
Node* newnode = new Node(data);
// 使用头插法将新节点插入到对应桶中
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
// 元素个数加 1
++_n;
// 返回新插入元素的迭代器和 true
return { Iterator(newnode, this), true };
}
// 在哈希表中查找指定键的元素
Iterator Find(const K& key) {
// 创建从数据中提取键的函数对象
KeyOfT koft;
// 创建哈希函数对象
Hash hash;
// 计算要查找元素的哈希值
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
// 遍历对应桶中的所有节点
while (cur)
{
if (koft(cur->_data) == key)
{
// 如果找到匹配的元素，返回该元素的迭代器
return Iterator(cur, this);
}
cur = cur->_next;
}
// 如果没有找到匹配的元素，返回 End 迭代器
return End();
}
// 从哈希表中删除指定键的元素
bool Erase(const K& key) {
// 创建从数据中提取键的函数对象
KeyOfT koft;
// 计算要删除元素的哈希值
size_t hashi = hash(key) % _tables.size();
// 记录前一个节点的指针
Node* prev = nullptr;
Node* cur = _tables[hashi];
// 遍历对应桶中的所有节点
while (cur)
{
if (koft(cur->_data) == key) {
if (prev == nullptr)
{
// 如果要删除的是第一个节点，更新桶的头指针
_tables[hashi] = cur->_next;
}
else
{
// 否则，更新前一个节点的指针
prev->_next = cur->_next;
}
// 释放要删除节点的内存
delete cur;
return true;
}
else {
// 移动前一个节点和当前节点的指针
prev = cur;
cur = cur->_next;
}
}
// 如果没有找到要删除的元素，返回 false
return false;
}
private:
// 存储哈希桶的指针数组
vector<Node*> _tables;
// 哈希表中元素的个数
size_t _n = 0;
};
}unordered_map
// 防止头文件被重复包含
#pragma once
// 包含自定义的哈希表头文件，因为 unordered_map 依赖于 Hashtable 的实现
#include"Hashtable.h"
// 自定义的命名空间，用于组织自定义的 map 和 set 相关的类和函数
namespace Map_Set_Hash {
// 定义一个模板类 unordered_map，实现类似标准库中 unordered_map 的功能
// K 表示键的类型，V 表示值的类型，Hash 是一个哈希函数对象类型，默认使用 HashFun<K>
template<class K, class V, class Hash = HashFun<K>>
class unordered_map
{
// 内部结构体 MapKeyOfT，用于从键值对中提取键
// 这在哈希表的查找、插入等操作中用于比较键
struct MapKeyOfT
{
// 重载 () 运算符，返回键值对中的键
const K& operator()(const pair<K, V>& kv) {
return kv.first;
}
};
public:
// 定义迭代器类型，使用哈希表类中的迭代器类型
// iterator 是普通迭代器类型，用于遍历和修改元素
typedef typename hash_bucket::Hashtable<K, pair<const K, V>, Hash, MapKeyOfT>::Iterator iterator;
// const_iterator 是常量迭代器类型，用于遍历元素但不能修改元素
typedef typename hash_bucket::Hashtable<K, pair<const K, V>, Hash, MapKeyOfT>::ConstIterator const_iterator;
// 迭代器方法，返回指向 unordered_map 第一个元素的迭代器
// 调用底层哈希表的 Begin 方法获取迭代器
iterator begin() {
return _ht.Begin();
}
// 迭代器方法，返回指向 unordered_map 末尾的迭代器
// 调用底层哈希表的 End 方法获取迭代器
iterator end() {
return _ht.End();
}
// 常量版本的迭代器方法，返回指向 unordered_map 第一个元素的常量迭代器
// 调用底层哈希表的 Begin 方法获取常量迭代器
const_iterator begin() const {
return _ht.Begin();
}
// 常量版本的迭代器方法，返回指向 unordered_map 末尾的常量迭代器
// 调用底层哈希表的 End 方法获取常量迭代器
const_iterator end() const {
return _ht.End();
}
// 重载 [] 运算符，用于通过键访问或插入元素
// 如果键不存在，插入一个新的键值对，值为默认构造的 V()
// 返回值的引用，方便进行赋值操作
V& operator[](const K& key) {
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
// 插入方法，向 unordered_map 中插入一个键值对
// 调用底层哈希表的 Insert 方法进行插入操作
// 返回一个 pair，包含插入元素的迭代器和插入是否成功的标志
pair<iterator, bool> insert(const pair<K, V>& key) {
return _ht.Insert(key);
}
// 查找方法，在 unordered_map 中查找指定键值对
// 调用底层哈希表的 Find 方法进行查找操作
// 返回找到元素的迭代器，如果未找到则返回 end() 迭代器
iterator find(const pair<K, V>& key) {
return _ht.Find(key);
}
// 删除方法，从 unordered_map 中删除指定键值对
// 调用底层哈希表的 Erase 方法进行删除操作
// 返回删除是否成功的标志
bool erase(const pair<K, V>& key) {
return _ht.Erase(key);
}
private:
// 底层使用的哈希表对象，存储键值对数据
// 模板参数指定了键的类型、值的类型、哈希函数对象类型和提取键的函数对象类型
hash_bucket::Hashtable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
};
// 测试函数 map_test，用于测试 unordered_map 类的功能
void map_test() {
// 创建一个键和值都是 string 类型的 unordered_map 对象 dict
unordered_map<string, string> dict;
// 向 dict 中插入一些键值对
dict.insert({ "sort", "排序" });
dict.insert({ "字符串", "string" });
// 尝试插入重复的键值对，这在哈希表中不会实际插入新元素
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
// 使用 [] 运算符修改已存在键的值，或者插入新的键值对
dict["left"] = "左边，剩余";
dict["insert"] = "插入";
dict["string"]; // 这里调用 [] 运算符创建了一个值为默认构造的键值对，但未进行赋值
// 使用范围 for 循环遍历 dict，输出每个键值对
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
// 使用迭代器遍历 dict，修改值并输出键值对
unordered_map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
// 键是 const 的，不能修改，这里是注释掉的示例代码
//it->first += 'x';
// 修改值
it->second += 'x';
cout << it->first << ":" << it->second << endl;
// 移动迭代器到下一个元素
++it;
}
cout << endl;
}
}unordered_set
// 防止头文件被重复包含
#pragma once
// 包含之前实现的哈希表的头文件，因为 unordered_set 基于该哈希表实现
#include"Hashtable.h"
namespace Map_Set_Hash {
// 定义一个模板类 unordered_set，类似于标准库中的 std::unordered_set
// K 表示集合中元素的类型，Hash 是一个哈希函数对象类型，默认使用 HashFun<K>
template<class K, class Hash = HashFun<K>>
class unordered_set {
private:
// 用于从元素中提取键的仿函数
// 对于 unordered_set 而言，元素本身就是键
struct SetKeyOfT {
// 重载 () 运算符，直接返回传入的元素
const K& operator()(const K& key) {
return key;
}
};
public:
// 定义迭代器类型
// iterator 是普通迭代器，可用于遍历和访问集合中的元素
typedef typename hash_bucket::Hashtable<K, const K, Hash, SetKeyOfT>::Iterator iterator;
// const_iterator 是常量迭代器，用于在常量对象上遍历和访问元素，不能修改元素
typedef typename hash_bucket::Hashtable<K, const K, Hash, SetKeyOfT>::ConstIterator const_iterator;
// 迭代器方法：返回指向集合第一个元素的迭代器
iterator begin() {
// 调用底层哈希表的 Begin 方法获取起始迭代器
return _ht.Begin();
}
// 迭代器方法：返回指向集合末尾（最后一个元素之后）的迭代器
iterator end() {
// 调用底层哈希表的 End 方法获取结束迭代器
return _ht.End();
}
// 常量版本的 begin 方法：返回指向常量集合第一个元素的常量迭代器
const_iterator begin() const {
// 调用底层哈希表的 Begin 方法获取常量起始迭代器
return _ht.Begin();
}
// 常量版本的 end 方法：返回指向常量集合末尾（最后一个元素之后）的常量迭代器
const_iterator end() const {
// 调用底层哈希表的 End 方法获取常量结束迭代器
return _ht.End();
}
// 插入元素到集合中
// key 是要插入的元素
// 返回一个 pair，包含插入元素的迭代器和插入是否成功的标志（如果元素已存在则插入失败）
pair<iterator, bool> insert(const K& key) {
// 调用底层哈希表的 Insert 方法进行插入操作
return _ht.Insert(key);
}
// 在集合中查找指定元素
// key 是要查找的元素
// 返回指向找到元素的迭代器，如果未找到则返回 end() 迭代器
iterator find(const K& key) {
// 调用底层哈希表的 Find 方法进行查找操作
return _ht.Find(key);
}
// 从集合中删除指定元素
// key 是要删除的元素
// 返回删除操作是否成功的标志（如果元素存在则删除成功）
bool erase(const K& key) {
// 调用底层哈希表的 Erase 方法进行删除操作
return _ht.Erase(key);
}
private:
// 底层使用的哈希表对象，存储集合中的元素
hash_bucket::Hashtable<K, const K, Hash, SetKeyOfT> _ht;
};
// 打印 unordered_set 中元素的函数
// s 是要打印的 unordered_set 常量对象
void print(const unordered_set<int>& s) {
// 使用常量迭代器遍历集合
unordered_set<int>::const_iterator it = s.begin();
while (it != s.end()) {
// 注释掉的代码试图修改元素，在 unordered_set 中元素是 const 的，不能修改
//*it = 1;
// 输出当前元素
cout << *it << " ";
// 移动迭代器到下一个元素
++it;
}
cout << endl;
// 使用范围 for 循环遍历集合并输出元素
for (auto e : s) {
cout << e << " ";
}
cout << endl;
}
// 测试 unordered_set 功能的函数
void set_test() {
// 定义一个整数数组
int a[] = { 3, 11, 86, 7, 88, 82, 1, 881, 5, 6, 7, 6 };
// 创建一个 unordered_set 对象，用于存储整数元素
unordered_set<int> s;
// 将数组中的元素插入到集合中
for (auto e : a) {
s.insert(e);
}
// 调用 print 函数打印集合中的元素
print(s);
// 使用普通迭代器遍历集合并输出元素
unordered_set<int>::iterator it = s.begin();
while (it != s.end()) {
// 注释掉的代码试图修改元素，在 unordered_set 中元素是 const 的，不能修改
//*it = 1;
cout << *it << " ";
++it;
}
cout << endl;
// 使用范围 for 循环遍历集合并输出元素
for (auto e : s) {
cout << e << " ";
}
cout << endl;
// 使用常量迭代器遍历集合并输出元素
unordered_set<int>::const_iterator st = s.begin();
while (st != s.end()) {
// 注释掉的代码试图修改元素，在 unordered_set 中元素是 const 的，不能修改
//*it = 1;
cout << *st << " ";
++st;
}
cout << endl;
}
}
