1. Set

在 C++ 标准库中，std::set 是另一种常用的关联容器，它以单个元素的形式存储数据，核心特点是元素唯一且有序。凭借底层红黑树的实现，set 支持高效的插入、删除和查找操作，在去重、有序存储等场景中应用广泛（比如存储唯一 ID、维护有序序列等）。本文将从 set 的核心特性出发，详解其用法、语法演进及同类容器 multiset 的差异。

核心特性

• 元素唯一：不允许存储重复元素（插入重复元素会被忽略）；

• 元素有序：默认按 less 规则升序排列（可通过自定义比较器修改排序行为）；

• 元素可排序：存储的元素类型必须支持比较操作（或提供自定义比较器）；

• 无下标访问：由于没有键值对结构，set 不支持 operator[] 访问元素。

1.1 初始化

std::set 的初始化方式与 std::map 类似，C++11 及以后推荐使用初始化列表，简洁直观。

基本初始化

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

int main() {
    // 初始化列表直接初始化（默认升序）
    std::set<int> nums = {3, 1, 4, 1, 5}; // 重复元素1会被去重，实际存储 {1, 3, 4, 5}

    // 自定义比较器（降序）
    struct Greater {
        bool operator()(const int& a, const int& b) const {
            return a > b;
        }
    };
    std::set<int, Greater> numsDesc = {3, 1, 4, 1, 5}; // 存储 {5, 4, 3, 1}

    // 遍历输出（验证排序和去重）
    std::cout << "升序set: ";
    for (const auto& num : nums) {
        std::cout << num << " ";
    }
    std::cout << "\n降序set: ";
    for (const auto& num : numsDesc) {
        std::cout << num << " ";
    }
    return 0;
}

C++17 模板参数自动推导（CTAD）

与 map 类似，std::set 在 C++17 中支持模板参数自动推导（CTAD），简化声明：

#include <set>

int main() {
    // 编译器自动推导元素类型为int（默认比较器less）
    std::set s = {1, 2, 3}; 

    // 若使用自定义比较器，仍需显式指定模板参数
    struct Greater { bool operator()(int a, int b) const { return a > b; } };
    std::set<int, Greater> sDesc = {3, 2, 1}; 
    return 0;
}

1.2 插入元素

std::set 提供两种主要插入方式：insert() 和 emplace()，均支持单个或批量插入，且会自动去重。

（1）insert()：标准插入接口

insert() 可插入单个元素或元素范围，返回 pair<iterator, bool>（其中 bool 表示是否插入成功，iterator 指向插入位置或已存在的元素）。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 2, 3};

    // 插入单个元素
    auto result = s.insert(4); // 插入成功，result.second为true
    if (result.second) {
        std::cout << "插入成功：" << *result.first << std::endl;
    }

    result = s.insert(2); // 插入重复元素，失败
    if (!result.second) {
        std::cout << "插入失败（元素已存在）：" << *result.first << std::endl;
    }

    // 批量插入（初始化列表）
    s.insert({5, 6, 2}); // 2重复，实际插入5、6

    // 遍历结果：1 2 3 4 5 6
    for (const auto& num : s) {
        std::cout << num << " ";
    }
    return 0;
}

（2）emplace()：C++11+ 高效插入

emplace() 直接在 set 内部构造元素，避免 insert() 可能产生的临时对象拷贝，效率更高（尤其对于自定义类型）。

#include <set>
#include <string>

struct Student {
    int id;
    std::string name;
    // 构造函数
    Student(int id, std::string name) : id(id), name(std::move(name)) {}
};

// 自定义比较器（按id排序）
struct CompareStudent {
    bool operator()(const Student& a, const Student& b) const {
        return a.id < b.id;
    }
};

int main() {
    std::set<Student, CompareStudent> students;

    // emplace直接传入构造参数，内部构造Student对象
    students.emplace(101, "Tom"); 
    students.emplace(102, "Jerry");

    // 等价于insert，但避免了临时对象拷贝
    // students.insert(Student(101, "Tom")); 
    return 0;
}

1.3 查找元素

std::set 提供 find() 和 count() 两种常用查找接口，利用红黑树特性，时间复杂度均为 O(logn)。

（1）find()：定位元素迭代器

find(value) 返回指向目标元素的迭代器；若元素不存在，返回 end() 迭代器。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 3, 5, 7};

    auto it = s.find(3);
    if (it != s.end()) {
        std::cout << "找到元素：" << *it << std::endl; // 输出：找到元素：3
    } else {
        std::cout << "未找到元素" << std::endl;
    }

    it = s.find(4);
    if (it == s.end()) {
        std::cout << "未找到元素4" << std::endl;
    }
    return 0;
}

（2）count()：检查元素存在性

由于 set 元素唯一，count(value) 的返回值只能是 0（不存在）或 1（存在），适合快速判断元素是否存在。

#include <set>
#include <iostream>

int main() {
    std::set<std::string> fruits = {"apple", "banana", "cherry"};

    if (fruits.count("banana")) {
        std::cout << "存在banana" << std::endl;
    }
    if (fruits.count("orange") == 0) {
        std::cout << "不存在orange" << std::endl;
    }
    return 0;
}

1.4 遍历

std::set 的遍历方式与 map 类似，随 C++ 标准演进逐渐简化，核心差异是 set 元素为单个值（无需访问 first/second）。

