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

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

前言

在 C++ STL 容器中，set 系列（set 与 multiset）是基于红黑树实现的关联式容器，核心特性是 '自动排序' 与 '高效查找'。它既能解决 '数据去重 + 排序' 的基础需求，也能在复杂场景中（如区间删除、频率统计）提供 O(log N) 级别的操作效率。本文将结合实战代码，从 set 的核心概念入手，拆解其构造、增删查、区间操作等关键接口，同时对比 set 与 multiset 的差异，帮你彻底掌握这一高频使用容器。

一、容器分类：序列式容器与关联式容器的本质区别

STL 容器的设计围绕 '数据如何存储与访问' 展开，序列式与关联式容器的核心差异体现在存储逻辑与访问方式上，具体对比如下：

特性	序列式容器（如 vector、list）	关联式容器（如 set、map）
存储逻辑	按插入顺序存储，元素位置由插入时机决定	按键（key）的内在规则存储（如排序规则）
访问方式	通过下标/迭代器位置访问（如 vec[2]）	通过键值匹配访问（如 set.find(3)）
底层结构	动态数组（vector）、双向链表（list）等	平衡二叉搜索树（红黑树，set/map）、哈希表（unordered_set）
核心优势	插入顺序稳定，适合频繁增删尾部元素	自动排序，查找/删除效率高（O(log N) 或 O(1)）
典型使用场景	存储连续数据、需要按插入顺序遍历、动态扩容需求	去重排序、快速查找、键值映射、区间操作

补充说明：

• 序列式容器强调 '位置'，元素的价值在于其存储的内容本身；
• 关联式容器强调 '关联关系'，元素的价值在于通过 key 快速定位（如 '根据 ID 查找用户信息'）；
• set 作为 'key' 型关联式容器，仅存储键值，核心功能是 '基于 key 的排序与查找'。

二、set 系列核心原理：红黑树赋能的高效特性

set 与 multiset 底层均基于红黑树（一种自平衡二叉搜索树）实现，这一结构赋予它们以下核心特性：

1. 自动排序：红黑树的中序遍历结果为有序序列，因此 set 插入元素后会自动按 key 的默认规则（less 升序）排序，无需手动调用排序函数，如果需要按自己的需求比较可以自行实现仿函数传给第二个模板参数。
2. 去重与允许重复：set 不允许存储重复 key（multiset 支持重复 key）；
3. 不可修改 key：set 的迭代器为 const_iterator，无法通过迭代器修改 key（修改会破坏红黑树结构）；
4. 高效操作：增删查操作的时间复杂度均为 O(log N)，远优于 vector 的 O(N)。

set 的声明：

template<class T, // set::key_type/value_type
           class Compare = less<T>, // set::key_compare/value_compare
           class Alloc = allocator<T>> // set::allocator_type
class 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 (& e : s) {
        cout << e << ;
    }
    cout << endl;
}

{
    ();
}

set 与 multiset 的核心差异总结：

操作	set	multiset
插入重复元素	自动去重，重复元素插入失败	不去重，保留所有重复元素，插入成功
find(key)	返回唯一匹配元素的迭代器，未找到返回 end()	返回中序遍历中第一个匹配元素的迭代器
count(key)	返回 0 或 1（仅用于判断元素是否存在）	返回元素在容器中实际出现的次数
erase(key)	若元素存在则删除 1 个，不存在则删除 0 个	删除容器中所有与 key 匹配的元素

五、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++ 开发者的必备技能。