std::set

std::set是C++标准库中的关联容器，基于红黑树实现，用于存储唯一且有序的元素。

基本特性

• 唯一性：不允许重复元素

• 有序性：元素自动按照比较函数排序

• 不可修改：元素一旦插入就不能直接修改

• 对数时间复杂度：插入、删除、查找都是O(log n)

17
1
// set的典型实现基于红黑树
2
template<class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>>
3
class set {
4
private:
5
    // 红黑树节点结构
6
    struct Node {
7
        Key data;
8
        Node* left;
9
        Node* right;
10
        Node* parent;
11
        bool is_red;  // 红黑树颜色
12
    };
13
    
14
    Node* root;
15
    Compare comp;  // 比较函数对象
16
    size_t size_;
17
};

基本用法

包含头文件和声明

14
1
#include <set>
2
#include <iostream>
3
#include <string>
4

5
int main() {
6
    // 基本声明
7
    std::set<int> int_set;
8
    std::set<std::string> string_set;
9
    
10
    // 使用自定义比较函数
11
    std::set<int, std::greater<int>> desc_set;  // 降序
12
    
13
    return 0;
14
}

插入元素

30
1
#include <set>
2
#include <iostream>
3

4
void insertion_examples() {
5
    std::set<int> s;
6
    
7
    // 1. 使用insert()插入单个元素
8
    auto result1 = s.insert(10);
9
    std::cout << "插入10: " << (result1.second ? "成功" : "失败") << std::endl;
10
    
11
    auto result2 = s.insert(10);  // 重复插入
12
    std::cout << "重复插入10: " << (result2.second ? "成功" : "失败") << std::endl;
13
    
14
    // 2. 插入多个元素
15
    s.insert({20, 30, 15, 25});
16
    
17
    // 3. 使用迭代器范围插入
18
    std::vector<int> vec = {5, 35, 40};
19
    s.insert(vec.begin(), vec.end());
20
    
21
    // 4. 使用emplace()就地构造
22
    s.emplace(45);
23
    
24
    // 输出所有元素（自动排序）
25
    std::cout << "set内容: ";
26
    for (const auto& elem : s) {
27
        std::cout << elem << " ";
28
    }
29
    std::cout << std::endl;
30
}

查找和访问

43
1
void search_examples() {
2
    std::set<int> s = {10, 20, 30, 40, 50};
3
    
4
    // 1. 使用find()查找
5
    auto it = s.find(30);
6
    if (it != s.end()) {
7
        std::cout << "找到元素: " << *it << std::endl;
8
    }
9
     
10
    // 2. 使用count()检查存在性
11
    if (s.count(25) > 0) {
12
        std::cout << "25存在" << std::endl;
13
    } else {
14
        std::cout << "25不存在" << std::endl;
15
    }
16
    
17
    // 3. 使用contains()（C++20）
18
    #if __cplusplus >= 202002L
19
    if (s.contains(40)) {
20
        std::cout << "40存在" << std::endl;
21
    }
22
    #endif
23
    
24
    // 4. 范围查找
25
    auto lower = s.lower_bound(25);  // 第一个>=25的元素
26
    auto upper = s.upper_bound(35);  // 第一个>35的元素
27
    
28
    std::cout << "范围[25, 35]内的元素: ";
29
    for (auto it = lower; it != upper; ++it) {
30
        std::cout << *it << " ";
31
    }
32
    std::cout << std::endl;
33
    
34
    // 5. equal_range()获取可以插入指定值而不破坏排序的位置范围 [range.first, range.second)
35
    // range.first  = lower_bound(30)  // 第一个 >= 30 的位置
36
    // range.second = upper_bound(30)  // 第一个 > 30 的位置
37
    auto range = s.equal_range(30);
38
    std::cout << "可以插入30的元素范围: ";
39
    for (auto it = range.first; it != range.second; ++it) {
40
        std::cout << *it << " ";
41
    }
42
    std::cout << std::endl;
43
}

删除元素

23
1
void deletion_examples() {
2
    std::set<int> s = {10, 20, 30, 40, 50};
3
    
4
    // 1. 按值删除
5
    size_t removed = s.erase(30);
6
    std::cout << "删除了 " << removed << " 个元素" << std::endl;
7
    
8
    // 2. 按迭代器删除
9
    auto it = s.find(40);
10
    if (it != s.end()) {
11
        s.erase(it);
12
    }
13
    
14
    // 3. 删除范围
15
    auto first = s.find(20);
16
    auto last = s.find(50);
17
    s.erase(first, last);  // 删除[20, 50)
18
    
19
    // 4. 清空所有元素
20
    s.clear();
21
    
22
    std::cout << "删除后set大小: " << s.size() << std::endl;
23
}

