C++标准模板库中的无序集

unordered_set 是一种无序关联容器，在哈希表中使用哈希函数将键散列到哈希表的索引中，因此插入始终是随机的。所有 unordered_set 上的操作在平均情况下都需要常数时间 O(1) ，在最坏情况下可能需要线性时间 O(n) ，这取决于内部使用的哈希函数，但实际上它们的表现非常好，通常提供一个常数时间的查找操作。

unordered_set可以包含任何类型的键-预定义或用户定义数据结构，但所有键必须是唯一的。它在< unordered_set >头文件中定义为 std::unordered_set 类。

语法：

std::unordered_set<data_type> name;

在std::unordered_set中，定义了许多函数，其中最常用的函数是：

• size()和empty()用于容量。
• find()用于搜索关键字。
• insert()和erase()用于修改。

示例：

// C++程序演示了unordered_set的各种功能
#include <bits/stdc++.h>
using namespace std;
int main()
{
// 声明用于存储字符串数据类型的set
    unordered_set<string> stringSet;
// 将各种字符串插入，重复的字符串只会存储一次
    stringSet.insert("code");
    stringSet.insert("in");
    stringSet.insert("c++");
    stringSet.insert("is");
    stringSet.insert("fast");
    string key = "slow";
// 如果未找到关键字，find()则返回end迭代器；否则，返回到关键字的迭代器
    if (stringSet.find(key) == stringSet.end())
        cout << key << " not found" << endl << endl;
    else
        cout << "Found " << key << endl << endl;
    key = "c++";
    if (stringSet.find(key) == stringSet.end())
        cout << key << " not found\n";
    else
        cout << "Found " << key << endl;
    cout << "\nAll elements : ";
    unordered_set<string>::iterator itr;
    for (itr = stringSet.begin(); itr != stringSet.end();
            itr++)
        cout << (*itr) << endl;
}

输出

slow not found

Found c++

All elements : is
fast
c++
in
code

find()、insert()和erase()函数平均需要一个恒定的时间。如果在集合中没有关键字，find()函数会返回end()迭代器，否则返回到关键字的迭代器。迭代器作为指向关键字值的指针，因此我们可以通过使用*运算符来解除引用并获取关键字。

我们还可以看到输出的顺序混乱，因为没有特定的顺序来存储unordered_set中的数据。

注意： unordered_set只允许唯一的关键字，而对于重复的关键字应该使用unordered_multiset。

C++STL中的set vs unordered_set

在无序集合上的实际问题

给定一个整数数组（列表），找出其中所有的重复项（假设重复项是一个由随机人猜测的相同的数字，在实验中）。

输入：

arr[] = {1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5}

输出：

重复项为：5 2 1 

例子：

//使用unordered_set从数组中找到重复
//C++程序
#include <bits/stdc++.h>
using namespace std;
 
//使用unordered_set在arr[0…n-1]中打印重复项
void printDuplicates(int arr[], int n)
{
    //声明unordered sets用于检查和存储
    //重复
    unordered_set<int> intSet;
    unordered_set<int> duplicate;
 
    //循环遍历数组元素
    for (int i = 0; i < n; i++) {
        //如果元素不存在则插入该元素
        if (intSet.find(arr[i]) == intSet.end())
            intSet.insert(arr[i]);
 
        //如果元素已经存在，则插入到重复集
        else
            duplicate.insert(arr[i]);
    }
 
    //打印结果
    cout << "重复项为：";
    unordered_set<int>::iterator itr;
 
    //Iterator itr从begin()到end()循环
    for (itr = duplicate.begin(); itr != duplicate.end();
         itr++)
        cout << *itr << " ";
}
 
//Driver code
int main()
{
    int arr[] = { 1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5 };
    int n = sizeof(arr) / sizeof(int);
 
    printDuplicates(arr, n);
    return 0;
}

输出

重复项为：5 2 1 

时间复杂度：O(n log n)
辅助空间：O(n)

std::unordered_set成员方法

以下表格包含std::unordered_set类的所有成员函数：