C++98/03 遍历（显式迭代器）

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 2, 3};

    // 普通迭代器（可修改元素？不！set元素是const的！）
    for (std::set<int>::iterator it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << " "; // 输出：1 2 3
        // *it = 4; // 编译错误！set元素不可修改（会破坏排序）
    }

    // 常量迭代器（只读，与普通迭代器效果一致，更明确）
    for (std::set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

注意：set 元素是常量（const），不能通过迭代器修改，否则会破坏内部排序结构。

C++11 遍历（范围循环 + auto）

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 2, 3};

    // 范围循环 + auto，简洁明了
    for (const auto& num : s) { // num类型为const int&
        std::cout << num << " "; // 输出：1 2 3
    }
    return 0;
}

C++17 遍历（结构化绑定无需，直接访问元素）

由于 set 元素是单个值，无需结构化绑定，直接遍历即可（比 map 更简单）：

#include <set>
#include <iostream>

int main() {
    std::set<std::string> fruits = {"apple", "banana", "cherry"};

    // 直接访问元素，无需first/second
    for (const auto& fruit : fruits) {
        std::cout << fruit << " "; // 输出：apple banana cherry
    }
    return 0;
}

1.5 删除元素

std::set 的 erase() 函数支持按迭代器、值、范围删除元素，需注意迭代器失效问题。

基本删除操作

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 2, 3, 4, 5};

    // 1. 按值删除
    size_t deleted = s.erase(3); // 删除值为3的元素，返回删除个数（1）
    std::cout << "删除了" << deleted << "个元素" << std::endl;

    // 2. 按迭代器删除
    auto it = s.find(4);
    if (it != s.end()) {
        s.erase(it); // 删除值为4的元素
    }

    // 3. 按范围删除（删除从2到末尾的元素）
    it = s.find(2);
    s.erase(it, s.end()); // 删除2、5

    // 剩余元素：1
    for (const auto& num : s) {
        std::cout << num << " ";
    }
    return 0;
}

遍历删除元素

与 map 类似，删除 set 元素后，被删除的迭代器会失效，但其他迭代器不受影响。正确做法是利用 erase 的返回值更新迭代器。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 2, 3, 4, 5, 6};

    // 目标：删除偶数
    auto it = s.begin();
    while (it != s.end()) {
        if (*it % 2 == 0) {
            // erase返回下一个有效迭代器
            it = s.erase(it); 
        } else {
            ++it;
        }
    }

    // 剩余元素：1 3 5
    for (const auto& num : s) {
        std::cout << num << " ";
    }
    return 0;
}

错误做法：删除后直接递增迭代器（会访问失效迭代器，导致未定义行为）。

1.6 清空

clear() 函数用于删除 set 中所有元素，调用后 size() 变为 0，但容器可继续使用。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 2, 3};

    std::cout << "清空前大小：" << s.size() << std::endl; // 输出：3
    s.clear();
    std::cout << "清空后大小：" << s.size() << std::endl; // 输出：0
    std::cout << "是否为空：" << (s.empty() ? "是" : "否") << std::endl; // 输出：是

    // 清空后可重新插入
    s.insert(4);
    std::cout << "重新插入后大小：" << s.size() << std::endl; // 输出：1
    return 0;
}

彻底释放内存

clear() 仅删除元素，可能保留底层红黑树的结构内存。若需彻底释放，可结合临时对象交换：

#include <set>

int main() {
    std::set<int> s;
    // 插入大量元素
    for (int i = 0; i < 10000; ++i) {
        s.insert(i);
    }

    // 彻底释放内存：与临时set交换
    std::set<int>().swap(s); 
    return 0;
}

2. Multiset

std::multiset 是 set 的 “兄弟容器”，核心特性与 set 一致，但允许元素重复。当需要存储有序且可重复的元素时（比如统计频率、保存多个相同值），multiset 是理想选择。

2.1 核心特性

• 元素可重复：插入重复元素会成功；

• 仍保持有序（默认升序，支持自定义比较器）；

• 无 operator[] 接口；

• 查找时 find() 返回第一个匹配元素，count() 返回元素出现次数，equal_range() 返回所有匹配元素的范围。

2.2 用法示例

#include <set>
#include <iostream>

int main() {
    // 存储重复元素的multiset
    std::multiset<int> ms = {2, 1, 3, 2, 2, 4}; // 存储：1, 2, 2, 2, 3, 4

    // 1. 统计元素2的出现次数
    std::cout << "元素2出现次数：" << ms.count(2) << std::endl; // 输出：3

    // 2. 查找所有元素2（用equal_range）
    auto [start, end] = ms.equal_range(2); // C++17结构化绑定
    std::cout << "所有元素2：";
    for (auto it = start; it != end; ++it) {
        std::cout << *it << " "; // 输出：2 2 2
    }
    std::cout << std::endl;

    // 3. 遍历所有元素
    std::cout << "所有元素：";
    for (const auto& num : ms) {
        std::cout << num << " "; // 输出：1 2 2 2 3 4
    }
    return 0;
}

3. 总结

1. set 与 map 的核心差异：set 存储单个元素（元素即键），map 存储键值对；set 无 operator[]，元素不可修改。

2. 初始化：优先用 C++11 初始化列表，C++17 无自定义比较器可省略模板参数。

3. 插入：优先用 emplace() 提高效率，insert() 适合已有元素的插入。

4. 查找：find() 用于获取元素迭代器，count() 快速判断存在性（set 中返回 0 或 1）。

5. 遍历：C++11 范围循环 + auto 最简洁，注意元素是 const 类型。

6. 去重需求选 set**，允许重复选 multiset**：根据元素唯一性要求选择。

7. 元素必须可排序：自定义类型需提供比较器（仿函数）。

掌握 std::set 和 std::multiset 的用法，能帮助你在有序存储、去重统计等场景中写出高效简洁的代码，与 map 形成互补，覆盖更多关联容器应用场景。