【C++】21.map和set的使用

---

1. 序列式容器和关联式容器

前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

本章节讲解的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

---

2. set系列的使用

2.1 set和multiset参考文档

https://legacy.cplusplus.com/reference/set/

---

2.2 set类的介绍

• set的声明如下，T就是set底层关键字的类型

• set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数

• set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。

• 一般情况下，我们都不需要传后两个模版参数。

• set底层是用红黑树实现，增删查效率是O(logN) ，迭代器遍历是走的搜索树的中序，所以是有序的。

• 前面部分我们已经学习了vector/list等容器的使用，STL容器接口设计，高度相似，所以这里我们就不再一个接口一个接口的介绍，而是直接挑比较重要的接口进行介绍。

template < class T, // set::key_type/value_typeclass Compare = less<T>, // set::key_compare/value_compareclass Alloc = allocator<T> // set::allocator_type> 
class set;  // 声明这是一个名为set的类

这是C++ STL中set容器的模板声明：

1. template <...> - 这是一个模板类声明，包含三个模板参数

2. 第一个参数 class T

   • 这是set存储的元素类型
   • 也是key和value的类型(在set中key就是value)
   • 必须显式指定，没有默认值

3. 第二个参数 class Compare = less<T>

   • 用于元素比较的仿函数类型
   • 默认使用less<T>，即按升序排序
   • 你可以自定义比较器来改变排序方式

4. 第三个参数 class Alloc = allocator<T>

   • 内存分配器类型
   • 默认使用标准allocator
   • 通常不需要修改此参数

---

2.3 set的构造和迭代器

set的构造我们关注以下几个接口即可。

set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for,set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1) 无参默认构造
explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>set (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());// copy (3) 拷贝构造
set (const set& x);
// initializer list (5) initializer 列表构造
set (initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// 迭代器是一个双向迭代器
iterator -> a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

构造函数：

1. 默认构造函数

explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

• 创建空set
• explicit防止隐式转换
• 可选参数：比较器和分配器
• key_compare& comp = key_compare()
  • 比较器参数，默认是less<T>
  • 用于维护set的元素顺序
• allocator_type& alloc = allocator_type()
  • 内存分配器参数
  • 默认使用std::allocator
  • 负责set内存的分配和释放

2. 迭代器区间构造

template <class InputIterator>
set (InputIterator first,            // 起始迭代器InputIterator last,             // 结束迭代器const key_compare& comp = key_compare(),        // 可选的比较器const allocator_type& = allocator_type()        // 可选的分配器
);

• 用迭代器范围内的元素构造set
• 常用于从其他容器构造set
• template <class InputIterator>
  • 接受任何满足InputIterator（输入迭代器）要求的迭代器类型
  • 可以是来自不同容器的迭代器，只要它们指向的元素类型可以转换为set的元素类型

3. 拷贝构造

set (const set& x);

• 复制另一个set创建新set

4. 初始化列表构造

set (initializer_list<value_type> il,     // 初始化列表const key_compare& comp = key_compare(),        // 可选的比较器const allocator_type& alloc = allocator_type()  // 可选的分配器
);

• 使用初始化列表构造set

---

双向迭代器

iterator -> a bidirectional iterator to const value_type 描述的是set迭代器的特性：

1. 双向迭代器(bidirectional iterator)

   • 可以前后移动（++和–操作）
   • 不支持随机访问（不能+n或-n）
   • 移动方向：向前(++)或向后(–)

2. const value_type

   • set中的元素不能通过迭代器修改
   • 这是因为修改可能破坏set的有序性

示例代码：

set<int> s = {1, 2, 3, 4, 5};// 正确用法
set<int>::iterator it = s.begin();
cout << *it;  // 可以读取
++it;         // 可以向前
--it;         // 可以向后// 错误用法
*it = 10;     // 编译错误：不能修改元素
it += 2;      // 编译错误：不支持随机访问
it = it + 2;  // 编译错误：不支持随机访问// 正确的遍历方式
for(set<int>::iterator it = s.begin(); it != s.end(); ++it) {cout << *it << " ";  // 只能读取，不能修改
}// 现代C++的简化写法
for(const auto& element : s) {cout << element << " ";
}

与vector的随机访问迭代器相比：

vector<int> v = {1, 2, 3, 4, 5};
vector<int>::iterator vit = v.begin();vit += 2;      // vector支持随机访问
*vit = 10;     // vector允许修改元素

---

迭代器：

1. 正向迭代器

iterator begin();  // 指向第一个元素
iterator end();    // 指向最后一个元素之后的位置

2. 反向迭代器

reverse_iterator rbegin();  // 指向最后一个元素
reverse_iterator rend();    // 指向第一个元素之前的位置

使用示例：

// 不同构造方式
set<int> s1;                         // 默认构造
set<int> s2({1,2,3,4});             // 初始化列表构造
vector<int> vec = {1,2,3,4};
set<int> s3(vec.begin(), vec.end()); // 迭代器区间构造
set<int> s4(s3);                     // 拷贝构造// 迭代器使用
for(auto it = s1.begin(); it != s1.end(); ++it) {// 正向遍历
}for(auto it = s1.rbegin(); it != s1.rend(); ++it) {// 反向遍历
}

---

2.4 set的增删查

set的增删查关注以下几个接口即可：

Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)// 单个数据插入，如果已经存在则插入失败
pair<iterator,bool> insert (const value_type& val);
// 列表插入，已经在容器中存在的值不会插入
void insert (initializer_list<value_type> il);
// 迭代器区间插入，已经在容器中存在的值不会插入
template <class InputIterator>void insert (InputIterator first, InputIterator last);
// 查找val，返回val所在的迭代器，没有找到返回end()
iterator find (const value_type& val);
// 查找val，返回Val的个数
size_type count (const value_type& val) const;
// 删除一个迭代器位置的值
iterator erase (const_iterator position);
// 删除val，val不存在返回0，存在返回1
size_type erase (const value_type& val);
// 删除一段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);
// 返回大于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回大于val位置的迭代器
iterator upper_bound (const value_type& val) const;

