一、map 核心知识
1. map 底层原理
map 是有序键值对容器，底层基于红黑树（平衡二叉搜索树）实现，默认按照键 key 升序排序，所有操作（查找、插入、删除）的时间复杂度均为O(logn)，效率稳定。
2. map 基础定义
// 字符串映射整数（统计字符串频次） map<string, int> cnt; // 整数映射字符串<int, string> id_name; // 嵌套map（复杂键值<int,<int, int>> mp_nest;3. map 核心操作
（1）插入元素
map 插入有 3 种常用方式，适用不同场景：
<int, string> mp; // 方式1：[]赋值（最简单，若key存在则覆盖value） mp[1] = "张三"; mp[2] = "李四"; // 方式2：insert插入pair（key存在则不插入，不覆盖） mp.insert({3, "王五"}); mp.insert(make_pair(4, "赵六")); // 方式3：emplace（C++11，直接构造元素，效率更高） mp.emplace(5, "孙七");（2）查找元素
find(key)：返回迭代器，找到指向该元素，未找到返回mp.end()count(key)：返回 key 出现次数（map 中只有 0/1），常用于判断 key 是否存在
// 查找key=2 auto it = mp.find(2); if (it != mp.end()) { // 输出value cout << it->second << endl; } // 判断key是否存在 if (mp.count(3))< "< endl; }（3）删除元素
erase(key)：按 key 删除，返回删除个数erase(iterator)：按迭代器删除，效率更高clear()：清空整个 map
// 按key删除 mp.erase(2); // 按迭代器删除 auto it = mp.find(3); if (it != mp.end()) mp.erase(it); // 清空 mp.clear();（4）遍历 map
map 支持迭代器遍历、范围 for 遍历，遍历结果默认按 key 升序：
// 迭代器遍历 <int, string>::iterator it = mp.begin(); it != mp.end(); it++) { cout< " " << it->second << endl; } // 范围for for (auto &p : mp) { // 引用传递，避免拷贝 < "< endl; }二、vector 知识点（补充）
1. vector 扩容机制
vector 是动态数组，底层连续内存存储，当容量不足时，会自动扩容（通常 1.5 倍 / 2 倍），扩容过程会重新分配内存、拷贝元素，效率较低。
// 正确删除元素 for (auto it = v.begin(); it != v.end();) { if (*it == 0) it = v.erase(it); else it++; }- 二维 vector 优化：提前初始化行列，避免动态扩容
// 5行10列，初始值<int>> v(5, vector<int>(10, 0));reserve(n)：只开内存，不创建元素，size 不变resize(n)：改变元素个数，多补少删
vector<int> v; v.reserve(100000); // 提前开好，避免多次扩容快速去重模板
sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());三、string 进阶知识点（补充）
1. string 高效操作
- substr(pos, len)：截取子串，第一个参数是起始下标，第二个是长度（易错点）
string s = "abcdef"; // 从下标1开始，截取3个字符：bcd string sub = s.substr(1, 3);- append vs +=：
append可拼接多个字符 / 字符串，效率更高 - find/rfind：查找子串，返回首次 / 末次出现下标，未找到返回
string::npos
2. string 与数字互转（进阶）
// 字符串转数字 string s1 = "12345"; int a = stoi(s1); long long b = stoll(s1); // 数字转字符串 int c = 67890; string s2 = to_string(c);
