C++ set容器

1. 什么是 std::set？

• 定义： std::set 是 C++ 标准模板库 (STL) 中提供的一种关联容器。
• 核心特性：
  • 唯一键 (Unique Keys)： 容器中的每个元素（键）都必须是唯一的。尝试插入重复元素会被忽略。
  • 有序性 (Sorted)： 元素在容器内部始终按照特定的严格弱序（默认是 std::less<Key>，即升序）自动排序。无论你以何种顺序插入元素，当你遍历 set 时，元素总是有序的。
  • 实现方式： 通常基于红黑树 (Red-Black Tree) 实现。这是一种自平衡的二叉搜索树 (BST)，保证了元素的有序性以及插入、删除、查找等操作在平均和最差情况下都具有对数时间复杂度 (O(log n))。
• 头文件： #include <set>
• 模板声明：

  template <
      class Key,
      class Compare = std::less<Key>,
      class Allocator = std::allocator<Key>
  > class set;
  

  • Key: 容器中存储元素的类型。
  • Compare: 用于比较元素的函数对象类型（默认为 std::less<Key>，即使用 < 运算符进行升序排序）。它定义了元素的排序准则。
  • Allocator: 内存分配器类型（通常使用默认值即可）。

2. 核心特性详解与代码示例

2.1 唯一性和有序性

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet;

    // 插入元素 (尝试插入重复元素)
    mySet.insert(30);
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(20); // 重复插入 20，会被忽略
    mySet.insert(5);
    mySet.insert(15);

    // 遍历输出 (自动排序且唯一)
    std::cout << "Elements in set (sorted and unique): ";
    for (const int& num : mySet) { // 使用范围for循环遍历
        std::cout << num << " ";
    }
    std::cout << std::endl; // 输出: 5 10 15 20 30

    return 0;
}

输出:

Elements in set (sorted and unique): 5 10 15 20 30

解释: 即使插入顺序是 30, 10, 20, 20, 5, 15，输出的元素是唯一且按升序排列的（5, 10, 15, 20, 30）。重复的 20 只保留了一个。所以当我们需要对一组数据进行排序和去重的时候，我们就可以将数据插入到set容器中，自动去重和排序。

2.2 构造与初始化

• 空集合：

  std::set<std::string> emptySet;
  

• 范围构造 (使用迭代器)：

  std::vector<int> vec = {7, 2, 9, 2, 4, 7};
  std::set<int> setFromVec(vec.begin(), vec.end()); // 包含: 2, 4, 7, 9 (唯一且排序)
  

• 拷贝构造：

  std::set<int> original = {1, 3, 5};
  std::set<int> copySet(original); // copySet 现在也是 {1, 3, 5}
  

• 移动构造 (C++11)：

  std::set<int> createSet() {
      std::set<int> tempSet = {100, 200, 300};
      return tempSet; // 触发移动语义
  }
  std::set<int> movedSet(createSet()); // 高效，资源从临时对象转移
  

• 初始化列表构造 (C++11)：

  std::set<char> charSet = {'a', 'c', 'b', 'a', 'd'}; // 最终: {'a', 'b', 'c', 'd'}
  

• 自定义比较器：

  // 自定义比较函数对象 (按字符串长度降序)
  struct LengthCompare {
      bool operator()(const std::string& a, const std::string& b) const {
          return a.length() > b.length(); // 注意：长度相同时需保证严格弱序，此处若长度相同则视为相等（会被唯一性过滤），实际应用需更严谨
      }
  };
  // 使用自定义比较器初始化
  std::set<std::string, LengthCompare> wordsByLength;
  wordsByLength.insert("apple");
  wordsByLength.insert("banana");
  wordsByLength.insert("cherry");
  wordsByLength.insert("kiwi");
  // 遍历输出: banana(6), cherry(6), apple(5), kiwi(4) (注意：长度相同的插入顺序可能影响最终顺序，但 set 不保证插入顺序)
  

2.3 迭代器 (Iterators)

std::set 提供双向迭代器，支持前进 (++) 和后退 (--)。

