在 C++ 的世界里，map 和 set 是两个非常实用的容器。它们就像是编程工具箱里的瑞士军刀，在各种场景下都能发挥巨大的作用。今天，我们就来全方位地了解一下这两个容器，从基础用法到算法题优化，一篇文章让你彻底掌握！

一、基础概念

1.1 什么是 map 和 set

在 C++ 标准模板库（STL）中，map 和 set 都属于关联容器。关联容器通过键（key）来存储和访问元素，而不是像顺序容器（如 vector、list）那样通过位置来访问。

• map：map 是一种键值对（key - value）的容器，每个键都是唯一的，通过键可以快速查找对应的值。它就像是一本字典，每个单词（键）都对应着一个解释（值）。
• set：set 是一种只存储键的容器，每个键也是唯一的。它可以用来存储一组不重复的元素，就像是一个收藏夹，里面的每一件物品都是独一无二的。

1.2 头文件和命名空间

要使用 map 和 set，需要包含 <map> 和 <set> 头文件，并且使用 std 命名空间。示例代码如下：

cpp

#include <iostream> #include <map> #include <set> using namespace std; int main() { // 后续代码将在这里添加 return 0; }

二、map 的基础用法

2.1 声明和初始化

map 的声明需要指定键和值的类型，例如：

cpp

map<string, int> student_scores;

这里声明了一个 map，键的类型是 string，表示学生的姓名，值的类型是 int，表示学生的分数。

初始化 map 有多种方式，下面是几种常见的方法：

cpp

// 直接插入元素 student_scores["Alice"] = 90; student_scores["Bob"] = 85; // 使用 insert 方法插入元素 student_scores.insert(pair<string, int>("Charlie", 78));

2.2 元素访问

可以通过键来访问 map 中的元素，例如：

cpp

int alice_score = student_scores["Alice"]; cout << "Alice's score: " << alice_score << endl;

如果键不存在，使用 [] 访问会自动插入一个默认值。如果不想插入默认值，可以使用 find 方法：

cpp

auto it = student_scores.find("Bob"); if (it != student_scores.end()) { cout << "Bob's score: " << it->second << endl; } else { cout << "Bob not found." << endl; }

2.3 元素删除

可以使用 erase 方法删除 map 中的元素，例如：

cpp

student_scores.erase("Charlie");

2.4 遍历 map

可以使用迭代器来遍历 map，示例代码如下：

cpp

for (auto it = student_scores.begin(); it != student_scores.end(); ++it) { cout << it->first << ": " << it->second << endl; }

也可以使用 C++11 引入的范围 for 循环：

cpp

for (const auto& pair : student_scores) { cout << pair.first << ": " << pair.second << endl; }

三、set 的基础用法

3.1 声明和初始化

set 的声明只需要指定键的类型，例如：

cpp

set<int> numbers;

初始化 set 可以直接插入元素，例如：

cpp

numbers.insert(10); numbers.insert(20); numbers.insert(30);

3.2 元素查找

可以使用 find 方法查找 set 中的元素，例如：

cpp

auto it = numbers.find(20); if (it != numbers.end()) { cout << "20 found in the set." << endl; } else { cout << "20 not found in the set." << endl; }

3.3 元素删除

可以使用 erase 方法删除 set 中的元素，例如：

cpp

numbers.erase(30);

3.4 遍历 set

同样可以使用迭代器或范围 for 循环来遍历 set，示例代码如下：

cpp

for (auto it = numbers.begin(); it != numbers.end(); ++it) { cout << *it << " "; } cout << endl; for (const auto& num : numbers) { cout << num << " "; } cout << endl;

四、map 和 set 的特性

4.1 有序性

map 和 set 都是有序容器，它们会根据键的大小对元素进行排序。默认情况下，使用 std::less 作为比较函数，即升序排列。例如：

cpp

set<int> sorted_numbers = {5, 3, 1, 4, 2}; for (const auto& num : sorted_numbers) { cout << num << " "; } cout << endl;

输出结果为：1 2 3 4 5

4.2 唯一性

map 的键和 set 的元素都是唯一的，如果插入重复的键或元素，不会产生新的元素。例如：

cpp

map<string, int> fruits; fruits["apple"] = 1; fruits["apple"] = 2; // 这里会覆盖原来的值 cout << fruits["apple"] << endl; // 输出 2 set<int> unique_numbers; unique_numbers.insert(1); unique_numbers.insert(1); // 不会插入新元素 cout << unique_numbers.size() << endl; // 输出 1

五、map 和 set 在算法题中的优化应用

5.1 统计元素出现次数

在很多算法题中，需要统计元素的出现次数。使用 map 可以很方便地实现这个功能。例如，统计一个数组中每个元素的出现次数：cpp

#include <iostream> #include <map> #include <vector> using namespace std; int main() { vector<int> nums = {1, 2, 3, 2, 1, 3, 1}; map<int, int> count_map; for (const auto& num : nums) { count_map[num]++; } for (const auto& pair : count_map) { cout << pair.first << " appears " << pair.second << " times." << endl; } return 0; }

5.2 查找不重复元素

使用 set 可以快速查找不重复的元素。例如，找出一个数组中所有不重复的元素：

cpp

#include <iostream> #include <set> #include <vector> using namespace std; int main() { vector<int> nums = {1, 2, 3, 2, 1, 3, 4}; set<int> unique_nums(nums.begin(), nums.end()); for (const auto& num : unique_nums) { cout << num << " "; } cout << endl; return 0; }

5.3 区间查找

map 和 set 提供了一些方法来进行区间查找，例如 lower_bound 和 upper_bound。lower_bound 可以找到第一个不小于给定值的元素，upper_bound 可以找到第一个大于给定值的元素。例如：

cpp

#include <iostream> #include <map> using namespace std; int main() { map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}}; auto it1 = m.lower_bound(2); auto it2 = m.upper_bound(3); for (auto it = it1; it != it2; ++it) { cout << it->first << ": " << it->second << endl; } return 0; }

map 和 set 是 C++ 中非常实用的关联容器，它们具有有序性和唯一性的特点。map 用于存储键值对，通过键可以快速查找对应的值；set 用于存储不重复的元素。在基础用法方面，我们学习了如何声明、初始化、访问、删除和遍历 map 和 set。在算法题优化方面，map 可以用于统计元素出现次数，set 可以用于查找不重复元素，它们还提供了区间查找的功能。

掌握 map 和 set 的使用，可以让我们在编程中更加高效地处理数据，解决各种复杂的问题。希望通过本文的介绍，你对 map 和 set 有了更深入的理解，能够在实际编程中灵活运用它们。

文章参考链接：
https://github.com/madebi12w3/tech-khkzrmwe/blob/main/README.md

https://github.com/madebi12w3/tech-ovuaonte/blob/main/README.md

https://github.com/madebi12w3/tech-okaxwykq/blob/main/README.md

https://github.com/madebi12w3/tech-hxbwdfct/blob/main/README.md

如果你在使用 map 和 set 的过程中遇到任何问题，或者有更好的应用案例，欢迎在评论区留言分享！让我们一起在编程的道路上不断进步！