深入理解 C++ 中 std::vector 和 std::set 容器的使用

一、引言
在 C++ 编程中，容器是非常重要的数据结构，它们为开发者提供了方便、高效的方式来管理和操作数据集合。std::vector 和 std::set 是标准模板库（STL）中两个常用的容器，各自具有独特的特性和适用场景。本文将深入探讨这两个容器的使用方法、内部实现原理以及如何在实际编程中灵活运用它们来解决常见的问题，如数据去重和集合操作等。
二、std::vector 容器详解
（一）std::vector 的基本概念
std::vector 是一个动态数组，它能够在运行时根据需要自动调整大小。这意味着我们可以方便地向其中添加或删除元素，而无需担心数组越界的问题。其内存布局是连续的，这使得它在随机访问元素时具有很高的效率，时间复杂度为 。
（二）std::vector 的常用操作
元素插入与删除
使用 push_back 方法可以在向量的末尾添加一个元素，例如：

std::vector vec;
vec.push_back(1);
vec.push_back(2);
如果要在指定位置插入元素，可以使用 insert 方法。例如，在索引为 1 的位置插入元素 3：
cpp
vec.insert(vec.begin() + 1, 3);
删除元素可以使用 erase 方法，比如删除索引为 2 的元素：
cpp
vec.erase(vec.begin() + 2);
元素访问
通过下标运算符 [] 可以直接访问向量中的元素，例如：
cpp
int num = vec[0];
也可以使用 at 方法，它会进行边界检查，如果越界会抛出 std::out_of_range 异常，相对更安全：
cpp
try {
int num = vec.at(1);
} catch (const std::out_of_range& e) {
std::cerr << "Out of range access: " << e.what() << std::endl;
}
获取向量的大小和容量
使用 size 方法可以获取向量中当前元素的个数：
cpp
std::cout << "Size of vector: " << vec.size() << std::endl;
而 capacity 方法则返回向量在不重新分配内存的情况下能够容纳的元素数量：
cpp
std::cout << "Capacity of vector: " << vec.capacity() << std::endl;
（三）std::vector 的内部实现原理
std::vector 内部通常维护三个指针：begin、end 和 end_capacity。begin 指向向量中第一个元素的位置，end 指向最后一个元素的下一个位置，end_capacity 指向向量容量的末尾位置。当向向量中添加元素时，如果当前元素个数等于容量，std::vector 会自动重新分配一块更大的内存空间，并将原有的元素复制到新的内存区域，然后再添加新元素。这个过程可能会导致一定的性能开销，尤其是在频繁插入大量元素时，可能会引发多次内存重新分配和元素复制操作。
三、std::set 容器详解
（一）std::set 的基本概念
std::set 是一个关联容器，它用于存储唯一的元素，并会自动对元素进行排序。其内部实现基于红黑树（一种自平衡二叉搜索树），这保证了元素的插入、删除和查找操作都具有较高的效率，平均时间复杂度为 ，其中 是容器中元素的个数。
（二）std::set 的常用操作
元素插入与删除
使用 insert 方法插入元素，例如：
cpp
std::set mySet;
mySet.insert(5);
mySet.insert(3);
mySet.insert(7);
删除元素可以使用 erase 方法，比如删除元素 5：
cpp
mySet.erase(5);
元素查找
使用 find 方法来查找元素，如果找到则返回指向该元素的迭代器，否则返回 end 迭代器：
cpp

auto it = mySet.find(7);
if (it!= mySet.end()) {
   
    std::cout << "Element 7 found in set" << std::endl;
} else {
   
    std::cout << "Element 7 not found in set" << std::endl;
}

获取集合的大小
通过 size 方法获取集合中元素的个数：
cpp
std::cout << "Size of set: " << mySet.size() << std::endl;
（三）std::set 的内部实现原理
如前所述，std::set 内部基于红黑树实现。红黑树的特性保证了元素的有序性以及高效的操作性能。在插入元素时，std::set 会根据元素的值将其插入到合适的位置，以维持树的有序性和平衡性。在查找元素时，通过二叉搜索树的特性，可以快速定位到目标元素（平均情况下）。由于红黑树的自平衡机制，即使在频繁插入和删除元素的情况下，也能保证操作的效率不会出现明显的退化。
四、std::vector 和 std::set 在数据处理中的应用实例
（一）数据去重问题
考虑这样一个场景，我们有两个 std::vector，需要找出它们中不重复的元素，并将这些不重复元素合并成一个新的向量。以下是使用 std::vector 和 std::set 解决这个问题的示例代码：
cpp

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

// 函数声明，用于获取两个向量中不重复元素组成的新向量
std::vector