• 获取迭代器：

  std::set<int> mySet = {10, 20, 30, 40, 50};
  
  // begin() / end()
  std::cout << "Forward traversal: ";
  for (auto it = mySet.begin(); it != mySet.end(); ++it) {
      std::cout << *it << " "; // 输出: 10 20 30 40 50
  }
  std::cout << std::endl;
  
  // cbegin() / cend() (C++11, 常量迭代器)
  std::cout << "Const traversal: ";
  for (auto cit = mySet.cbegin(); cit != mySet.cend(); ++cit) {
      // *cit = 100; // 错误！不能通过常量迭代器修改元素
      std::cout << *cit << " ";
  }
  std::cout << std::endl;
  
  // rbegin() / rend() (反向迭代器)
  std::cout << "Reverse traversal: ";
  for (auto rit = mySet.rbegin(); rit != mySet.rend(); ++rit) {
      std::cout << *rit << " "; // 输出: 50 40 30 20 10
  }
  std::cout << std::endl;
  
  // crbegin() / crend() (C++11, 常量反向迭代器)
  

• 重要： 通过迭代器获取的 Key 是 const 类型。不能通过迭代器修改 set 中的元素值！ 因为修改元素值可能会破坏内部红黑树的排序结构。如果需要修改元素，通常的做法是先删除旧元素，再插入新元素。这里大家实际使用的时候，可以将删除操作和插入操作包装成一个修改元素的函数，方便使用。

2.4 容量 (Capacity)

• empty(): 检查集合是否为空。
• size(): 返回集合中元素的数量。
• max_size(): 返回集合理论上可容纳的最大元素数量（通常是一个非常大的数，受系统和库实现限制）。

std::set<double> dblSet;
std::cout << "Is empty? " << std::boolalpha << dblSet.empty() << std::endl; // true
std::cout << "Size: " << dblSet.size() << std::endl; // 0
std::cout << "Max size: " << dblSet.max_size() << std::endl; // 一个很大的数

dblSet.insert(3.14);
dblSet.insert(2.71);
std::cout << "Is empty now? " << dblSet.empty() << std::endl; // false
std::cout << "Size now: " << dblSet.size() << std::endl; // 2

2.5 元素访问 (Element Access)

• find(const Key& key): 查找键值为 key 的元素。
  • 如果找到，返回指向该元素的迭代器。
  • 如果没找到，返回 end()。

  std::set<std::string> fruitSet = {"apple", "banana", "orange"};
  auto it = fruitSet.find("banana");
  if (it != fruitSet.end()) {
      std::cout << "Found: " << *it << std::endl; // Found: banana
  } else {
      std::cout << "Not found." << std::endl;
  }
  
  it = fruitSet.find("grape");
  if (it == fruitSet.end()) {
      std::cout << "Grape not found." << std::endl; // Grape not found.
  }
  

• count(const Key& key): 统计键值为 key 的元素个数。由于 set 元素的唯一性，返回值只能是 0 (不存在) 或 1 (存在)。

  std::set<int> numSet = {1, 2, 3, 4, 5};
  std::cout << "Count of 3: " << numSet.count(3) << std::endl; // 1
  std::cout << "Count of 6: " << numSet.count(6) << std::endl; // 0
  

• lower_bound(const Key& key): 返回指向第一个不小于（即大于或等于）key 的元素的迭代器。
• upper_bound(const Key& key): 返回指向第一个大于 key 的元素的迭代器。
• equal_range(const Key& key): 返回一个 std::pair，包含 lower_bound 和 upper_bound 的结果。对于 set，因为元素唯一，如果元素存在，则 pair::first 指向该元素，pair::second 指向下一个元素；如果不存在，则两者都指向大于 key 的第一个元素的位置（或 end()）。

std::set<int> scores = {50, 65, 80, 90, 95};

// 查找 >= 80 的第一个元素
auto lb = scores.lower_bound(80);
if (lb != scores.end()) {
    std::cout << "Lower bound for 80: " << *lb << std::endl; // 80
}

