set 的底层是如何实现的？

C++STL面试题 5月前 0 215

C++ 标准模板库（STL）中的 std::set 通常是基于平衡二叉搜索树实现的，与 std::map 类似，它的底层实现通常也是红黑树。红黑树的特性和优势同样适用于 std::set，使得它在插入、删除和查找操作上的时间复杂度都是 O(log n)，其中 n 是树中元素的数量。

std::set 的关键特性：

它存储的是唯一键值。即在 std::set 中，没有两个元素可以有相同的值。
元素被自动排序（通常是按照升序），这是由底层的二叉搜索树的性质决定的。

应用场景：

当需要一个集合来存储唯一元素，并且频繁进行查找、插入和删除操作时，std::set 是一个非常合适的选择。
std::set 常用于需要自动排序且不包含重复元素的场景，如在一组数据中查找不重复的元素，或者维护一个已排序的唯一元素集合。

示例代码：

#include <iostream>
#include <set>

int main() {
    // 创建一个set
    std::set<int> myset;

    // 插入元素
    myset.insert(3);
    myset.insert(1);
    myset.insert(4);
    myset.insert(1); // 这个插入操作不会成功，因为1已经存在

    // 遍历和打印元素
    std::cout << "Elements in set: ";
    for (int elem : myset) {
        std::cout << elem << " "; // 输出将是 1 3 4
    }
    std::cout << std::endl;

    // 查找元素
    if (myset.find(3) != myset.end()) {
        std::cout << "Element 3 is found in the set." << std::endl;
    }

    // 删除元素
    myset.erase(3);

    return 0;
}

在这段代码中，我们创建了一个 std::set<int> 并插入了几个整数。注意到尽管我们尝试插入了两次数字1，但在 std::set 中它只会存在一次。接下来，代码展示了如何遍历 std::set，检查元素是否存在，以及如何删除元素。由于 std::set 自动对元素进行排序，因此遍历结果将是有序的。

C++STL面试题

发表评论 取消回复

发表评论取消回复