C++ STL set自动排序实现方法

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

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

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

解决方案：

1. 包含头文件： 首先，你需要包含 <set> 头文件才能使用 set 容器。

2. 声明 set 对象： 声明一个 set 对象，指定你要存储的数据类型。例如，set<int> 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 <iostream>
   #include <set>
   
   int main() {
       std::set<int> 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 <iostream>
   #include <set>
   
   struct MyCompare {
       bool operator()(int a, int b) const {
           return a > b; // 降序排列
       }
   };
   
   int main() {
       std::set<int, MyCompare> 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() 方法在 set 中查找特定元素。 find() 方法返回一个迭代器，指向找到的元素。 如果 set 中不存在该元素，则返回 set::end()。 由于 set 基于红黑树实现，查找的时间复杂度是 O(log n)。

#include <iostream>
#include <set>

int main() {
    std::set<int> 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;
}