C++ STL set 系列：底层原理、核心接口与实战场景

参考文档：set - C++ Reference

set 的构造相关接口：

// empty (1) 无参默认构造
explicit set(const key_compare& comp = key_compare(),
             const allocator_type& alloc = allocator_type());

// range (2) 迭代器区间构造
template<class InputIterator>
set(InputIterator first, InputIterator last,
    const key_compare& comp = key_compare(),
    const allocator_type& = allocator_type());

// copy (3) 拷贝构造
set(const set& x);

// initializer list (5) initializer 列表构造
set(initializer_list<value_type> il,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

// 迭代器是一个双向迭代器 iterator -> a bidirectional iterator to const value_type
// 正向迭代器 iterator begin(); iterator end();
// 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();

三、set 核心接口实战：基于实操代码详解

下面会通过多个测试函数覆盖 set 的核心操作，我们结合代码解析其使用方法与注意事项。

3.1 初始化与插入：去重 + 自动排序

set 支持多种插入方式，插入后自动去重并按升序排列。代码示例（注意看注释）：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <set>
using namespace std;

// 测试 set 的插入与遍历（去重 + 自动排序）
void test_set1() {
    set<int> s;
    // 方式 1：单个元素插入
    // s.insert(3); s.insert(1); s.insert(2); s.insert(5); s.insert(3); s.insert(5); s.insert(6);
    
    // 方式 2：初始化列表批量插入
    s.insert({3, 1, 2, 5, 3, 5, 6});
    
    // 遍历方式 1：迭代器遍历（注意：*it 不可修改）
    // 遍历结果：去重 + 有序
    set<int>::iterator it = s.begin();
    while (it != s.end()) {
        //*it = 1; // 不能修改
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
    // 遍历方式 2：范围 for 循环
    for (auto& e : s) {
        cout << e << " ";
    }
    cout << endl;
}

int main() {
    test_set1();
    return 0;
}

关键说明：

• 若需降序排序，可指定排序仿函数：set<int, greater<int>> s。

3.2 查找与删除：精准操作单个元素

set 提供 find（查找）、count（统计）、erase（删除）接口，支持按 key 或迭代器操作：

// 测试 set 的查找与删除
void test_set2() {
    set<int> s;
    s.insert({3, 1, 2, 5, 3, 5, 6}); // 去重后：1 2 3 5 6
    int x = 0;
    cin >> x;
    cout << s.erase(x) << endl; // 删掉了几个返回值就是几，在 set 里就是 1，没删掉就是 0
    
    // 查找元素：find 返回迭代器，未找到则返回 s.end()
    // auto pos = s.find(x);
    // if (pos != s.end()) { s.erase(pos); } // 找到后删除
    
    // 统计元素个数：set 中仅返回 0 或 1（判断存在性）
    if (s.count(x)) {}
    
    for (auto& e : s) {
        cout << e << " ";
    }
    cout << endl;
}

int main() {
    test_set2();
    return 0;
}

关键说明：

• erase 的返回值是删除元素的个数，在 set 里要么是 0 要么是 1，multiset 删了几个就是几。
• count 在 set 中主要用于判断元素是否存在，在 multiset 中返回实际个数。

3.3 区间操作：lower_bound 与 upper_bound

set 的区间操作依赖 lower_bound 和 upper_bound，用于快速定位边界，结合 erase 可高效删除区间元素：

// 测试 set 的区间操作
void test_set3() {
    set<int> s;
    s.insert({3, 1, 2, 5, 3, 5, 6, 7, 9});
    for (auto& e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    // 需求：删除 [3, 8] 区间的元素（即>=3 且<=8）
    // lower_bound(val)：返回第一个>=val 的迭代器（此处指向 3）
    auto it1 = s.lower_bound(3);
    // upper_bound(val)：返回第一个>val 的迭代器（此处指向 9）
    auto it2 = s.upper_bound(8);
    
    // 按迭代器区间删除：删除 [it1, it2) 内的元素
    s.erase(it1, it2);
    
    for (auto& e : s) {
        cout << e << " ";
    }
    cout << endl;
}

int main() {
    test_set3();
}

关键说明：

• lower_bound 与 upper_bound 的时间复杂度均为 O(log N)，是区间操作的核心；
• 区间 [it1, it2) 为 '左闭右开'，这样符合 STL 迭代器区间的通用设计（如 [begin, end)）。

四、multiset：支持重复 key 的关联式容器

multiset 与 set 接口一致，核心差异是允许重复 key，适用于需要存储相同元素并统计频率的场景：

// 测试 multiset（支持重复 key）
void test_multiset() {
    multiset<int> s;
    // 插入重复元素（不会去重）
    s.insert({3, 1, 2, 5, 3, 5, 6, 3, 3});
    
    // 1. 遍历：有序但保留重复元素
    multiset<int>::iterator it = s.begin();
    while (it != s.end()) {
        //*it = 1; // 不能修改
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
    // 2. 查找：返回中序遍历的第一个目标元素
    auto pos = s.find(3);
    // 打印所有 3
    while (pos != s.end() && *pos == 3) {
        cout << *pos << " ";
        ++pos;
    }
    cout << endl;
    
    // 3. 查找有 3 的区间，左闭右开，【)//std::pair<multiset<int>::iterator, multiset<int>::iterator> ret = s.equal_range(3);
    auto ret = s.equal_range(3);
    
    // 4. 统计：返回元素实际个数
    cout << s.count(3) << endl; // 有几个 3
    
    // 5. 删除：按 key 删除所有匹配元素
    cout << s.erase(3) << endl; // 删掉所有的 3，并返回删掉的 3 的个数
    s.erase(5); // 删掉所有的 5
    
    for (auto& e : s) {
        cout << e << " ";
    }
    cout << endl;
}

int main() {
    test_multiset();
}

set 与 multiset 的核心差异总结：

五、set 系列的实战价值：解决实际开发问题

set 系列的 '自动排序 + 高效查找' 特性在算法与工程中应用广泛，以下是两个典型题目：

5.1：环形链表 II

题目链接：142. 环形链表 II - 力扣（LeetCode） 题目要求：找到环形链表的入口结点 思路：用 set 存储遍历过的节点，若插入节点时发现已存在，该节点即为入口。

C++ 算法代码：

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while (cur) {
            auto ret = s.find(cur);
            // 不存在就插入节点
            if (ret == s.end()) s.insert(cur);
            // 已经存在证明这就是入环节点
            else return cur;
            cur = cur->next;
        }
        return nullptr;
    }
};

5.2 两个数组的交集（扩展差集思路）

题目链接：349. 两个数组的交集 - 力扣（LeetCode） 题目要求：给定两个数组，计算它们的交集（结果需去重）。 思路：用 set 对两个数组去重 + 排序，再用双指针遍历两个 set，找到共同元素。

C++ 算法代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        // 1. 用 set 对两个数组去重 + 排序
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        
        // 2. 双指针遍历，找共同元素
        while (it1 != s1.end() && it2 != s2.end()) {
            // 小的++
            if (*it1 < *it2) ++it1;
            else if (*it1 > *it2) ++it2;
            // 相等的是交集，加入结果，然后同时++
            else {
                ret.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return ret;
    }
};

差集和交集的实战使用：多端文件同步的逻辑

通过 '差集识别新增 / 缺失文件，交集比对时间戳确定更新方向'，避免全量传输，大幅减少带宽消耗和同步时间，是云存储、多端协作工具（如网盘、协同办公软件）的常见底层逻辑之一。

结语

set 系列作为 STL 关联式容器的核心，以红黑树为支撑，实现了自动排序、高效查找与去重（或允许多重复）的能力，是处理 '有序数据管理' 场景的利器。掌握其接口与特性，既能简化代码逻辑，又能在算法、工程中提升性能，是 C++ 开发者的必备技能。