全面解析 C++ STL 中的 set 和 map

C++ 标准模板库（STL）中的关联式容器以其强大的功能和高效性成为开发者解决复杂数据组织问题的重要工具。其中，set 和 map 是最常用的两类关联容器。本篇博客将从基本特性、底层实现、用法详解、高级案例以及性能优化等多个角度，详细解读它们的设计与使用。

目录

1. 什么是关联式容器

关联式容器的核心特性

2. set 容器详解

2.1 基本概念与特性

2.2 底层实现：红黑树

红黑树的特性

红黑树的操作

2.3 构造函数

2.4 常用操作与复杂度分析

插入操作

查找操作

删除操作

遍历

2.5 特殊操作与技巧

(1) 自定义排序规则

(2) 范围删除

(3) 应用：求两个数组的交集

2.6 multiset 的区别与应用

1. 什么是关联式容器

关联式容器是一类根据关键字组织和管理数据的容器。与序列式容器（如 vector 和 list）相比，关联式容器的主要区别如下：

关联式容器分为有序和无序两类：

1. 有序容器：如 set 和 map，基于平衡二叉树（红黑树）实现，数据按排序规则组织。
2. 无序容器：如 unordered_set 和 unordered_map，基于哈希表实现，提供更高效的查找速度，但不保证元素顺序。

关联式容器的核心特性

• 键值对：关联式容器通过关键字对元素进行组织，set 中的关键字即为数据本身，而 map 则以键值对形式存储数据。
• 自动排序：有序容器会自动对数据进行排序（升序或自定义规则）。
• 高效操作：插入、删除、查找的平均时间复杂度为 O(log⁡N)O(\log N)O(logN)（红黑树实现）。

2. set 容器详解

2.1 基本概念与特性

set 是一种集合数据结构，用于存储唯一且自动排序的元素。它的主要特点如下：

• 数据唯一性：同一元素不能重复插入。
• 自动排序：默认按升序排序，可通过自定义比较器更改排序规则。
• 迭代器类型：set 支持双向迭代器，不支持随机访问。
• 底层实现：使用红黑树作为存储结构。

2.2 底层实现：红黑树

红黑树的特性

红黑树是一种平衡二叉搜索树，满足以下性质：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点（nullptr 或 NIL 节点）是黑色。
4. 如果一个节点是红色，则其子节点必须是黑色（即红色节点不能相邻）。
5. 从任意节点到其每个叶子节点的路径都包含相同数量的黑色节点。

红黑树的操作

• 插入：通过旋转和重新着色，确保平衡性和红黑性质。
• 删除：比插入更复杂，同样通过旋转和着色维护树的性质。
• 查找：沿树遍历，时间复杂度为 O(log⁡N)O(\log N)O(logN)。

在 set 和 map 中，红黑树用来高效实现元素的有序存储和快速查找。

2.3 构造函数

set 提供以下几种构造方式：

1. 默认构造：创建一个空集合。

   set<int> s;
   

2. 初始化列表构造：直接用 {} 初始化集合。

   set<int> s = {3, 1, 4, 1, 5, 9};  // 重复元素自动去重
   

3. 迭代器区间构造：从其他容器的元素构造集合。

   vector<int> v = {1, 2, 3, 4};
   set<int> s(v.begin(), v.end());
   

4. 自定义比较规则：

   set<int, greater<int>> s = {3, 1, 4};  // 按降序排序
   

2.4 常用操作与复杂度分析

插入操作

set<int> s;
auto res = s.insert(10);  // 插入 10
if (res.second) {
    cout << "插入成功" << endl;
} else {
    cout << "插入失败" << endl;
}

查找操作

if (s.find(20) != s.end()) {
    cout << "找到元素 20" << endl;
}

删除操作

s.erase(10);  // 删除值为 10 的元素

遍历

for (int x : s) {
    cout << x << " ";  // 正向遍历
}
for (auto it = s.rbegin(); it != s.rend(); ++it) {
    cout << *it << " ";  // 反向遍历
}

