1️⃣ vector动态数组基本操作#includevectorusingnamespacestd;vectorintv;// 声明vectorintv(10);// 声明长度为10的vectorvectorintv(10,5);// 声明长度为10初始值为5vectorintv{1,2,3};// 初始化列表// 增v.push_back(x);// 尾部添加元素v.pop_back();// 删除尾部元素v.insert(v.begin()i,x);// 在位置i插入xO(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)coutx ;// 范围forfor(inti0;iv.size();i)...// 下标遍历for(autoitv.begin();it!v.end();it)...// 迭代器// 2. 排序sort(v.begin(),v.end());// 升序sort(v.begin(),v.end(),greaterint());// 降序// 3. 去重需要先排序sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());// 4. 二维vectorvectorvectorintmat(n,vectorint(m));// n行m列// 5. 清空并释放内存vectorint().swap(v);// 彻底释放内存2️⃣ queue队列基本操作#includequeueusingnamespacestd;queueintq;// 声明// 增q.push(x);// 入队// 删q.pop();// 出队删除队首// 查q.front()// 队首元素q.back()// 队尾元素// 其他q.size()// 元素个数q.empty()// 是否为空优先队列priority_queuepriority_queueintpq;// 大根堆默认priority_queueint,vectorint,greaterintpq;// 小根堆// 自定义比较结构体structNode{intval,priority;booloperator(constNodeother)const{returnpriorityother.priority;// 大根堆}};priority_queueNodepq;// 操作pq.push(node);// 入队pq.pop();// 出队pq.top();// 访问堆顶pq.size();pq.empty();双端队列deque#includedequedequeintdq;// 两端都可以操作dq.push_back(x);// 尾部插入dq.push_front(x);// 头部插入dq.pop_back();// 尾部删除dq.pop_front();// 头部删除dq[i]// 随机访问O(1)3️⃣ map映射基本操作#includemapusingnamespacestd;mapint,stringmp;// 声明按键升序unordered_mapint,stringmp;// 哈希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或1mp.find(key)// 查找返回迭代器// 其他mp.size()mp.empty()mp.begin()mp.end()常用技巧// 1. 遍历for(autop:mp){coutp.first p.secondendl;}// 2. 查找是否存在if(mp.count(key)){cout存在: mp[key]endl;}// 3. 使用find避免自动创建autoitmp.find(key);if(it!mp.end()){cout找到: it-secondendl;}// 4. 反向遍历map特有for(autoitmp.rbegin();it!mp.rend();it){coutit-first it-secondendl;}// 5. 统计词频mapstring,intcnt;cnt[word];// 自动初始化为0// 6. 自定义排序structcmp{booloperator()(constinta,constintb)const{returnab;// 降序}};mapint,string,cmpmp;multimap允许重复键multimapint,stringmmp;mmp.insert({key,value});// 插入允许多个相同keymmp.count(key);// 返回key的个数mmp.lower_bound(key);// 第一个key的位置mmp.upper_bound(key);// 第一个key的位置4️⃣ set集合基本操作#includesetusingnamespacestd;setints;// 声明自动去重排序unordered_setints;// 哈希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)coutx ;// 2. 去重vectorintv{1,2,2,3};setints(v.begin(),v.end());// 3. 查找第一个x的元素autoits.lower_bound(x);if(it!s.end())cout*it;// 4. 查找第一个x的元素autoits.upper_bound(x); 复杂度对比容器查找插入删除访问vectorO(n)O(1)*O(n)O(1)dequeO(n)O(1)O(n)O(1)queue-O(1)O(1)O(1)mapO(log n)O(log n)O(log n)O(log n)unordered_mapO(1)O(1)O(1)O(1)setO(log n)O(log n)O(log n)-*vector 尾部插入是 O(1)中间插入是 O(n) 竞赛选择指南需求推荐容器动态数组频繁访问vectorBFSqueue最短路Dijkstrapriority_queue需要排序去重set键值对需要有序map键值对不需要有序unordered_map两端操作deque快速查找元素是否存在unordered_set⚠️ 易错点提醒vector 越界v[i]不检查边界v.at(i)检查map 自动创建mp[key]不存在时会创建值为默认值迭代器失效删除元素后迭代器可能失效unordered 可能退化极端情况下退化为 O(n)优先队列默认大根堆小根堆要用greaterint