C++ STL 核心容器速查表

1️⃣ vector（动态数组）

基本操作

#include<vector>usingnamespacestd;vector<int>v;// 声明vector<int>v(10);// 声明长度为10的vectorvector<int>v(10,5);// 声明长度为10，初始值为5vector<int>v{1,2,3};// 初始化列表// 增v.push_back(x);// 尾部添加元素v.pop_back();// 删除尾部元素v.insert(v.begin()+i,x);// 在位置i插入x（O(n)）// 删v.erase(v.begin()+i);// 删除位置i的元素（O(n)）v.erase(v.begin()+l,v.begin()+r);// 删除[l, r)区间v.clear();// 清空v.resize(n);// 调整大小为n// 查v[i]// 访问第i个元素（不检查边界）v.at(i)// 访问第i个元素（检查边界）v.front()// 第一个元素v.back()// 最后一个元素// 其他v.size()// 元素个数v.empty()// 是否为空v.capacity()// 容量v.begin()// 起始迭代器v.end()// 结束迭代器

竞赛常用技巧

// 1. 遍历for(intx:v)cout<<x<<" ";// 范围forfor(inti=0;i<v.size();i++)...// 下标遍历for(autoit=v.begin();it!=v.end();it++)...// 迭代器// 2. 排序sort(v.begin(),v.end());// 升序sort(v.begin(),v.end(),greater<int>());// 降序// 3. 去重（需要先排序）sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());// 4. 二维vectorvector<vector<int>>mat(n,vector<int>(m));// n行m列// 5. 清空并释放内存vector<int>().swap(v);// 彻底释放内存

2️⃣ queue（队列）

基本操作

#include<queue>usingnamespacestd;queue<int>q;// 声明// 增q.push(x);// 入队// 删q.pop();// 出队（删除队首）// 查q.front()// 队首元素q.back()// 队尾元素// 其他q.size()// 元素个数q.empty()// 是否为空

优先队列（priority_queue）

priority_queue<int>pq;// 大根堆（默认）priority_queue<int,vector<int>,greater<int>>pq;// 小根堆// 自定义比较（结构体）structNode{intval,priority;booloperator<(constNode&other)const{returnpriority<other.priority;// 大根堆}};priority_queue<Node>pq;// 操作pq.push(node);// 入队pq.pop();// 出队pq.top();// 访问堆顶pq.size();pq.empty();

双端队列（deque）

#include<deque>deque<int>dq;// 两端都可以操作dq.push_back(x);// 尾部插入dq.push_front(x);// 头部插入dq.pop_back();// 尾部删除dq.pop_front();// 头部删除dq[i]// 随机访问（O(1)）

3️⃣ map（映射）

基本操作

#include<map>usingnamespacestd;map<int,string>mp;// 声明（按键升序）unordered_map<int,string>mp;// 哈希map（无序，更快）// 增/改mp[key]=value;// 插入或修改mp.insert({key,value});// 插入mp.insert(make_pair(k,v));// 插入// 删mp.erase(key);// 删除键为key的元素mp.erase(mp.begin());// 删除第一个元素mp.clear();// 清空// 查mp[key]// 访问（不存在会创建）mp.at(key)// 访问（不存在会抛异常）mp.count(key)// 是否存在（0或1）mp.find(key)// 查找，返回迭代器// 其他mp.size()mp.empty()mp.begin()mp.end()

常用技巧

// 1. 遍历for(autop:mp){cout<<p.first<<" "<<p.second<<endl;}// 2. 查找是否存在if(mp.count(key)){cout<<"存在: "<<mp[key]<<endl;}// 3. 使用find（避免自动创建）autoit=mp.find(key);if(it!=mp.end()){cout<<"找到: "<<it->second<<endl;}// 4. 反向遍历（map特有）for(autoit=mp.rbegin();it!=mp.rend();it++){cout<<it->first<<" "<<it->second<<endl;}// 5. 统计词频map<string,int>cnt;cnt[word]++;// 自动初始化为0// 6. 自定义排序structcmp{booloperator()(constint&a,constint&b)const{returna>b;// 降序}};map<int,string,cmp>mp;

multimap（允许重复键）

multimap<int,string>mmp;mmp.insert({key,value});// 插入（允许多个相同key）mmp.count(key);// 返回key的个数mmp.lower_bound(key);// 第一个>=key的位置mmp.upper_bound(key);// 第一个>key的位置

4️⃣ set（集合）

基本操作

#include<set>usingnamespacestd;set<int>s;// 声明（自动去重+排序）unordered_set<int>s;// 哈希set（无序）// 增s.insert(x);// 删s.erase(x);s.clear();// 查s.count(x)// 是否存在s.find(x)// 查找// 其他s.size()s.empty()s.begin()s.end()

常用技巧

// 1. 遍历（自动有序）for(intx:s)cout<<x<<" ";// 2. 去重vector<int>v={1,2,2,3};set<int>s(v.begin(),v.end());// 3. 查找第一个>=x的元素autoit=s.lower_bound(x);if(it!=s.end())cout<<*it;// 4. 查找第一个>x的元素autoit=s.upper_bound(x);

📊 复杂度对比

*vector 尾部插入是 O(1)，中间插入是 O(n)

🎯 竞赛选择指南

⚠️ 易错点提醒

1. vector 越界：v[i]不检查边界，v.at(i)检查
2. map 自动创建：mp[key]不存在时会创建（值为默认值）
3. 迭代器失效：删除元素后，迭代器可能失效
4. unordered 可能退化：极端情况下退化为 O(n)
5. 优先队列默认大根堆：小根堆要用greater<int>