极客笔记C++ 无序集合
概述
在C++中，无序集合是一种容器数据结构，用于存储元素而不考虑它们的顺序。本文涵盖了很多主题，包括无序集合的定义、如何在C++中创建和初始化无序集合以及它与该语言中的集合的区别。为了充分理解C++中无序集合的功能和用法，我们还将讨论各种示例和示例代码。
C++的无序集合是什么意思
介绍
在C++中， 无序集合 类似于容器数据结构。它意味着我们可以在其中存储各种元素。无序集合的独特之处在于它只包含单个元素。在C++中，如果您将重复的元素添加到无序集合中，它仍然只包含一个实例。此容器还具有以任何顺序存储组件的独特特性。因此，无序集合与C++的集合不同，后者以升序存储元素。
让我们通过一个示例来尝试理解C++中无序集合是如何存储元素的。如果我们将1、4、9、2、1和10添加到C++中的无序集合中，该无序集合将如下所示：
insert(1);
insert(4);
insert(9);
insert(2);
insert(1);
insert(10);
unordered_set: 10, 2, 1, 9, 4
正如您所看到的，元素 1’s duplicate 被排除在外，而元素的摆放顺序并无特定要求。
无序集合在需要快速准确地确定某个元素是否至少出现一次在一组元素中，计算不同组件的数量，或者两者兼而有之时非常有用。在接下来的几节中，我们将详细介绍无序集合C++的复杂度。
如何创建一个无序集合
现在我们知道了C++中无序集合可能用于的目的，让我们看看如何创建一个无序集合。
首先， unordered set> 头文件包含了一个头库，使我们能够在C++中使用无序集合。我们必须在函数的开始处包含它以使用C++中的无序集合。
语法：
在C++中，使用以下语法声明一个空的无序集合：
unordered_set<data_type>set_name;
将要添加到无序集中的元素的数据类型在此情况下由 data type 表示。
如何初始化无序集
已经介绍了在C++中创建空的无序集。然而，如果您希望构建一个已经包含一些元素的无序集，您必须首先导入 unordered set> 头文件。在C++中初始化无序集使用以下语法：
unordered_set<data_type>set_name = {e1, e2, e3, e4, ...};
or,
unordered_set<data_type>set_name {e1, e2, e3, e4, ...};
这两种方法都会导致相同的结果。 e1，e2，e3，e4，… 这些是在创建unordered set时要插入的项目，data type表示将插入unordered set中的元素的数据类型。
让我们来看一下unordered set函数的一些C++代码。
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> p1;
unordered_set<char> p2 {'p', 'q', 'r', 's'};
return 0;
}
C++的无序集合的内部实现方式是如何的
展示了C++中无序集合的创建和初始化方式，但是内部是如何存储这些容器中的组件的呢？在C++中，使用哈希表来实现无序集合。因此，我们添加到无序集合中的每个元素都会经过哈希操作，生成一个哈希键，然后保存在哈希表中。C++中的无序集合随机存储元素，没有特定的顺序，因为哈希键由函数确定，并通过随机方法生成。
这也是哈希函数底层复杂度影响无序集合复杂度的另一个原因。C++中对无序集合的所有操作通常需要 O(1) 的常数时间，但在极端情况下可能需要 O(n) 的时间，这是非常罕见的。
集合与无序集合
集合是C++中的另一个容器元素，与无序集合几乎相同。无序集合与集合的区别在于，它随机存储其唯一元素，并没有特定的顺序，而集合会按照值的递增顺序进行排列。
由于在C++中使用哈希表来实现无序集合，我们之前已经介绍过，元素会以随机顺序存储。另一方面，C++的集合实现了一个平衡树，使其能够按照排序顺序保存元素。
这种实现的差异会影响这两个容器的时间复杂度和各种操作。虽然C++中的集合平均时间复杂度为 O(log(n)) ，但无序集合所有操作的平均时间复杂度都是 O(1) 。但是它们的空间复杂度都是 O(n) ，其中n是存储的元素数量。
C++中的无序集合方法
让我们一起来看看在C++中可以使用的许多方法来处理无序集合，以及它们的语法和计算要求。
| 方法名 | 说明 | 语法 | 时间复杂度 |
|---|---|---|---|
| insert() | 用于向无序集合中添加新元素。 | set_name.insert(element); | 0(1) |
| begin() | 返回一个迭代器，用于遍历无序集合的第一个元素。 | set_name.begin(); | 0(1) |
| end() | 返回指向无序集合最后一个元素的迭代器。此迭代器指示无序集合中最后一个元素之后的位置。 | set_name.end(); | 0(1) |
| count() | 在无序集合中用于确定元素是否存在。如果元素存在，则返回1，否则返回0。 | set_name.count(element); | 0(1) |
| size() | 用于返回无序集合的大小或已添加到集合中的新元素的总数。 | set_name.size(); | 0(1) |
| find() | 使用此方法定位并返回无序集合中特定值的迭代器。如果无法找到请求的元素，则返回指向无序集合末尾的迭代器。 | set_name.find(*itr); | 0(1) |
| empty() | 用于确定无序集合是否为空。如果无序集合为空，则返回1，否则返回0。 | set_name.empty() | O(1) |
| erase() | 使用迭代器从无序集合中删除特定元素或一组元素。 | set_name.erase(itr); 或 set_name.erase(itr_begin, *itr_end); | 0(被删除的元素个数) |
| clear() | 完全清空无序集合。 | set_name.clear(); | 0(元素个数) |
如何在C++中遍历无序集合的元素
在C++中，我们可以使用索引来遍历数组，但是在无序集合中没有索引的概念。另一方面，迭代器是指向无序集合中各个项的指针。我们可以使用这些迭代器来遍历无序集合及其所有项。
正如在上一节中所演示的那样，begin() 方法返回一个指向无序集合起始位置的迭代器，我们的循环可以从这里开始。循环的终止条件将是通过end() 方法返回的无序集合最后一个元素之后的迭代器。
#include
#include
using namespace std;
int main() {
unordered_set p1 = {11,81,15,31,7,8,21};
auto itr = p1.begin();
while(itr != p1.end()){
cout<<*itr<<" ";
itr++;
}
return 0;
}
输出结果
21 8 7 31 15 81 11
在上面的代码中，我们在将迭代器初始化为无序集合的开始后，直到达到结束迭代器为止。在C++中，我们可以以以下方式探索无序集合的元素。 结论 在C++中，无序集合是一种容器数据结构，用于存储不考虑顺序的不同元素。 unordered_set包含的头文件包含了使我们能够在C++中使用无序集合的头文件库。 在C++中，哈希表用于实现无序集合。对C++无序集合的所有操作通常都需要常数时间O(1)，但有时可能需要时间O(n)。 与C++中的无序集合不同，集合使用平衡树结构进行实现，并按升序保持唯一元素。 在C++中，可以使用各种函数访问无序集合，包括insert()，begin()，end()，size()，empty()，clean()，erase()，count()和find()。