自定义比较函数

使用函数对象

39
1
#include <set>
2
#include <string>
3

4
// 自定义比较函数对象
5
struct StringLengthCompare {
6
    bool operator()(const std::string& a, const std::string& b) const {
7
        if (a.length() != b.length()) {
8
            return a.length() < b.length();
9
        }
10
        return a < b;  // 长度相同时按字典序
11
    }
12
};
13

14
void custom_comparator_examples() {
15
    // 按字符串长度排序的set
16
    std::set<std::string, StringLengthCompare> length_set;
17
    
18
    length_set.insert({"apple", "hi", "banana", "cat", "elephant"});
19
    
20
    std::cout << "按长度排序的字符串: ";
21
    for (const auto& str : length_set) {
22
        std::cout << str << "(" << str.length() << ") ";
23
    }
24
    std::cout << std::endl;
25
    
26
    // 使用lambda表达式
27
    auto lambda_comp = [](const int& a, const int& b) {
28
        return a > b;  // 降序
29
    };
30
    
31
    std::set<int, decltype(lambda_comp)> desc_set(lambda_comp);
32
    desc_set.insert({5, 2, 8, 1, 9});
33
    
34
    std::cout << "降序排列: ";
35
    for (const auto& num : desc_set) {
36
        std::cout << num << " ";
37
    }
38
    std::cout << std::endl;
39
}

自定义类型的set

28
1
struct Person {
2
    std::string name;
3
    int age;
4
    
5
    Person(const std::string& n, int a) : name(n), age(a) {}
6
    
7
    // 重载<运算符
8
    bool operator<(const Person& other) const {
9
        if (age != other.age) {
10
            return age < other.age;
11
        }
12
        return name < other.name;
13
    }
14
};
15

16
void custom_type_examples() {
17
    std::set<Person> people;
18
    
19
    people.emplace("Alice", 25);
20
    people.emplace("Bob", 30);
21
    people.emplace("Charlie", 25);
22
    people.emplace("David", 20);
23
    
24
    std::cout << "按年龄和姓名排序的人员: " << std::endl;
25
    for (const auto& person : people) {
26
        std::cout << person.name << " (" << person.age << ")" << std::endl;
27
    }
28
}

迭代器操作

32
1
void iterator_examples() {
2
    std::set<int> s = {10, 20, 30, 40, 50};
3
    
4
    // 1. 正向迭代器
5
    std::cout << "正向遍历: ";
6
    for (auto it = s.begin(); it != s.end(); ++it) {
7
        std::cout << *it << " ";
8
    }
9
    std::cout << std::endl;
10
    
11
    // 2. 反向迭代器
12
    std::cout << "反向遍历: ";
13
    for (auto it = s.rbegin(); it != s.rend(); ++it) {
14
        std::cout << *it << " ";
15
    }
16
    std::cout << std::endl;
17
    
18
    // 3. 常量迭代器
19
    std::cout << "常量迭代器: ";
20
    for (auto it = s.cbegin(); it != s.cend(); ++it) {
21
        std::cout << *it << " ";
22
        // *it = 100;  // 编译错误，不能修改
23
    }
24
    std::cout << std::endl;
25
    
26
    // 4. 范围for循环
27
    std::cout << "范围for循环: ";
28
    for (const auto& elem : s) {
29
        std::cout << elem << " ";
30
    }
31
    std::cout << std::endl;
32
}

set的变体

multiset - 允许重复元素

xxxxxxxxxx
25
1
#include <set>
2

3
void multiset_examples() {
4
    std::multiset<int> ms;
5
    
6
    // 可以插入重复元素
7
    ms.insert({10, 20, 10, 30, 20, 10});
8
    
9
    std::cout << "multiset内容: ";
10
    for (const auto& elem : ms) {
11
        std::cout << elem << " ";
12
    }
13
    std::cout << std::endl;
14
    
15
    // 统计某个值的出现次数
16
    std::cout << "10出现了 " << ms.count(10) << " 次" << std::endl;
17
    
18
    // 删除所有指定值
19
    ms.erase(10);
20
    std::cout << "删除所有10后: ";
21
    for (const auto& elem : ms) {
22
        std::cout << elem << " ";
23
    }
24
    std::cout << std::endl;
25
}

unordered_set - 基于哈希表

xxxxxxxxxx
21
1
#include <unordered_set>
2

