1. 为什么STL容器是LeetCode刷题利器
在算法竞赛和面试刷题中，STL（Standard Template Library）就像程序员的瑞士军刀。我刷完LeetCode Hot 100后发现，90%的题目都可以用vector、unordered_map等核心容器简化代码。这些容器不仅封装了底层数据结构，还提供了丰富的成员函数，能让我们专注于算法逻辑而非重复造轮子。
以经典的Two Sum问题为例，暴力解法需要O(n²)时间，而使用unordered_map可以将时间复杂度降到O(n)。这种效率提升在面试中往往是决定性的。更重要的是，熟练使用STL能让你的代码更简洁、更专业——面试官看到你熟练运用STL函数时，会默认你具备扎实的C++功底。
2. 七大核心容器深度解析
2.1 vector：动态数组的终极形态
vector是LeetCode中使用频率最高的容器，它完美模拟了动态数组的行为。不同于普通数组，vector的size()和capacity()机制让它能在O(1)时间完成尾部插入（均摊时间）：
vector<int> nums = {1,2,3}; nums.push_back(4); // 不需要手动管理内存关键特性：
- 随机访问O(1)：nums[i]直接定位元素
- 尾部操作O(1)：push_back/pop_back
- 中间插入O(n)：insert/erase需要移动元素
注意：reserve()可以预分配空间避免频繁扩容。当元素数量已知时，先reserve能显著提升性能。
2.2 string：不只是字符串
在LeetCode字符串类题目中，string比char[]更安全高效。其内部也是动态数组实现，支持所有vector操作，还额外提供：
string s = "hello"; s.substr(1,3); // "ell" s.find("ll"); // 返回位置2实用技巧：
- 用+=拼接字符串比直接+更高效
- stoi/stol转换字符串到数值
- to_string将数值转为字符串
2.3 pair：轻量级结构体替代品
当需要存储两个相关联的值时，pair比定义结构体更方便：
pair<int, string> p = {1, "apple"}; cout << p.first << " " << p.second; // 输出: 1 apple在BFS中常用pair存储坐标(x,y)，在贪心算法中存储权重和值的组合。
2.4 unordered_map：哈希表的完美封装
基于哈希表实现的unordered_map是处理查找问题的神器，平均O(1)的查找时间：
unordered_map<string, int> wordCount; wordCount["apple"] = 5; // 插入 if(wordCount.find("banana") != wordCount.end()) {...}与map对比：
- unordered_map：哈希表实现，无序，平均O(1)
- map：红黑树实现，有序，O(log n)
2.5 unordered_set：快速去重工具
当需要检查元素是否存在或去重时，unordered_set比遍历数组高效得多：
unordered_set<int> seen; if(seen.count(num)) { /* 重复 */ } seen.insert(num);2.6 queue & stack：算法题的双子星
虽然可以用deque/list模拟，但专用容器语义更清晰：
queue<int> q; // BFS标准配置 q.push(1); q.pop(); stack<int> st; // 括号匹配/表达式求值 st.push(1); st.pop();3. LeetCode实战应用案例
3.1 两数之和（unordered_map典范）
vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> num_map; // 值->索引 for(int i=0; i<nums.size(); ++i){ int complement = target - nums[i]; if(num_map.count(complement)){ return {num_map[complement], i}; } num_map[nums[i]] = i; } return {}; }3.2 二叉树层序遍历（queue经典应用）
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if(!root) return res; queue<TreeNode*> q; q.push(root); while(!q.empty()){ int levelSize = q.size(); vector<int> level; for(int i=0; i<levelSize; ++i){ TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } res.push_back(level); } return res; }3.3 有效的括号（stack教科书案例）
bool isValid(string s) { stack<char> st; for(char c : s){ if(c=='(' || c=='[' || c=='{') st.push(c); else { if(st.empty()) return false; char top = st.top(); st.pop(); if((c==')' && top!='(') || (c==']' && top!='[') || (c=='}' && top!='{')) return false; } } return st.empty(); }4. 性能优化与避坑指南
4.1 避免不必要的拷贝
// 错误示范：值传递导致整个vector拷贝 void process(vector<int> nums){...} // 正确做法：传引用或const引用 void process(const vector<int>& nums){...}4.2 预分配空间提升性能
vector<int> nums; nums.reserve(1000); // 预先分配避免多次扩容 for(int i=0;i<1000;++i) nums.push_back(i);4.3 警惕unordered_map的哈希冲突
极端情况下哈希冲突会使查找退化为O(n)。对于关键应用，可以：
- 自定义哈希函数
- 改用map保证最差O(log n)
4.4 迭代器失效陷阱
在遍历容器时修改结构会导致未定义行为：
vector<int> v = {1,2,3,4}; for(auto it=v.begin(); it!=v.end(); ++it){ if(*it == 2) v.erase(it); // 危险！迭代器失效 }安全做法是使用erase返回值：
for(auto it=v.begin(); it!=v.end(); ){ if(*it == 2) it = v.erase(it); else ++it; }5. 进阶技巧与组合应用
5.1 自定义哈希函数
当使用自定义类型作为unordered_map键时：
struct Point { int x,y; }; struct HashPoint { size_t operator()(const Point& p) const { return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1); } }; unordered_map<Point, int, HashPoint> pointMap;5.2 优先队列的特殊用法
虽然priority_queue不是STL容器，但作为适配器非常实用：
// 最小堆 priority_queue<int, vector<int>, greater<int>> minHeap; // 带自定义比较的堆 auto cmp = [](const pair<int,int>& a, const pair<int,int>& b){ return a.second > b.second; }; priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);5.3 容器组合解决复杂问题
例如LFU缓存问题需要同时使用：
- unordered_map存储键值对
- 另一个unordered_map存储频率到双向链表的映射
- list实现的双向链表维护访问顺序
class LFUCache { unordered_map<int, list<pair<int, int>>> freq_map; // freq -> {key,value} unordered_map<int, pair<int, list<pair<int,int>>::iterator>> key_map; // key -> {freq, iterator} int min_freq, capacity; public: LFUCache(int capacity) : capacity(capacity), min_freq(0) {} int get(int key) { if(!key_map.count(key)) return -1; // ...更新频率逻辑 } void put(int key, int value) { if(capacity <= 0) return; // ...插入/更新逻辑 } };我在实际刷题中发现，STL容器的组合使用能解决90%以上的Medium难度题目。比如union-find问题可以用vector实现父节点数组，图算法中vector<list >表示邻接表，回溯法中用vector记录路径等。
