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;
}