C++笔记4
·
本节将描述unordered_map的用法并自己手写一个无序map
使用unordered_map
定义与常用操作
unordered_map 是 C++ 标准库中的关联容器，提供了基于哈希表的键值对存储结构。与 map （基于红黑树实现）不同，unordered_map 提供的是平均常数时间复杂度的查找、插入和删除操作，但不保证元素的顺序
哈希表复习：王道考研 数据结构
头文件
#include<unordered_map>基本定义
std::unordered_map<KeyType,
ValueType,
Hash = std::hash<KeyType>,
KeyEqual = std::equal_to<KeyType>,
Allocator = std::allocator<std::pair<const KeyType, ValueType>>>此为STL源码中的一段，参数如下：
- KeyType：键的类型，需要支持哈希运算和相等比较
- ValueType：值的类型
- Hash：哈希函数，默认为
std::hash<KeyType> - KeyEqual：键相等的比较函数，默认为
std::equal_to<KeyType> - Allocator：内存分配器，默认为
std::allocator
常用操作
创建和初始化
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
int main()
{
unordered_map<string, int> umap;
unordered_map<string, int> mymap = {
{"apple",3},
{"banana",2},
{"cherry",5}
};
//mymap的迭代器可以不写，直接这样
//unordered_map<string, int>umap2(mymap);
unordered_map<string, int>umap2(mymap.begin(),mymap.end());
return 0;
}插入
// 方法1：使用下标操作符
umap["grape"] = 7;
// 方法2：使用 insert
umap.insert({"melon", 6});
// 方法3：使用 emplace，直接在容器内部构造元素
umap.emplace("kiwi", 4);若map内无该元素则也会插入并调用值的默认构造
auto apple_count = umap["apple"];
cout << "apple count: " << apple_count << endl;//输出apple count: 0
cout << umap.count("apple") << endl;//输出1访问
// 使用下标操作符访问或插入
int apple_count = umap["apple"]; // 如果 "apple" 不存在，会插入一个默认值
// 使用 at() 方法访问，不存在时会抛出异常
try {
int banana_count = umap.at("banana");
} catch (const std::out_of_range& e) {
cerr << "Key not found." << endl;
}
// 使用 find() 方法查找
auto it = umap.find("orange");
if (it != umap.end()) {
cout << "Orange count: " << it->second << endl;
} else {
cout << "Orange not found." << endl;
}删除
// 根据键删除
umap.erase("grape");
// 根据迭代器删除
auto it = umap.find("banana");
if (it != umap.end()) {
umap.erase(it);
}
// 清空整个容器
umap.clear();遍历
for (const auto& pair : umap) {
cout << pair.first << ": " << pair.second << endl;
}
// 使用迭代器
for (auto it = umap.begin(); it != umap.end(); ++it) {
cout << it->first << ": " << it->second << endl;
}其他
// 获取大小
size_t size = umap.size();
// 检查是否为空
bool is_empty = umap.empty();
// 获取桶的数量（用于哈希表内部结构）
size_t bucket_count = umap.bucket_count();
// 重新哈希，调整桶的数量
umap.rehash(20);
// 从一个容器中移交元素到另一个容器
unordered_map<string, int> umap2 = move(umap);性能优化
预分配桶数
umap.reserve(100); // 预分配足够容纳100个元素的桶自定义哈希函数
struct Point {
int x;
int y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
// 自定义哈希函数
struct PointHash {
size_t operator()(const Point& p) const {
size_t h1=hash<int>()(p.x);
size_t h2=hash<int>()(p.y);
return h1^ (h2 << 1);//h2左移1位再与h1异或
}
};
// 定义 unordered_map 使用自定义哈希函数
unordered_map<Point, string, PointHash> point_map;
point_map[{1, 2}] = "A";
point_map[{3, 4}] = "B";自定义键相等比较
struct PointEqual {
bool operator()(const Point& a, const Point& b) const {
return (a.x == b.x) && (a.y == b.y);
}
};
// 定义 unordered_map 使用自定义哈希和比较函数
unordered_map<Point,string, PointHash, PointEqual> point_map;与 map 的比较
- 底层实现：
unordered_map基于哈希表，实现的操作平均时间复杂度为O(1)级别；map基于红黑树，实现的查找、插入、删除操作时间复杂度为对数级别 - 元素顺序：
unordered_map不保证元素的顺序；map按键的顺序（通常是升序）存储元素 - 适用场景：当需要快速查找、插入和删除，且不关心元素顺序时，选择
unordered_map；当需要有序存储或按顺序遍历时，选择map
实现无序map
哈希表原理
哈希表是一种基于键值对的数据结构，通过哈希函数（Hash Function）将键映射到表中的一个索引位置，以实现快速的数据访问。哈希表的关键特性包括：
- 哈希函数：将键映射到表中一个特定的桶（Bucket）或槽（Slot）
- 冲突解决：当不同的键通过哈希函数映射到同一个桶时，需要一种机制来处理这些冲突。常见的方法有链地址法（Separate Chaining）和开放地址法（Open Addressing）
- 负载因子（Load Factor）：表示表中已存储元素的数量与表大小之间的比率。高负载因子可能导致更多的冲突，需要通过扩容来维持性能
在本实现中，我们将采用链地址法来处理哈希冲突，即每个桶存储一个链表（或其他动态数据结构）来存储具有相同哈希值的元素
哈希表结构如下：
数据结构
首先我们新建一个类MyHash，先在.h内包含要用的头文件：
#pragma once
#include<iostream>
#include<algorithm>
#include<list>
#include<functional>
#include<utility>
#include<vector>
#include<iterator>
#include<stdexcept>
using namespace std;创建一个结构体HashNode：
template<typename Key,typename T>
struct HashNode
{
pair<Key, T> data;
HashNode* next;
HashNode(const pair<Key, T>& d) :data(d), next(nullptr) {}
};HashNode内包含了数据域与指针域，正如上图所示，并添加构造函数（用初始化列表方式为成员赋值）
备注：成员是const、引用、自定义类型（无默认构造）、需要高效初始化、或基类构造时，必须或建议用初始化列表。其他简单类型（如int、double等）虽然可以在构造函数体内赋值，但用初始化列表更规范、高效
然后我们考虑中央数组的结构，桶的结构其实和HashNode结构一致，然后我们可以用vector来保存这些桶，哈希函数直接用std的hash<>
template<typename Key, typename T, typename Hash = hash<Key>>
class MyHash
{
public:
class iterator;
using key_type = Key;//起别名
using mapped_type = T;
using value_type = pair<Key, T>;
using size_type = size_t;
private:
vector<HashNode<Key, T>*>buckets_;//每个桶即HashNode类型的指针
size_type element_count_;
size_type bucket_count_;
double max_load_factor_;//负载因子
Hash hash_func_;//哈希函数
void reHash();//重新分配
}然后我们直接在public内写迭代器iterator的实现：
class iterator
{
public:
using iterator_category = forward_iterator_tag;//定义迭代器类型（++）
using value_type = pair<Key, T>;
using difference_type = ptrdiff_t;//偏移量
using pointer = value_type*;
using reference = value_type&;
iterator(MyHash* map, size_type index, HashNode<Key, T>* node):
map_(map), bucket_index_(index), current_node_(node){}//构造函数
//重载运算符
pointer operator->()const;
reference operator&()const;
iterator& operator++();//前自增
iterator operator++(int);//后自增
bool operator==(const iterator& other) const;
bool operator!=(const iterator& other) const;
private:
MyHash* map_;//用于记录找哪个map
HashNode<Key, T>* current_node_;//记录当前的结点（链表中的node）
size_type bucket_index_;//桶的索引
void advance();//遍历函数
}记住iterator的构造函数（参数为map对象，索引，结点），一会要用
接着为MyHash补上构造与析构，然后禁止拷贝与赋值：
MyHash(size_type initial_capacity = 16, double max_load_factor = 0.75):
bucket_count_(initial_capacity),
element_count_(0),
max_load_factor_(max_load_factor),
hash_func_(Hash())
{
buckets_.resize(bucket_count_);
}
~MyHash()
{
clear();//此函数在下边实现
}
MyHash(const MyHash& other)=delete;
MyHash& operator=(const MyHash& other) = delete;常见操作
查找
T* find(const Key& key)//find返回的是迭代器类型,我们这里图省事就返回指针了
{
size_type hash_value = hash_func_(key);
size_type index = hash_value % bucket_count_;
auto* node = buckets_[index];
while (node)
{
if (node->data.first == key)
{
return &(node->data.second);//返回value的地址
}
node = node->next;
}
return nullptr;//没找到返回空指针
}假设映射到的index为0，则我们用node暂存链表的第一个元素，并对链表进行遍历，查找与key相匹的结点，过程如下图所示
删除
bool erase(const Key& key)
{
auto hash_value=hash_func_(key);
auto index = hash_value % bucket_count_;
auto* node = buckets_[index];
HashNode<Key, T>* prev = nullptr;
while (node)
{
if (node->data.first == key)
{
if (prev)
prev->next = node->next;
else
buckets_[index] = node->next;
delete node;
--element_count_;
return true;
}
prev = node;
node = node->next;
}
}举个例子解释一下：
假设，我们要删除键为B的结点，初始状态如下
buckets_[1]: ○(A) → ○(B) → ○(C) → nullptr
↑
node
prev = nullptr第一轮循环
-
检查：
node->data.first == "A" ≠ "B"→ 条件不成立 -
移动指针：
-
prev = node(prev 指向 ○(A)) -
node = node->next(node 指向 ○(B))
-
第二轮循环：
当前状态: ○(A) → ○(B) → ○(C) → nullptr
↑ ↑
prev node-
检查：
node->data.first == "B" == "B"→ 条件成立 -
执行删除：
-
prev->next = node->next(○(A) 指向 ○(C)) -
delete node(删除 ○(B)) -
返回 true
-
插入
void insert(const Key&key,const T& value)
{
size_type hash_value = hash_func_(key);
size_type index = hash_value % bucket_count_;
auto* node = buckets_[index];
while (node)
{
if (node->data.first == key)
{
node->data.second = value;//如果key已经存在，更新value
return;
}
node = node->next;
}
auto* new_node = new HashNode<Key, T>(make_pair(key, value));
new_node->next = buckets_[index];//在链表头插入
buckets_[index] = new_node;
++element_count_;
auto load_factor = static_cast<double>(element_count_)/bucket_count_;//计算负载因子
if (load_factor > max_load_factor_)//若负载因子超过阈值，则进行重新开辟大小
{
rehash();
}
}举两个例子，懒得画图了，问deepseek要的图（？）
例1：插入新键（key不存在）
初始状态：
buckets_[1]: ○(A,val1) → ○(C,val3) → nullptr插入 (B, val2)：
-
计算
index = 1 -
遍历链表：A ≠ B, C ≠ B → key不存在
-
创建新节点 ○(B,val2)
-
头插法：
new_node->next = buckets_[1] // ○(B) → ○(A) buckets_[1] = new_node // buckets_[1] 指向 ○(B) -
结果：
buckets_[1]: ○(B,val2) → ○(A,val1) → ○(C,val3) → nullptr
例2：更新已存在键
初始状态：
buckets_[1]: ○(A,val1) → ○(B,old_val) → ○(C,val3) → nullptr插入 (B, new_val)：
-
计算
index = 1 -
遍历链表：
-
○(A): key="A" ≠ "B" → 继续
-
○(B): key="B" == "B" → 找到
-
-
执行更新：
node->data.second = value -
结果：
buckets_[1]: ○(A,val1) → ○(B,new_val) → ○(C,val3) → nullptr
返回大小
size_type size() const
{
return element_count_;
}判空
bool empty() const
{
return element_count_ == 0;
}清空
void clear()
{
for(size_type i = 0; i < bucket_count_; ++i)
{
HashNode<Key, T>* current_node = buckets_[i];//第一个元素的指针
while (current_node)//current_node不为空时
{
HashNode<Key, T>* temp = current_node;//一定要先保存当前节点
current_node = current_node->next;
delete temp;
}
buckets_[i] = nullptr;
}
element_count_ = 0;
}迭代器begin与end
iterator begin()
{
for (size_type i = 0; i < bucket_count_; ++i)
{
if (buckets_[i])//找到第一个非空桶
{
return iterator(this, i, buckets_[i]);
}
}
return end();//如果所有桶都为空，返回end
}
iterator end()
{
return iterator(this, bucket_count_, nullptr);
}动态扩容reHash
void reHash()
{
auto new_bucket_count = bucket_count_ * 2;
vector<HashNode<Key, T>*> new_buckets(new_bucket_count, nullptr);
for (size_type i = 0; i < bucket_count_; ++i)
{
auto* node = buckets_[i];
while (node)
{
auto* next_node = node->next;
//记住是对新的桶数量取模
size_type new_index = hash_func_(node->data.first) % new_bucket_count;
//还是采用头插法
node->next = new_buckets[new_index];
new_buckets[new_index] = node;
node = next_node;
}
}
buckets_ = std::move(new_buckets);
bucket_count_ = new_bucket_count;
}当负载因子超过阈值时，扩容哈希表并重新分配所有元素
iterator内的函数实现
遍历函数
void advance()//遍历函数
{
if(current_node_!=nullptr)
{
current_node_ = current_node_->next;
}
while(current_node_==nullptr)
{
if (bucket_index_ + 1 < map_->bucket_count_)
{
++bucket_index_;
current_node_ = map_->buckets_[bucket_index_];
}
else if (bucket_index_ + 1 == map_->bucket_count_)
{
++bucket_index_;
cout << "end of iterator" << endl;
break;
}
}
}重载*和->
pointer operator->() const
{
if(!current_node_)
{
throw out_of_range("Dereferencing end iterator");
}
return &(current_node_->data);
}
reference operator*() const
{
if(!current_node_)
{
throw out_of_range("Dereferencing end iterator");
}
return current_node_->data;
}重载==和!=
bool operator==(const iterator& other) const
{
return map_ == other.map_ &&
bucket_index_ == other.bucket_index_ &&
current_node_ == other.current_node_;
}
bool operator!=(const iterator& other) const
{
return !(*this == other);
}重载前自增与后自增
iterator& operator++()
{
advance();
return *this;
}
iterator operator++(int)
{
iterator temp = *this;
advance();
return temp;
}使用示例
#include<iostream>
#include<string>
#include"MyHash.h"
using namespace std;
int main()
{
MyHash<string,int> my_hash;
my_hash.insert("one", 1);
my_hash.insert("two", 2);
for (auto it = my_hash.begin(); it != my_hash.end(); ++it)
{
cout << it->first << ": " << it->second << endl;
}
cout << "-----------------"<<endl;
my_hash.erase("one");
//最好不要在遍历时删除元素
for (auto it = my_hash.begin(); it != my_hash.end(); ++it)
{
cout << it->first << ": " << it->second << endl;
}
return 0;
}输出
two: 2
one: 1
end of iterator
-----------------
two: 2
end of iterator参考：
https://www.bilibili.com/video/BV18bwPe4EfG?spm_id_from=333.788.videopod.sections&vd_source=7c8ff13ea415e148112fa8ecdfa6f75e
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
27
0- 0
已为社区贡献2条内容
所有评论(0)