---

2.5 insert和迭代器遍历使用样例：

#include<iostream>
#include<set>  // 包含set容器头文件
using namespace std;int main()
{// set默认情况：// 1. 去重：相同元素只保留一个// 2. 升序：使用less<T>比较器，从小到大排序set<int> s;// 如果想降序，可以使用greater<int>比较器//set<int, greater<int>> s;  // 注释掉的降序写法// 插入元素，重复的5只会保存一次s.insert(5);s.insert(2);s.insert(7);s.insert(5);  // 这个5会插入失败，因为已经存在// 使用迭代器遍历//set<int>::iterator it = s.begin();  // 完整的迭代器类型声明auto it = s.begin();                  // 使用auto自动推导类型while (it != s.end()){// set中的元素不能修改，因为修改可能会破坏有序性// *it = 1;  // 错误：set迭代器指向的元素是只读的cout << *it << " ";  // 只能读取元素++it;               // 迭代器移动到下一个位置}cout << endl;// 使用初始化列表插入多个元素// 如果元素已存在（如2），则该元素插入失败// 新元素（如3,8,9）会插入并保持有序s.insert({ 2,8,3,9 });// 使用范围for循环遍历for (auto e : s){cout << e << " ";}cout << endl;// 创建string类型的set// 使用初始化列表构造set<string> strset = { "sort", "insert", "add" };// string比较规则：// 1. 按字典序（ASCII码）比较// 2. 从第一个字符开始，按位比较ASCII值// 输出会按字典序排列："add" "insert" "sort"for (auto& e : strset){cout << e << " ";}cout << endl;return 0;
}

补充说明：

1. set的特性：
   • 元素唯一性（去重）
   • 自动排序
   • 元素不可修改（const）
2. 排序规则：
   • 默认使用less<T>，升序排序
   • 可以使用greater<T>或自定义比较器实现降序或其他排序方式
3. string的排序：
   • 按字典序比较，即ASCII码值的大小
   • 例如：“add” < “insert” < “sort”
4. 迭代器：
   • set的迭代器是只读的，不能通过迭代器修改元素
   • 因为修改可能破坏set的有序性

---

2.6 find和erase使用样例：