// 查找 > 80 的第一个元素
auto ub = scores.upper_bound(80);
if (ub != scores.end()) {
    std::cout << "Upper bound for 80: " << *ub << std::endl; // 90
}

// 查找范围 [80, ...) 直到下一个大于80的元素之前
std::cout << "Elements from 80 onwards: ";
for (auto it = lb; it != ub; ++it) { // 等价于 it != scores.upper_bound(80)
    std::cout << *it << " "; // 80 (因为 80 是唯一的)
}
std::cout << std::endl;

// 查找范围处于[50,90]范围中的元素
auto llb = scores.lower_bound(50);
auto uub = scores.upper_bound(90);//在这里返回的其实就是指向95的迭代器
for (auto it = llb; it != uub; ++it) { 
    std::cout << *it << " "; // 50 65 80 90
}
std::cout << std::endl;

// 使用 equal_range
auto range = scores.equal_range(80);
std::cout << "Equal range for 80: [";
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it; // 80
}
std::cout << "]" << std::endl; // [80]

// 查找不存在的元素 (85)
lb = scores.lower_bound(85); // 指向 90
ub = scores.upper_bound(85); // 指向 90 (因为 90 > 85)
std::cout << "Lower bound for 85: " << (lb != scores.end() ? std::to_string(*lb) : "end") << std::endl; // 90
std::cout << "Upper bound for 85: " << (ub != scores.end() ? std::to_string(*ub) : "end") << std::endl; // 90
range = scores.equal_range(85); // first 和 second 都指向 90

在这里补充一下：我们现实生活中需要查找数据的时候，一般都是这样的：查找某组数据中处于[50,90]范围中的元素。我们使用的一般都是闭区间。但是在C++中，我们使用迭代器去遍历查找元素的时候，我们需要提供的查找区间往往都是左闭右开的区间，也就是一般都是这样[50,95)。所以在set容器中提供了lower_bound和upper_bound。

2.6 修改器 (Modifiers)

这里我先给大家补充一下：

std::pair 类模板简介

std::pair 是 C++ 标准库中的一个基础类模板，用于将两个值组合成一个单元（类似二元组）。它在关联容器（如 std::map）中扮演核心角色，用于存储键值对。

基本结构

template <class T1, class T2>
struct pair {
    T1 first;   // 第一个元素
    T2 second;  // 第二个元素
    
    // 构造函数和其他成员函数...
};

核心特性

1. 简单封装：将两个任意类型的值组合成单一实体
2. 公有成员：直接通过 first 和 second 访问元素
3. 头文件：#include <utility>（或间接通过 <map> 引入）

---

创建与使用示例

#include <iostream>
#include <utility>  // 包含 pair 的定义

int main() {
    // 方法1：直接构造
    std::pair<int, std::string> student(101, "Alice");
    std::cout << "ID: " << student.first 
              << ", Name: " << student.second << "\n";
    // 输出: ID: 101, Name: Alice

    // 方法2：使用 make_pair（自动推导类型）
    auto product = std::make_pair("iPhone", 999.99);
    std::cout << product.first << " costs $" << product.second << "\n";
    // 输出: iPhone costs $999.99

    // 方法3：C++11 统一初始化
    std::pair coordinates{3.5, -2.7};  // 推导为 pair<double, double>
    coordinates.second = 4.2;  // 修改第二个元素

    return 0;
}

---

std::pair 在 std::set 中的关键作用

在 std::set 中，std::pair 主要出现在插入操作的返回值中。虽然 set 本身只存储单个值（不像 map 存储键值对），但其插入操作返回一个 pair 对象，提供关于插入结果的关键信息。

核心应用：插入操作的返回值

std::set::insert() 返回一个 std::pair<iterator, bool>：

• first：迭代器，指向插入的元素（或已存在的等价元素）
• second：布尔值，表示是否成功插入新元素
  • true：元素是新插入的
  • false：元素已存在（未插入）

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> uniqueNames;
    
    // 插入新元素
    auto [it1, inserted1] = uniqueNames.insert("Alice");
    std::cout << "插入Alice: " << std::boolalpha << inserted1 << "\n"; // true
    
    // 插入已存在元素
    auto [it2, inserted2] = uniqueNames.insert("Alice");
    std::cout << "再次插入Alice: " << inserted2 << "\n"; // false
    
    // 使用迭代器
    if (inserted1) {
        std::cout << "新元素: " << *it1 << "\n"; // Alice
    }
    
    return 0;
}

