C++ 无序集合

概述

在 C++ 中，无序集合（unordered_set）是一个容器数据结构，用于存储不考虑顺序的元素。本文涵盖了广泛的主题，包括什么是无序集合，如何在 C++ 中创建和初始化它，以及它与 C++ 中集合（set）的区别。为了充分理解 C++ 中无序集合的工作原理及其使用方法，我们还将探讨各种示例和示例代码。

C++ 中的无序集合是什么意思？

引言

在 C++ 中，无序集合类似于一个容器数据结构。这意味着我们可以在其中存储各种元素。无序集合的独特之处在于它只包含单个元素。如果您在 C++ 的无序集合中添加重复元素，它只会保留该元素的单个实例。此容器还有一个独特的功能，可以按任意顺序存储元素。因此，无序集合与 C++ 的集合（set）不同，后者按升序存储元素。

让我们通过一个示例来尝试理解无序集合在 C++ 中如何存储元素。如果我们向 C++ 的无序集合中添加条目 1、4、9、2、1 和 10，则该无序集合将显示如下：

如您所见，元素1 的重复项已被消除，并且元素排列没有特定顺序。

当您需要快速准确地确定某个元素是否至少出现一次、计算不同元素的数量，或者两者都需要时，无序集合非常有用。在接下来的部分中，我们将更详细地介绍 C++ 无序集合的复杂性。

如何创建无序集合？

现在我们知道了 C++ 中无序集合的用途，让我们看看如何创建它。

首先，<unordered_set>头文件包含了使我们能够在 C++ 中使用无序集合的头文件库。要使用 C++ 中的无序集合，我们必须在其函数开头包含它。

语法

在 C++ 中，以下语法用于声明一个空的无序集合：

在此，数据类型代表将添加到无序集合中的元素的类型。

如何初始化无序集合？

我们已经介绍了在 C++ 中创建空无序集合的方法。但是，如果您想创建一个已经包含一些元素的无序集合，您必须首先包含 <unordered_set>头文件。在 C++ 中初始化无序集合使用以下语法：

这两种方法都会产生相同的结果。e1、e2、e3、e4...是要在创建时插入无序集合的元素，而数据类型表示将要插入无序集合的元素的类型。

让我们看一些 C++ 无序集合功能的代码。

C++ 中无序集合的内部实现方式是什么？

我们已经演示了 C++ 无序集合的创建和初始化，那么元素在这些容器内部是如何存储的呢？无序集合在 C++ 中是通过哈希表实现的。因此，我们添加到无序集合中的每个元素都会经过哈希运算，生成一个哈希键，然后保存在哈希表中。C++ 中的无序集合之所以能随机且不按特定顺序存储元素，是因为哈希键由函数决定，并且是通过随机方法生成的。

这也是为什么哈希函数的底层复杂度会影响无序集合复杂度的另一个原因。C++ 中无序集合的所有操作通常需要 O(1) 的常数时间，但在最坏的情况下，它们可能需要 O(n) 的时间，这种情况极其罕见。

集合（Set）与无序集合（Unordered Set）

集合（set）是 C++ 中的另一个容器元素，与无序集合几乎相同。无序集合与集合的区别在于，它随机存储其唯一元素且不按特定顺序排列，而集合则按其值的升序排列。

由于无序集合在 C++ 中是通过哈希表实现的（我们之前已经讲过），元素是随机排序存储的。另一方面，C++ 的集合（set）实现了一个平衡树，使其能够按排序顺序存储元素。

这种实现方式上的差异会影响这两种容器的时间复杂度和各种操作。虽然 C++ 中的集合（set）的平均时间复杂度为 O(log(n))，但无序集合的所有操作的平均时间复杂度为 O(1)。但是，n 是存储在其中的元素数量，两者的空间复杂度均为 O(n)。

C++ 中的无序集合方法

让我们来看看 C++ 中可以与无序集合一起使用的各种方法，以及它们的语法和计算要求。

如何在 C++ 中遍历无序集合的元素

在 C++ 中，我们可以使用索引来遍历数组，但在无序集合中没有索引的概念。另一方面，迭代器是指向无序集合中各个元素的指针。我们可以使用这些迭代器来遍历无序集合及其所有元素。

正如在前一部分中所演示的，begin() 方法返回一个指向无序集合开头的迭代器，我们的循环可以在那里开始。我们循环的终止条件将是 end() 方法返回的指向无序集合最后一个元素之后的那个迭代器。

输出

21 8 7 31 15 81 11

在上面的代码中，在将迭代器初始化为无序集合的开头后，我们一直遍历到结束迭代器。在 C++ 中，我们可以通过以下方式遍历无序集合的元素。

结论

在 C++ 中，无序集合（unordered_set）是一个容器数据结构，用于存储不考虑顺序的唯一元素。<unordered_set>头文件包含了使我们能够在 C++ 中使用无序集合的头文件库。

无序集合在 C++ 中是通过哈希表实现的。C++ 中无序集合的所有操作通常需要 O(1) 的常数时间，但有时可能需要 O(n) 的时间。

C++ 中的集合（set）与无序集合（unordered_set）的区别在于，集合使用平衡树结构来实现，并按升序存储唯一元素。

在 C++ 中，可以使用各种函数访问无序集合，包括 insert()、begin()、end()、size()、empty()、clear()、erase()、count() 和 find()。