#include<iostream>
#include<set>  // 包含set容器头文件
using namespace std;int main()
{// 使用初始化列表构造set// set会自动排序并去重：{2,4,5,7,8,9}set<int> s = { 4,2,7,2,8,5,9 };  // 使用范围for循环遍历set中的元素for (auto e : s){cout << e << " ";  // 输出每个元素}cout << endl;// 删除最小值(即第一个元素)// s.begin()返回指向第一个元素的迭代器s.erase(s.begin());// 再次遍历输出set中的元素for (auto e : s){cout << e << " ";}cout << endl;// 方式1：直接删除值为x的元素int x;cin >> x;// erase返回实际删除的元素个数：存在则返回1，不存在返回0int num = s.erase(x);if (num == 0){cout << x << "不存在！" << endl;}// 输出删除后的结果for (auto e : s){cout << e << " ";}cout << endl;// 方式2：先查找再删除cin >> x;// find返回指向找到元素的迭代器，如果没找到返回end()auto pos = s.find(x);if (pos != s.end())  // 找到了{s.erase(pos);    // 使用迭代器删除元素}else{cout << x << "不存在！" << endl;}// 输出删除后的结果for (auto e : s){cout << e << " ";}cout << endl;// 两种查找方式的比较// 1. 算法库的find：遍历查找，时间复杂度O(N)auto pos1 = find(s.begin(), s.end(), x); // 2. set容器自带的find：二叉搜索树查找，时间复杂度O(logN)auto pos2 = s.find(x); // 使用count间接实现快速查找// count对于set来说返回值只可能是0或1，因为set不允许重复cin >> x;if (s.count(x))  // 如果count返回1，表示存在{cout << x << "在！" << endl;}else  // 如果count返回0，表示不存在{cout << x << "不存在！" << endl;}return 0;
}

#include<iostream>
#include<set>  // 包含set容器头文件
using namespace std;int main()
{// 创建空的set容器std::set<int> myset;// 插入1-9的10倍数到set中for (int i = 1; i < 10; i++)myset.insert(i * 10); // 插入后set内容：10 20 30 40 50 60 70 80 90// 遍历并打印set中的所有元素for (auto e : myset){cout << e << " ";}cout << endl;// lower_bound(key)：返回指向大于或等于key的第一个元素的迭代器// 这里返回指向30的迭代器，因为30是第一个大于等于30的元素auto itlow = myset.lower_bound(30);// upper_bound(key)：返回指向大于key的第一个元素的迭代器// 这里返回指向70的迭代器，因为70是第一个大于60的元素auto itup = myset.upper_bound(60);// erase(first, last)：删除[first,last)区间的所有元素// 这里删除[30,60]这个闭区间的所有元素// 即删除30,40,50,60这些元素myset.erase(itlow, itup);// 再次遍历打印，检查删除结果// 预期输出：10 20 70 80 90for (auto e : myset){cout << e << " ";}cout << endl;return 0;
}

补充说明：

1. lower_bound和upper_bound都是基于二分搜索实现的，时间复杂度为O(logN)
2. 区间[itlow,itup)是一个左闭右开区间：
   • itlow指向第一个>=30的元素（即30）
   • itup指向第一个>60的元素（即70）
   • 因此这个区间包含了30,40,50,60这些元素
3. 如果要删除的key不存在，lower_bound和upper_bound会返回最接近的位置：
   • 如果key小于所有元素，返回begin()
   • 如果key大于所有元素，返回end()

---

2.7 multiset和set的差异

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，那么insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。

