一、map 核心知识1. map 底层原理map 是有序键值对容器底层基于红黑树平衡二叉搜索树实现默认按照键 key 升序排序所有操作查找、插入、删除的时间复杂度均为O(logn)效率稳定。2. map 基础定义// 字符串映射整数统计字符串频次 mapstring, 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] 李四; // 方式2insert插入pairkey存在则不插入不覆盖 mp.insert({3, 王五}); mp.insert(make_pair(4, 赵六)); // 方式3emplaceC11直接构造元素效率更高 mp.emplace(5, 孙七);2查找元素find(key)返回迭代器找到指向该元素未找到返回mp.end()count(key)返回 key 出现次数map 中只有 0/1常用于判断 key 是否存在// 查找key2 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遍历 mapmap 支持迭代器遍历、范围 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, vectorint(10, 0));reserve(n)只开内存不创建元素size 不变resize(n)改变元素个数多补少删vectorint 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::npos2. string 与数字互转进阶// 字符串转数字 string s1 12345; int a stoi(s1); long long b stoll(s1); // 数字转字符串 int c 67890; string s2 to_string(c);3.string 可以直接比较字典序