3
void unordered_set_examples() {
4
    std::unordered_set<int> us;
5
    
6
    // 插入元素（无序）
7
    us.insert({30, 10, 40, 20, 50});
8
    
9
    std::cout << "unordered_set内容（无序）: ";
10
    for (const auto& elem : us) {
11
        std::cout << elem << " ";
12
    }
13
    std::cout << std::endl;
14
    
15
    // 平均O(1)的查找时间
16
    auto start = std::chrono::high_resolution_clock::now();
17
    bool found = us.find(30) != us.end();
18
    auto end = std::chrono::high_resolution_clock::now();
19
    
20
    std::cout << "查找结果: " << (found ? "找到" : "未找到") << std::endl;
21
}

高级技巧

使用场景选择

xxxxxxxxxx
37
1
// 场景1: 需要有序遍历 - 使用std::set
2
void scenario_ordered_traversal() {
3
    std::set<int> scores = {85, 92, 78, 96, 88};
4
    
5
    std::cout << "成绩排序（从低到高）: ";
6
    for (const auto& score : scores) {
7
        std::cout << score << " ";
8
    }
9
    std::cout << std::endl;
10
}
11

12
// 场景2: 需要范围查询 - 使用std::set
13
void scenario_range_query() {
14
    std::set<int> ages = {18, 25, 30, 35, 42, 50, 65};
15
    
16
    // 查找30-50岁之间的人
17
    auto lower = ages.lower_bound(30);
18
    auto upper = ages.upper_bound(50);
19
    
20
    std::cout << "30-50岁之间: ";
21
    for (auto it = lower; it != upper; ++it) {
22
        std::cout << *it << " ";
23
    }
24
    std::cout << std::endl;
25
}
26

27
// 场景3: 只需要快速查找 - 使用std::unordered_set
28
void scenario_fast_lookup() {
29
    std::unordered_set<std::string> valid_users = {
30
        "alice", "bob", "charlie", "david"
31
    };
32
    
33
    std::string user = "alice";
34
    if (valid_users.count(user)) {
35
        std::cout << user << " 是有效用户" << std::endl;
36
    }
37
}

自定义哈希函数（用于unordered_set）

xxxxxxxxxx
24
1
struct Point {
2
    int x, y;
3
    
4
    bool operator==(const Point& other) const {
5
        return x == other.x && y == other.y;
6
    }
7
};
8

9
// 自定义哈希函数
10
struct PointHash {
11
    size_t operator()(const Point& p) const {
12
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
13
    }
14
};
15

16
void custom_hash_example() {
17
    std::unordered_set<Point, PointHash> point_set;
18
    
19
    point_set.insert({1, 2});
20
    point_set.insert({3, 4});
21
    point_set.insert({1, 2});  // 重复，不会插入
22
    
23
    std::cout << "点集大小: " << point_set.size() << std::endl;
24
}

使用set实现集合运算

xxxxxxxxxx
36
1
#include <algorithm>
2

3
void set_operations() {
4
    std::set<int> set1 = {1, 2, 3, 4, 5};
5
    std::set<int> set2 = {4, 5, 6, 7, 8};
6
    
7
    // 交集
8
    std::set<int> intersection;
9
    std::set_intersection(set1.begin(), set1.end(),
10
                         set2.begin(), set2.end(),
11
                         std::inserter(intersection, intersection.begin()));
12
    
13
    // 并集
14
    std::set<int> union_set;
15
    std::set_union(set1.begin(), set1.end(),
16
                   set2.begin(), set2.end(),
17
                   std::inserter(union_set, union_set.begin()));
18
    
19
    // 差集
20
    std::set<int> difference;
21
    std::set_difference(set1.begin(), set1.end(),
22
                       set2.begin(), set2.end(),
23
                       std::inserter(difference, difference.begin()));
24
    
25
    std::cout << "交集: ";
26
    for (const auto& elem : intersection) std::cout << elem << " ";
27
    std::cout << std::endl;
28
    
29
    std::cout << "并集: ";
30
    for (const auto& elem : union_set) std::cout << elem << " ";
31
    std::cout << std::endl;
32
    
33
    std::cout << "差集: ";
34
    for (const auto& elem : difference) std::cout << elem << " ";
35
    std::cout << std::endl;
36
}

注意事项

元素不可修改性

xxxxxxxxxx
13
1
void immutability_example() {
2
    std::set<int> s = {10, 20, 30};
3
    
4
    // 错误：不能直接修改set中的元素
5
    // *s.begin() = 100;  // 编译错误
6
    
7
    // 正确：删除后重新插入
8
    auto it = s.find(20);
9
    if (it != s.end()) {
10
        s.erase(it);
11
        s.insert(25);
12
    }
13
}

迭代器失效

