前言
本篇博客讲解c++中stl的set/map，本篇讲的如何使用
? 个人主页：普通young man-CSDN博客
⏩ 文章专栏：C++_普通young man的博客-CSDN博客
⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com
若有问题 评论区见?
?欢迎大家点赞?收藏⭐文章
————————————————
看这篇博客之前请先去看：C++ | 二叉搜索树-CSDN博客
目录
序列式容器和关联式容器
set的使用
参考文档
set的基本介绍
set的构造和迭代器
构造
迭代器
正向迭代器
反向迭代器
set的增删查
插入操作
单个数据插入
列表插入
区间插入
查找操作
查找特定值
计算特定值的个数
删除操作
删除指定位置的元素
删除特定值
删除区间内的元素
边界查找
查找大于等于特定值的位置
查找大于特定值的位置
insert和迭代器遍历使⽤样例
find和erase使⽤样例：
multiset和set的差异
multiset 与 set 的差异
第一部分：遍历 multiset
第二部分：查找、计数和删除元素
题目练习
map的使用
map类的介绍
std::map 的声明及特性
功能特性表格
pair类型介绍
什么是 pair？
pair 的工作原理
1. 定义 pair
2. 构造 pair
3. 访问 pair 的成员
map的构造
std::map 的构造接口
std::map 的迭代遍历
支持范围 for 循环
修改 value 数据
不支持修改 key 数据
map的增删查
std::map 的增删查接口
插入（Insert）
查找（Find）
删除（Erase）
map的数据修改
std::map 数据修改接口
修改 mapped_type 数据
插入接口
operator[] 的内部实现
operator[] 的内部实现示例
构造遍历及增删查使用样例
map的迭代器和[]功能样例
示例 1：使用 find 和迭代器修改功能统计水果出现次数
示例 2：使用 operator[] 插入和修改功能统计水果出现次数
示例 3：使用 std::map operator[]
multimap和map的差异
std::map 和 std::multimap 的主要差异
1. 键的唯一性
2. 查找操作
3. 插入操作
4. 计数操作
5. 删除操作
6. operator[]
使用 std::map
题目练习
序列式容器和关联式容器
想象一下你有两个盒子来存放你的东西，一个是用来放T恤的，另一个是用来放袜子的。
序列式容器就像是你的T恤盒子：
它们存放的东西是按照一定的顺序排列的，比如你可以根据颜色或者大小来摆放T恤。如果你想换一件T恤的位置，比如把红色的T恤放在最上面，这是可以做到的，并且不会影响其他T恤的位置。序列式容器的例子包括vector（向量）、list（列表）、deque（双端队列）等，它们的特点就是里面的元素是按照插入的顺序存放的，你可以很容易地通过位置来找到一个元素。 关联式容器则像是你的袜子盒子：
这个盒子里的每只袜子都有一个标签，比如图案或者材质，用来区分不同的袜子。如果你想把两只袜子的位置对调，比如把图案A的袜子和图案B的袜子换一下位置，那么这个盒子的整个组织方式就会被打乱，因为袜子的位置是由它们的标签决定的。关联式容器包括map（映射）和set（集合），set是专门用来存放没有重复的关键字，而map则是用来存放关键字和对应值的配对。在这些容器里，元素是按照关键字的顺序来存放的，而不是它们插入的顺序。 set的使用
参考文档
<set> - C++ Reference (cplusplus.com)
set的基本介绍
| 特性/操作 | 描述 |
|---|---|
| 声明 | std::set<T, Compare, Allocator>; |
| 底层实现 | 使用红黑树（Red-Black Tree），保证插入、删除和查找操作的时间复杂度为 O(log N)。 |
| 默认比较 | 默认使用 std::less<T>，即元素按照升序排列。 |
| 自定义比较 | 可以通过第二个模板参数传递自定义的比较函数对象。 |
| 内存管理 | 默认使用 std::allocator<T> 管理内存，可以通过第三个模板参数自定义内存分配策略。 |
| 插入 | insert(value_type val); - 插入值 val，如果已存在则不插入。 |
| 删除 | erase(iterator it); - 删除指定迭代器指向的元素。<br>erase(const key_type& k); - 删除键值为 k 的元素。<br>clear(); - 删除所有元素。 |
| 查找 | find(const key_type& k); - 查找键值为 k 的元素。<br>count(const key_type& k); - 返回键值为 k 的元素数量（0 或 1）。<br>contains(const key_type& k); - 如果包含键值为 k 的元素则返回 true（C++20）。 |
| 迭代器 | begin(), end(); - 分别返回指向容器首尾的迭代器。<br>cbegin(), cend(); - 对于 const 容器。<br>rbegin(), rend(); - 返回反向迭代器。 |
| 状态检查 | empty(); - 如果集合为空则返回 true。<br>size(); - 返回集合中元素的数量。<br>max_size(); - 返回容器所能容纳的最大元素数量。 |
set的构造和迭代器
构造
std::set 支持多种构造方式，常用的构造接口包括：
| 构造函数 | 描述 |
|---|---|
std::set(); | 默认构造函数，创建一个空的 set 容器。 |
std::set(InputIterator first, InputIterator last); | 创建一个 set 容器，并初始化该容器，使其包含从 [first, last) 范围内的元素。 |
std::set(const set& other); | 复制构造函数，创建一个新的 set 容器，并用另一个 set 容器的内容初始化它。 |
std::set(set&& other); | 移动构造函数，创建一个新的 set 容器，并用另一个 set 容器的内容初始化它，通常更高效。 |
std::set(initializer_list<T> il); | 使用 initializer_list 初始化 set 容器。 |
std::set(InputIterator first, InputIterator last, const Compare& comp); | 创建一个 set 容器，并初始化该容器，同时指定自定义比较器 comp。 |
std::set(const set& other, const Allocator& alloc); | 复制构造函数，同时允许指定不同的分配器 alloc。 |
std::set(initializer_list<T> il, const Compare& comp); | 使用 initializer_list 初始化 set 容器，并指定自定义比较器 comp。 |
迭代器
std::set 支持正向和反向迭代，用于遍历容器中的元素。由于 std::set 底层使用的是红黑树，迭代器遍历采用的是中序遍历，因此遍历结果是按照元素的升序排列。
正向迭代器
std::set 的正向迭代器支持从前往后的遍历：
| 方法 | 描述 |
|---|---|
begin(); | 返回一个指向容器中第一个元素的迭代器。 |
cbegin(); | 返回一个指向容器中第一个元素的常量迭代器。适用于 const 容器。 |
end(); | 返回一个超出最后一个元素的迭代器。 |
cend(); | 返回一个超出最后一个元素的常量迭代器。适用于 const 容器。 |
反向迭代器
std::set 的反向迭代器支持从后往前的遍历：
| 方法 | 描述 |
|---|---|
rbegin(); | 返回一个指向容器中最后一个元素的反向迭代器。 |
crbegin(); | 返回一个指向容器中最后一个元素的常量反向迭代器。适用于 const 容器。 |
rend(); | 返回一个超出容器中第一个元素位置的反向迭代器。 |
crend(); | 返回一个超出容器中第一个元素位置的常量反向迭代器。适用于 const 容器。 |
set的增删查
其实这里就是接口的使用，这些都可以通过参考文档学会
插入操作
单个数据插入
pair<iterator,bool> insert (const value_type& val);val。返回一个 pair，其中包含一个迭代器和一个布尔值。迭代器指向新插入元素的位置（如果插入成功）或尝试插入元素的位置（如果插入失败），布尔值表示插入是否成功。 列表插入
void insert (initializer_list<value_type> il);initializer_list 表达的多个元素。 template <class T>class initializer_list {public: typedef T value_type; typedef T* iterator; typedef const T* const_iterator;private: T* begin_; T* end_;public: // 构造函数，接受一对指针，表示元素的起始和结束位置 initializer_list(T* begin, T* end) noexcept : begin_(begin), end_(end) {} // 返回迭代器，指向列表的第一个元素 iterator begin() const noexcept { return begin_; } // 返回迭代器，指向列表的结束位置 iterator end() const noexcept { return end_; } // 返回列表中元素的数量 size_t size() const noexcept { return end_ - begin_; } // 判断列表是否为空 bool empty() const noexcept { return begin_ == end_; } // 访问列表的第一个元素（如果存在） reference front() const { return *begin_; } // 访问列表的最后一个元素（如果存在） reference back() const { return *(end_ - 1); } // 返回指向第一个元素的指针 pointer data() const noexcept { return begin_; }};// 非成员函数，用于创建 initializer_list 实例template <typename T>inline initializer_list<T> make_initializer_list(T* begin, T* end) { return initializer_list<T>(begin, end);}
构造函数，它会接收指向数组首元素的指针 和指向数组末尾之后的指针 首元素 + sizeof(*) / sizeof(*)。
区间插入
template <class InputIterator>void insert (InputIterator first, InputIterator last);first 到 last 的区间内的所有元素。已经存在于容器中的值不会被插入。 查找操作
查找特定值
iterator find (const value_type& val);val 的元素。返回指向该元素的迭代器，如果没有找到，则返回 end()。 计算特定值的个数
size_type count (const value_type& val) const;val 的元素的数量。对于 std::set，返回值只能是 0 或 1。 删除操作
删除指定位置的元素
iterator erase (const_iterator position);position 指向的元素。返回紧接着被删除元素之后的下一个元素的迭代器。 删除特定值
size_type erase (const value_type& val);val 的元素。返回删除的元素数量，如果值不存在则返回 0。 删除区间内的元素
iterator erase (const_iterator first, const_iterator last);[first, last) 区间内的所有元素。返回紧接着被删除元素之后的下一个元素的迭代器。 边界查找
查找大于等于特定值的位置
iterator lower_bound (const value_type& val) const;val 的元素的迭代器。 查找大于特定值的位置
iterator upper_bound (const value_type& val) const;val 的元素的迭代器。 insert和迭代器遍历使⽤样例
//set插入int main() {set<int> s1;s1.insert(1);s1.insert(2);s1.insert(3);s1.insert(4);s1.insert(5);auto it = s1.begin();while (it != s1.end()){cout << *it << " ";it++;}cout << endl;// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败set<int> s2;s2.insert({ 1,2,3,4,5,6 });//范围for遍历for (auto it : s2){cout << it << " ";}cout << endl;string s3[] = { "张三","李四","王五" };set<string> s4;//通过指针来遍历s4.insert(s3, s3 + sizeof(s3) / sizeof(string));for (auto it : s4){cout << it << " ";}cout << endl;set<string> strset = { "sort", "insert", "add" };for (auto it : strset){cout << it << " ";}cout << endl;return 0;}find和erase使⽤样例：
//set删除/查找//int main() {//set<int> s1 = {4,2,7,2,8,5,9};#if 0for (auto it : s1){cout << it << " ";}cout << endl;//删除最小值()s1.erase(s1.begin());for (auto it : s1){cout << it << " ";}cout << endl;int x;cin >> x;int ret = s1.erase(x);if (ret == 0){cout << "不存在" << endl;}else{cout << x << "删除成功" << endl;for (auto it : s1){cout << it << " ";}cout << endl;}#endif // 0#if 0//利用查找删除int xx;cin >> xx;auto pos = s1.find(xx);if (pos != s1.end()){s1.erase(pos);cout << "删除成功！" << endl;for (auto it : s1){cout << it << " ";}}else{cout << "不存在" << endl;}#endif // 0#if 0//直接调用erase接口删除int i;cin >> i;int ret = s1.erase(i);if (ret) {cout << "删除成功！" << endl;for (auto it : s1){cout << it << " ";}}else{cout << "不存在" << endl;}#endif // 0#if 0//库中find算法O(N)auto tmp1 = find(s1.begin(),s1.end(),5);//set中find算法O(logN) (1)auto tmp2 = s1.find(5);#endif // 0#if 0//count -- 计数，如果容器包含等效于 val 的元素，则为 1，否则为 0。int i;cin >> i;if (s1.count(i))cout << "找到了" << endl;elsecout << "没有找到" << endl;return 0;#endif // 0#if 0//实现区间查找set<int> s2;for (int i = 1; i < 10; i++){s2.insert(i * 10);}for (auto it : s2){cout << it << " ";}cout << endl;//删除[10,50]auto itlow = s2.lower_bound(10);auto itup = s2.upper_bound(50);s2.erase(itlow, itup);for (auto it : s2){cout << it << " ";}cout << endl;#endif // 0multiset和set的差异
multiset 与 set 的差异
支持重复元素：
std::set 不允许重复的元素，而 std::multiset 支持重复元素的存储。 插入元素：
std::set 和 std::multiset 都支持插入元素，但是 std::set 在插入重复元素时不会插入，而 std::multiset 会保留所有重复元素。 查找元素：
std::set 中查找元素时，如果元素存在，则返回指向该元素的迭代器；如果不存在，则返回 end()。std::multiset 中查找元素时，返回指向第一个匹配元素的迭代器。由于可能有多个相同的元素，因此需要循环遍历找到所有匹配的元素。 计数元素：
std::set 的 count() 成员函数总是返回 0 或 1，表示元素是否存在。std::multiset 的 count() 成员函数返回指定元素的实际个数。 删除元素：
std::set 中删除元素时，只会删除一个匹配的元素（实际上只可能有一个）。std::multiset 中删除元素时，如果提供了一个值而不是迭代器，则会删除所有匹配的元素。 第一部分：遍历 multiset
#if 0multiset<int> s1 = { 4,2,7,2,4,8,4,5,4,9 };auto it = s1.begin();while (it != s1.end()){cout << *it << " "; ++it;}#endif // 0这一部分代码创建了一个 multiset 并插入了一些重复的整数。然后通过迭代器遍历整个 multiset 并打印出每个元素。
第二部分：查找、计数和删除元素
#if 0int i;cin >> i;multiset<int> s1 = { 4,2,7,2,4,8,4,5,4,9 };auto pos = s1.find(i);while (pos != s1.end() && *pos == i){cout << *pos << " ";++pos;}cout << endl;// 相⽐set不同的是，count会返回x的实际个数 cout << s1.count(i) << endl;// 相⽐set不同的是，erase给值时会删除所有的x s1.erase(i);for (auto e : s1){cout << e << " ";}cout << endl;#endif // 0这一部分代码首先从用户输入一个整数 i，然后查找 multiset 中是否存在这个整数，并打印出来。接着使用 count() 函数统计 i 在 multiset 中出现的次数，并打印出来。最后，使用 erase() 函数删除所有值为 i 的元素，并再次遍历 multiset 打印剩余的元素。
题目练习
利用了set去重的特点
349. 两个数组的交集 - 力扣（LeetCode）
class Solution {public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { //将两个num set<int> s1(nums1.begin(),nums1.end()); set<int> s2(nums2.begin(),nums2.end()); //定义一个数组 vector<int> ret; //利用双指针法(迭代器) auto it_one = s1.begin(); auto it_two = s2.begin(); //小进行++（小的前面的数不可能和大的相等） while(it_one != s1.end() && it_two != s2.end()){ if(*it_one > *it_two){ it_two++; } else if(*it_one < *it_two){ it_one++; } else{ ret.push_back(*it_one); it_one++; it_two++; } } return ret; }};| 步骤 | 操作 | 描述 |
|---|---|---|
| 1 | set<int> s1(nums1.begin(), nums1.end()); | 将向量 nums1 转换为 set 类型，去除重复元素并排序。 |
| 2 | set<int> s2(nums2.begin(), nums2.end()); | 将向量 nums2 转换为 set 类型，去除重复元素并排序。 |
| 3 | vector<int> ret; | 创建一个空的 vector 用于存储交集元素。 |
| 4 | auto it_one = s1.begin(); | 初始化指向 s1 集合起始位置的迭代器 it_one。 |
| 5 | auto it_two = s2.begin(); | 初始化指向 s2 集合起始位置的迭代器 it_two。 |
| 6 | while (it_one != s1.end() && it_two != s2.end()) { ... } | 循环直到至少有一个迭代器达到其对应集合的末尾。 |
| 6.1 | if (*it_one > *it_two) { it_two++; } | 如果 s1 中的元素大于 s2 中的元素，则移动 s2 的迭代器 it_two。 |
| 6.2 | else if (*it_one < *it_two) { it_one++; } | 如果 s1 中的元素小于 s2 中的元素，则移动 s1 的迭代器 it_one。 |
| 6.3 | else { ret.push_back(*it_one); it_one++; it_two++; } | 如果两个元素相等，则将该元素添加到结果向量 ret 中，并同时移动两个迭代器。 |
| 7 | return ret; | 返回包含交集元素的结果向量 ret。 |
142. 环形链表 II - 力扣（LeetCode）
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* detectCycle(ListNode* head) { set<ListNode*> s1; ListNode* cur = head; while (cur) { //直接判断是否(注意这里判断的是地址，而不是值) if (s1.count(cur)) { return cur; } else { s1.insert(cur); } cur = cur->next; } return nullptr; }};| 步骤 | 操作 | 描述 |
|---|---|---|
| 1 | struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; | 定义链表节点结构，包含值 val 和指向下一个节点的指针 next。 |
| 2 | ListNode* detectCycle(ListNode* head) | 定义检测环的函数，接收链表头节点 head 作为参数。 |
| 3 | set<ListNode*> s1; | 创建一个 set 用于存储遍历过的节点指针。 |
| 4 | ListNode* cur = head; | 初始化一个指针 cur 指向链表头节点 head。 |
| 5 | while (cur) | 当 cur 不为 nullptr 时执行循环。 |
| 5.1 | if (s1.count(cur)) | 检查当前节点是否已经在 set 中。 |
| 5.1.1 | return cur; | 如果当前节点在 set 中，则返回该节点（环的起始节点地址）。 |
| 5.2 | else { s1.insert(cur); } | 如果当前节点不在 set 中，则将其插入 set 中。 |
| 5.3 | cur = cur->next; | 将 cur 指向下一个节点。 |
| 6 | return nullptr; | 如果遍历完链表都没有发现环，则返回 nullptr。 |
map的使用
参考文档
<map> - C++ Reference (cplusplus.com)
map类的介绍
std::map 的声明及特性
声明
template <class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key, T>> // map::allocator_type > class map;功能特性表格
| 模板参数 | 描述 |
|---|---|
Key | 映射的键类型，用于唯一标识一个条目。 |
T | 映射的值类型，即每个键所关联的数据类型。 |
Compare | 比较函数对象类型，默认为 std::less<Key>，用于比较键的大小。可以根据需要自定义。 |
Alloc | 分配器类型，默认为 std::allocator<std::pair<const Key, T>>，用于管理内存分配。 |
| 特性 | 描述 |
|---|---|
| 底层实现 | 使用红黑树（Red-Black Tree），保证插入、删除和查找操作的时间复杂度为 O(log N)。 |
| 比较机制 | 默认使用 std::less<Key> 进行比较，可以自定义比较函数对象。 |
| 内存管理 | 内存从分配器申请，默认使用 std::allocator。可以根据需要自定义分配器。 |
| 迭代器遍历 | 迭代器遍历按照键的升序顺序（中序遍历），因此遍历结果是有序的。 |
pair类型介绍
什么是 pair？
std::pair 是 C++ 标准库中的一个模板类，用于将两个不同类型的数据组合在一起。它可以看作是一个简单的容器，用来存储两个相关的值。这两个值可以是任意类型，但必须是已知的类型。
pair 的工作原理
1. 定义 pair
假设我们需要存储一个整数和一个字符串，我们可以这样定义一个 pair：
#include <utility> // 包含pair定义#include <iostream>int main() { std::pair<int, std::string> myPair;}这里 myPair 是一个 pair，它的第一个类型是 int，第二个类型是 std::string。
2. 构造 pair
std::pair 提供了几种构造函数来初始化它的成员变量：
默认构造函数：
std::pair<int, std::string> myPair; // 默认构造这会创建一个 pair，其中 first 和 second 都会被初始化为各自类型的默认值（例如 int 为 0，std::string 为一个空字符串）。
初始化构造函数：
std::pair<int, std::string> myPair(42, "hello"); // 初始化构造这里直接给 pair 的 first 和 second 成员赋初值。
从其他类型的 pair 构造：
std::pair<double, char> otherPair(3.14, 'a');std::pair<int, std::string> convertedPair(otherPair); // 从其他类型构造这里可以使用一个不同类型的 pair 来构造一个新的 pair。
使用 make_pair：
std::pair<int, std::string> myPair = std::make_pair(42, "hello");make_pair 是一个方便的函数，用于创建 pair 对象。
3. 访问 pair 的成员
std::pair 有两个成员变量 first 和 second，可以用来访问存储的值：
std::pair<int, std::string> myPair = std::make_pair(42, "hello");std::cout << "First: " << myPair.first << std::endl; // 输出 First: 42std::cout << "Second: " << myPair.second << std::endl; // 输出 Second: hellomap的构造
std::map 的构造接口
| 构造函数 | 描述 | 示例代码 |
|---|---|---|
map(); | 创建一个空的 std::map。 | |
template <class InputIterator>\nmap(InputIterator first, InputIterator last); | 创建一个 std::map，包含从迭代器 first 到 last 的所有元素。 | cpp\nstd::vector<std::pair<std::string, int>> vec = {{"apple", 1}, {"banana", 2}, {"orange", 3}};\nstd::map<std::string, int> myMap(vec.begin(), vec.end());\n |
map(const map& x); | 创建一个 std::map，包含另一个 std::map 的所有元素。 | cpp\nstd::map<std::string, int> myMap1 = {{"apple", 1}, {"banana", 2}, {"orange", 3}};\nstd::map<std::string, int> myMap2(myMap1);\n |
template <class InputIterator>\nmap(InputIterator first, InputIterator last,\nconst key_compare& comp,\nconst allocator_type& alloc = allocator_type()); | 创建一个 std::map，包含从迭代器 first 到 last 的所有元素，并使用指定的比较函数和分配器。 | cpp\nstd::vector<std::pair<std::string, int>> vec = {{"apple", 1}, {"banana", 2}, {"orange", 3}};\nstd::map<std::string, int, std::greater<std::string>> myMap(vec.begin(), vec.end());\n |
std::map 的迭代遍历
| 遍历方式 | 描述 | 示例代码 |
|---|---|---|
| 正向迭代 | 使用正向迭代器遍历 std::map，默认按照键的升序顺序。 | cpp\nfor (const auto &entry : myMap) {\n std::cout << entry.first << ": " << entry.second << std::endl;\n}\n |
| 反向迭代 | 使用反向迭代器遍历 std::map，按照键的降序顺序。 | cpp\nfor (auto rit = myMap.rbegin(); rit != myMap.rend(); ++rit) {\n std::cout << rit->first << ": " << rit->second << std::endl;\n}\n |
支持范围 for 循环
| 描述 | 示例代码 |
|---|---|
std::map 支持范围 for 循环，可以直接遍历 std::map 的键值对。 | cpp\nfor (const auto &entry : myMap) {\n std::cout << entry.first << ": " << entry.second << std::endl;\n}\n |
修改 value 数据
| 描述 | 示例代码 |
|---|---|
可以修改 std::map 中的 value 数据，即 pair 的 second 成员。 | cpp\nmyMap["apple"] = 2;\n |
不支持修改 key 数据
| 描述 | 示例代码 |
|---|---|
由于 std::map 的键值（key）决定了元素在红黑树中的位置，因此不允许直接修改键值。 | （不推荐）cpp\nmyMap["apple"] = "orange"; // 错误做法，实际修改的是 value\n |
#include <iostream>#include <map>#include <vector>int main() { // 默认构造 std::map<std::string, int> myMap; // 初始化构造 std::vector<std::pair<std::string, int>> vec = {{"apple", 1}, {"banana", 2}, {"orange", 3}}; std::map<std::string, int> myMapInit(vec.begin(), vec.end()); // 拷贝构造 std::map<std::string, int> myMapCopy(myMapInit); // 区间构造 std::map<std::string, int, std::greater<std::string>> myMapDesc(vec.begin(), vec.end()); // 正向迭代遍历 std::cout << "Forward iteration:" << std::endl; for (const auto &entry : myMapInit) { std::cout << entry.first << ": " << entry.second << std::endl; } // 反向迭代遍历 std::cout << "Reverse iteration:" << std::endl; for (auto rit = myMapInit.rbegin(); rit != myMapInit.rend(); ++rit) { std::cout << rit->first << ": " << rit->second << std::endl; } // 修改 value 数据 myMapInit["apple"] = 2; return 0;}map的增删查
std::map 的增删查接口
插入（Insert）
| 方法 | 描述 | 返回值 | 示例代码 |
|---|---|---|---|
pair<iterator,bool> insert (const value_type& val); | 插入一个键值对 pair，如果键已存在则插入失败。 | 返回一个 pair，其中 first 是插入位置的迭代器，second 是一个布尔值，表示是否插入成功。 | cpp\nstd::pair<std::map<std::string, int>::iterator, bool> result = myMap.insert({{"apple", 2}});\n |
void insert (initializer_list<value_type> il); | 插入一个初始化列表，已存在的值不会插入。 | 无返回值。 | cpp\nmyMap.insert({{"apple", 1}, {"banana", 2}, {"orange", 3}});\n |
template <class InputIterator>\nvoid insert (InputIterator first, InputIterator last); | 插入一个迭代器区间内的元素，已存在的值不会插入。 | 无返回值。 | cpp\nstd::vector<std::pair<std::string, int>> vec = {{"apple", 1}, {"banana", 2}, {"orange", 3}};\nmyMap.insert(vec.begin(), vec.end());\n |
查找（Find）
| 方法 | 描述 | 返回值 | 示例代码 |
|---|---|---|---|
iterator find (const key_type& k); | 查找键 k，返回指向键 k 的迭代器，如果没有找到则返回 end()。 | 迭代器 | cpp\nauto it = myMap.find("apple");\nif (it != myMap.end()) {\n std::cout << it->first << ": " << it->second << std::endl;\n}\n |
size_type count (const key_type& k) const; | 计算键 k 在 std::map 中出现的次数。 | 键 k 的出现次数（对于 std::map，最多为 1）。 | cpp\nsize_t count = myMap.count("apple");\nstd::cout << "Count of 'apple': " << count << std::endl;\n |
iterator lower_bound (const key_type& k); | 返回大于等于键 k 的第一个元素的迭代器。 | 迭代器 | cpp\nauto it = myMap.lower_bound("banana");\n |
const_iterator lower_bound (const key_type& k) const; | 返回大于等于键 k 的第一个元素的常量迭代器。 | 常量迭代器 | cpp\nauto it = myMap.lower_bound("banana");\n |
删除（Erase）
| 方法 | 描述 | 返回值 | 示例代码 |
|---|---|---|---|
iterator erase (const_iterator position); | 删除一个迭代器位置的值，返回下一个元素的迭代器。 | 迭代器 | cpp\nauto it = myMap.find("apple");\nif (it != myMap.end()) {\n auto nextIt = myMap.erase(it);\n}\n |
size_type erase (const key_type& k); | 删除键 k，返回删除的元素数量（对于 std::map，最多为 1）。 | 删除的元素数量 | cpp\nsize_t count = myMap.erase("apple");\nstd::cout << "Erased 'apple': " << count << std::endl;\n |
iterator erase (const_iterator first, const_iterator last); | 删除一段迭代器区间的值，返回最后一个未删除元素的迭代器。 | 迭代器 | cpp\nauto rangeBegin = myMap.lower_bound("apple");\nauto rangeEnd = myMap.upper_bound("orange");\nmyMap.erase(rangeBegin, rangeEnd);\n |
#include <iostream>#include <map>#include <vector>int main() { // 创建一个空的 map std::map<std::string, int> myMap; // 插入键值对 std::pair<std::map<std::string, int>::iterator, bool> result = myMap.insert({{"apple", 1}}); if (result.second) { std::cout << "Inserted 'apple': " << result.first->second << std::endl; } // 使用初始化列表插入 myMap.insert({{"banana", 2}, {"orange", 3}}); // 使用迭代器区间插入 std::vector<std::pair<std::string, int>> vec = {{"grape", 4}, {"mango", 5}}; myMap.insert(vec.begin(), vec.end()); // 查找键 "apple" auto it = myMap.find("apple"); if (it != myMap.end()) { std::cout << "Found 'apple': " << it->second << std::endl; } // 计算键 "apple" 的出现次数 size_t count = myMap.count("apple"); std::cout << "Count of 'apple': " << count << std::endl; // 找到大于等于 "banana" 的元素 auto lbIt = myMap.lower_bound("banana"); if (lbIt != myMap.end()) { std::cout << "Lower bound of 'banana': " << lbIt->first << ": " << lbIt->second << std::endl; } // 删除 "apple" size_t erasedCount = myMap.erase("apple"); std::cout << "Erased 'apple': " << erasedCount << std::endl; // 删除一段迭代器区间的值 auto rangeBegin = myMap.lower_bound("banana"); auto rangeEnd = myMap.upper_bound("orange"); myMap.erase(rangeBegin, rangeEnd); return 0;}map的数据修改
std::map 数据修改接口
修改 mapped_type 数据
| 方法 | 描述 | 返回值 | 示例代码 |
|---|---|---|---|
iterator find (const key_type& k); | 查找键 k，返回指向键 k 的迭代器，如果没有找到则返回 end()。通过迭代器可以修改键对应的 mapped_type 值。 | 迭代器 | cpp\nauto it = myMap.find("apple");\nif (it != myMap.end()) {\n it->second = 2;\n}\n |
mapped_type& operator[] (const key_type& k); | 多功能接口，支持查找、插入和修改数据。如果键 k 已经存在，则返回键对应的 mapped_type 的引用；如果不存在，则插入默认值并返回引用。 | mapped_type 的引用 | cpp\nmyMap["apple"] = 2;\n |
插入接口
| 方法 | 描述 | 返回值 | 示例代码 |
|---|---|---|---|
pair<iterator,bool> insert (const value_type& val); | 插入一个键值对 pair，如果键已存在则插入失败。返回一个 pair，其中 first 是插入位置的迭代器，second 表示是否插入成功。 | pair<iterator, bool>，其中 first 是迭代器，second 是布尔值，表示是否插入成功。 | cpp\nstd::pair<std::map<std::string, int>::iterator, bool> result = myMap.insert({{"apple", 2}});\n |
operator[] 的内部实现
| 方法 | 描述 | 返回值 | 示例代码 |
|---|---|---|---|
mapped_type& operator[] (const key_type& k); | 多功能接口，支持查找、插入和修改数据。如果键 k 已经存在，则返回键对应的 mapped_type 的引用；如果不存在，则插入默认值并返回引用。 | mapped_type 的引用 | cpp\nmapped_type& ref = myMap["apple"];\nref = 2;\n |
operator[] 的内部实现示例
| 描述 | 示例代码 |
|---|---|
如果键 k 不在 std::map 中，insert 会插入键 k 和 mapped_type 的默认值，并返回结点中存储的 mapped_type 值的引用。 | cpp\nmapped_type& ref = myMap["newKey"];\nref = 5;\n |
如果键 k 已经在 std::map 中，insert 会插入失败，但返回的 pair 对象的 first 指向键结点的迭代器，并返回结点中存储的 mapped_type 值的引用。 | cpp\nmapped_type& ref = myMap["existingKey"];\nref = 3;\n |
构造遍历及增删查使用样例
#include <iostream>#include <map>using namespace std;int main() { // initializer_list构造及迭代遍历 map<string, string> dict = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"}, {"string", "字符串"} }; // 使用 auto 自动推导类型 auto it = dict.begin(); while (it != dict.end()) { // 使用迭代器的 operator-> 和 operator* 访问元素 cout << it->first << ":" << it->second << endl; ++it; } cout << endl; // insert 插入 pair 对象的 4 种方式，对比之下，最后一种最方便 pair<string, string> kv1("first", "第一个"); dict.insert(kv1); dict.insert(pair<string, string>("second", "第二个")); dict.insert(make_pair("sort", "排序")); dict.insert({"auto", "自动的"}); // "left" 已经存在，插入失败 dict.insert({"left", "左边，剩余"}); // 范围 for 遍历 for (const auto& e : dict) { cout << e.first << ":" << e.second << endl; } cout << endl; string str; while (cin >> str) { auto ret = dict.find(str); if (ret != dict.end()) { cout << "->" << ret->second << endl; } else { cout << "无此单词，请重新输入" << endl; } } // erase 接口跟 set 完全类似，这里就不演示讲解了 return 0;}map的迭代器和[]功能样例
为了更好地展示 std::map 的迭代器和 operator[] 功能，我们将给出的示例代码整理并加以解释。以下是两个不同的实现方法，用于统计水果出现的次数，以及一个使用 std::map 的其他功能的示例。
示例 1：使用 find 和迭代器修改功能统计水果出现次数
#include <iostream>#include <map>#include <string>using namespace std;int main() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (const auto& str : arr) { // 先查找水果在不在map中 auto ret = countMap.find(str); if (ret == countMap.end()) { // 如果不在，说明水果第一次出现，则插入 {水果, 1} countMap.insert({str, 1}); } else { // 如果在，则查找到的节点中水果对应的次数++ ret->second++; } } for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; return 0;}示例 2：使用 operator[] 插入和修改功能统计水果出现次数
#include <iostream>#include <map>#include <string>using namespace std;int main() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (const auto& str : arr) { // [] 先查找水果在不在map中 // 如果不在，说明水果第一次出现，则插入 {水果, 0}，同时返回次数的引用，++ 一下就变成1次了 // 如果在，则返回水果对应的次数++ countMap[str]++; } for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; return 0;}示例 3：使用 std::map operator[]
#include <iostream>#include <map>#include <string>using namespace std;int main() { map<string, string> dict; dict.insert(make_pair("sort", "排序")); // key不存在->插入 {"insert", ""} （默认构造） dict["insert"]; // 插入+修改 dict["left"] = "左边"; // 修改 dict["left"] = "左边、剩余"; // key存在->查找 cout << dict["left"] << endl; return 0;}multimap和map的差异
让我们以通俗易懂的方式解释 std::map 和 std::multimap 的主要差异，以及它们各自的使用场景。
std::map 和 std::multimap 的主要差异
1. 键的唯一性
std::map：在 std::map 中，键是唯一的。这意味着每个键只能对应一个值。如果你试图插入一个已经存在的键，插入操作将不会成功。
std::map<std::string, int> myMap;myMap.insert({"apple", 1});myMap.insert({"apple", 2}); // 这个操作不会成功std::multimap：在 std::multimap 中，键可以重复。这意味着同一个键可以对应多个值。如果你插入一个已经存在的键，新的键值对将会被插入到适当的位置。
例子：
std::multimap<std::string, int> myMultimap;myMultimap.insert({"apple", 1});myMultimap.insert({"apple", 2}); // 这个操作会成功2. 查找操作
std::map：由于键是唯一的，因此 find 方法总是返回指向特定键的迭代器，如果没有找到，则返回 end()。
例子：
auto it = myMap.find("apple");if (it != myMap.end()) { // 找到了 "apple"}std::multimap：由于键可以重复，find 方法返回的是指向键的第一个匹配项的迭代器。此外，equal_range 方法可以返回键的第一个和最后一个匹配项之间的范围。
例子：
auto range = myMultimap.equal_range("apple");for (auto it = range.first; it != range.second; ++it) { // 遍历所有 "apple" 的匹配项}3. 插入操作
std::map：如果键已经存在，插入操作不会成功。
例子：
bool inserted = myMap.insert({"apple", 2}).second; // inserted 为 falsestd::multimap：如果键已经存在，插入操作仍然会成功，并将新的键值对插入到适当的位置。
例子：
bool inserted = myMultimap.insert({"apple", 2}).second; // inserted 为 true4. 计数操作
std::map：count 方法对于任何键总是返回 1 或 0（键存在与否）。
例子：
int count = myMap.count("apple"); // count 为 1 或 0std::multimap：count 方法可以返回一个键的出现次数，可以大于 1。 例子：
int count = myMultimap.count("apple"); // count 可能大于 15. 删除操作
std::map：删除操作通常删除一个键值对。
例子：
myMap.erase("apple");std::multimap：删除操作可以删除一个键的所有匹配项。 例子：
myMultimap.erase("apple");6. operator[]
std::map：支持 operator[]，可以用于查找、插入和修改键对应的值。
例子：
myMap["apple"] = 1;std::multimap：不支持 operator[]，因为键可以重复，operator[] 只能用于插入新的键值对，而不能用于修改值。 例子：
// 不支持// myMultimap["apple"] = 1;
使用 std::map
#include <iostream>#include <map>int main() { std::map<std::string, int> myMap; myMap.insert({"apple", 1}); myMap.insert({"banana", 2}); // 插入重复键，不会成功 myMap.insert({"apple", 2}); // 使用 operator[] 修改值 myMap["apple"] = 3; // 输出 for (const auto& e : myMap) { std::cout << e.first << ": " << e.second << std::endl; } return 0;}使用 std::multimap
题目练习
138. 随机链表的复制 - 力扣（LeetCode）
/*// Definition for a Node.class Node {public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; }};*/class Solution {public: Node* copyRandomList(Node* head) { map<Node*, Node*> Map; Node *tmphead = nullptr, *tmptail = nullptr; Node* cur = head; // 建立关系 while (cur) { if (tmptail == nullptr) { tmphead = tmptail = new Node(cur->val); } else { tmptail->next = new Node(cur->val); tmptail = tmptail->next; } // 建立map Map[cur] = tmptail; cur = cur->next; } // 处理random cur = head; Node* copy = tmphead; while (cur) { if (cur->random == nullptr) { copy->random = nullptr; } else { //Map返回cur的value copy->random = Map[cur->random]; } cur = cur->next; copy = copy->next; } return tmphead; }};
| 步骤 | 描述 | 目的 | 代码示例 |
|---|---|---|---|
| 1 | 初始化辅助变量 | 用于存储复制链表的头节点和尾节点 | Node *tmphead = nullptr, *tmptail = nullptr; |
| 2 | 遍历原链表 | 复制每个节点，并构建新链表 | while (cur) {...} |
| 3 | 新建节点 | 创建新节点，并设置其值 | tmphead = tmptail = new Node(cur->val); |
| 4 | 连接新节点 | 将新节点连接到新链表的末尾 | tmptail->next = new Node(cur->val); |
| 5 | 更新尾指针 | 更新新链表的尾指针 | tmptail = tmptail->next; |
| 6 | 建立映射关系 | 在 map 中记录原节点与其副本的关系 | Map[cur] = tmptail; |
| 7 | 遍历原链表（第二次） | 设置新链表中节点的 random 指针 | while (cur) {...} |
| 8 | 设置 random 指针 | 根据原节点的 random 指针设置新节点的 random 指针 | copy->random = Map[cur->random]; |
| 9 | 返回新链表头节点 | 最终返回复制的新链表的头节点 | return tmphead; |
class Solution {public: class Compare { public: //比较单词出现数 bool operator()(const pair<string, int>& x, const pair<string, int>& y) { // 如果 return x.second > y.second || (x.second == y.second && x.first < y.first); //个数相等，比较单词 } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> constmap; // 统计所有单词 for (auto it : words) { constmap[it]++; } // 将所有数据放进一个vector vector<pair<string, int>> v(constmap.begin(), constmap.end()); // 排序(stable_sort--稳定排序) //stable_sort(v.begin(), v.end(), Compare()); sort(v.begin(), v.end(), Compare()); // for (auto it : v) { // cout<<it.first<<":"<<it.second<<" "; // } cout<<endl; // 取前k个 vector<string> ret; for (int i = 0; i < k; i++) { ret.push_back(v[i].first); } return ret; }};| 步骤 | 描述 | 目的 | 代码示例 |
|---|---|---|---|
| 1 | 初始化辅助数据结构 | 存储单词及其出现次数 | std::map<std::string, int> freqMap; |
| 2 | 统计单词出现次数 | 记录每个单词出现的次数 | for (const auto& word : words) { freqMap[word]++; } |
| 3 | 创建优先队列 | 用于存储前 k 个频繁元素 | std::priority_queue<std::pair<std::string, int>, std::vector<std::pair<std::string, int>>, Compare> pq; |
| 4 | 遍历统计结果 | 将统计结果加入优先队列 | for (const auto& item : freqMap) { pq.push(item); if (pq.size() > k) { pq.pop(); } } |
| 5 | 提取前 k 个单词 | 从优先队列中提取前 k 个单词 | std::vector<std::string> result(k); for (int i = k - 1; i >= 0; --i) { result[i] = pq.top().first; pq.pop(); } |
| 6 | 返回结果 | 返回前 k 个频繁单词 | return result; |