2.5 特殊操作与技巧

(1) 自定义排序规则

set 默认按升序排序，使用仿函数或 std::greater 可修改排序规则：

set<int, greater<int>> s = {3, 1, 4};

(2) 范围删除

删除值在 [low, high) 范围内的所有元素：

s.erase(s.lower_bound(10), s.upper_bound(50));

(3) 应用：求两个数组的交集

vector<int> intersection(const vector<int>& nums1, const vector<int>& nums2) {
    set<int> s1(nums1.begin(), nums1.end());
    set<int> s2(nums2.begin(), nums2.end());
    vector<int> result;

    for (int x : s1) {
        if (s2.count(x)) result.push_back(x);
    }

    return result;
}

2.6 multiset 的区别与应用

multiset 与 set 的区别在于：

1. multiset 允许存储重复元素。
2. 插入、删除和查找操作的接口与 set 相同，但返回的结果会包含重复项。

multiset<int> ms = {1, 2, 2, 3};
ms.insert(2);  // 再次插入 2

3. map 容器详解

3.1 基本概念与特性

map 是一个关联式容器，用于存储键值对（key-value）。与 set 相比，map 不仅存储键（key），还存储与每个键关联的值（value）。
map 的主要特点包括：

• 键唯一性：每个键在 map 中都是唯一的。
• 自动排序：默认按照键的升序排序，也可以通过自定义比较器来更改排序规则。
• 底层实现：基于红黑树实现，操作复杂度为 O(log⁡N)O(\log N)O(logN)。
• 支持随机访问：与 set 不同，map 中存储的键值对支持通过键快速查找对应的值。

map<int, string> m;
m[1] = "apple";  // 插入键值对 (1, "apple")
m[2] = "banana"; // 插入键值对 (2, "banana")
m[3] = "cherry"; // 插入键值对 (3, "cherry")

内部存储结构

map 使用红黑树存储数据，保证了所有元素按键值自动排序。在 map 中，每个节点存储一个 pair<const Key, T>，其中 const Key 表示键，T 表示值。红黑树的特点确保了查找、插入和删除操作的时间复杂度都为 O(log⁡N)O(\log N)O(logN)。

3.2 构造与初始化

map 提供了多种构造方法，以适应不同的使用场景：

1. 默认构造：创建一个空 map。

   map<int, string> m;
   

2. 初始化列表构造：通过初始化列表直接创建 map。

   map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};
   

3. 范围构造：从另一个容器（如 set、vector 等）构造 map。

   vector<pair<int, string>> v = {{1, "apple"}, {2, "banana"}};
   map<int, string> m(v.begin(), v.end());
   

4. 自定义比较器：通过传入自定义比较器，指定键的排序方式。

   map<int, string, greater<int>> m;  // 降序排序
   m[2] = "banana";
   m[1] = "apple";
   

3.3 常用操作与复杂度分析

插入与查找操作

• 插入：可以通过 insert 方法插入新的键值对，也可以通过 operator[] 插入或修改键值对。

  map<int, string> m;
  m.insert({1, "apple"});
  m[2] = "banana";  // 插入或修改
  

• 查找：find 方法返回一个迭代器，指向指定键的键值对，若未找到则返回 end()。

  auto it = m.find(1);
  if (it != m.end()) {
      cout << "Found: " << it->second << endl;  // 输出 "apple"
  }
  

删除操作

删除某个键值对：

m.erase(1);  // 删除键为 1 的元素

3.4 遍历与修改

map 提供了多种遍历方法：

1. 范围 for：

   for (const auto& [key, value] : m) {
       cout << key << ": " << value << endl;
   }
   

2. 传统迭代器：

   for (auto it = m.begin(); it != m.end(); ++it) {
       cout << it->first << ": " << it->second << endl;
   }
   

修改值

可以通过迭代器直接修改值，operator[] 也支持修改已有键的值：

