文章目录容器介绍一、C常用容器有哪些二、逐个容器详细介绍算法介绍一、常见基础算法有哪些二、逐个算法讲解说明今天来讲解一些STL常用的容器和算法在算法竞赛中能巧用STL来做题容器介绍一、C常用容器有哪些有stringvectorqueuestackdequemapsetunordered_map unordered_setpriority_queue大概就这么多由于stringvector容器比较简单就不怎么讲了二、逐个容器详细介绍1栈stack其满足 先进后出原理定义stackintstk//能定义的类型不止这一个栈的核心操作1push(x)入栈把x放进栈顶2top看栈顶元素最上面那个3pop() 弹出栈顶删除最上面的那个不返回值4empty()判断栈空不空空返回1否则返回05size() 返回栈里面的元素个数栈的注意事项1栈不能下标访问stk[0]直接报错 2栈不能遍历不能用for循环挨个取 3pop()只删除不返回值要取值先top()2队列queue其遵守 先进先出 原理定义queueintq;//同样是不止可以定义int类型队列的常用操作1q.push(x)队尾入队从队伍末尾加一个元素2q.front()对首元素排队最前面那个(要出队的那个)3q.back()队尾元素最后面刚进来的那个元素4q.pop()队首出队删除最前面那个不返回值5q.empty()判断是否为空6q.size()返回当前队伍有多少元素队列注意事项:1:不能下标访问q[0] 直接报错 2不能中间遍历不能随便插中间 3只能尾进头出3双端队列deque定义dequeintdq//同样是不止定义这一种类型deque双头开口的数组头能加头能删尾能加尾能删还能像普通数组一样下标随机访问deque的常用操作1头尾增删 dq.push_front(10);// 头部插入dq.push_back(20);// 尾部插入​ dq.pop_front();// 删除头部dq.pop_back();// 删除尾部2访问首尾 dq.front();// 队首dq.back();// 队尾3支持下标访问 dq[0]5;coutdq[1];4大小判空清空 dq.size();dq.empty();dq.clear();5能用assign// 生成 4 个 7dq.assign(4,7);// 复制另一个容器区间dq.assign(v.begin(),v.end());deque能实现队列和栈它们两个的功能并且还能访问下标能前插后插前删后删但中间不能乱插并且用的时候逻辑不能乱了。4mapmap 就是「字典 / 对照表」存 键 (key)→值 (value) 一一对应map的特点1它里面的key(也可以说是元素吧)自动唯一重复插不进去 2自动按照key从小到大排序 3底层红黑树速度O(log n) 4:可以用count()来查有没有某个key 5不能用insert()以外乱搞不能assign不能下标遍历以外乱玩定义// 格式map键类型, 值类型 变量名;mapint,intmp;// int键 → int值mapstring,intmp2;// 字符串键 → int值mapchar,doublemp3;// char键 → 浮点值按照左边的键来排序不能push_backkey不能重复重复赋值会覆盖旧值常用操作1插入/赋值 mapstring,intmp;mp[张三]18;mp[李四]20;2取值 coutmp[张三];// 输出 183用count()判断key是否存在if(mp.count(张三)){cout有这个人;}else{cout没有;}4遍历mapfor(autop:mp){// p.first 是keyp.second 是valuecoutp.first p.secondendl;}5删除清空 mp.erase(张三);// 删除某个键mp.clear();// 全部清空mp.size();// 个数mp.empty();// 是否为空5unordered_map它和map的作用几乎一样区别map自动排序它不排序乱序但是查找的更快 用法的话同上差不多 需要最后按 key 从小到大输出 → 用 map 只需要存键值对、查找、统计次数不需要排序 → 优先 unordered_map 更快6setset自动去重自动从小到大排序的容器你放什么进去重复的-自动丢掉乱序的-自动排好序特点1不允许重复 2自动从小到大排序 3只能存单个元素定义setintst;// 整数集合setcharst2;// 字符集合setstringst3;// 字符串集合setdoublest4;// 浮点数集合常用的操作1插入st.insert(x)st.insert(5);st.insert(2);st.insert(5);// 重复自动丢掉2判断有没有 xst.count(x)if(st.count(5)){cout存在;}3遍历自动从小到大for(autox:st){coutx ;}4删除 st.erase(5);// 删除元素 5st.clear();// 清空5大小判空 st.size();// 几个元素st.empty();// 空不空set注意事项1不能访问下标 2不能用assign 3不能用push_back 4不能修改里面的值什么时候用set呢1 需要去重 2 需要自动排序 3 需要快速判断元素是否存在7 unordered_setunordered_set 只去重不排序乱序查找更快的集合 和set的区别set自动去重自动升序排序 unordered_set自动去重不排序乱序速度更快 用法的话和set基本一致可以看上面。8priority_queue作用自动帮你排序的队列每次取都是当时最大/最小元素默认是大根堆队首永远是最大值 cpp#includequeuepriority_queueintq;小根堆 priority_queueint,vectorint,greaterintq;支持所有类型。核心成员函数q.push(x);// 入堆自动排序q.top();// 取堆顶元素最大/最小q.pop();// 弹出堆顶q.empty();// 判断空q.size();// 元素个数注意事项1没有front(),没有back() 2:只能看top(),只能删pop()堆顶 3:不能下标访问不能遍历不能用assign insertcounterase算法介绍一、常见基础算法有哪些今天介绍的成员函数有assigninsertcounteraselower_bound,upper_bound二、逐个算法讲解说明1assign作用清空容器原有的所以内容重新批量复制覆盖​ 哪些容器能用 vectorstringdeque只有这三个​ 用法1assign(个数值),表示生成n个相同的元素覆盖原有的内容。vectorintv;v.assign(5,8);// 结果5个8 → [8,8,8,8,8]//同样的他能用于其他类型的比如string类型的话可以是s.assign(4,x) 表示对s清空并且开一个4个单位的x结果是“xxxx”​ 用法2assign(起始迭代器结束迭代器) 把另一个容器的区间内容复制过来覆盖自己vectorinta{1,2,3,4};vectorintb;// 把 a 全部复制给 bb.assign(a.begin(),a.end());b.assign(a.begin(),a.begin()3);// 只复制前3个string s1hello;string s2;s2.assign(s1.begin(),s1.end());2insertinsert插入元素​能用容器vectorstringdequesetmapstackqueue不能用​1vector/string/dequevectorintv{1,2,3};v.insert(v.begin()1,99);// 变成1,99,2,3vectorintv{1,2,3};v.insert(v.begin()1,99);// 变成1,99,2,3string sabc;s.insert(s.begin()1,x);// 变成 a x b c2:setsetintst;st.insert(5);st.insert(2);st.insert(5);// 重复自动丢掉​ 3:mapmapint,stringmp;mp.insert({1,小明});mp.insert({2,小红});3count作用统计某个值在容器里出现的个数 ​对集合/映射来说只能来判断有没有这个元素哪些容器能用setmap vectordequestring无自带count但是可以用算法 stackqueue完全没有count​set用法setintst;st.insert(5);coutst.count(5);// 1coutst.count(9);// 0map用法mapstring,intmp;mp[张三]18;coutmp.count(张三);// 1coutmp.count(李四);// 0​ vector/deque/string用法#includealgorithmvectorintv{1,2,2,3,2};// 统计2出现几次intcntcount(v.begin(),v.end(),2);coutcnt;// 3string saabcc;intcntcount(s.begin(),s.end(),c);4erase哪些容器能用vector,string,deque,set,map(stack,queue不能用)​1vector/string/deque用法vectorintv{10,20,30,40};v.erase(v.begin()1);// 删除第 1 个位置 → 删掉 20​2setsetintst;st.insert(5);st.erase(5);// 直接删掉 5​3mapmapint,stringmp;mp[1]小明;mp.erase(1);// 删掉 key15:lower_bound和upper_bound其前提是只能用在有序的东西上适用于vector(有序)set(本身有序)map(本身有序)假如你找的数是x lower_bound(起点终点x)//找到第一个“”大于等于x“的位置 upper_bound(起点终点x)//找到第一个“大于x”的位置对于vector来说首先得是一个有序的数组举个例子1355579 找x5 lower_bound-指向第一个5 upper_bound-指向7在vector里面怎么用呢vectorintv{1,3,5,5,5,7,9};// 找 5 的第一个位置autoit1lower_bound(v.begin(),v.end(),5);// 找 5 的第一个位置autoit2upper_bound(v.begin(),v.end(),5);在set/map里怎么用呢由于他们自带成员函数autoitst.lower_bound(x);autoitst.upper_bound(x);