xxxxxxxxxx
18
1
void iterator_invalidation() {
2
    std::set<int> s = {10, 20, 30, 40, 50};
3
    
4
    // 删除操作会使被删除元素的迭代器失效
5
    for (auto it = s.begin(); it != s.end(); ) {
6
        if (*it % 20 == 0) {
7
            it = s.erase(it);  // erase返回下一个有效迭代器
8
        } else {
9
            ++it;
10
        }
11
    }
12
    
13
    std::cout << "删除20的倍数后: ";
14
    for (const auto& elem : s) {
15
        std::cout << elem << " ";
16
    }
17
    std::cout << std::endl;
18
}

选择合适的容器

xxxxxxxxxx
9
1
void container_selection_guide() {
2
    std::cout << "容器选择指南:" << std::endl;
3
    std::cout << "1. 需要有序 + 唯一 → std::set" << std::endl;
4
    std::cout << "2. 需要有序 + 允许重复 → std::multiset" << std::endl;
5
    std::cout << "3. 只需唯一 + 快速查找 → std::unordered_set" << std::endl;
6
    std::cout << "4. 允许重复 + 快速查找 → std::unordered_multiset" << std::endl;
7
    std::cout << "5. 需要范围查询 → std::set/std::multiset" << std::endl;
8
    std::cout << "6. 频繁插入删除 + 不需要有序 → std::unordered_set" << std::endl;
9
}

std::map

std::map 是 C++ 标准库中的关联容器，用于存储键值对（key-value pairs）。

基本特性:

1. 有序性：元素按键（key）自动排序

2. 唯一性：每个键只能出现一次

3. 关联性：通过键来访问对应的值

4. 动态大小：可以动态增加或删除元素

std::map 通常使用红黑树（Red-Black Tree）实现：

• 保证 O(log n) 的插入、删除、查找时间复杂度

• 自动保持树的平衡

• 元素按键的顺序存储

模板参数

xxxxxxxxxx
6
1
template<
2
    class Key,                                    // 键类型
3
    class T,                                      // 值类型
4
    class Compare = std::less<Key>,               // 比较器
5
    class Allocator = std::allocator<std::pair<const Key, T>>
6
> class map;

基本用法

声明和初始化

xxxxxxxxxx
17
1
#include <map>
2
#include <string>
3
#include <iostream>
4

5
// 基本声明
6
std::map<int, std::string> id_to_name;
7
std::map<std::string, int> name_to_age;
8

9
// 初始化列表
10
std::map<int, std::string> students = {
11
    {1, "Alice"},
12
    {2, "Bob"},
13
    {3, "Charlie"}
14
};
15

16
// 拷贝构造
17
std::map<int, std::string> copy_students(students);

插入元素

xxxxxxxxxx
14
1
std::map<int, std::string> m;
2

3
// 方法1：使用 insert
4
m.insert(std::make_pair(1, "Alice"));
5
m.insert({2, "Bob"});  // C++11
6

7
// 方法2：使用 emplace（C++11）
8
m.emplace(3, "Charlie");
9

10
// 方法3：使用下标操作符
11
m[4] = "David";
12

13
// 方法4：使用 insert_or_assign（C++17）
14
m.insert_or_assign(5, "Eve");

访问元素

xxxxxxxxxx
19
1
std::map<int, std::string> m = {{1, "Alice"}, {2, "Bob"}};
2

3
// 使用下标操作符（如果键不存在会创建）
4
std::string name1 = m[1];
5
m[3] = "Charlie";  // 创建新元素
6

7
// 使用 at()（如果键不存在会抛出异常）
8
try {
9
    std::string name2 = m.at(2);
10
    std::string name3 = m.at(10);  // 抛出 std::out_of_range
11
} catch (const std::out_of_range& e) {
12
    std::cout << "Key not found: " << e.what() << std::endl;
13
}
14

15
// 使用 find()
16
auto it = m.find(1);
17
if (it != m.end()) {
18
    std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
19
}

查找和检查

xxxxxxxxxx
21
1
std::map<int, std::string> m = {{1, "Alice"}, {2, "Bob"}, {3, "Charlie"}};
2

3
// 检查键是否存在
4
if (m.find(2) != m.end()) {
5
    std::cout << "Key 2 exists" << std::endl;
6
}
7

8
// 使用 count()（对于 map 只返回 0 或 1）
9
if (m.count(3) > 0) {
10
    std::cout << "Key 3 exists" << std::endl;
11
}
12

13
// C++20: 使用 contains()
14
if (m.contains(1)) {
15
    std::cout << "Key 1 exists" << std::endl;
16
}
17

18
// 查找范围
19
auto lower = m.lower_bound(2);
20
auto upper = m.upper_bound(2);
21
auto range = m.equal_range(2);

