C++ STL 容器常用函数与实战技巧

2.3 迭代器与范围 for

for(auto it = v.begin(); it != v.end();++it){...}
for(int x : v){ cout << x << " "; } // 更简洁！

力扣应用：几乎所有数组类题目都可用 vector 代替原生数组，配合 sort、lower_bound 等函数，事半功倍。

3. string：不只是字符串

string 本质是 vector<char> 的特化，支持大量操作：

3.1 常用方法

string s = "hello";
s.length() 或 s.size(); // 长度
s.substr(1,3); // "ell"（从索引 1 开始取 3 个字符）
s.find("ll"); // 返回子串首次出现位置（未找到返回 string::npos）
s.replace(1,2,"xx"); // 从 1 开始替换 2 个字符为"xx"
s += " world"; // 拼接
reverse(s.begin(), s.end()); // 逆序（需 #include <algorithm>）

3.2 字符串转数字 / 数字转字符串

#include<string>
stoi("123"); // string to int
to_string(123); // int to string

力扣应用：回文判断、子串匹配、字符串变换类题目常需 substr + sort + == 判断字母异位词。

4. map 与 unordered_map：键值对神器

4.1 map（有序，基于红黑树）

map<string,int> m;
m["apple"]=5;
m["banana"]=3;
for(auto& p : m){ cout << p.first <<": "<< p.second << endl; // 自动按键排序}

4.2 unordered_map（无序，哈希表，更快）

unordered_map<char,int> freq;
for(char c :"hello") freq[c]++; // 统计字符频次

⚠️ 注意：map[key] 若 key 不存在会自动插入 {key, 0}，慎用于只读场景！可用 .count(key) 或 .find(key) != .end() 判断存在性。

力扣应用：两数之和 → unordered_map 存储值到索引；字母异位词分组 → 用排序后的字符串作 key；前缀和 + 哈希 → 子数组和为 K

5. set 与 unordered_set：去重与快速查找

set<int> s ={3,1,4,1,5}; // 自动去重并排序：{1,3,4,5}
unordered_set<int> us ={3,1,4,1,5}; // 无序，但插入/查找平均 O(1)
if(s.count(4)){/* 存在 */}

力扣应用：判断数组是否有重复 → 插入 set 后比较 size；滑动窗口去重（如最长无重复子串）；快速判存在（替代 bool 数组，尤其值域大时）

6. 容器适配器：栈、队列、优先队列

6.1 stack（LIFO）

stack<int> st;
st.push(1);
st.top(); // 查看栈顶
st.pop(); // 弹出栈顶

应用：括号匹配、表达式求值、DFS 模拟

6.2 queue（FIFO）

queue<int> q;
q.push(1);
q.front(); // 队首
q.pop(); // 出队

应用：BFS、层序遍历

6.3 priority_queue（堆，默认大顶堆）

priority_queue<int> pq; // 大顶堆（最大值在顶）
priority_queue<int, vector<int>, greater<int>> min_pq; // 小顶堆
pq.push(3);
pq.push(1);
pq.push(4);
cout << pq.top(); // 4

力扣经典应用：Top K 问题 → 小顶堆维护 K 个最大元素；合并 K 个有序链表 → 堆存每个链表头；任务调度、带权最短路径（Dijkstra）

7. 进阶技巧：容器组合 + Lambda

示例：按频率排序字符

string s ="tree";
unordered_map<char,int> freq;
for(char c : s) freq[c]++;
vector<pair<char,int>>vec(freq.begin(), freq.end());
sort(vec.begin(), vec.end(),[](constauto& a,constauto& b){return a.second > b.second;// 频率降序});

示例：用 priority_queue 实现频率排序

auto cmp =[](const pair<char,int>& a,const pair<char,int>& b){return a.second < b.second;// 小顶堆？不！这里要大顶堆，所以用 <};
priority_queue<pair<char,int>, vector<pair<char,int>>,decltype(cmp)>pq(cmp);

提示：priority_queue 的比较函数逻辑与 sort 相反！sort 中 a < b 表示 a 排在 b 前；priority_queue 中 a < b 表示 b 优先级更高（因为底层是 less，但堆顶是最大值）

8. 总结：选择合适的容器

掌握 STL 容器与算法是解决算法问题的关键。在力扣刷题中，大部分中等题都能通过合理组合 vector、map/set、sort 和 priority_queue 高效解决。

建议初学者：

1. 熟记各容器的时间复杂度（如 vector 插入尾部 O(1)，中间 O(n)；map 插入 O(log n)）。
2. 多写 Lambda 表达式，提升代码简洁度。
3. 遇到新题先想：'这题的核心数据结构是什么？'