在 std::set 中的典型工作流程

#include <set>
#include <vector>

int main() {
    std::set<int> numberSet;
    std::vector<int> numbers = {5, 2, 5, 8, 2, 3};

    for (int num : numbers) {
        auto result = numberSet.insert(num);
        
        if (result.second) {
            std::cout << num << " 插入成功\n";
        } else {
            std::cout << num << " 已存在，未插入\n";
        }
    }
    
    /* 输出:
        5 插入成功
        2 插入成功
        5 已存在，未插入
        8 插入成功
        2 已存在，未插入
        3 插入成功
    */
    
    return 0;
}

为什么需要这个返回值？

1. 避免冗余操作：检测元素是否已存在

   std::set<std::string> usernames;
   
   auto result = usernames.insert("new_user");
   if (!result.second) {
       std::cout << "用户名已存在，请选择其他用户名\n";
   }
   

2. 获取元素位置：直接获得插入位置的迭代器

   std::set<int> sortedData;
   auto [pos, inserted] = sortedData.insert(42);
   
   if (inserted) {
       // 在新元素后插入相关数据
       sortedData.insert(++pos, 43); 
   }
   

3. 高效更新：结合自定义类型使用

   struct Product {
       int id;
       std::string name;
       bool operator<(const Product& p) const { return id < p.id; }
   };
   
   std::set<Product> inventory;
   auto result = inventory.insert({101, "Widget"});
   
   if (!result.second) {
       // 产品已存在，更新信息
       const_cast<Product&>(*result.first).name = "Improved Widget";
   }
   

注意事项

• set 元素本身是常量（不可修改键），因此不能直接通过迭代器修改元素
• 返回的迭代器指向集合中的实际元素（常量对象）
• C++17 起可使用结构化绑定简化代码

总结

在 std::set 中，std::pair 的核心作用是：

1. 提供插入操作的完整结果反馈
2. 返回包含两个关键信息的复合值：
   • 迭代器（指向插入位置或现有元素）
   • 布尔值（表示是否实际插入）
3. 使操作更高效，避免额外的查找步骤
4. 支持现代 C++ 的结构化绑定语法

这种设计模式体现了 C++ “不为你不需要的东西付费” 的原则，只在需要时提供完整的状态信息，同时保持基础操作的高效性。

---

• insert: 插入元素。有几种形式：

  • insert(const value_type& value): 插入单个值。返回一个 std::pair<iterator, bool>。
    • pair::first 是指向插入元素（或阻止插入的现有元素）的迭代器。
    • pair::second 是一个 bool 值：true 表示插入成功，false 表示元素已存在（插入失败）。

    std::set<int> s;
    auto result = s.insert(10);
    if (result.second) {
        std::cout << "10 inserted successfully." << std::endl;
    }
    result = s.insert(10); // 再次插入
    if (!result.second) {
        std::cout << "10 already exists. Insertion failed." << std::endl;
        std::cout << "Existing element: " << *(result.first) << std::endl; // 10
    }
    

  • insert(value_type&& value) (C++11): 移动插入。
  • insert(iterator hint, const value_type& value): 使用提示位置 hint (通常指向插入点之后的元素) 尝试优化插入。返回指向插入元素（或现有元素）的迭代器。提示正确可以接近 O(1)，否则退化为 O(log n)。

    std::set<int> s = {10, 30, 50};
    auto hint = s.find(30); // 找到 30 的位置
    if (hint != s.end()) {
        // 在 hint 之后插入 (优化位置)
        auto it = s.insert(hint, 40); // 插入在 30 和 50 之间
        std::cout << "Inserted 40 using hint." << std::endl;
    }
    

  • insert(InputIt first, InputIt last): 插入范围 [first, last) 内的元素。

    std::vector<int> v = {5, 15, 25};
    s.insert(v.begin(), v.end()); // s 现在包含 5, 10, 15, 25, 30, 40, 50 (假设之前例子)
    

  • insert(std::initializer_list<value_type> ilist) (C++11): 插入初始化列表。

    s.insert({1, 2, 3}); // 插入 1, 2, 3
    

