c++ std::set使用笔记

std::set 是 C++ 标准库中的一个关联容器，用于存储唯一的元素，并按照特定的排序规则自动排序。它基于红黑树实现，因此插入、删除和查找操作的时间复杂度均为 (O(\log n))。

以下是 std::set 的简单使用指南：

1. 包含头文件

首先需要包含 <set> 头文件：

#include <set>
#include <iostream>

2. 创建和初始化

可以创建一个空的 std::set，或者使用初始化列表进行初始化：

std::set<int> set1; // 创建一个空的 set
std::set<int> set2 = {3, 1, 4, 1, 5, 9}; // 使用初始化列表，重复元素会被忽略

3. 插入元素

使用 insert() 方法插入元素：

set1.insert(10);
set1.insert(20);
set1.insert(30);
set1.insert(20); // 重复元素不会被插入

4. 遍历元素

可以使用范围 for 循环或迭代器来遍历 std::set：

// 使用范围 for 循环
for (const auto& elem : set2) {
    std::cout << elem << " ";
}
std::cout << std::endl;

// 使用迭代器
for (auto it = set1.begin(); it != set1.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

5. 查找元素

使用 find() 方法查找元素。如果找到，返回指向该元素的迭代器；否则返回 end()：

auto it = set2.find(4);
if (it != set2.end()) {
    std::cout << "Element 4 found in set2!" << std::endl;
} else {
    std::cout << "Element 4 not found in set2!" << std::endl;
}

6. 删除元素

使用 erase() 方法删除元素：

set2.erase(1); // 删除值为 1 的元素

auto it = set1.find(20);
if (it != set1.end()) {
    set1.erase(it); // 通过迭代器删除元素
}

7. 其他常用操作

• size()：返回 set 中元素的数量。
• empty()：检查 set 是否为空。
• clear()：清空 set。
• count()：返回某个值的出现次数（对于 std::set，只能是 0 或 1）。
• lower_bound() 和 upper_bound()：用于范围查找。

if (!set1.empty()) {
    std::cout << "Set1 size: " << set1.size() << std::endl;
}

set1.clear(); // 清空 set

// 使用 count 检查元素是否存在
if (set2.count(5)) {
    std::cout << "Element 5 exists in set2!" << std::endl;
}

// 使用 lower_bound 和 upper_bound
auto low = set2.lower_bound(3); // 第一个 >= 3 的元素
auto high = set2.upper_bound(6); // 第一个 > 6 的元素
std::cout << "Range [3, 6]: ";
for (auto it = low; it != high; ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

8. 自定义排序规则

std::set 默认使用 < 运算符进行排序。可以通过提供自定义比较函数或函数对象来改变排序规则：

// 使用 greater<int> 实现降序排序
std::set<int, std::greater<int>> set3 = {3, 1, 4, 1, 5, 9};

// 自定义比较函数
struct CaseInsensitiveCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::tolower(a[0]) < std::tolower(b[0]);
    }
};

std::set<std::string, CaseInsensitiveCompare> set4 = {"Apple", "banana", "Cherry"};
for (const auto& elem : set4) {
    std::cout << elem << " ";
}
std::cout << std::endl;

9. 示例代码

以下是一个完整的示例代码：

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

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

    // 插入元素
    set.insert(2);
    set.insert(7);

    // 遍历并打印元素
    std::cout << "Set elements: ";
    for (const auto& elem : set) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 查找元素
    auto it = set.find(4);
    if (it != set.end()) {
        std::cout << "Element 4 found!" << std::endl;
    }

    // 删除元素
    set.erase(1);
    set.erase(it);

    // 再次遍历并打印元素
    std::cout << "Set after erase: ";
    for (const auto& elem : set) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 使用 lower_bound 和 upper_bound
    auto low = set.lower_bound(3);
    auto high = set.upper_bound(6);
    std::cout << "Range [3, 6]: ";
    for (auto it = low; it != high; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：

Set elements: 1 2 3 4 5 7 9 
Element 4 found!
Set after erase: 2 3 5 7 9 
Range [3, 6]: 3 5 

总结

std::set 是一个高效的关联容器，适合存储唯一元素并自动排序。它的主要特点包括：

• 元素唯一性。
• 自动排序。
• 高效的查找、插入和删除操作（(O(\log n))）。
• 支持自定义排序规则。

如果需要存储重复元素，可以使用 std::multiset。