当前位置：首页 > news >正文

C++ set替换vector进行优化

news 来源：原创 2025/8/11 13:31:10

文章目录

- demo
- - 代码解释：
- 底层原理
- - 1. 二叉搜索树基础
  - 2. 红黑树的特性
  - 3. `std::set` 基于红黑树的实现优势
  - 4. 插入操作
  - 5. 删除操作
  - 6. 查找操作

demo

#include <iostream>
#include <set>int main() {// 创建一个存储整数的std::setstd::set<int> mySet;// 插入元素mySet.insert(300);mySet.insert(1);mySet.insert(2);mySet.insert(3);  mySet.insert(3);  // 重复元素不会被插入mySet.insert(300);  // 重复元素不会被插入mySet.insert(300);  // 重复元素不会被插入// 输出集合中的元素std::cout << "Set elements: ";for (auto it = mySet.begin(); it != mySet.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;// 查找元素auto findIt = mySet.find(2);if (findIt != mySet.end()){std::cout << "Element 2 found in the set." << std::endl;} else{std::cout << "Element 2 not found in the set." << std::endl;}// 删除元素mySet.erase(1);std::cout << "Set elements after erasing 1: ";for (auto it = mySet.begin(); it != mySet.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;// 检查集合是否为空if (mySet.empty()) {std::cout << "The set is empty." << std::endl;}else{std::cout << "The set is not empty." << std::endl;}// 获取集合的大小std::cout << "The size of the set is: " << mySet.size() << std::endl;// 清除集合中所有内容mySet.clear();std::cout << "Set elements after clearing: ";for (auto it = mySet.begin(); it != mySet.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;// 再次检查集合是否为空if (mySet.empty()){std::cout << "The set is empty after clearing." << std::endl;} else {std::cout << "The set is not empty after clearing." << std::endl;}return 0;
}

在这里插入图片描述

代码解释：

创建集合：使用std::set<int> mySet;创建一个存储整数的std::set。
插入元素：通过insert方法向集合中插入元素，重复元素不会被插入。
遍历集合：使用迭代器遍历集合中的元素并输出。
查找元素：使用find方法查找指定元素，如果找到则返回指向该元素的迭代器，否则返回end()。
删除元素：使用erase方法删除指定元素。
检查集合是否为空：使用empty方法检查集合是否为空。
获取集合大小：使用size方法获取集合中元素的数量。

底层原理

在C++标准库中，std::set 是一个关联容器，用于存储唯一的元素，并且这些元素会按照一定的顺序排列（默认是升序）。它的底层通常基于红黑树（Red - Black Tree）这种自平衡二叉搜索树（Self - Balancing Binary Search Tree）来实现

1. 二叉搜索树基础

二叉搜索树（Binary Search Tree，BST）是一种二叉树，对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。这种特性使得在二叉搜索树中进行查找、插入和删除操作的平均时间复杂度为 $O (l o g n)$ ，其中 $n$ 是树中节点的数量。

2. 红黑树的特性

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色（红色或黑色）。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。红黑树必须满足以下五个性质：

每个节点要么是红色，要么是黑色。
根节点是黑色。
每个叶子节点（NIL节点，空节点）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

3. `std::set` 基于红黑树的实现优势

有序性：由于红黑树是一种二叉搜索树，插入到 std::set 中的元素会根据元素的键值自动排序。例如，插入整数时会按照从小到大的顺序排列。
唯一性：在插入元素时，红黑树会进行比较，如果发现元素已经存在，则不会插入，保证了 std::set 中元素的唯一性。
高效的查找、插入和删除操作：红黑树的自平衡特性保证了树的高度始终保持在 $O (l o g n)$ 级别，因此查找、插入和删除操作的时间复杂度都是 $O (l o g n)$ 。

4. 插入操作

当向 std::set 中插入一个新元素时，底层的红黑树会执行以下步骤：

按照二叉搜索树的规则找到新元素应该插入的位置。
将新元素插入到该位置，并将其颜色设置为红色。
检查红黑树的性质是否被破坏，如果破坏了则通过一系列的颜色调整和旋转操作来恢复红黑树的性质。

5. 删除操作

当从 std::set 中删除一个元素时，红黑树会执行以下步骤：

按照二叉搜索树的规则找到要删除的节点。
如果该节点有两个子节点，则用其右子树中的最小节点替换该节点，然后删除右子树中的最小节点。
删除节点后，检查红黑树的性质是否被破坏，如果破坏了则通过一系列的颜色调整和旋转操作来恢复红黑树的性质。

6. 查找操作

查找操作相对简单，根据二叉搜索树的特性，从根节点开始比较，如果要查找的元素值小于当前节点的值，则在左子树中继续查找；如果大于当前节点的值，则在右子树中继续查找；如果相等，则找到了该元素。由于红黑树的高度为 $O (l o g n)$ ，因此查找操作的时间复杂度也是 $O (l o g n)$ 。

综上所述，std::set 基于红黑树实现，利用红黑树的特性保证了元素的有序性、唯一性以及高效的查找、插入和删除操作。