STL07——手写一个简单版本的unordered_set

时间：2024-10-06 14:23:48

STL07——手写一个简单版本的unordered_set

    • 1.特点
    • 2.使用方法
    • 3.【STL 专题之 unordered_set】unordered_set 的实现

1.特点

  • 唯一性：用于存储唯一元素的集合（使用 HashTable 类作为底层数据结构来维护元素）

  • 只是存储了一个key值，不存储value（哈希表每个参数就是一堆KV, unordered_set只去掉KV中的V就可以了）

  • 元素是无序的

    (前2个与set一致，最后一点与set不同)

2.使用方法

  • 包含头文件#include<unordered_set>
  • 提供比set更快的插入、删除和查找操作，但不支持顺序访问和范围查询。

3.【STL 专题之 unordered_set】unordered_set 的实现

题目描述

本题需要设计一个 unordered_set 类，实现如下功能：

1、基础功能

  • 构造函数：初始化 unordered_set 实例
  • 析构函数：清理资源，确保无内存泄露

2、核心功能

  • 在 unordered_set 中插入一个元素
  • 在 unordered_set 中删除一个元素
  • 判断一个元素是否在 unordered_set 中
  • 判断 unordered_set 是否为空
  • 获取 unordered_set 的大小

输入描述

题目的包含多行输入，第一行为正整数 N, 代表后续有 N 行命令序列。

接下来 N 行，每行包含一个命令，命令格式为 [operation] [parameters] ，具体命令如下：

insert 命令：

  • 格式：insert [element]
  • 功能：在 unordered_set 中添加元素，如果元素已经存在，则不进行任何操作

erase 命令：

  • 格式：erase [element]
  • 功能：删除 unordered_set 中的元素，如果元素不存在，则不进行任何操作

find 命令：

  • 格式：find [element]
  • 功能：查询 unordered_set 中的元素

empty 命令：

  • 格式：empty
  • 功能：判断无序集合是否为空

size 命令：

  • 格式：size
  • 功能：获取无序集合的大小

输出描述

输出为每行命令执行后的结果，具体输出格式如下：

insert 命令：无输出

erase 命令：无输出

find 命令：如果元素存在，则输出 true，否则输出 false

empty 命令：如果 unordered_set 为空，则输出 true，否则输出 false

size 命令：输出 unordered_set 的大小

#include"HashTable.h"
#include<cstddef>

template<typename Key>
class Unordered_set
{
public:
	Unordered_set() :HashTable() {};

	~Unordered_set(){}

	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) 
	{ 
		HashTable.insertKey(key); 
	}

	void erase(const Key& key) 
	{ 
		HashTable.erase(key); 
	}

	bool find(const Key& key)
	{
		return HashTable.find(key) != NULL;
	}
private:
	HashTable<Key, Key> HashTable;
};

int main() {
	Unordered_set<int> mySet;
	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 element;

		if (command == "insert") {
			iss >> element;
			mySet.insert(element);
		}

		if (command == "erase") {
			iss >> element;
			mySet.erase(element);
		}

		if (command == "find") {
			iss >> element;
			std::cout << (mySet.find(element) ? "true" : "false") << std::endl;
		}

		if (command == "size") {
			std::cout << mySet.size() << std::endl;
		}

		if (command == "empty") {
			std::cout << (mySet.empty() ? "true" : "false") << std::endl;
		}
	}
	return 0;
}

相关文章