C++ STL Set

在 C++ 中，set 代表了基本的数据结构，它将唯一的元素按某种排序顺序排列并存储起来。set 被称为关联容器，而唯一的已排序元素被称为已排序键。我们可以插入或删除这些键，但不能修改它们。

默认情况下，set 遵循升序来排序键。set 是 C++ 中可用的 标准模板库 (STL) 的一部分，在 STL 中，set 类提供了有用的组件，可以提高 set 操作的效率。由于 set 使用默认的排序顺序来处理键，并且不使用索引机制，因此我们无法通过其索引号访问这些键。

语法

它具有以下语法：

参数

• T： T 代表存储在容器 set 中的元素的类型。
• Compare：一个比较类，接受两个相同类型的参数，返回 bool 值。此参数是可选的，默认值为二元谓词 less<T>。
• Alloc：分配器对象的类型，用于定义存储分配模型。

Set 的声明和初始化

在 C++ 中，我们可以使用 <set> 头文件声明 set，并使用 std::set 容器进行初始化。

语法

它具有以下语法：

C++ Set 的声明和初始化示例

让我们以一个例子来说明如何在 C++ 中声明和初始化一个 set。

输出

3 6 7 8 9

说明

在这个例子中，我们创建了一个名为 val 的整数 set，并用值 {8, 6, 7, 3, 9} 初始化。之后，set 会自动按排序顺序存储元素并删除任何重复项。for 循环以升序打印每个元素。

Set 的操作

虽然在 C++ 中可以对 set 执行多种操作。其中一些如下：

1) 插入元素

在 C++ 中，insert() 函数用于在 set 中插入元素。insert() 或 emplace() 操作用于插入元素，如果我们尝试插入一个已存在的元素到 set 中，它将不会被插入。此外，我们不能指定插入位置，因为它会在排序时自动处理。

C++ 插入元素示例

让我们以一个例子来说明如何在 C++ set 中插入元素。

输出

1 3 4 5 7 8 9

说明

在这个例子中，我们创建了一个名为 a 的 set 并用 {1, 3, 5} 初始化，然后使用 insert() 和 emplace() 添加了额外的元素。之后，set 存储所有元素并保持排序和唯一性，因此输出以升序打印元素。

2) 访问元素

在 C++ set 中，我们不能直接使用索引访问元素。begin() 和 end() 迭代器用于按位置访问元素。除了这些，还可以使用 next() 和 advance() 方法来访问 set 元素。

C++ 访问元素示例

让我们以一个例子来说明如何在 C++ set 中访问元素。

输出

1 5

说明

在这个例子中，我们初始化了一个整数 set 并使用迭代器访问元素。begin() 函数返回第一个（最小）元素，next (val1, 2) 函数向前移动两个位置以访问排序后的第三个元素。

3) 查找元素

在 C++ 中，find() 函数用于从 set 中查找元素。find() 函数支持按值快速搜索操作，如果搜索到的元素存在于 set 中，它将返回该值，否则返回 end() 迭代器。

C++ 查找元素示例

让我们以一个例子来说明如何在 C++ set 中查找元素。

输出

8

说明

在此示例中，我们演示了如何使用 find() 函数在 set 中搜索元素。它会在 set 中查找元素 8，如果找到则打印它；否则，它会显示一条消息，表明该元素不存在。

4) 遍历元素

在 C++ 中，begin() 和 end() 迭代器与基于范围的 for 循环一起用于遍历或迭代 set。

C++ 遍历元素示例

让我们以一个例子来说明如何在 C++ set 中遍历元素。

输出

2 3 4 5 7 8

说明

在此示例中，我们使用 set<int> 来存储唯一的整数并保持排序。之后，它使用迭代器（val）遍历 set 并打印每个元素。

5) 删除元素

在 C++ 中，erase() 方法用于按值或按位置从 set 中删除元素。

C++ 删除元素示例

让我们以一个例子来说明如何在 C++ set 中删除元素。

输出

3 5 6 7 9

说明

在此示例中，我们演示了如何从 set 中删除元素。之后，它通过值删除元素 9，并通过迭代器删除第一个元素。最后，它以排序顺序打印剩余的元素，因为 set 会自动维护升序。

基本操作的时间复杂度

基本操作的时间复杂度如下：

• 插入： 插入元素的时间复杂度为 O(log n)。
• 删除： 删除元素的时间复杂度为 O(log n)。
• 查找： 搜索元素的时间复杂度为 O(1)。
• 按值查找： 按值搜索元素的时间复杂度为 O(log n)。
• 遍历： 遍历 set 中元素的时间复杂度为 O(n)。

成员函数

以下是 C++ set 中所有成员函数的列表

构造函数/析构函数

给定的表格显示了 C++ Set 中使用的几个构造函数/析构函数。

迭代器

给定的表格显示了 C++ Set 中使用的几个迭代器函数。

容量

给定的表格显示了 C++ Set 中使用的几个容量函数。

修饰符

给定的表格显示了 C++ Set 中使用的几个修改器函数。

观察器

给定的表格显示了 C++ Set 中使用的几个观察者函数。

操作

给定的表格显示了 C++ Set 中执行的几个操作。

分配器

给定的表格显示了 C++ Set 中使用的分配器函数。

非成员重载函数

给定的表格显示了 C++ Set 中使用的几个非成员重载函数。

Set 的类型

C++ 中有两种 set，它们是：

1) 有序 Set

在 C++ 中，在存储元素时遵守排序顺序的 set 被称为有序 Set。

2) 无序 Set

在 C++ 中，以任意顺序存储元素的 set 被称为无序 Set。

有序 Set 与无序 Set 的区别

C++ 中有序 Set 和无序 Set 之间的几点区别如下：

• 有序 Set 在存储元素时遵循排序机制，默认情况下是升序。另一方面，无序 Set 以任意顺序存储元素。
• 在有序 Set 中，插入、删除和查找等操作需要对数 O(log n) 的时间复杂度来执行指定的任务。另一方面，无序 Set 在执行任何操作（如插入、删除或访问元素）时使用哈希技术，因此需要 O(1) 的时间复杂度来执行指定的任务。

C++ Set 选择题

1) 在 C++ 中使用 std::set 容器需要以下哪个头文件？

1. < map >
2. < vector >
3. < set >
4. < unordered_set >

2) 在 C++ 的 std::set 中插入元素的时间复杂度是多少？

1. O (n)
2. O (1)
3. O (n log n)
4. O (log n)

3) 选择用值初始化 std::set 的正确语法。

1. Std :: set <int> s = ( 1, 2, 3 );
2. Std:: set <int> s ( 1, 2, 3 );
3. Std:: set <int> s ( 3, 2, 1 );
4. Std :: set <int> s = { 1, 2, 2, 3 };

4) C++ 中 std::set 的 insert() 方法的返回类型是什么？

1. Pair <iterator, bool>
2. Bool
3. Void
4. Iterator

5) 关于 std:: set 的迭代器，以下哪个陈述是正确的？

1. 它们允许修改元素
2. 它们指向排序顺序的元素
3. 它们不支持 ++ 运算符
4. 它们只能用于反向访问元素。