STL 容器 set、multiset、map、multimap 及 pair 的核心特性与常用操作。涵盖容器构造、元素增删查改、迭代器使用及底层原理。通过 insert、erase、find 等函数展示用法，结合 LeetCode 题目（数组交集、环形链表、随机链表复制、前 K 个高频单词）实战演练，掌握关联式容器应用场景与性能优化。
前面我们已经接触过 STL 中的部分容器，如：
vector、list、等，这些容器统称为
deque序列容器的核心特征是：
连续（如：vector）或 离散（如：list），但元素间仅通过线性顺序关联vector[i]）或迭代器顺序访问，不依赖元素值的大小或关系关联容器的核心特征是：
树（如：红黑树）或 哈希表 实现，元素间通过键值的有序性或哈希映射建立关联map 容器通过键值对 (key, value) 存储数据，查找时直接通过 key 定位，时间复杂度为 O(logn)（红黑树实现）或平均 O(1)（哈希表实现）两类容器的核心差异总结：
| 维度 | 序列式容器 | 关联式容器 |
|---|---|---|
| 逻辑结构 | 线性序列（数组、链表等） | 非线性结构（树、哈希表等） |
| 元素关联 | 仅通过 位置的顺序 关联 | 通过 键值的有序 或 哈希的映射 关联 |
| 访问依据 | 存储位置（索引或迭代器） | 关键字（Key） |
| 典型实现 | vector、list、deque | set、mapunordered_set、unordered_map |
cplusplus 网站上关于 C++ 的
set 容器的介绍：set - C++ Reference
template<class T,// set::key_type/value_type
class Compare = less<T>,// set::key_compare/value_compare
class Alloc = allocator<T>// set::allocator_type>
class set;
关于 C++ STL 中
set容器的模板参数说明：
- 元素类型（
T）：set 底层存储的关键字类型，需保证该类型支持比较操作（默认需支持<运算符）- 比较器（
Compare，默认less<T>）：用于定义元素间的排序规则。- 内存分配器（
Allocator，默认allocator<T>）：负责管理 set 的内存分配与释放。
如需优化内存使用（如：高频插入/删除场景），可自定义分配器（如：内存池）
set<T, less<T>, MyAllocator<T>> mySet;// 使用自定义分配器
若 T 不支持默认比较（如：自定义类），或 需自定义排序逻辑，可通过仿函数重载比较规则
struct MyComparator {
bool operator()(const T& a, const T& b) const {
return a.custom_key < b.custom_key; // 自定义比较逻辑
}
};
set<T, MyComparator> mySet; // 使用自定义比较器
*C++ 标准模板库（STL）中的
set 容器相关知识，主要可以分为以下一个部分：*成员函数：提供了set 容器的 各类操作接口，涵盖元素插入、删除、查找、迭代、容量管理等功能。
// constructing sets
#include<iostream>
#include<set>
// 1. 定义一个普通函数作为比较函数，用于比较两个整数的大小
bool fncomp(int lhs, int rhs) {
return lhs < rhs;
}
// 2. 定义一个函数对象（仿函数）类，用于比较两个整数的大小
struct classcomp {
bool operator()(const int& lhs, const int& rhs) const {
return lhs < rhs;
}
};
int main() {
/*------------------使用不同的构造函数创建 set 容器------------------*/
// 1. 使用'默认构造函数'创建一个空的 set，元素类型为 int
std::set<int> s1;
// 2. 使用'迭代器范围构造函数'创建包含 5 个元素的 set，初始化元素来自数组 myints
int myints[] = {10, 20, 30, 40, 50};
std::set<int> s2(myints, myints + 5);
// 3. 使用'拷贝构造函数'创建 set 容器 third，third 是 second 的一个副本
std::set<int> s3(s2);
// 4. 使用'迭代器构造函数'创建 set，通过迭代器范围 [second.begin(), second.end()) 初始化
std::set<int> s4(s2.begin(), s2.end());
// 注意：这实际上和拷贝构造效果相同
/*------------------使用不同的方式作为 set 容器的比较器------------------*/
// 5. 使用'自定义的函数对象'作为比较器
std::set<int, classcomp> s5;
// 注意：classcomp 是一个定义了函数调用运算符的结构体
// 6. 使用'函数指针'作为比较器
// 6.1：首先定义一个函数指针指向 fncomp 函数
bool (*fn_pt)(int, int) = fncomp;
// 6.2：然后在模板参数中指定比较器类型，并在构造函数中传入函数指针
std::set<int, bool(*)(int, int)> s6(fn_pt);
return 0;
}
// set::size
#include<iostream>
#include<set>
int main() {
std::set<int> myints;
std::cout << "初始状态下的 set 大小的 size 为：" << myints.size() << '\n';
for (int i = 0; i < 10; ++i) myints.insert(i);
std::cout << "插入 10 个元素后 set 大小的 size 为：" << myints.size() << '\n';
myints.insert(100);
std::cout << "插入元素 100 后 set 大小的 size 为：" << myints.size() << '\n';
myints.erase(5);
std::cout << "删除 5 个元素后 set 大小的 size 为：" << myints.size() << '\n';
return 0;
}
// set::empty
#include<iostream>
#include<set>
int main() {
std::set<int> myset;
myset.insert(20);
myset.insert(30);
myset.insert(10);
std::cout << "myset 容器中的内容为:";
while (!myset.empty()) {
std::cout << ' ' << *myset.begin();
myset.erase(myset.begin());
}
std::cout << '\n';
return 0;
}
// set::clear
#include<iostream>
#include<set>
int main() {
std::set<int> myset;
myset.insert(100);
myset.insert(200);
myset.insert(300);
std::cout << "初始状态下 myset 容器中的内容为:";
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
myset.clear();
myset.insert(1101);
myset.insert(2202);
std::cout << "进行清空和插入操作后 myset 容器中的内容为:";
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
return 0;
}
// swap sets
#include<iostream>
#include<set>
int main() {
int myints[] = {12, 75, 10, 32, 20, 25};
std::set<int> first(myints, myints + 3); // 10,12,75
std::set<int> second(myints + 3, myints + 6); // 20,25,32
first.swap(second);
std::cout << "交换后 first 容器中的内容为:";
for (std::set<int>::iterator it = first.begin(); it != first.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
std::cout << "交换后 second 容器中的内容为:";
for (std::set<int>::iterator it = second.begin(); it != second.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
return 0;
}
// set::insert (C++98)
#include<iostream>
#include<set>
int main() {
// 1. 创建一个存储 int 类型的 set 容器
std::set<int> myset;
// 2. 定义一个迭代器，用于指向 set 中的元素
std::set<int>::iterator it;
// 3. 定义一个 pair 对象，用于接收 insert 函数的返回值
std::pair<std::set<int>::iterator, bool> ret;
/* 注意事项：
* 1. 第一个元素是迭代器，指向插入的元素或已存在的元素
* 2. 第二个元素是 bool 值，表示插入是否成功
*/
/*--------------------插入形式一：单个元素的插入--------------------*/
for (int i = 1; i <= 5; ++i) {
myset.insert(i * 10);
}
// 1. 尝试插入已存在的元素 20（元素已存在）
ret = myset.insert(20);
/* 注意事项：
* 1. 返回的 pair 中 bool 值为 false，表示插入失败
* 2. 迭代器指向已存在的元素 20
*/
// 2. 如果插入失败，将迭代器 it 指向已存在的元素 20
if (ret.second == false) it = ret.first;
std::cout << "myset 容器中的内容为:";
for (it = myset.begin(); it != myset.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
/*--------------------插入形式二：带提示位置的插入--------------------*/
myset.insert(it, 25); // 注意：提示位置为 it（指向元素 20），实际插入位置由 set 的有序性决定
myset.insert(it, 24); // 元素 24 会被插入到 20 之后（按升序排列）
myset.insert(it, 26);
/* 注意事项：
* 1. 提示位置对插入位置没有帮助（26 应在 25 之后）
* 2. 提示位置仅作为优化建议，不影响最终插入位置
*/
std::cout << "myset 容器中的内容为:";
for (it = myset.begin(); it != myset.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
/*--------------------插入形式三：范围插入--------------------*/
int myints[] = {5, 10, 15};
myset.insert(myints, myints + 3); // 注意：会插入 5, 10, 15 三个元素，但 10 已存在，不会重复插入
std::cout << "myset 容器中的内容为:";
for (it = myset.begin(); it != myset.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
return 0;
}
// erasing from set
#include<iostream>
#include<set>
int main() {
// 1. 创建一个存储 int 类型的 set 容器
std::set<int> myset;
// 2. 定义一个迭代器，用于指向 set 中的元素
std::set<int>::iterator it;
// 3. 插入元素
for (int i = 1; i < 10; i++) {
myset.insert(i * 10);
}
// 4. 让迭代器 it 指向 myset 容器的第二个元素 20
it = myset.begin(); ++it;
/*--------------------删除形式一：迭代器位置删除--------------------*/
myset.erase(it);
/* 注意事项：
* 1. 删除 it 指向的元素 (20)
* 2. erase 返回的迭代器指向被删除元素的下一个元素
*/
/*--------------------删除形式二：按值删除--------------------*/
myset.erase(40);
/* 注意事项：
* 1. 删除键为 40 的元素
* 2. 返回值表示删除的元素数量 (set 中为 0 或 1)
*/
/*--------------------删除形式三：迭代器范围删除--------------------*/
it = myset.find(60);
myset.erase(it, myset.end());
/* 注意事项：
* 1. 查找值为 60 的元素，将迭代器 it 指向该元素
* 2. 删除从 it(指向 60) 到 set 末尾的所有元素
* 3. 返回值表示删除的元素数量 (set 中为 0 或 1)
*/
std::cout << "myset 容器中的内容为:";
for (it = myset.begin(); it != myset.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
return 0;
}
// set::key_comp
#include<iostream>
#include<set>
int main() {
// 1. 创建一个存储 int 类型的 set 容器
std::set<int> myset;
// 2. 获取 set 的键比较函数对象
std::set<int>::key_compare mycomp = myset.key_comp();
// 注意：key_compare 默认是 std::less<int>，用于定义元素的排序规则
// 3. 插入元素
for (int i = 0; i <= 5; i++) {
myset.insert(i);
// 注意：set 会自动根据比较函数对元素进行排序
}
std::cout << "myset 容器的内容为:";
// 4. 获取 set 中的最后一个元素 (最大值)
int highest;
highest = *myset.rbegin();
// 注意：rbegin() 返回指向逆序第一个元素的迭代器 (即正序的最后一个元素)
// 5. 获取指向 set 第一个元素的迭代器
std::set<int>::iterator it = myset.begin();
// 6. 使用比较函数遍历 set 中的元素，直到遇到最后一个元素
do {
std::cout << ' ' << *it;
} while (mycomp(*(++it), highest));
// 注意：mycomp(*(++it), highest) 等价于 ++it < highest
std::cout << '\n';
return 0;
}
// set::value_comp
#include<iostream>
#include<set>
int main() {
// 1. std::set<int> myset;
// 2. std::set<int>::value_compare mycomp = myset.value_comp();
// 3.
for (int i = 0; i <= 5; i++) {
myset.insert(i);
}
std::cout << "myset 容器中内容为:";
// 4. int highest = *myset.rbegin();
// 5. std::set<int>::iterator it = myset.begin();
// 6.
do {
std::cout << ' ' << *it;
} while (mycomp(*(++it), highest));
std::cout << '\n';
return 0;
}
// set::find
#include<iostream>
#include<set>
int main() {
// 1. std::set<int> myset;
std::set<int>::iterator it;
// 2.
for (int i = 1; i <= 5; i++) {
myset.insert(i * 10);
}
it = myset.find(20);
myset.erase(it);
myset.erase(myset.find(40));
std::cout << "myset 容器中的内容为:";
for (it = myset.begin(); it != myset.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
return 0;
}
// set::count
#include<iostream>
#include<set>
int main() {
// 1. 创建 std::set<int> myset;
std::set<int> myset;
// 2. 赋值
for (int i = 1; i < 5; ++i) {
myset.insert(i * 3); // set: 3, 6, 9, 12
}
// 3. 判断
for (int i = 0; i < 10; ++i) {
std::cout << i;
if (myset.count(i) != 0) std::cout << "在 myset 容器中\n";
else std::cout << "不在 myset 容器中\n";
}
return 0;
}
// set::lower_bound/upper_bound
#include<iostream>
#include<set>
int main() {
std::set<int> myset;
std::set<int>::iterator itlow, itup;
for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
itlow = myset.lower_bound(30); // ^
itup = myset.upper_bound(60); // ^
myset.erase(itlow, itup); // 10 20 70 80 90
std::cout << "myset 容器的内容为:";
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it) {
std::cout << ' ' << *it;
}
std::cout << '\n';
return 0;
}
// set::equal_range
#include<iostream>
#include<set>
int main() {
// 1. 创建一个整数类型的 set 容器
std::set<int> myset;
// 2. 插入元素：
for (int i = 1; i <= 5; i++) myset.insert(i * 10); // myset: 10 20 30 40 50
// 3. 使用 equal_range 查找值为 30 的元素范围
std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;
ret = myset.equal_range(30);
/* 注意事项：
* equal_range 返回一个 pair，包含两个迭代器：
* 1. first：指向第一个不小于 30 的元素（即：30 本身）
* 2. second：指向第一个大于 30 的元素（即：40）
*/
// 4. 输出结果
std::cout << "lower_bound（ret.first）指向：" << *ret.first << '\n';
std::cout << "upper_bound（ret.second）指向：" << *ret.second << '\n';
return 0;
}
代码示例 1：插入 + 迭代器遍历 + 批量插入 + set 容器存储字符串类型的变量
#include<iostream>
#include<set>
using namespace std;
int main() {
// 1. 基础特性：去重 + 排序（默认升序，底层用红黑树实现）
set<int> s;
/* 注意事项：
* 语法：如果需要降序排序，可显式指定比较函数：set<int, greater<int>> s;
* 原理：greater<int> 是 STL 提供的'大于'比较仿函数，让元素按降序排列
*/
// 2. 插入元素：重复元素会被自动过滤
s.insert(5); // 插入 5 → 集合：{5}
s.insert(2); // 插入 2 → 集合：{2,5}（自动升序）
s.insert(7); // 插入 7 → 集合：{2,5,7}
s.insert(5); // 插入重复的 5 → 无变化，集合仍为 {2,5,7}
// 3. 迭代器遍历：set 的迭代器是'常量迭代器'，不允许修改元素（否则破坏有序性）
auto it = s.begin();
/* 注意事项：auto it = s.begin();
* 早期写法：set<int>::iterator it = s.begin();
* C++11 后推荐用 auto 自动推导类型，更简洁
*/
while (it != s.end()) {
// *it = 1; // 编译报错：'it': 不能给常量赋值
/* 注意事项：*it = 1
* set 的元素是'逻辑常量'，不能通过迭代器修改
* 原因：如果允许修改，会破坏 set 内部的有序性（红黑树结构会混乱）
*/
cout << *it << " "; // 正确用法：只读访问元素
++it;
}
cout << endl;
// 4. 批量插入：用 initializer_list 插入多个元素（重复值会被过滤）
// 插入 {2,8,3,9} → 实际生效的是 8、3、9（2 已存在）
// 插入后集合：{2,3,5,7,8,9}（自动升序排序）
s.insert({2, 8, 3, 9});
for (auto e : s) {
cout << e << " ";
}
cout << endl;
// 6. 字符串 set 的特性：按字典序（ASCII 码）排序
set<string> strset = {"sort", "insert", "add"};
for (auto& e : strset) {
cout << e << " ";
}
cout << endl;
// 解释：
// - 字符串比较默认按字典序（本质是逐个字符的 ASCII 码比较）
// - 示例中 "add"（a 开头）< "insert"（i 开头）< "sort"（s 开头）
return 0;
}
代码示例 2：迭代器的遍历 + 删除的'迭代器位置删除、按值删除' + 先查找再删除 + 两种查找算法的对比 + 使用 count 间接判断元素是否存储在
#include<iostream>
#include<set>
using namespace std;
int main() {
// 1. 初始化 set：自动去重 + 升序排序
set<int> s = {4, 2, 7, 2, 8, 5, 9};
// 注意：原数组 {4,2,7,2,8,5,9} → 去重后按升序排列为 {2,4,5,7,8,9}
// 2. 遍历输出初始 set
for (auto& e : s) {
cout << e << " ";
}
cout << endl;
// 3. 迭代器位置删除：删除最小值（set 升序排列，最小值是 begin() 指向的元素）
s.erase(s.begin()); // 删除第一个元素（即最小值 2）
for (auto e : s) {
cout << e << " "; // 输出：4 5 7 8 9
}
cout << endl;
// 4. 按值删除：直接按值删除：通过 erase(x) 删除，返回删除个数（0 或 1）
int x;
cin >> x;
int num = s.erase(x);
if (num == 0) {
cout << x << " 不存在！" << endl;
} else {
cout << x << " 存在！" << endl;
}
for (auto e : s) {
cout << e << " ";
}
cout << endl;
// 5. 先查找再删除：通过 find 定位元素，再 erase 迭代器
cin >> x;
auto pos = s.find(x);
if (pos != s.end()) {
s.erase(pos);
} else {
cout << x << " 不存在！" << endl;
}
for (auto e : s) {
cout << e << " ";
}
cout << endl;
// 6. 对比两种查找方式的效率差异
// 6.1 算法库的 find：线性遍历（时间复杂度 O(N)）
auto pos1 = find(s.begin(), s.end(), x);
// 6.2 set 自身的 find：红黑树查找（时间复杂度 O(logN)）
auto pos2 = s.find(x);
// 7. 利用 count 间接判断元素是否存在
cin >> x;
if (s.count(x)) // count 返回 0 或 1（set 元素唯一）
{
cout << x << " 在！" << endl;
} else {
cout << x << " 不存在！" << endl;
}
return 0;
}
代码案例 3：插入 + 迭代器遍历 + lower_bound/upper_bound 的使用 + erase 的迭代器范围删除
#include<iostream>
#include<set>
using namespace std;
int main() {
// 1. 创建一个空的 set 容器
std::set<int> myset;
// 2. 插入元素
for (int i = 1; i < 10; i++) {
myset.insert(i * 10); // 插入后 myset: {10,20,30,40,50,60,70,80,90}
}
// 3. 遍历输出初始 set 的内容
cout << "初始状态下的 myset 容器中的内容为：" << endl;
for (auto& e : myset) {
cout << e << " "; // 输出：10 20 30 40 50 60 70 80 90
}
cout << endl;
// 4. 利用 lower_bound 和 upper_bound 定位区间 ---> 找到包含 [30, 60] 的区间（注意是左闭右开）
// 4.1 lower_bound(30)：找到第一个 >= 30 的元素
auto itlow = myset.lower_bound(30); // 返回指向 30 的迭代器
// 4.2 upper_bound(60)：找到第一个 > 60 的元素
auto itup = myset.upper_bound(60); // 返回指向 70 的迭代器（因为 60 是最后一个 <=60 的元素）
// 5. 删除区间 [itlow, itup) 的元素
myset.erase(itlow, itup); /// 即删除 30,40,50,60（因为 itup 指向 70，不包含 70）
// 6. 遍历输出删除后的 set 内容
cout << "进行迭代器范围删除之后 myset 容器中的内容为：" << endl;
for (auto e : myset) {
cout << e << " "; // 输出：10 20 70 80 90
}
cout << endl;
return 0;
}
cplusplus 网站上关于 C++ 的
multiset 容器的介绍：multiset - C++ Reference
C++ 标准模板库（STL）中的
multiset 容器的接口函数，主要可以分为以下一个部分：
template<class T,// multiset::key_type/value_type
class Compare = less<T>,// multiset::key_compare/value_compare
class Alloc = allocator<T>>// multiset::allocator_type>
class multiset;
可以发现，它与
set容器的模板声明形式完全一致都通过T（元素类型）、Compare（比较规则）、Alloc（内存分配器） 这三个模板参数定义容器。但需要注意：
set和multiset虽模板声明形式相同，核心特性却有本质区别
set会自动去重，容器中元素唯一multiset允许元素重复，侧重按序存储重复数据
代码示例：multiset 容器和 set 容器的区别
#include<iostream>
#include<set>
using namespace std;
int main() {
// 1. multiset 核心特性：自动排序，但允许重复元素
// 对比 set：set 会自动去重，而 multiset 保留所有重复值
multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
// 2. 遍历 multiset：输出排序后的所有元素（升序）
// 排序规则：默认用 less<int>，即小→大排列
// 插入的原始数据 {4,2,7,2,4,8,4,5,4,9} → 排序后：2,2,4,4,4,4,5,7,8,9
cout << "初始状态的 multiset 容器中的内容为：" << endl;
auto it = s.begin();
while (it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
// 3. find 特性：仅返回第一个匹配的元素迭代器
// 对比 set：set 中元素唯一，find 直接定位唯一值；但 multiset 可能有多个重复值
// 需求：输入一个值 x，找到第一个 x，然后遍历后续所有 x（因可能有重复）
cout << "请输入你想查找的节点的键" << endl;
int x;
cin >> x;
auto pos = s.find(x); // 找到第一个 x 的位置（若存在）
cout << "multiset 容器中所有键为" << x << "的节点为：" << endl;
while (pos != s.end() && *pos == x) {
cout << *pos << " "; // 输出所有连续的 x（如输入 4 则输出：4 4 4 4）
++pos;
}
cout << endl;
// 4. count 特性：返回元素的实际重复次数
// 对比 set：set 中 count 只能返回 0 或 1（元素唯一）；multiset 返回真实数量
cout << "multiset 容器中键为" << x << "的节点的数量为：" << endl;
cout << s.count(x) << endl; // 输出 x 的重复次数（如输入 4 则输出：4）
// 5. erase 特性：按值删除时，删除所有匹配的元素
// 对比 set：set 中按值删除最多删 1 个；multiset 会删除全部重复值
cout << "请输入你想删除的节点的键" << endl;
cin >> x;
cout << "删除所有键为" << x << "的节点之后 multiset 容器中的内容为：" << endl;
s.erase(x); // 删除所有 x（如输入 4，则所有 4 都会被删除）
for (auto it : s) {
cout << it << " "; // 输出删除后剩余元素（如删除 4 后：2 2 5 7 8 9）
}
cout << endl;
return 0;
}
cplusplus 网站上关于 C++ 的
pair 类模板的介绍：pair - C++ Reference
pair：用于将两个不同类型（或相同类型）的数据组合成一个逻辑单元。它是 C++ 标准库（<utility>头文件）中的一个模板类其核心设计思想是 '存储一对相关联的值'，语法形式如下：
std::pair<Type1, Type2> pairName(value1, value2);
1. 元素访问方式通过
first和second成员变量直接访问：2. 默认构造与赋值****无参构造：
std::pair<int, double> p;（first和second为默认值，如：0和0.0）拷贝构造：std::pair p2 = p1;赋值操作：p2 = p1;3. 比较操作支持按字典序比较（先比
first，若相等再比second）：
代码示例：map 容器中的 pair 的使用
/*-------------任务 1：定义 map 中 value_type 的类型别名-------------*/
// 说明：在 map 中，键值对的类型是 pair<const Key, T>，这里用 typedef 简化名称
typedef pair<const Key, T> value_type;
/*-------------任务 2：定义 pair 模板结构体-------------*/
// 作用：将两个任意类型（T1、T2）的值组合成一个单元
template<class T1, class T2>
struct pair {
// 1. 类型别名：为 T1 和 T2 定义更语义化的名称
// first_type 表示第一个元素的类型
typedef T1 first_type;
// second_type 表示第二个元素的类型
typedef T2 second_type;
// 2. 成员变量：存储两个元素
// first 存储第一个值（类型 T1）
T1 _first;
// second 存储第二个值（类型 T2）
T2 _second;
// 3. 默认构造函数：值初始化
// 说明：
// - T1() 和 T2() 是值初始化（如 int 初始化为 0，string 初始化为空）
// - 作用：创建 pair 时，若未显式赋值，成员会被默认初始化
pair() : _first(T1()), _second(T2()) {}
// 4. 带参构造函数：用传入的值初始化成员
// 说明：
// - a 和 b 是 const 引用，避免拷贝开销
// - 直接用 a 和 b 初始化 first 和 second
pair(const T1& a, const T2& b) : _first(a), _second(b) {}
// 5. 模板拷贝构造函数：支持不同类型的 pair 拷贝
// 说明：
// - U 和 V 是任意类型，只要能转换为 T1 和 T2
// - pr 是其他 pair<U, V> 的引用
// - 作用：允许从其他类型的 pair 构造当前 pair（如从 pair<int, int> 构造 pair<long, double>）
template<class U, class V>
pair(const pair<U, V>& pr) : _first(pr.first), _second(pr.second) {}
};
/*-------------任务 3：使用辅助函数：make_pair-------------*/
// 说明：
// - 自动推导模板参数 T1 和 T2，简化 pair 的创建
// - 示例：auto p = make_pair(1, "hello"); 等价于 auto p = pair<int, string>(1, "hello")
template<class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y) {
return (pair<T1, T2>(x, y));
}
cplusplus 网站上关于 C++ 的
map 容器的介绍：map - C++ Reference
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;
关于 C++ STL 中
map容器的模板参数说明：
- 键类型（
Key）：map 中用于索引和排序的关键字类型，它决定了 map 容器的查找依据。需保证该类型支持比较操作（默认需支持<运算符 ），map会根据键的大小关系，自动维护键值对的有序性（默认按键升序排列 ）- 映射值类型（
T）：map 中与键关联的具体数据类型，也就是常说的'映射值'类型。键（Key）用于查找，而T用于存储与键对应的实际业务数据，二者共同构成pair<const Key, T>类型的键值对，存于map容器中- 比较器（
Compare，默认less<Key>）：用于定义键之间的排序规则。- 内存分配器（
Alloc，默认allocator<pair<const Key, T>>）：负责管理 map 底层存储的键值对（pair<const Key, T>类型）的内存分配与释放。简单来说：map 通过这四个模板参数，灵活控制了
键的类型、映射值的类型、键的排序规则以及内存管理方式，让开发者可根据实际需求定制 map 的行为，适配不同的业务场景。
如需优化内存使用（如：高频插入、删除键值对的场景，或对内存分配有特殊定制需求 ），可自定义分配器（如：实现内存池等 ）
map<Key, T, less<Key>, MyAllocator<pair<const Key, T>>> myMap; // 使用自定义分配器
若 Key 不支持默认比较（如：自定义类作为键，未重载 < 运算符 ），或需自定义键的排序逻辑（如：按键降序、按键的某一成员排序等 ），可通过仿函数重载比较规则
struct MyKeyComparator {
bool operator()(const Key& a, const Key& b) const {
return a.custom_member < b.custom_member; // 自定义键比较逻辑，假设 Key 有 custom_member 成员
}
};
map<Key, T, MyKeyComparator> myMap; // 使用自定义键比较器
C++ 标准模板库（STL） 中的
map 容器的接口函数，主要可以分为以下一个部分：
// constructing maps
#include<iostream>
#include<map>
/*-----------------函数比较器：比较两个字符的大小-----------------*/
bool fncomp(char lhs, char rhs) {
return lhs < rhs;
}
/*-----------------函数对象比较器：重载 () 运算符实现字符比较-----------------*/
struct classcomp {
bool operator()(const char& lhs, const char& rhs) const {
return lhs < rhs;
}
};
int main() {
/*--------------------使用不同的构造函数创建 map 容器--------------------*/
// 1. 默认构造函数：创建一个空的 map
std::map<char, int> m1; // 键类型为 char，值类型为 int，使用默认的比较器 std::less<char>
m1['a'] = 10; m1['b'] = 30; m1['c'] = 50; m1['d'] = 70;
/* 注意事项：
* 1. 插入元素：使用下标操作符 []
* 2. 如果键不存在，会自动创建并初始化为默认值，然后赋值
*/
// 2. 范围构造函数：使用迭代器范围 [first.begin(), first.end()) 初始化
std::map<char, int> m2(m1.begin(), m1.end());
/* 注意事项：
* 1. 复制 m1 中的所有元素到 m2
* 2. 注意：map 的迭代器遍历是按键的升序排列的
*/
// 3. 拷贝构造函数：创建 m2 的副本
std::map<char, int> m3(m2); // m3 和 m2 的内容完全相同，使用相同的比较器
/*--------------------使用不同的比较器作为 map 容器的比较器--------------------*/
// 4. 使用自定义类作为比较器
std::map<char, int, classcomp> m4; // 注意：m4 的类型是 map<char, int, classcomp>，与前三个不同
// 5. 使用函数指针作为比较器
// 5.1：定义一个函数指针并指向 fncomp 函数
bool (*fn_pt)(char, char) = fncomp;
// 5.2：创建 map 时传入函数指针作为比较器
std::map<char, int, bool(*)(char, char)> m5(fn_pt); // 注意：m5 的比较器类型是 bool(*)(char, char)，函数指针类型
return 0;
}
// map::size
#include<iostream>
#include<map>
int main() {
// 1. std::map<char, int> mymap;
// 2. mymap['a'] = 101; mymap['b'] = 202; mymap['c'] = 302;
// 3. std::cout << "mymap 的大小为：" << mymap.size() << '\n';
return 0;
}
// map::empty
#include<iostream>
#include<map>
int main() {
// 1. std::map<char, int> mymap;
// 2. mymap['a'] = 10; mymap['b'] = 20; mymap['c'] = 30;
// 3.
while (!mymap.empty()) {
std::cout << mymap.begin()->first << " => " << mymap.begin()->second << '\n';
mymap.erase(mymap.begin());
}
return 0;
}
map提供了两种修改值的方式：
- 通过迭代器：无论是
遍历过程中还是通过find 获取到键的迭代器后，都可以修改对应的值- 通过 operator[]：这是一个多功能接口，不仅支持
修改已存在的键值对，还能用于插入新数据或查找数据（当键不存在时会自动插入默认值）
// accessing mapped values
#include<iostream>
#include<map>
#include<string>
int main() {
/*-----------------第一步：创建 map 容器-----------------*/
std::map<char, std::string> mymap; // 键为 char 类型，值为 string 类型
/*-----------------第二步：赋值 map 容器-----------------*/
// 1. 使用下标操作符 [] 插入元素
mymap['a'] = "an element"; // 注意：如果键'a'不存在，会自动创建并初始化为空字符串，然后赋值为"an element"
mymap['b'] = "another element"; // 同理，插入键'b'，值为"another element"
// 2. 使用已存在的键'b'的值来初始化键'c'
mymap['c'] = mymap['b']; // 注意：这里是值的拷贝，而非引用
/*-----------------第三步：访问 map 容器-----------------*/
// 1. 使用下标操作符 [] 访问 map 容器中存在的键
std::cout << "mymap['a'] is " << mymap['a'] << '\n'; // 输出：an element
std::cout << "mymap['b'] is " << mymap['b'] << '\n'; // 输出：another element
std::cout << "mymap['c'] is " << mymap['c'] << '\n'; // 输出：another element
// 2. 使用下标操作符 [] 访问 map 容器中不存在的键
std::cout << "mymap['d'] is " << mymap['d'] << '\n'; // 输出空字符串，但已插入键'd'
/* 注意事项：
* 1. 下标操作符 [] 会在键不存在时自动插入一个默认值（空字符串）
* 2. 这可能导致意外的插入操作
*/
// 3. 使用 size() 接口判断 map 容器的中键的数量
std::cout << "mymap now contains " << mymap.size() << " elements.\n"; // 此时 map 的大小为 4，因为插入了'a', 'b', 'c', 'd'四个键
return 0;
}
代码案例：operator 接口函数的使用
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
// 1. 定义一个 map 容器
map<string, string> dict;
// 2. 使用 make_pair 函数创建一个 pair 对象
dict.insert(make_pair("sort", "排序"));
/*--------------------展示 operator[] 接口函数的三种功能--------------------*/
/*------------插入功能------------*/
dict["insert"];
/* 注意事项：当使用 [] 访问 map 中不存在的键 "insert" 时
* 1. 会自动插入一个键为 "insert"
* 2. 值为 string 默认构造（空字符串）的键值对
*/
/*------------插入 + 修改 功能------------*/
dict["left"] = "左边";
/* 注意事项：使用 [] 访问键 "left"
* 1. 由于该键不存在，会先插入键 "left"，值为 string 默认构造（空字符串）
* 2. 值为 string 默认构造（空字符串）然后将值修改为 "左边"
*/
/*------------修改功能------------*/
dict["left"] = "左边、剩余";
/* 注意事项：直接使用 [] 访问已存在的键
* 1. "left"，将其对应的值修改为 "左边、剩余"
*/
/*------------查找功能------------*/
cout << dict["left"] << endl;
/* 注意事项：key 存在 -> 查找
* 1. 使用 [] 访问已存在的键 "left"，输出其对应的值
*/
return 0;
}
// map::clear
#include<iostream>
#include<map>
int main() {
// 1. std::map<char, int> mymap;
// 2. mymap['x'] = 100; mymap['y'] = 200; mymap['z'] = 300;
// 3. std::cout << "初始状态下 mymap 容器中的内容为:\n";
// for(std::map<char,int>::iterator it = mymap.begin(); it != mymap.end();++it){
// std::cout << it->first << " => " << it->second << '\n';
// }
// 4. mymap.clear(); mymap['a']=1101; mymap['b']=2202;
// 5. std::cout << "清空又插入节点之后 mymap 容器中的内容为:\n";
// for(std::map<char,int>::iterator it = mymap.begin(); it != mymap.end();++it){
// std::cout << it->first << " => " << it->second << '\n';
// }
return 0;
}
// swap maps
#include<iostream>
#include<map>
int main() {
// 1. 创建两个 map 容器
std::map<char, int> foo, bar;
// 2. 为第一个容器 foo 进行赋值
foo['x'] = 100; foo['y'] = 200;
// 3. 为第二个容器 bar 进行赋值
bar['a'] = 11; bar['b'] = 22; bar['c'] = 33;
// 4. 交换两个 map 容器的内容
foo.swap(bar);
// 5. 输出 foo 容器中内容
std::cout << "foo 容器中的内容为:\n";
for (std::map<char, int>::iterator it = foo.begin(); it != foo.end(); ++it) {
std::cout << it->first << " => " << it->second << '\n';
}
// 6. 输出 bar 容器中的内容
std::cout << "bar 容器中的内容为:\n";
for (std::map<char, int>::iterator it = bar.begin(); it != bar.end(); ++it) {
std::cout << it->first << " => " << it->second << '\n';
}
return 0;
}
// map::insert (C++98)
#include<iostream>
#include<map>
int main() {
/*------------------第一步：创建 map 容器------------------*/
std::map<char, int> mymap;
/*------------------第二步：插入 map 容器------------------*/
// 1. 单个元素插入：使用 insert(const value_type&)
mymap.insert(std::pair<char, int>('a', 100));
mymap.insert(std::pair<char, int>('z', 200));
/* 注意事项：
* 1. 插入键值对 ('a', 100) 和 ('z', 200)
* 2. 返回值被忽略，若键已存在则插入失败（但此处键不存在，插入成功）
*/
// 检查插入状态：使用 insert 返回的 pair<iterator, bool>
std::pair<std::map<char, int>::iterator, bool> ret;
ret = mymap.insert(std::pair<char, int>('z', 500));
if (ret.second == false) {
std::cout << "元素'z'已经存在\n";
std::cout << "其值为：" << ret.first->second << '\n';
}
/* 注意事项：
* 1. ret.first：指向插入位置（或已存在元素）的迭代器
* 2. ret.second：插入成功（true）或失败（false，键已存在）
*/
// 2. 带提示位置的插入：使用 insert(position, value)
std::map<char, int>::iterator it = mymap.begin();
mymap.insert(it, std::pair<char, int>('b', 300)); // 提示位置正确，最高效
mymap.insert(it, std::pair<char, int>('c', 400)); // 提示位置错误，无优化
/* 注意事项：
* 1. it 指向 mymap.begin()（即 'a'），作为提示位置
* 2. 插入 'b'：提示位置正确（'b' 应插入在 'a' 后），效率最高
* 3. 插入 'c'：提示位置错误（'c' 应插入在 'b' 后），效率未优化
*/
// 3. 范围插入：使用 insert(first, last)
std::map<char, int> anothermap;
anothermap.insert(mymap.begin(), mymap.find('c'));
/* 注意事项：
* 1. 从 mymap 中复制 [begin(), find('c')) 区间的元素到 anothermap
* 2. 即复制 'a' 和 'b'（左闭右开区间，不包含 'c'）
*/
/*------------------第二步：输出 map 容器------------------*/
std::cout << "mymap 容器中的内容为:\n";
for (it = mymap.begin(); it != mymap.end(); ++it) {
std::cout << it->first << " => " << it->second << '\n';
}
std::cout << "anothermap 容器中内容为:\n";
for (it = anothermap.begin(); it != anothermap.end(); ++it) {
std::cout << it->first << " => " << it->second << '\n';
}
return 0;
}
// erasing from map
#include<iostream>
#include<map>
int main() {
/*------------------第一步：准备 map 容器基本数据------------------*/
std::map<char, int> mymap;
std::map<char, int>::iterator it;
// 插入元素：构建映射 {'a':10, 'b':20, 'c':30, 'd':40, 'e':50, 'f':60}
mymap['a'] = 10; mymap['b'] = 20; mymap['c'] = 30; mymap['d'] = 40; mymap['e'] = 50; mymap['f'] = 60;
/*------------------第二步：展示 map 容器的删除操作------------------*/
// 1. 迭代器位置删除：删除键 'b'
// find('b') 返回指向键 'b' 的迭代器，erase(it) 删除该元素
it = mymap.find('b');
mymap.erase(it);
// 2. 按键删除：删除键 'c'
// erase('c') 直接删除键为 'c' 的元素，返回删除数量（1 表示成功）
mymap.erase('c');
// 3. 迭代器范围删除：删除从 'e' 到末尾的所有元素
// find('e') 返回指向 'e' 的迭代器，erase(it, mymap.end()) 删除 [it, end) 区间
it = mymap.find('e');
mymap.erase(it, mymap.end());
/*------------------第三步：输出 map 容器的剩余内容------------------*/
for (it = mymap.begin(); it != mymap.end(); ++it) {
std::cout << it->first << " => " << it->second << '\n';
}
return 0;
}
// map::find
#include<iostream>
#include<map>
int main() {
/*------------------第一步：准备 map 容器基本数据------------------*/
std::map<char, int> mymap;
std::map<char, int>::iterator it;
// 插入元素，构建映射关系：{'a':50, 'b':100, 'c':150, 'd':200}
mymap['a'] = 50; mymap['b'] = 100; mymap['c'] = 150; mymap['d'] = 200;
/*------------------第二步：展示 map 容器的查找操作------------------*/
// 1. 使用 find() 查找键 'b'
it = mymap.find('b'); // find() 返回一个迭代器，指向键匹配的元素或 end()（若未找到）
// 2. 检查是否找到（若未找到，it == mymap.end()）
if (it != mymap.end()) mymap.erase(it);
/*------------------第三步：输出 map 容器的剩余内容------------------*/
// 1. 输出剩余元素
std::cout << "mymap 容器中元素为：" << '\n';
std::cout << "a => " << mymap.find('a')->second << '\n'; // 安全：键 'a' 存在
std::cout << "c => " << mymap.find('c')->second << '\n'; // 安全：键 'c' 存在
std::cout << "d => " << mymap.find('d')->second << '\n'; // 安全：键 'd' 存在
// 2. 若尝试访问已删除的键 'b'：
// std::cout << "b => " << mymap.find('b')->second << '\n'; // 未定义行为！find('b') 返回 end()，解引用导致崩溃
return 0;
}
// map::count
#include<iostream>
#include<map>
int main() {
// 1. 创建 map 容器
std::map<char, int> mymap;
char c;
// 2. 插入元素
mymap['a'] = 101; mymap['c'] = 202; mymap['f'] = 303;
// 3. 遍历字符 'a' 到 'g'，检查每个字符是否为 map 的键
for (c = 'a'; c < 'h'; c++) {
std::cout << c;
// 注意：map::count(key) 返回键 key 的出现次数（对于 map 只能是 0 或 1）
if (mymap.count(c) > 0) // 因为 map 不允许重复键，所以 count(key) > 0 等价于键存在
std::cout << "是 mymap 容器中的元素\n";
else
std::cout << "不是 mymap 容器中的元素\n";
}
return 0;
}
// map::lower_bound/upper_bound
#include<iostream>
#include<map>
int main() {
/*------------------第一步：准备 map 容器基本数据------------------*/
std::map<char, int> mymap;
std::map<char, int>::iterator itlow, itup;
// 插入元素，构建有序映射：{'a':20, 'b':40, 'c':60, 'd':80, 'e':100}
mymap['a'] = 20; mymap['b'] = 40; mymap['c'] = 60; mymap['d'] = 80; mymap['e'] = 100;
/*------------------第二步：展示 map 容器 lower_bound/upper_bound 接口函数的使用------------------*/
// 1. lower_bound(key)：返回首个"大于等于 key"的元素迭代器
// 此处 key='b'，mymap 中首个 >= 'b' 的元素是 'b' 自身
// 因此 itlow 指向 {'b', 40}
itlow = mymap.lower_bound('b');
// 2. upper_bound(key)：返回首个"大于 key"的元素迭代器
// 此处 key='d'，mymap 中首个 > 'd' 的元素是 'e'
// 因此 itup 指向 {'e', 100}（注意：不包含 'd' 本身）
itup = mymap.upper_bound('d');
// 3. erase 区间 [itlow, itup)：删除包含 itlow 但不包含 itup 的元素
// 即删除 ['b', 'e')，实际删除 'b'、'c'、'd'，保留 'a' 和 'e'
mymap.erase(itlow, itup); // 删除 ['b', 'e')
/*------------------第三步：输出 map 容器的剩余内容------------------*/
for (std::map<char, int>::iterator it = mymap.begin(); it != mymap.end(); ++it) {
std::cout << it->first << " => " << it->second << '\n';
}
return 0;
}
// map::equal_range
#include<iostream>
#include<map>
int main() {
/*------------------第一步：准备 map 容器基本数据------------------*/
std::map<char, int> mymap;
mymap['a'] = 10; // 键 'a' 对应值 10
mymap['b'] = 20; // 键 'b' 对应值 20
mymap['c'] = 30; // 键 'c' 对应值 30
/*------------------第二步：展示 map 容器 equal_range 接口函数的使用------------------*/
// 1. 使用 equal_range('b') 获取键 'b' 的范围迭代器对
std::pair<std::map<char, int>::iterator, std::map<char, int>::iterator> ret;
ret = mymap.equal_range('b'); // 注意：返回值是一个 pair<lower_bound, upper_bound>
/*------------------第三步：输出 map 容器的剩余内容------------------*/
// 1. 输出 lower_bound 指向的元素
std::cout << "lower_bound 指向的元素是：";
std::cout << ret.first->first << " => " << ret.first->second << '\n';
// 2. 输出 upper_bound 指向的元素
std::cout << "upper_bound 指向的元素是：";
std::cout << ret.second->first << " => " << ret.second->second << '\n';
return 0;
}
代码示例：map 核心的接口函数的设计说明
（find/insert/operator[]）
// map 核心接口设计说明（find/insert/operator[]）
#include<map>
using namespace std;
/*-----------------------第一部分：类型别名-----------------------*/
using key_type = /* 模板参数 Key */;
using mapped_type = /* 模板参数 T */;
using value_type = pair<const key_type, mapped_type>; // 键值对类型，固定为 pair<const key_type, mapped_type>（键 const 保证红黑树结构稳定）
/* 注意事项：
* 1. key_type: 模板第一个参数，即 map 的'键'类型
* 2. mapped_type: 模板第二个参数，即 map 的'值'类型
* 3. value_type: 键值对类型，固定为 pair<const key_type, mapped_type>（键 const 保证红黑树结构稳定）
*/
/*-----------------------第二部分：find 接口：查找键并返回迭代器-----------------------*/
iterator find(const key_type& k);
/* 注意事项：
* 1. 功能：查找键 k，返回指向该键值对的迭代器；若未找到，返回 end()
* 2. 特殊点：通过迭代器可修改 mapped_type（值），但无法修改 key_type（键，因键是 const 类型）
*/
/*-----------------------第三部分：insert 接口：插入键值对，返回插入状态-----------------------*/
pair<iterator, bool> insert(const value_type& val);
/* 注意事项：
* 1. 重载形式：pair<iterator, bool> insert(const value_type& val);
* 返回值说明：
* 1. pair.first: 指向'键所在节点'的迭代器（无论插入成功/失败，都指向已存在或新插入的键）
* 2. pair.second: true（插入新键成功） / false（键已存在，插入失败）
* 3. 设计巧思：插入失败时，first 仍指向已存在的键 → 可替代 find 实现'查找 + 插入'复合逻辑
*/
/*-----------------------第四部分：operator[] 接口：多功能复合操作（插入/查找/修改值）-----------------------*/
mapped_type& operator[](const key_type& k) {
// 1. 插入默认值的键值对，依赖 insert 的'查找 + 插入'特性
pair<iterator, bool> ret = insert({k, mapped_type()});
// 2. 指向已存在或新插入的键
iterator it = ret.first;
// 3. 返回值引用，支持修改
return it->second;
}
/* 注意事项：
* 1. 语法：mapped_type& operator[](const key_type& k);
*
* 内部实现原理：
* 1. 调用 insert({k, mapped_type()})，尝试插入新键（值为默认构造的 mapped_type）
* 2. 利用 insert 返回的 pair，通过 first 拿到键对应迭代器
* 3. 返回迭代器指向的 mapped_type 引用 → 支持直接修改值
*
* 功能覆盖：
* 1. 键不存在 → 插入新键（值为默认构造） + 返回值引用（可修改）
* 2. 键已存在 → 查找键位置 + 返回值引用（可修改）
*/
/* 核心逻辑总结：
* 1. find：基础查找工具，返回迭代器（未找到返回 end()）
* 2. insert：插入 + 隐含查找功能（失败时返回已存在键的迭代器）
* 3. operator[]：基于 insert 实现，一站式支持'插入新键、查找旧键、修改值'
* 设计亮点：
* - insert 返回的 pair 复用迭代器，让'插入失败'场景也能充当查找 → 为 operator[] 提供底层支撑
* - operator[] 通过返回值引用，无缝支持'赋值修改'和'直接访问'，语法简洁但功能强大
* - 键为 const 类型 → 保证红黑树的有序性不被破坏（禁止直接修改键值）
*/
代码示例 1：使用'构造函数 + insert() 函数 + find() 函数'
#include<iostream>
#include<map>
using namespace std;
int main() {
/*----------------------第一部分：展示 map 容器的构造函数的使用----------------------*/
// 1. 初始化列表构造 map + 迭代器遍历
map<string, string> dict = {{"left", "左边"}, {"right", "右边"}, {"insert", "插入"}, {"string", "字符串"}}; // 用初始化列表构造一个 map，键是 string 类型，值是 string 类型
// 2. 迭代器遍历 map
auto it = dict.begin();
while (it != dict.end()) {
// 方式 1：显式解引用 + 访问成员（可读性稍弱）
// cout << (*it).first << ":" << (*it).second << endl;
// 注意：map 迭代器解引用得到 pair<const key_type, mapped_type>
// 方式 2：利用迭代器的 operator-> 重载（底层返回 pair 指针，语法糖）
// cout << it.operator->()->first << ":" << it.operator->()->second << endl;
// 原理：it.operator->() 返回 pair*，接着 ->first / ->second 访问成员
// 方式 3：最简洁的写法（编译器自动处理 operator-> 调用）
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
/*----------------------第二部分：展示 map 容器的 insert() 函数的使用----------------------*/
// 1. insert 插入 pair 对象的 4 种方式对比
// 方式 1：先构造 pair 对象，再插入
pair<string, string> kv1("first", "第一个");
dict.insert(kv1);
// 方式 2：直接构造临时 pair 对象插入
dict.insert(pair<string, string>("second", "第二个"));
// 方式 3：用 make_pair 简化临时 pair 构造（自动推导类型）
dict.insert(make_pair("sort", "排序"));
// 方式 4：用初始化列表直接构造 pair（C++11 及以上支持，最简洁）
dict.insert({"auto", "自动的"});
// 2. 测试重复键插入："left" 已存在，插入会失败（map 不允许重复键）
dict.insert({"left", "左边，剩余"});
// 3. 范围 for 遍历（C++11 及以上支持）
for (const auto& e : dict) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
/*----------------------第三部分：展示 map 容器的 find() 函数的使用----------------------*/
string str;
while (cin >> str) {
auto ret = dict.find(str);
if (ret != dict.end()) {
cout << "=> " << ret->second << endl;
} else {
cout << "无此单词，请重新输入" << endl;
}
}
return 0;
}
代码片段 2：用'find + 迭代器'统计水果次数
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
/*------------------第一步：准备 map 容器基本数据------------------*/
string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
map<string, int> countMap;
/*------------------第二步：用 find + 迭代器统计水果次数------------------*/
for (const auto& str : arr) {
// 1. 先查找当前水果是否在 map 中
auto ret = countMap.find(str);
if (ret == countMap.end()) {
// 2. 不在 map 中 → 第一次出现，插入 {水果，1}
countMap.insert({str, 1});
} else {
// 3. 在 map 中 → 找到的节点中次数 +1
ret->second++;
}
}
/*------------------第三步：输出 map 容器的剩余内容------------------*/
for (const auto& e : countMap) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
return 0;
}
代码片段 3：用
operator[]简化统计逻辑
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
/*------------------第一步：准备 map 容器基本数据------------------*/
string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
map<string, int> countMap;
/*------------------第二步：用 operator[] 简化统计逻辑------------------*/
for (const auto& str : arr) {
countMap[str]++; /* 注意事项：一行代码完成'查找 + 插入 + 计数'
* 1. 若水果不存在：插入 {水果，0}，返回值引用后 +1 → 最终值为 1
* 2. 若水果已存在：返回值引用后 +1 → 次数累加
*/
}
/*------------------第三步：输出 map 容器的剩余内容------------------*/
for (const auto& e : countMap) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
return 0;
}
cplusplus 网站上关于 C++ 的
multimap 容器的介绍：multimap - C++ Reference
C++ 标准模板库（STL）中的
multimap 容器的接口函数，主要可以分为以下一个部分：
template<class Key,// multimap::key_type
class T,// multimap::mapped_type
class Compare = less<Key>,// multimap::key_compare
class Alloc = allocator<pair<const Key, T>>// multimap::allocator_type>
class multimap;
可以发现，它与
map容器的模板声明形式完全一致都通过Key（键类型）、T（映射值类型）、Compare（比较规则）、Alloc（内存分配器） 这四个模板参数定义容器。但需要注意：
map和multimap虽模板声明形式相似，核心特性却有本质区别
map会自动保证键唯一，容器中每个键对应唯一的映射关系multimap允许键冗余，侧重按序存储键可重复的映射数据*简单说：*map 像'严格的字典'，同一个字（键）只能查一个解释（值），重复插入同键会静默 覆盖/失败。multimap 像'宽松的便签本'，同一个字（键）能记多个解释（值），适合存'一对多'的映射关系。
map 和 multimap 的基础用法高度相似，核心区别在于 multimap 支持键（key）的冗余存储 基于这一特性，它的
insert（插入）、find（查找）、count（计数）、erase（删除）等操作，都会围绕'键可重复'进行适配这一点和set/multiset的差异逻辑完全一致（比如：find遇到重复键时，会返回中序遍历的第一个匹配元素）此外，multimap 不支持 operator[] 因为键可冗余的场景下，
[]无法明确指定修改哪一个键对应的值 它仅能用于插入新键值对（但也会因'键重复'的特性，失去 map 中[]兼具'查找 + 修改'的复合能力）
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
/* 思路：这道题要求'输出结果中的每个元素一定是 唯一 的' ---> 所以我们在找交集元素之前应该先将两个数组中的元素进行去重
* 因此：怎么进行去重处理？---> 存入 set 容器中的数据天然就会进行去重
* 怎么找到它们的交集？ ---> 因为存入 set 容器中的数据会自动进行升序排序，所以后面可以循环遍历对比
*/
// 1. 将数组中元素添加到 set 容器中
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
// 2. 定义数组存储最终的交集结果
vector<int> ret;
// 3. 分别获取两个 set 容器的起始迭代器
auto it1 = s1.begin();
auto it2 = s2.begin();
// 4. 使用 while 循环遍历这两个 set 容器来找交集
while (it1 != s1.end() && it2 != s2.end()) // 如果有任意 set 容器已经遍历完毕循环就结束
{
// 情况一：s1 当前元素 < s2 当前元素
if (*it1 < *it2) {
it1++;
}
// 情况二：s1 当前元素 > s2 当前元素
else if (*it1 > *it2) {
it2++;
}
// 情况三：s1 当前元素 = s2 当前元素
else {
// 1. 将交集元素添加到结果数组中
ret.push_back(*it1);
// 2. 同时移动两个迭代器
it1++; it2++;
}
}
return ret;
}
};
/**
* 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 容器天然有进行去除的作用
* 思路：
* 1. 使用循环遍历链表
* 2. 将遍历到的节点添加到 set 容器中
* 3. 如果如果插入失败说明当前节点就是链表尾连接到链表中的位置
*/
// 1. 定义一个 set 容器用于存储已经访问过的链表节点指针
set<ListNode*> s;
// 2. 定义当前节点指针用于遍历链表
ListNode* cur = head;
// 3. 使用 while 循环进行遍历链表
while (cur) // 当当前的节点 cur 不为空的时持续遍历链表
{
// 3.1：尝试将当前节点添加到 set 容器中
auto ret = s.insert(cur);
/* set 的 insert 方法会返回一个 pair
* 1. 其中 first 是指向插入位置的迭代器
* 2. second 是 bool 类型
*/
// 3.2：如果插入失败 ---> 该链表是环形链表
if (ret.second == false) return cur;
// 3.3：如果插入成功 ---> 继续向后遍历
cur = cur->next;
}
// 4. 如果可以遍历完整个链表 ---> 该链表不是环形链表
return nullptr;
}
};
/* // 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) // 函数功能：深拷贝带有随机指针的链表，返回拷贝后链表的头节点
{
/*---------------- 定义准备阶段 ----------------*/
// 1. 定义 map 容器用于存储'原节点'和对应'拷贝节点'的映射关系
map<Node*, Node*> m;
// 2. 定义指向拷贝链表的头节点和尾节点的指针
Node* copyHead = nullptr;
Node* copyTail = nullptr;
// 3. 定义用于遍历原链表的指针
Node* curr = head;
/*---------------- next 指针拷贝阶段 ----------------*/
while (curr) // 如果原链表的遍历结束则循环退出
{
// 1. 把原链表中的当前节点拷贝到拷贝链表中
// 情况一：如果拷贝链表还没有节点
if (copyTail == nullptr) {
// 操作：创建新节点 + 让拷贝链表的头/尾指针指向该节点
copyHead = copyTail = new Node(curr->val);
}
// 情况二：如果拷贝链表中已经有了节点
else {
// 操作 1：在拷贝链表的尾节点的后面创建新节点
copyTail->next = new Node(curr->val);
// 操作 2：更新拷贝链表的尾指针的指向
copyTail = copyTail->next;
}
// 2. 将原节点和对应的拷贝节点存入映射表中
m[curr] = copyTail;
// 3. 原链表当前节点后移
curr = curr->next;
}
/*---------------- random 指针处理阶段 ----------------*/
// 1. 重新将原链表当前节点指针指向原链表头节点 ---> 准备遍历原链表处理 random 指针
curr = head;
// 2. 定义用于遍历拷贝链表的指针
Node* copy = copyHead;
// 3. 核心逻辑
while (curr) // 如果原链表的遍历结束循环退出
{
// 1. 根据原链表中节点的 random 指针处理拷贝链表的 random 指针
// 情况一：如果原节点的 random 指针为 nullptr
if (curr->random == nullptr) {
// 操作：拷贝节点的 random 指针也设为 nullptr
copy->random = nullptr;
}
// 情况二：如果原节点的 random 指针不为 nullpt
else {
// 操作：将拷贝节点的 random 指针指向该节点
copy->random = m[curr->random]; // 细节：通过映射表找到对应的拷贝节点
}
// 2. 原链表当前节点后移
curr = curr->next;
// 3. 拷贝链表当前节点后移
copy = copy->next;
}
// 最后：返回拷贝后链表的头节点
return copyHead;
}
};
class Solution {
public:
/*------------------- 仿函数 -------------------*/
// 函数功能：用于自定义排序规则
struct Compare {
// 1. 重载 () 运算符，实现仿函数功能 ---> 用于比较两个 pair<string, int> 类型的元素
bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
/*
* 函数参数为 const 引用 ---> 避免拷贝
* 函数使用 const 进行修饰 ---> 保证不会修改传入的元素
*/
return x.second > y.second; // 按照 pair 的第二个元素（即单词出现的次数）降序排列
}
};
/*------------------- 函数 -------------------*/
// 函数功能：找出 words 中出现频率最高的前 k 个单词
vector<string> topKFrequent(vector<string>& words, int k) {
// 1. 定义用于统计每个单词出现次数的 map 容器
map<string, int> m;
// 2. 定义存储最高频的前 K 个单词的 vector 容器
vector<string> ret;
// 3. 使用范围 for 循环统计每个单词出现的次数
for (auto& e : words) {
m[e]++; // 键为单词，值为出现次数
}
// 4. 将 map 中的键值对转换位 pair 存储在 vector 中 ---> 方便后续排序
vector<pair<string, int>> v(m.begin(), m.end());
// 5. 使用 stable_sort 进行稳定排序
stable_sort(v.begin(), v.end(), Compare());
/*
* stable_sort 能保证相等元素的相对顺序不变，sort 则不保证
* 排序规则由 Compare 仿函数指定（按出现次数降序）
*/
// 6. 提取排序后前 k 个单词存入结果 vector 中
for (int i = 0; i < k; i++) {
ret.push_back(v[i].first);
}
// 7. 返回包含前 k 个高频单词的 vector 容器
return ret;
}
};
class Solution {
public:
/*------------------- 仿函数 -------------------*/
// 函数功能：用于自定义排序规则
struct Compare {
// 1. 重载 () 运算符，实现仿函数功能 ---> 用于比较两个 pair<string, int> 类型的元素
bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
// 排序规则：首先按出现次数降序排列；若次数相同，按单词字典序升序排列
return x.second > y.second || (x.second == y.second && x.first < y.first);
}
};
/*------------------- 函数 -------------------*/
// 函数功能：找出 words 中出现频率最高的前 k 个单词
vector<string> topKFrequent(vector<string>& words, int k) {
// 1. 定义用于统计每个单词出现次数的 map 容器
map<string, int> m;
// 2. 定义存储最高频的前 K 个单词的 vector 容器
vector<string> ret;
// 3. 使用范围 for 循环统计每个单词出现的次数
for (auto& e : words) {
m[e]++; // 键为单词，值为出现次数
}
// 4. 将 map 中的键值对转换位 pair 存储在 vector 中 ---> 方便后续排序
vector<pair<string, int>> v(m.begin(), m.end());
// 5. 使用 sort 进行排序
sort(v.begin(), v.end(), Compare()); // 排序规则由 Compare 仿函数指定
// 6. 提取排序后前 k 个单词存入结果 vector 中
for (int i = 0; i < k; i++) {
ret.push_back(v[i].first);
}
// 7. 返回包含前 k 个高频单词的 vector 容器
return ret;
}
};
class Solution {
public:
/*------------------- 仿函数 -------------------*/
// 函数功能：用于自定义排序规则
struct Compare {
// 1. 重载 () 运算符，实现仿函数功能 ---> 用于比较两个 pair<string, int> 类型的元素
bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
return x.second < y.second || (x.second == y.second && x.first > y.first);
/* 注意：
* 优先队列底层是大顶堆，要实现'次数高的优先，次数相同时字典序小的优先'
* 所以比较时，若次数小，或者次数相同但字典序大，返回真（这样该元素会被放在堆的下方）
*/
}
};
/*------------------- 函数 -------------------*/
// 函数功能：找出 words 中出现频率最高的前 k 个单词
vector<string> topKFrequent(vector<string>& words, int k) {
// 1. 定义用于统计每个单词出现次数的 map 容器
map<string, int> m;
// 2. 定义存储最高频的前 K 个单词的 vector 容器
vector<string> ret;
// 3. 使用范围 for 循环统计每个单词出现的次数
for (auto& e : words) {
m[e]++; // 键为单词，值为出现次数
}
// 4. 将 map 中的键值对传入优先队列，构建大顶堆
priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(m.begin(), m.end());
/* 定义大顶堆：
* 1. 存储 pair<string, int> 类型
* 2. 底层容器为 vector
* 3. 比较规则由 Compare 仿函数指定
*/
// 5. 提取堆顶前 k 个元素存入结果向量
for (int i = 0; i < k; i++) {
// 5.1：将堆顶元素的单词部分放入结果向量
ret.push_back(p.top().first);
// 5.2：弹出堆顶元素，让下一个元素成为新的堆顶
p.pop();
}
// 6. 返回包含前 k 个高频单词的 vector 容器
return ret;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online