STL10——手写一个简单版本的unordered_map(包含特点和基本用法)
1.特点
键值对存储:存储的元素是一组键值对,其中每个键都是唯一的,并且每个键映射到一个值。
哈希表实现:底层通过哈希表实现(使用哈希函数将键转换为索引,这些索引将用于在内部数组中找到值的位置)
无序:元素的顺序取决于哈希函数和元素的添加顺序,而不是元素的键值。
查找性能非常高:查找访问操作只有O(1)的时间复杂度
2.基本用法
- 包含头文件#include <unordered_map>
unordered_map<string, int> wordCount;
- 插入元素
wordCount["apple"] = 1;
wordCount.insert({"banana", 2});
wordCount.emplace("cherry", 3); // 使用emplace直接构造元素,效率更高
- 访问元素
cout << "apple count: " << wordCount["apple"] << std::endl; //map[键]
cout << "banana count: " << wordCount.at("banana") << std::endl; // 使用at方法访问元素,如果键不存在,会抛出std::out_of_range异常(map.at())
- 更新元素
wordCount["apple"] = 5;
- 删除元素
wordCount.erase("banana");//map.erase(键)
手写一个简单版本的unordered_map
【STL 专题之 unordered_map】unordered_map 的实现
题目描述
本题需要设计一个 unordered_map 类,实现如下功能
1、基础功能
- 构造函数:初始化 unordered_map 实例
- 析构函数:清理资源,确保无内存泄露
2、核心功能
- 在 unordered_map 中插入一个元素
- 在 unordered_map 中删除元素
- 判断一个元素是否在 unordered_map 中
- 判断 unordered_map 是否为空
- 获取 unordered_map 的大小
输入描述
题目的包含多行输入,第一行为正整数 N, 代表后续有 N 行命令序列。
接下来 N 行,每行包含一个命令,命令格式为 [operation] [parameters] ,具体命令如下:
insert 命令:
- 格式:insert [key] [value]
- 功能:在 map 中添加 key-value 键值对,如果对应的 key 已经存在,则不进行任何操作
erase 命令:
- 格式:erase [key]
- 功能:删除 unordered_map 中 key 对应的键值对,如果 key 不存在,则不进行任何操作
find 命令:
- 格式:find [key]
- 功能:查询 unordered_map 是否存在 key 对应的键值对
empty 命令:
- 格式:empty
- 功能:判断 unordered_map 是否为空
size 命令:
- 格式:size
- 功能:获取 unordered_map 的大小
输出描述
输出为每行命令执行后的结果,具体输出格式如下:
insert 命令:无输出
erase 命令:无输出
empty 命令:如果 unordered_map 为空,则输出 true,否则输出 false,输出独占一行
size 命令:输出一个整数,独占一行,代表 unordered_map 的大小
find 命令:如果 key 存在,则输出 true,否则输出 false,输出独占一行
#include "HashTable.h"
#include <cstddef>
template<typename Key,typename Value>
class Unordered_map
{
private:
HashTable<Key, Value> hashtable;
public:
Unordered_map() :hashtable();
~Unordered_map(){}
bool empty() const noexcept { return hashtable.size() == 0; }
size_t size() const noexcept { return hashtable.size(); }
void clear() noexcept { hashtable.clear(); }
void insert(const Key& key, const Value& value) {
hashtable.insert(key, value);
}
void erase(const Key& key) { hashtable.erase(key); }
bool find(const Key& key) { return hashtable.find(key) != nullptr; }
Value &operator[](const Key& key)
{
Value* Val = hashtable.find(key);
if (Val != NULL)
return *Val;
else
{
hashtable.insertKey(key);
Val = hashtable.find(key);//find返回的是value的地址
return *Val;
}
}
};
int main() {
Unordered_map<int, int> map;
int N;
std::cin >> N;
getchar();
std::string line;
for (int i = 0; i < N; i++) {
std::getline(std::cin, line);
std::istringstream iss(line);
std::string command;
iss >> command;
int key;
int value;
if (command == "insert") {
iss >> key >> value;
map.insert(key, value);
}
if (command == "erase") {
iss >> key;
map.erase(key);
}
if (command == "find") {
iss >> key;
if (map.find(key)) {
std::cout << "true" << std::endl;
}
else {
std::cout << "false" << std::endl;
}
}
// size 命令
if (command == "size") {
std::cout << map.size() << std::endl;
}
// empty 命令
if (command == "empty") {
if (map.empty()) {
std::cout << "true" << std::endl;
}
else {
std::cout << "false" << std::endl;
}
}
}
return 0;
}