删除元素

xxxxxxxxxx
16
1
std::map<int, std::string> m = {{1, "Alice"}, {2, "Bob"}, {3, "Charlie"}};
2

3
// 按键删除
4
m.erase(2);
5

6
// 按迭代器删除
7
auto it = m.find(1);
8
if (it != m.end()) {
9
    m.erase(it);
10
}
11

12
// 删除范围
13
m.erase(m.begin(), m.end());  // 清空
14

15
// 清空所有元素
16
m.clear();

遍历

xxxxxxxxxx
21
1
std::map<int, std::string> m = {{1, "Alice"}, {2, "Bob"}, {3, "Charlie"}};
2

3
// 范围for循环（C++11）
4
for (const auto& pair : m) {
5
    std::cout << pair.first << " -> " << pair.second << std::endl;
6
}
7

8
// 结构化绑定（C++17）
9
for (const auto& [key, value] : m) {
10
    std::cout << key << " -> " << value << std::endl;
11
}
12

13
// 传统迭代器
14
for (auto it = m.begin(); it != m.end(); ++it) {
15
    std::cout << it->first << " -> " << it->second << std::endl;
16
}
17

18
// 反向遍历
19
for (auto it = m.rbegin(); it != m.rend(); ++it) {
20
    std::cout << it->first << " -> " << it->second << std::endl;
21
}

常用成员函数

xxxxxxxxxx
14
1
std::map<int, std::string> m = {{1, "Alice"}, {2, "Bob"}};
2

3
// 大小相关
4
std::cout << "Size: " << m.size() << std::endl;
5
std::cout << "Empty: " << m.empty() << std::endl;
6
std::cout << "Max size: " << m.max_size() << std::endl;
7

8
// 交换
9
std::map<int, std::string> other = {{3, "Charlie"}};
10
m.swap(other);
11

12
// 获取比较器
13
auto comp = m.key_comp();
14
auto value_comp = m.value_comp();

自定义比较器

xxxxxxxxxx
17
1
// 自定义比较器结构体
2
struct DescendingCompare {
3
    bool operator()(int a, int b) const {
4
        return a > b;  // 降序排列
5
    }
6
};
7

8
// 使用自定义比较器
9
std::map<int, std::string, DescendingCompare> desc_map;
10
desc_map[3] = "Three";
11
desc_map[1] = "One";
12
desc_map[2] = "Two";
13
// 输出顺序：3, 2, 1
14

15
// 使用 lambda 表达式（需要指定类型）
16
auto lambda_comp = [](int a, int b) { return a > b; };
17
std::map<int, std::string, decltype(lambda_comp)> lambda_map(lambda_comp);

map 的变体

std::multimap

• 允许重复键

• 相同键的元素相邻存储

xxxxxxxxxx
3
1
std::multimap<int, std::string> mm;
2
mm.insert({1, "Alice"});
3
mm.insert({1, "Bob"});  // 允许重复键

std::unordered_map

• 基于哈希表实现

• 平均 O(1) 的查找时间

• 元素无序

xxxxxxxxxx
3
1
std::unordered_map<int, std::string> um;
2
um[1] = "Alice";
3
// 查找更快，但无序

std::unordered_multimap

• 哈希表 + 允许重复键

实际应用示例

xxxxxxxxxx
40
1
#include <map>
2
#include <string>
3
#include <iostream>
4

5
// 单词计数器
6
void word_counter_example() {
7
    std::map<std::string, int> word_count;
8
    std::string text = "hello world hello cpp world";
9
    
10
    // 简单的单词分割和计数
11
    std::istringstream iss(text);
12
    std::string word;
13
    while (iss >> word) {
14
        word_count[word]++;  // 自动创建或递增
15
    }
16
    
17
    // 输出结果（自动按字典序排序）
18
    for (const auto& [word, count] : word_count) {
19
        std::cout << word << ": " << count << std::endl;
20
    }
21
}
22

23
// 学生成绩管理
24
void student_grade_example() {
25
    std::map<std::string, std::map<std::string, int>> grades;
26
    
27
    // 添加成绩
28
    grades["Alice"]["Math"] = 95;
29
    grades["Alice"]["English"] = 87;
30
    grades["Bob"]["Math"] = 78;
31
    grades["Bob"]["English"] = 92;
32
    
33
    // 查询和输出
34
    for (const auto& [student, subjects] : grades) {
35
        std::cout << student << "'s grades:" << std::endl;
36
        for (const auto& [subject, grade] : subjects) {
37
            std::cout << "  " << subject << ": " << grade << std::endl;
38
        }
39
    }
40
}