• emplace (C++11): 直接在 set 内部构造元素，避免不必要的拷贝或移动。参数是构造 Key 对象所需的参数。返回值类型与 insert(value) 相同 (pair<iterator, bool>)。

  struct Person {
      std::string name;
      int age;
      Person(std::string n, int a) : name(std::move(n)), age(a) {}
      // 需要定义比较运算符 (通常重载 <) 或为 set 提供自定义比较器
      bool operator<(const Person& other) const {
          return name < other.name; // 按名字排序
      }
  };
  
  std::set<Person> people;
  // 使用 insert 需要构造临时 Person 对象 (可能涉及拷贝)
  people.insert(Person("Alice", 30));
  
  // 使用 emplace 直接在集合内构造 Person
  auto empResult = people.emplace("Bob", 25); // 传递构造参数
  if (empResult.second) {
      std::cout << "Bob emplaced successfully." << std::endl;
  }
  

• emplace_hint (C++11): 类似带提示的 insert，但使用 emplace 的方式构造元素。参数为提示迭代器和构造参数。

  auto hint = people.find(Person("Alice", 30)); // 假设存在
  if (hint != people.end()) {
      people.emplace_hint(hint, "Charlie", 40); // 尝试在 Alice 附近插入 Charlie
  }
  

• erase: 删除元素。有几种形式：

  • erase(iterator pos): 删除迭代器 pos 指向的元素。返回指向被删除元素之后元素的迭代器（或 end()）。注意： pos 必须是有效的、可解引用的迭代器，不能是 end()。

    std::set<int> s = {1, 2, 3, 4, 5};
    auto it = s.find(3);
    if (it != s.end()) {
        it = s.erase(it); // 删除 3, it 现在指向 4
        std::cout << "After erase(3), *it is: " << *it << std::endl; // 4
    }
    

  • erase(const key_type& key): 删除键值为 key 的元素（如果存在）。返回被删除的元素个数（对于 set 是 0 或 1）。

    int count = s.erase(2); // 删除键 2
    std::cout << "Removed " << count << " element(s)." << std::endl; // 1
    count = s.erase(10); // 键 10 不存在
    std::cout << "Removed " << count << " element(s)." << std::endl; // 0
    

  • erase(iterator first, iterator last): 删除范围 [first, last) 内的元素。返回 last（C++11 起）。

    auto first = s.lower_bound(2);
    auto last = s.upper_bound(4);
    s.erase(first, last); // 删除所有 >=2 且 <5 的元素 (假设 s={1, 4, 5} 后，删除4)
    // 现在 s 包含 1 和 5
    

• clear(): 删除所有元素，使容器变为空。

  std::cout << "Size before clear: " << s.size() << std::endl; // e.g., 2
  s.clear();
  std::cout << "Size after clear: " << s.size() << std::endl; // 0
  std::cout << "Is empty? " << s.empty() << std::endl; // true
  

• swap(set& other): 交换两个同类型 set 容器的内容。高效（通常只交换内部指针）。

  std::set<int> setA = {1, 2, 3};
  std::set<int> setB = {4, 5, 6};
  setA.swap(setB);
  // 现在 setA = {4,5,6}, setB = {1,2,3}
  

• extract (C++17): 从集合中“抽取”节点。返回一个 node_type 句柄。不破坏元素本身。之后可以将该节点插入到另一个允许重复键或使用相同比较器的 set 或 multiset，或者修改其键（如果安全）后再插回。

  std::set<int> s = {10, 20, 30};
  auto node = s.extract(20); // 尝试抽取键为 20 的节点
  if (!node.empty()) { // 检查抽取是否成功
      std::cout << "Extracted value: " << node.value() << std::endl; // 20
      // 可以修改 node.value() (如果比较器允许且修改后仍保持唯一性和排序)
      // node.value() = 25; // 修改值
      s.insert(std::move(node)); // 将节点插回原集合或另一个兼容集合
  }
  // 如果修改了值，插入时会根据新值找到合适位置
  