#include<iostream>
#include<set>  // 包含set/multiset容器头文件
using namespace std;int main()
{// multiset特点：// 1. 有序：默认按照小于比较，从小到大排序// 2. 允许重复值存在// 排序后结果为：{2,2,4,4,4,4,5,7,8,9}multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };// 使用迭代器遍历multiset中的所有元素auto it = s.begin();  // 获取指向第一个元素的迭代器while (it != s.end()) // 当迭代器未到达末尾时继续循环{cout << *it << " ";  // 解引用迭代器，输出当前元素++it;               // 迭代器移动到下一个位置}cout << endl;// 查找元素xint x;cin >> x;// find在multiset中返回第一个等于x的元素位置// 如果有多个相同元素，find返回中序遍历遇到的第一个auto pos = s.find(x);// 通过迭代器遍历所有等于x的元素// 因为multiset是有序的，所有相等的元素都是相邻的while (pos != s.end() && *pos == x){cout << *pos << " ";  // 输出当前找到的x++pos;               // 移动到下一个位置继续查找}cout << endl;// count返回元素x在multiset中出现的次数// 而在set中count只会返回0或1cout << s.count(x) << endl;// erase删除所有值等于x的元素// 而在set中最多只会删除一个元素s.erase(x);// 使用范围for循环遍历删除后的结果for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

multiset与set的主要区别：

1. multiset允许重复元素，set不允许
2. find在multiset中返回第一个匹配的元素位置
3. count在multiset中返回实际出现次数，在set中只返回0或1
4. erase在multiset中删除所有匹配的元素，在set中最多删除一个

---

2.8 349. 两个数组的交集 - 力扣（LeetCode）

349. 两个数组的交集 - 力扣（LeetCode）

class Solution {
public:// 函数功能：求两个数组的交集// 参数：两个整型vector数组的引用// 返回值：包含交集元素的vectorvector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 构造两个set，利用set自动去重和排序的特性// 用nums1和nums2的迭代器区间初始化setset<int> s1(nums1.begin(), nums1.end());  // nums1中的不重复元素set<int> s2(nums2.begin(), nums2.end());  // nums2中的不重复元素// 创建结果数组，用于存储交集元素vector<int> ret;// 获取两个set的起始迭代器auto it1 = s1.begin();auto it2 = s2.begin();// 同时遍历两个set，直到其中一个遍历完while(it1 != s1.end() && it2 != s2.end()){if(*it1 < *it2)  {// 如果s1当前元素小，移动s1的迭代器it1++;}else if(*it1 > *it2){// 如果s2当前元素小，移动s2的迭代器it2++;}else  // *it1 == *it2{// 相等说明是交集元素ret.push_back(*it1);  // 将交集元素加入结果数组// 两个迭代器都要往后移动it1++;it2++;}}return ret;  // 返回结果数组}
};

算法思路解析：

1. 预处理：
   • 将两个数组转换为set，实现去重和排序
   • 时间复杂度：O(NlogN)，空间复杂度：O(N)
2. 求交集：
   • 利用set有序的特性，用双指针（迭代器）同时遍历两个set
   • 类似归并排序的思路，比较两个当前元素：
     • 如果s1当前元素小，移动s1迭代器
     • 如果s2当前元素小，移动s2迭代器
     • 如果相等，就是交集元素，加入结果数组，两个迭代器都移动
   • 时间复杂度：O(min(N,M))，N和M是两个set的大小
3. 优势：
   • 利用set的特性自动去重和排序
   • 双指针遍历的方式效率高
   • 代码简洁易懂

---

2.9 142. 环形链表 II - 力扣（LeetCode）

142. 环形链表 II - 力扣（LeetCode）

数据结构初阶阶段，我们通过证明一个指针从头开始走一个指针从相遇点开始走，会在入口点相遇，理解证明都会很麻烦。这里我们使用set查找记录解决非常简单方便，这里体现了set在解决一些问题时的价值，完全是降维打击。

class Solution {
public:// 函数功能：检测链表中的环，并返回环的入口节点// 参数：链表头节点指针// 返回值：如果有环，返回环的入口节点；如果无环，返回nullptrListNode *detectCycle(ListNode *head) {// 创建一个存储ListNode指针的set容器// 用于记录已经访问过的节点地址set<ListNode*> s;// cur指针用于遍历链表ListNode* cur = head;// 遍历链表while(cur){// 尝试将当前节点地址插入set中// insert返回一个pair:// - first是一个迭代器，指向插入位置// - second是一个bool值，表示插入是否成功//   - true表示插入成功（之前没有这个元素）//   - false表示插入失败（已经存在这个元素）auto ret = s.insert(cur);// 如果插入失败(ret.second为false)// 说明这个节点之前已经访问过// 也就是找到了环的入口if(ret.second == false)return cur;  // 返回环的入口节点// 继续遍历下一个节点cur = cur->next;}// 如果遍历完整个链表都没有找到重复节点// 说明链表中没有环return nullptr;}
};

算法思路解析：

1. 基本思想：
   • 用set存储已经访问过的节点地址
   • 如果某个节点地址已经在set中存在，说明找到了环
2. 具体步骤：
   • 创建set存储节点地址
   • 遍历链表，尝试将每个节点地址插入set
   • 如果插入失败，说明这个地址之前已存在，即找到环的入口
   • 如果遍历结束都没有重复地址，说明无环
3. 时间复杂度分析：
   • O(N)，N为链表节点数
   • 每个节点最多被访问一次
   • set的插入操作是O(logN)
4. 空间复杂度分析：
   • O(N)，需要额外空间存储访问过的节点地址

---

3. map系列的使用

3.1 map和multimap参考文档

https://legacy.cplusplus.com/reference/map/

---

3.2 map类的介绍

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是O(logN) ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。

template < class Key, // map::key_typeclass T, // map::mapped_typeclass Compare = less<Key>, // map::key_compareclass Alloc = allocator<pair<const Key,T> > // map::allocator_type> 
class map;

1. Key - key_type（键类型）

template <class Key>  // 第一个模板参数

• 用作map中的键
• 必须支持比较操作（能够排序）
• 不可重复

2. T - mapped_type（值类型）

class T    // 第二个模板参数

• 存储的实际数据类型
• 可以修改
• 没有特殊要求

3. Compare - key_compare（比较器）

class Compare = less<Key>  // 第三个模板参数，有默认值

• 用于键的排序
• 默认使用less<Key>
• 可自定义比较规则

4. Alloc - allocator_type（分配器）

class Alloc = allocator<pair<const Key,T>>  // 第四个模板参数，有默认值

• 内存分配器
• 注意是pair的分配器
• 键值对pair中的Key是const的

---

3.3 pair类型介绍

map底层的红黑树节点中的数据，使用pair<Key, T>存储键值对数据。

// value_type定义了map中存储的键值对类型
// Key是const的，防止键被修改
typedef pair<const Key, T> value_type;// pair是一个通用的模板结构体，用于存储两个不同类型的值
template <class T1, class T2>
struct pair 
{// 定义first成员的类型别名typedef T1 first_type;// 定义second成员的类型别名typedef T2 second_type;// pair的两个公有成员变量T1 first;    // 第一个成员T2 second;   // 第二个成员// 默认构造函数// 使用T1和T2的默认构造函数初始化first和secondpair(): first(T1()), second(T2()){}// 带参数的构造函数// @param a: first成员的初始值// @param b: second成员的初始值pair(const T1& a, const T2& b): first(a), second(b){}// 拷贝构造函数模板// 允许从不同类型的pair进行构造（如果类型可以转换）// @param pr: 源pair对象// @template U: 源pair的first类型// @template V: 源pair的second类型template<class U, class V> pair (const pair<U,V>& pr): first(pr.first), second(pr.second){}
};// 辅助函数：创建pair对象的便捷方式
// 通过类型推导自动确定pair的类型
// @param x: 第一个值
// @param y: 第二个值
// @return: 返回构造好的pair对象
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

为什么写成pair(): first(T1()), second(T2())而不是pair(): first(T1), second(T2)

1. T1() vs T1 的区别：

pair(): first(T1()), second(T2())    // 值初始化
pair(): first(T1), second(T2)        // 默认初始化

2. 对于不同类型的影响：

// 基本类型(int, double等)
int n1();      // 值初始化 -> 0
int n2;        // 默认初始化 -> 未定义值// 示例
pair<int, int> p1;  // 使用T1()
// p1.first = 0, p1.second = 0pair<int, int> p2;  // 如果使用T1
// p1.first = 未定义值, p1.second = 未定义值

---

3.4 map的构造

map的构造我们关注以下几个接口即可。

map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1) 无参默认构造
explicit map (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
// - explicit防止隐式转换
// - key_compare默认是less<Key>
// - allocator_type是内存分配器，默认使用标准分配器
// range (2) 迭代器区间构造
template <class InputIterator>     // 模板参数，可以接受任何输入迭代器类型
map (InputIterator first,         // 起始迭代器InputIterator last,          // 结束迭代器const key_compare& comp = key_compare(),         // 比较器const allocator_type& = allocator_type());       // 分配器
// copy (3) 拷贝构造
map (const map& x);
// initializer list (5) initializer 列表构造
// 4. 初始化列表构造函数
map (// 接收初始化列表作为参数,类型为 initializer_list// 其中 value_type 通常是 pair<const Key, T>// 例如: {"key", value} 这样的初始化形式initializer_list<value_type> il,// 接收比较函数对象,用于定义键的排序规则// key_compare 默认是 less<Key>// comp 参数可选,如果不传则使用默认构造的 key_compareconst key_compare& comp = key_compare(),// 接收内存分配器,用于管理map的内存分配// allocator_type 是分配器类型// alloc 参数可选,如果不传则使用默认构造的 allocator_typeconst allocator_type& alloc = allocator_type()
);// 迭代器是一个双向迭代器
// 这表示：
// 1. 迭代器是双向的
// 2. 键是const的，不能修改
// 3. value_type是pair<const Key, T>类型
iterator -> a bidirectional iterator to const value_type// 正向迭代器// 正向迭代器声明
iterator begin();   // 返回指向第一个元素的迭代器
iterator end();     // 返回指向最后一个元素后面的迭代器// 反向迭代器声明
reverse_iterator rbegin();  // 返回指向最后一个元素的反向迭代器
reverse_iterator rend();    // 返回指向第一个元素前面的反向迭代器

---

3.5 map的增删查

map的增删查关注以下几个接口即可：

map增接口，插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>
// 单个数据插入，如果已经key存在则插入失败,key存在相等value不相等也会插入失败
pair<iterator,bool> insert (const value_type& val);
// 列表插入，已经在容器中存在的值不会插入
void insert (initializer_list<value_type> il);
// 迭代器区间插入，已经在容器中存在的值不会插入
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
// 查找k，返回k所在的迭代器，没有找到返回end()
iterator find (const key_type& k);
// 查找k，返回k的个数
size_type count (const key_type& k) const;
// 删除一个迭代器位置的值
iterator erase (const_iterator position);
// 删除k，k存在返回0，存在返回1
size_type erase (const key_type& k);
// 删除一段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);// 返回大于等k位置的迭代器
iterator lower_bound (const key_type& k);
// 返回大于k位置的迭代器
const_iterator lower_bound (const key_type& k) const;

---

3.6 map的数据修改

前面我提到map支持修改mapped_type 数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

map第一个支持修改的方式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口

需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。

Member typeskey_type -> The first template parameter (Key)mapped_type -> The second template parameter (T)value_type -> pair<const key_type,mapped_type>// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的mapped_type值iterator find (const key_type& k);
// 文档中对insert返回值的说明
// The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to theelement with an equivalent key in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed.
// insert插入一个pair<key, T>对象
// 1、如果key已经在map中，插入失败，则返回一个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false
// 2、如果key不在在map中，插入成功，则返回一个pair<iterator,bool>对象，返回pair对象first是新插入key所在结点的迭代器，second是true
// 也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器
// 那么也就意味着insert插入失败时充当了查找的功能，正是因为这一点，insert可以用来实现operator[]
// 需要注意的是这里有两个pair，不要混淆了，一个是map底层红黑树节点中存的pair<key, T>，另一个是insert返回值pair<iterator,bool>
pair<iterator,bool> insert (const value_type& val);
mapped_type& operator[] (const key_type& k);
// operator的内部实现
mapped_type& operator[] (const key_type& k)
{// 1、如果k不在map中，insert会插入k和mapped_type默认值，同时[]返回结点中存储mapped_type值的引用，那么我们可以通过引用修改返映射值。所以[]具备了插入+修改功能// 2、如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引用，所以[]具备了查找+修改的功能pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

---

3.7 构造遍历及增删查使用样例

#include<iostream>
#include<map>
using namespace std;
int main()
{// initializer_list构造及迭代遍历map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插入"},{ "string", "字符串" } };//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//cout << (*it).first <<":"<<(*it).second << endl;// map的迭代基本都使用operator->,这里省略了一个->// 第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据//cout << it.operator->()->first << ":" << it.operator->()->second << endl;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;
}

---

3.8 map的迭代器和[]功能样例：

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{// 利用find和iterator修改功能，统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// 先查找水果在不在map中// 1、不在，说明水果第一次出现，则插入{水果, 1}// 2、在，则查找到的节点中水果对应的次数++auto ret = countMap.find(str);if (ret == countMap.end()){countMap.insert({ str, 1 });}else{ret->second++;}}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{// 利用[]插入+修改功能，巧妙实现统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// []先查找水果在不在map中// 1、不在，说明水果第一次出现，则插入{水果, 0}，同时返回次数的引用，++一下就变成1次了// 2、在，则返回水果对应的次数++countMap[str]++;}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在->插入 {"insert", string()}dict["insert"];// 插入+修改dict["left"] = "左边";// 修改dict["left"] = "左边、剩余";// key存在->查找cout << dict["left"] << endl;return 0;
}

---

3.9 multimap和map的差异

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。

---

3.10 138. 随机链表的复制 - 力扣（LeetCode）

138. 随机链表的复制 - 力扣（LeetCode）

数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。这里我们直接让{原结点,拷贝结点}建立映射关系放到map中，控制随机指针会非常简单方便，这里体现了map在解决一些问题时的价值，完全是降维打击。

class Solution {
public:// 函数功能：深拷贝带随机指针的链表// 参数：原链表的头节点指针// 返回值：拷贝后的新链表的头节点指针Node* copyRandomList(Node* head) {// 创建map用于存储原节点到拷贝节点的映射关系// key: 原链表节点地址// value: 对应的拷贝节点地址map<Node*, Node*> nodeMap;// copyhead指向拷贝链表的头节点// copytail指向拷贝链表的尾节点Node* copyhead = nullptr, *copytail = nullptr;// 第一次遍历：复制节点值和next指针Node* cur = head;while(cur){// 如果是第一个节点if(copytail == nullptr){// 创建头节点copyhead = copytail = new Node(cur->val);}else{// 创建新节点并连接到尾部copytail->next = new Node(cur->val);copytail = copytail->next;}// 建立原节点和拷贝节点的映射关系nodeMap[cur] = copytail;// 继续处理下一个节点cur = cur->next;}// 第二次遍历：处理random指针cur = head;          // cur指向原链表Node* copy = copyhead;  // copy指向拷贝链表while(cur){// 如果原节点的random为空if(cur->random == nullptr){copy->random = nullptr;}else{// 通过map找到原节点random指向的节点对应的拷贝节点copy->random = nodeMap[cur->random];}// 继续处理下一个节点cur = cur->next;copy = copy->next;}return copyhead;}
};

算法思路解析：

1. 整体思路：
   • 分两次遍历完成深拷贝
   • 第一次遍历复制节点值和next指针，同时建立映射关系
   • 第二次遍历处理random指针
2. 具体步骤：
   • 第一次遍历：
     • 复制每个节点的值
     • 建立next连接
     • 将原节点和对应的拷贝节点存入map
   • 第二次遍历：
     • 根据原节点的random指向
     • 通过map找到对应的拷贝节点
     • 建立random连接
3. 时间复杂度：
   • O(N)，需要两次遍历链表
   • map的插入和查找操作是O(logN)
4. 空间复杂度：
   • O(N)，需要额外的map存储映射关系

---

3.11 692. 前K个高频单词 - 力扣（LeetCode）

692. 前K个高频单词 - 力扣（LeetCode）

本题目我们利用map统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。

解决思路1：

用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的。

解决思路1：

class Solution {
public:// 定义仿函数，用于排序规则的比较struct Compare{// 重载operator()，实现比较规则// 参数：两个pair<string,int>的常引用// 返回值：bool，表示x是否应该排在y前面bool operator()(const pair<string, int>& x, const pair<string, int>& y)const{// 按照频率降序排列（即频率高的在前）return x.second > y.second;}};// 函数功能：找出字符串数组中出现频率最高的k个字符串// 参数：字符串数组的引用，和需要返回的个数k// 返回值：包含前k个高频字符串的vectorvector<string> topKFrequent(vector<string>& words, int k) {// 统计每个字符串出现的频率// key: 字符串// value: 出现次数map<string, int> countMap;for(auto& e : words){countMap[e]++;  // 统计频率}// 将map中的数据转换为pair的vector// 便于排序vector<pair<string, int>> v(countMap.begin(), countMap.end());// 使用stable_sort保持相同频率字符串的原有顺序// Compare()定义排序规则：按照频率降序排列stable_sort(v.begin(), v.end(), Compare());// sort和stable_sort的区别：// sort不保证相等元素的相对位置// stable_sort保证相等元素的相对位置不变//sort(v.begin(), v.end(), Compare());// 取排序后的前k个字符串vector<string> strV;for(int i = 0; i < k; ++i){strV.push_back(v[i].first);  // 只需要字符串，不需要频率}return strV;}
};

算法思路解析：

1. 步骤分解：
   • 统计频率：使用map记录每个字符串出现的次数
   • 转换数据：将map转为pair的vector便于排序
   • 排序：按照频率降序排列
   • 获取结果：取前k个字符串
2. 关键点解析：
   • 使用map统计频率的优势：
     • 自动去重
     • 按照key排序
     • 高效的查找和统计
   • Compare仿函数：
     • 定义排序规则
     • 按照pair的second（频率）降序排序
     • 可以方便地修改排序规则
   • stable_sort vs sort：
     • stable_sort能保持相同频率字符串的原有顺序
     • 在处理相同频率的字符串时更稳定
3. 时间复杂度分析：
   • 统计频率：O(NlogM)，N是words长度，M是不同字符串个数
   • 排序：O(MlogM)，M是不同字符串个数
   • 总体：O(NlogM + MlogM)
4. 空间复杂度：
   • O(M)，M是不同字符串个数

---

解决思路2：

将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。

class Solution {
public:// 定义仿函数，实现自定义排序规则struct Compare{bool operator()(const pair<string, int>& x, const pair<string, int>& y)const{// 排序规则：// 1. 按频率降序排序（频率高的在前）// 2. 如果频率相同，按字典序升序排序（字母顺序小的在前）return x.second > y.second ||  // 频率降序(x.second == y.second && x.first < y.first);  // 频率相同时字典序升序}};// 函数功能：找出字符串数组中出现频率最高的k个字符串// 要求：1. 按照出现频率降序排列//      2. 频率相同时，按照字典序升序排列vector<string> topKFrequent(vector<string>& words, int k) {// 统计每个字符串出现的频率map<string, int> countMap;for(auto& e : words){countMap[e]++;}// 将map转换为pair的vector以便排序vector<pair<string, int>> v(countMap.begin(), countMap.end());// 使用自定义的Compare仿函数排序// 不需要使用stable_sort，因为已经在Compare中处理了相等情况sort(v.begin(), v.end(), Compare());// 取前k个字符串vector<string> strV;for(int i = 0; i < k; ++i){strV.push_back(v[i].first);}return strV;}
};

算法思路解析：

1. 关键改进：

   • 在Compare仿函数中增加了第二个排序条件
   • 当频率相同时，按字典序排序

2. Compare仿函数详解：

   x.second > y.second ||  // 条件1：频率降序
   (x.second == y.second && x.first < y.first)  // 条件2：频率相同时字典序升序
   

   • 条件1：优先按频率降序排序
   • 条件2：频率相同时，按字符串字典序升序排序

3. 不再需要stable_sort：

   • 因为Compare仿函数已经完整定义了相等情况的处理规则
   • 使用普通的sort即可

class Solution {
public:// 定义仿函数，为优先级队列提供比较规则struct Compare{bool operator()(const pair<string, int>& x, const pair<string, int>& y)const{// 注意：priority_queue默认是大顶堆，但比较规则是相反的// 如果要实现次数降序，反而要用小于号// 如果要实现字典序升序，反而要用大于号return x.second < y.second ||  // 频率降序(x.second == y.second && x.first > y.first);  // 频率相同时字典序升序}};vector<string> topKFrequent(vector<string>& words, int k) {// 统计词频map<string, int> countMap;for(auto& e : words){countMap[e]++;}// 创建优先级队列// 模板参数：// 1. 存储的元素类型：pair<string,int>// 2. 底层容器：vector// 3. 比较规则：Compare仿函数priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(countMap.begin(), countMap.end());// 取出前k个元素vector<string> strV;for(int i = 0; i < k; ++i){strV.push_back(p.top().first);  // 只需要单词，不需要频率p.pop();}return strV;}
};

算法思路解析：

1. 关键点：优先级队列的特性
   • priority_queue默认是大顶堆
   • 但其比较规则与直觉相反：
     • 如果a < b返回true，则a排在b后面
     • 如果a < b返回false，则a排在b前面
2. Compare仿函数详解：

x.second < y.second ||  // 频率比较
(x.second == y.second && x.first > y.first)  // 字典序比较

• 频率比较用<号：实际效果是频率高的在队列顶部
• 字典序比较用>号：实际效果是字典序小的在顶部

1. 处理流程：
   • 统计词频：使用map记录每个单词出现次数
   • 构建优先级队列：
     • 直接用map的迭代器范围构造
     • 自动按照Compare规则排序
   • 获取结果：
     • 连续k次取出队列顶部元素
     • 每次取出后删除顶部元素
       则是相反的
       // 如果要实现次数降序，反而要用小于号
       // 如果要实现字典序升序，反而要用大于号
       return x.second < y.second || // 频率降序
       (x.second == y.second && x.first > y.first); // 频率相同时字典序升序
       }
       };