m[2] = "grape";  // 修改键为 2 的值为 "grape"
auto it = m.find(2);
if (it != m.end()) {
    it->second = "orange";  // 通过迭代器修改值
}

3.5 特殊操作与进阶技巧

(1) 下界与上界

通过 lower_bound() 和 upper_bound() 方法，可以获取某个键的下界和上界，常用于区间查找。

• lower_bound(key)：返回第一个大于等于 key 的元素。
• upper_bound(key)：返回第一个大于 key 的元素。

map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};
auto lb = m.lower_bound(2);  // 返回键为 2 或大于 2 的第一个元素
cout << lb->second << endl;  // 输出 "banana"

(2) 自定义排序规则

如同 set，map 也可以通过自定义比较器来实现不同的排序规则。

map<int, string, greater<int>> m = {{1, "apple"}, {3, "cherry"}, {2, "banana"}};
for (const auto& [key, value] : m) {
    cout << key << ": " << value << endl;
}  // 输出：3: cherry 2: banana 1: apple

(3) 范围删除

删除某个键值范围内的元素，常用于清除一段区间：

map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};
m.erase(m.lower_bound(2), m.upper_bound(3));  // 删除键为 2 和 3 的元素

3.6 multimap 的区别与应用

multimap 是 map 的扩展，允许相同的键有多个值（即支持键的冗余）。与 map 的区别在于，multimap 在插入重复键时不会丢失数据，而 map 会自动覆盖原有键。

multimap<int, string> mm;
mm.insert({1, "apple"});
mm.insert({1, "banana"});
mm.insert({2, "cherry"});

for (const auto& [key, value] : mm) {
    cout << key << ": " << value << endl;  // 输出：1: apple 1: banana 2: cherry
}

multimap 在某些场景下非常有用，例如存储学生成绩时，可能有多个学生取得相同的分数。

4. 高级案例：综合利用 set 和 map

4.1 查找两个数组的交集

vector<int> intersection(const vector<int>& nums1, const vector<int>& nums2) {
    set<int> s1(nums1.begin(), nums1.end());
    set<int> s2(nums2.begin(), nums2.end());
    vector<int> result;

    for (int x : s1) {
        if (s2.count(x)) result.push_back(x);
    }

    return result;
}

4.2 构建词频统计表

map<string, int> wordCount(const vector<string>& words) {
    map<string, int> wordMap;
    for (const string& word : words) {
        wordMap[word]++;
    }
    return wordMap;
}

4.3 高效查找链表中的环

bool hasCycle(ListNode* head) {
    set<ListNode*> visited;
    while (head != nullptr) {
        if (visited.find(head) != visited.end()) {
            return true;  // 找到环
        }
        visited.insert(head);
        head = head->next;
    }
    return false;
}

5. 性能优化与注意事项

5.1 使用 unordered_map 和 unordered_set

在很多查找密集型的应用中，unordered_map 和 unordered_set 基于哈希表实现，提供常数时间复杂度 O(1)O(1)O(1) 的查找和插入操作。它们的性能优势适用于不需要保持元素顺序的场景。

5.2 避免不必要的拷贝

当插入大量数据时，可以使用 emplace() 来避免不必要的对象拷贝。emplace() 可以直接构造元素，而无需创建临时对象。

map<int, string> m;
m.emplace(1, "apple");  // 不会发生拷贝

5.3 避免频繁修改键

map 不支持修改键，修改键会导致数据结构破坏。因此，避免频繁修改键，而应使用新的键值对进行插入和删除。

6. 总结

通过本文的详细解析，我们全面了解了 C++ 中 set 和 map 容器的使用、底层实现以及高效操作技巧。掌握这些基本知识后，开发者可以灵活使用 set 和 map 来处理各种复杂的关联数据问题，从而提高程序的效率和可读性。

在实际开发中，选择合适的容器（如 map 与 unordered_map，set 与 unordered_set）可以帮助我们应对不同的数据处理需求，避免性能瓶颈。希望通过本文的学习，你能够深入掌握这些强大的容器，提升 C++ 编程技能。