• merge (C++17): 将另一个兼容的 set 或 multiset 的元素“合并”到当前 set 中。源容器中能成功插入（唯一键）的元素会被移动到当前容器，不能插入的（重复键）则保留在源容器中。

  std::set<int> src = {15, 25, 35};
  std::set<int> dst = {10, 20, 30};
  
  dst.merge(src);
  // 现在 dst 可能包含: 10, 15, 20, 25, 30, 35 (假设全部唯一)
  // src 现在为空 (所有元素都被移动走)
  std::cout << "dst size: " << dst.size() << std::endl; // 6
  std::cout << "src size: " << src.size() << std::endl; // 0
  
  std::set<int> src2 = {20, 40}; // 20 在 dst 已存在
  dst.merge(src2);
  // dst 现在: 10, 15, 20, 25, 30, 35, 40 (20 已存在，不会被移动；40 是新的，被移动)
  // src2 现在: {20} (重复的 20 没被移走)
  

2.7 观察器 (Observers)

• key_comp(): 返回用于比较键的函数对象（比较器）的副本。
• value_comp(): 对于 set，因为 key 就是 value，所以 value_comp() 等同于 key_comp()。返回用于比较值的函数对象的副本。

std::set<int, std::greater<int>> descendingSet = {50, 20, 80}; // 使用 std::greater 降序排序

// 获取比较器对象
auto keyComp = descendingSet.key_comp();
auto valueComp = descendingSet.value_comp(); // 与 key_comp 相同

std::cout << "Using key_comp: ";
// 比较两个键 (80 和 50)
std::cout << "Is 80 'less than' 50 according to our comparator? "
          << std::boolalpha << keyComp(80, 50) << std::endl; // true! 因为 greater: 80 > 50, 所以 80 "小于" 50 在 greater 语义下是 false? 注意语义
// 正确理解: keyComp(a, b) 在基于 greater 的 set 中，如果 a 应该排在 b 前面，则返回 true。
// 在 greater 下，大的数排前面。keyComp(80, 50) 检查 80 是否应该排在 50 前面 -> 80>50 是 true，所以 keyComp(80,50) 返回 true。

// 遍历并理解排序
std::cout << "Elements (descending): ";
for (int num : descendingSet) {
    std::cout << num << " "; // 80 50 20
}
std::cout << std::endl;

// 使用 value_comp 做同样的事情 (结果相同)
std::cout << "value_comp(80, 50): " << valueComp(80, 50) << std::endl; // true

2.8 非成员函数 (Non-member functions - Overloaded Operators)

• 比较运算符 (==, !=, <, <=, >, >=): 可以比较两个 set。比较基于元素的字典序 (lexicographical comparison)，使用各自的 key_comp() 函数对象来比较元素。

  std::set<int> a = {1, 2, 3};
  std::set<int> b = {1, 2, 3};
  std::set<int> c = {1, 2, 4};
  std::set<int> d = {1, 2};
  
  std::cout << "a == b: " << (a == b) << std::endl; // true (元素和顺序都相同)
  std::cout << "a == c: " << (a == c) << std::endl; // false (元素不同)
  std::cout << "a != d: " << (a != d) << std::endl; // true (大小不同)
  std::cout << "a < c: " << (a < c) << std::endl;   // true (在第一个不同元素处, 3 < 4)
  std::cout << "c > a: " << (c > a) << std::endl;   // true (同上)
  std::cout << "d < a: " << (d < a) << std::endl;   // true (d 是 a 的前缀)
  

• std::swap(set1, set2) (C++11): 非成员函数版本的 swap，效果同成员函数 swap。

  std::swap(a, c); // 交换 a 和 c 的内容
  

3. 关键点总结与注意事项

