set 的底层是如何实现的？

参考回答

std::set 是 C++ STL 中的一种关联容器，底层通过 红黑树 (Red-Black Tree) 实现。它的设计与 std::map 类似，但主要区别在于 std::set 只存储键，不存储键值对。红黑树的自平衡特性使得 std::set 在插入、删除和查找操作上的时间复杂度始终为 (O(\log n))。

详细讲解与拓展

1. 红黑树的基本概念

红黑树是 std::set 的底层数据结构，它是一种 自平衡二叉搜索树，具有以下特性：
1. 每个节点要么是红色，要么是黑色。
2. 根节点始终是黑色。
3. 红色节点的子节点必须是黑色（不能有连续的红色节点）。
4. 从任意节点到叶节点的每条路径都包含相同数量的黑色节点。
5. 树的高度保持接近 (\log_2(n))，确保高效的操作性能。

红黑树的结构使得 std::set 的插入、删除和查找的时间复杂度均为 (O(\log n))。

2. std::set 的存储结构

• 节点：
  • 每个节点只存储一个键（key）。
  • 每个节点包含指向左子节点、右子节点和父节点的指针，以及节点的颜色（红或黑）。

示意图（以整数为例）：

        8(B)
       /   \
    3(R)   10(B)
   /   \
  1(B)  6(B)

• 键的唯一性：
  红黑树的特性使得 std::set 保证了键的唯一性。如果试图插入重复的键，插入操作将失败。

3. 插入操作

插入时，std::set 会遵循以下规则：
1. 插入位置：根据二叉搜索树规则找到合适位置，将新键作为叶节点插入。
2. 颜色调整：初始将新节点标记为红色。
3. 修复平衡：
– 如果插入破坏了红黑树的性质（如出现连续红色节点），通过旋转（左旋或右旋）和重新着色调整树的平衡。

示例代码：

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> mySet;

    mySet.insert(10);  // 插入键10
    mySet.insert(20);  // 插入键20
    mySet.insert(15);  // 插入键15

    for (int val : mySet) {
        cout << val << " ";
    }

    return 0;
}

输出：

10 15 20

注意：std::set 自动对元素进行排序。

4. 查找操作

std::set 的查找基于二叉搜索树规则：
1. 从根节点开始，与目标键比较。
2. 如果目标键小于当前节点，查找左子树；否则查找右子树。
3. 如果找到匹配的键，返回对应的迭代器；否则返回 end()。

示例代码：

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> mySet = {10, 20, 30};

    auto it = mySet.find(20);  // 查找键20
    if (it != mySet.end()) {
        cout << "Found: " << *it << endl;
    } else {
        cout << "Not Found" << endl;
    }

    return 0;
}

输出：

Found: 20

5. 删除操作

删除操作会先找到目标节点，然后调整红黑树的结构以保持平衡：
1. 叶节点：直接删除。
2. 单子节点：用子节点替代被删除节点。
3. 双子节点：找到中序后继节点，用后继节点替代被删除节点，再删除后继节点。

删除后可能破坏红黑树的性质，因此需要通过旋转和重新着色修复。

示例代码：

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> mySet = {10, 20, 30};

    mySet.erase(20);  // 删除键20

    for (int val : mySet) {
        cout << val << " ";
    }

    return 0;
}

输出：

10 30

6. 自定义比较规则

默认情况下，std::set 使用 < 运算符对元素排序。可以通过传递自定义比较函数更改排序规则。

示例：按降序排序

#include <set>
#include <iostream>
using namespace std;

struct Compare {
    bool operator()(int a, int b) const {
        return a > b;  // 降序比较
    }
};

int main() {
    set<int, Compare> mySet = {10, 20, 15};

    for (int val : mySet) {
        cout << val << " ";
    }

    return 0;
}

输出：

20 15 10

7. 常见操作的时间复杂度

8. 红黑树与哈希表的对比

如果性能是主要考虑因素，std::unordered_set（基于哈希表实现）可能是更好的选择：
– std::set：基于红黑树，支持自动排序和范围操作，时间复杂度为 (O(\log n))。
– std::unordered_set：基于哈希表，不支持排序，插入和查找的平均时间复杂度为 (O(1))。

总结

std::set 的底层实现是红黑树，通过自平衡特性保证插入、删除和查找的时间复杂度为 (O(\log n))。它自动对元素排序，且元素唯一，非常适合需要有序集合的场景。如果不需要排序且对性能有更高要求，可以使用 std::unordered_set。理解其红黑树的实现原理有助于在实际开发中更好地选择合适的容器。

帅地永久会员

打赏 收藏 海报挣佣金 推广链接