C++标准模板库（STL）unordered_set

陈一男学习网站[ ChenYinan.com ] - CCF - NOI - 菜鸟教程 - 编程题库 - C++语言 - API

一、定义与头文件

1. 定义

在C++中，unordered_set是一个无序的关联容器。它存储唯一的元素，并且不允许有重复的值。与set不同的是，unordered_set中的元素没有特定的顺序（不像set是按照元素的值自动排序的），它基于哈希表实现，这使得查找、插入和删除操作平均时间复杂度为常数时间（在理想情况下）。

2. 头文件

需要包含<unordered_set>头文件才能使用unordered_set容器。

二、基本操作

1. 创建unordered_set对象

可以创建一个空的unordered_set，例如：

std::unordered_set<int> mySet;     // 这里创建了一个存储int类型元素的unordered_set

也可以在创建时初始化：

std::unordered_set<int> mySet = {1, 3, 5};

2. 插入元素

使用insert方法。例如：

mySet.insert(7);

如果插入的元素已经存在于unordered_set中，插入操作将被忽略，因为unordered_set不允许重复元素。

3. 查找元素

使用find方法。例如：

std::unordered_set<int>::iterator it = mySet.find(5);

如果it!= mySet.end()，则表示找到了元素，否则表示元素不存在。

4. 遍历unordered_set

可以使用迭代器遍历unordered_set。例如：

for (auto it = mySet.begin(); it!= mySet.end(); ++it) {
    std::cout << *it << " ";
}

或者使用基于范围的for循环（C++11及以上）：

for (const auto& element : mySet) {
    std::cout << element << " ";
}

5. 删除元素

使用erase方法。例如：

如果要删除值为5的元素：

mySet.erase(5);

也可以通过迭代器删除：

auto it = mySet.find(5);
if (it!= mySet.end()) {
    mySet.erase(it);
}

三、自定义哈希函数和相等比较器（针对自定义类型）

1. 自定义哈希函数

当unordered_set存储自定义类型时，需要提供自定义的哈希函数。例如，对于一个自定义的结构体MyType：

struct MyType {
    int value;
};
struct MyHash {
    std::size_t operator()(const MyType& obj) const {
        return std::hash<int>()(obj.value);
    }
};

然后创建unordered_set时使用自定义哈希函数：

std::unordered_set<MyType, MyHash> myCustomSet;

2. 自定义相等比较器

如果默认的相等比较（基于operator==）不满足需求，可以定义自定义的相等比较器。例如：

struct MyEqual {
    bool operator()(const MyType& a, const MyType& b) const {
        return a.value == b.value;
    }
};

然后创建unordered_set时同时使用自定义哈希函数和相等比较器：

std::unordered_set<MyType, MyHash, MyEqual> myFullCustomSet;

C++编程语言基础

C++ | API