1. 唯一键与排序： set 的核心价值在于自动维护元素的唯一性和排序。这是选择 set 而非 vector 或 list 的主要原因。
2. 查找效率： 基于红黑树的实现保证了查找（find, count, lower_bound 等）、插入（insert, emplace）和删除（erase）操作的平均和最差时间复杂度都是 O(log n)，非常高效，尤其适合需要频繁查找的场景。
3. 元素不可直接修改： 不能通过迭代器修改元素的值（因为这会破坏排序）。修改的标准做法是先 erase 旧元素，再 insert 新元素。C++17 的 extract 提供了一种更高效的修改方式（先抽取节点，修改键，再插回）。
4. 迭代器稳定性：
   • 插入操作 (insert, emplace)：通常不会使指向其他元素的迭代器、指针或引用失效（除非该插入导致树的重平衡影响了特定节点，但标准库通常保证指向未删除元素的迭代器在插入后仍然有效）。
   • 删除操作 (erase)：会使指向被删除元素的迭代器、指针和引用失效。指向其他元素的迭代器、指针和引用通常保持有效。
5. 自定义类型： 要在 set 中存储自定义类型 (如 struct 或 class)：
   • 必须定义严格的弱序： 最常见的方式是在类型内部重载 < 运算符 (bool operator<(const MyType& other) const)。
   • 或者提供自定义比较器： 在声明 set 时作为第二个模板参数传入（如 std::set<Person, PersonCompare>）。比较器可以是函数对象 (Functor) 或函数指针。比较器必须实现严格的弱序关系。
6. 内存： set 的每个元素都需要存储额外的树节点信息（颜色、父指针、子指针等），内存开销通常比 vector 或数组大。
7. set vs unordered_set：
   • set: 有序（排序遍历），基于红黑树 (O(log n) 操作)，内存开销相对大，迭代器稳定（除删除元素外）。
   • unordered_set: 无序（基于哈希表），平均 O(1) 操作（最坏 O(n)），内存开销可能更大（桶），迭代器在重哈希时可能失效，需要为元素定义哈希函数。
   • 选择： 如果需要元素有序遍历或有序范围查询 (lower_bound)，选 set。如果只需要检查存在性、唯一性，且对顺序无要求，追求平均 O(1) 的查找速度，选 unordered_set。
8. set vs multiset： multiset 允许重复键值，而 set 不允许。两者的接口非常相似，但 multiset 的 count 可以返回大于 1 的值，find 返回第一个匹配元素的迭代器，equal_range 更有用。

4. 应用场景示例

• 维护唯一元素列表： 例如，从大量数据中提取不重复的用户 ID、单词等。
• 需要快速查找成员： 例如，实现白名单/黑名单（检查一个元素是否在集合中）。
• 需要有序遍历： 例如，按分数排序的学生名单，按时间戳排序的事件（但注意 set 排序基于键值本身，不是插入顺序）。
• 范围查询： 例如，查找成绩在 [80, 90] 分之间的所有学生（使用 lower_bound(80) 和 upper_bound(90)）。
• 作为其他算法的基础： set 的有序性和唯一性使其成为实现集合运算（并集 std::set_union, 交集 std::set_intersection, 差集 std::set_difference）的理想输入容器。

5. 时间复杂度总结

操作	平均时间复杂度	最差时间复杂度	备注
insert	O(log n)	O(log n)
emplace	O(log n)	O(log n)
erase	O(log n)	O(log n)	按值或单迭代器
erase (范围)	O(k log n)	O(k log n)	k 是删除的元素数量
find	O(log n)	O(log n)
count	O(log n)	O(log n)
lower_bound	O(log n)	O(log n)
upper_bound	O(log n)	O(log n)
equal_range	O(log n)	O(log n)
begin/end	O(1)	O(1)
size	O(1)	O(1)	C++11 起保证
empty	O(1)	O(1)
clear	O(n)	O(n)	析构所有元素
swap	O(1)	O(1)	只交换内部指针
extract(节点)	O(log n)	O(log n)	抽取单个节点
merge	O(n log (m+n))	O(n log (m+n))	n = this->size(), m = source.size()