C++如何使用STL set实现自动排序

STL set容器基于红黑树实现，自动排序且去重，插入查找时间复杂度为O(log n)，支持自定义排序，不支持随机访问；遍历时元素有序，find用于查找元素，multiset允许重复而set不允许。

STL set 容器在 C++ 中提供了一种自动排序且唯一的数据存储方式。简单来说，你把元素放进去，它就自动排好了，而且重复的元素会被忽略。

使用 set 的关键在于理解它内部基于红黑树实现，所以插入和查找效率都很高，但不支持随机访问。

解决方案：

1. 包含头文件： 首先，你需要包含

   头文件才能使用

   set

   容器。

   立即学习“C++免费学习笔记（深入）”；

2. 声明 set 对象： 声明一个

   set

   对象，指定你要存储的数据类型。例如，

   set mySet;

   声明了一个存储整数的 set。

3. 插入元素： 使用

   insert()

   方法向 set 中插入元素。

   mySet.insert(10);

   mySet.insert(5);

   mySet.insert(15);

   mySet.insert(5);

   注意，重复插入 5 不会有任何效果，set 中只会保留一个 5。
   

   快剪辑

   国内⼀体化视频⽣产平台

   下载

4. 遍历 set： 可以使用迭代器来遍历 set 中的元素。因为 set 已经自动排序，所以遍历出来的元素也是有序的。

   #include 
   #include 
   
   int main() {
       std::set mySet;
       mySet.insert(10);
       mySet.insert(5);
       mySet.insert(15);
       mySet.insert(5); // 重复插入，无效
   
       for (auto it = mySet.begin(); it != mySet.end(); ++it) {
           std::cout << *it << " ";
       }
       std::cout << std::endl; // 输出: 5 10 15
   
       return 0;
   }

5. 自定义排序： 如果你想使用自定义的排序规则，可以提供一个比较函数或函数对象给 set。

   #include 
   #include 
   
   struct MyCompare {
       bool operator()(int a, int b) const {
           return a > b; // 降序排列
       }
   };
   
   int main() {
       std::set mySet; // 使用 MyCompare 作为排序规则
       mySet.insert(10);
       mySet.insert(5);
       mySet.insert(15);
   
       for (auto it = mySet.begin(); it != mySet.end(); ++it) {
           std::cout << *it << " ";
       }
       std::cout << std::endl; // 输出: 15 10 5
   
       return 0;
   }

set 的底层实现原理是什么？为什么它能自动排序？

set 底层通常使用红黑树（Red-Black Tree）实现。 红黑树是一种自平衡二叉搜索树，它保证了在最坏情况下，插入、删除和查找操作的时间复杂度都是 O(log n)。 自动排序的特性正是来源于红黑树的有序性。 每个节点都大于其左子树的所有节点，小于其右子树的所有节点。 当插入新元素时，红黑树会进行必要的旋转和颜色调整，以保持树的平衡和有序性。

set 和 multiset 的区别是什么？什么时候应该选择哪个？

set

multiset

set

multiset

set

multiset

multiset

set

insert()

multiset

如何在 set 中查找特定元素？查找的时间复杂度是多少？

可以使用

find()

find()

set::end()

#include 
#include 

int main() {
    std::set mySet;
    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(15);

    auto it = mySet.find(10);
    if (it != mySet.end()) {
        std::cout << "找到元素: " << *it << std::endl;
    } else {
        std::cout << "未找到元素" << std::endl;
    }

    it = mySet.find(20);
    if (it != mySet.end()) {
        std::cout << "找到元素: " << *it << std::endl;
    } else {
        std::cout << "未找到元素" << std::endl; // 输出：未找到元素
    }

    return 0;
}