《STL容器》第一课第一课程序王国的百宝箱——认识STL第一幕程序王国的新挑战1、很久很久以前。1程序王国里有一位小程序员——小C。他刚学会数组。每天都在用数组解决问题。2例如存10个同学成绩。int score[10];存100个数字。int a[100];存1000个学生编号。int id[1000];3直到有一天……国王给他出了几个新的任务。2、第一关学生越来越多1国王说今天学校来了很多学生。先来10个。过一会又来了20个。下午又来了100个。晚上又来了500个。请你把所有学生都保存下来。小C想我用数组于是写int stu[10];2可是……后来来了第11个学生。怎么办数组已经满了3只能重新开一个更大的数组。例如int stu[100];然后把前10个人再复制过去。是不是很麻烦如果又来了1000个人呢还要重新复制一次。4数组最大的缺点大小固定。建立以后不能自动变大。就像一个盒子。里面只能放10个苹果。第11个苹果放不进去。3、第二关删除一个学生1国王继续说第5个学生退学了。请删除。2数组1 2 3 4 5 6 7 8删除5以后。要变成1 2 3 4 6 7 8怎么办3只能这样6往前搬 7往前搬 8往前搬全部搬一次。如果有100万个数据呢是不是很慢4、第三关查名字1现在不是数字。而是Tom 95 Jack 88 Lucy 99 Mike 1002老师问Tom多少分数组怎么办只能Tom? 第一个不是 第二个不是 第三个不是 第四个找到了一个一个找。是不是越来越慢5、第四关实时排行榜1比赛开始了。不断有人交题。分数不断变化。2老师每次都问第一名是谁数组怎么办每次排序。sort(...)3如果一分钟问100次呢排序100次。是不是太累了6、第五关排队买冰淇淋1操场上。大家开始排队。先来的先买。这时候。数组也能做。2但是前面买完一个。后面所有人都要往前移动。是不是又搬家了7、第六关盘子游戏1老师把盘子一层一层叠起来。只能最后放上去。最后拿下来。2数组虽然也能做。程序员希望有专门管理盘子的工具。8、第七关电话号码本1老师问张三 电话是多少2数组怎么办存两列名字 电话3然后一个一个找。如果有10万人找半天。9、第八关去掉重复数字1例如5 3 8 5 9 3 82要求不重复的留下3 5 8 93数组怎么办不断比较。十分麻烦。10、小C崩溃了1他说为什么所有事情都让我用数组2程序王国的大法师笑了。他说孩子。不是所有事情都应该用数组。不同的问题。可以使用不同的工具。第二幕百宝箱出现了1、大法师打开一个金色宝箱。里面放着很多神奇工具。他说这个宝箱就是STLStandard Template Library中文标准模板库。里面装着各种已经做好的数据结构。不用自己重新发明。直接拿来用。2、百宝箱里的工具1他拿出第一件工具。vector会自己长大的盒子。放满了自己变大。2第二件。queue排队神器。先来的先出去。3第三件。stack盘子神器。最后放进去。最先拿出来。4第四件。priority_queue自动排行榜。不用排序。第一名永远放最前面。5第五件。map神奇字典。输入名字。马上找到成绩。6第六件。set自动去重。放进去两个5。最后只留下一个。7第七件。unordered_map超级哈希字典。查找速度飞快。8第八件。unordered_set超级去重神器。速度最快。STL八大神器英文名称常见中文名称容易理解的名字像什么最适合做什么vector动态数组会长大的盒子 会变大的盒子保存很多数据queue队列排队队伍 排队BFS、先来先服务stack栈盘子堆️ 一摞盘子撤销、括号匹配、DFSpriority_queue优先队列自动排行榜 排行榜最大值、最小值、Top Kmap映射电话本、字典 电话本根据名字找信息set集合魔法集合 不重复的收藏盒去重、自动排序unordered_map无序映射哈希映射超级电话本⚡ 哈希电话本极速查找unordered_set无序集合哈希集合超级收藏盒⚡ 哈希集合极速去重① vector —— 动态数组会长大的数组同学们以前学的是数组Array今天认识动态数组Dynamic Array为什么叫动态因为它会自己长大。所以vector 动态数组② queue —— 队列队列就是排队。大家小时候都排过队。所以queue就是队列。③ stack —— 栈有的同学还不知道栈是什么。我们可以理解成一摞盘子只能在上面放新的盘子拿走的时候也只能在上面拿。以后我们讲栈顶top大家马上知道是最上面的盘子。④ priority_queue —— 优先队列它的中文叫优先队列。就是谁优先级最高。谁站最前面。就像比赛排行榜。或者医院急诊。重病的人先看。这就是优先队列。⑤ map —— 映射它的中文叫映射。我们可以把它理解成一本电话本。或者一本字典。例如张三 → 100分 李四 → 98分 王五 → 90分名字。映射到。成绩。所以叫映射Map。⑥ set —— 集合有的同学数学里已经学过集合。例如{1,2,3}特点没有重复。所以set就是集合。⑦ unordered_map这个名字特别长。unordered意思无序。map映射。所以unordered_map就是无序映射。因为里面使用哈希(Hash)。我们也叫哈希表。也叫哈希映射无序映射⑧ unordered_set同理。unordered无序。set集合。就是无序集合。或者哈希集合。一句口诀数组太小会发愁vector长大不用愁。排队买饭用queue盘子叠高叫stack。找第一名找priority_queue查电话本用map。去掉重复找set想要更快用unordered。第三幕第一个 STL 程序1、想使用 STL需要先请工具出场。#include vector #include iostream using namespace std; int main() { vectorint nums; nums.push_back(10); nums.push_back(20); nums.push_back(30); cout 盒子里的数字有 endl; for (int x : nums) { cout x ; } cout endl; return 0; }运行结果盒子里的数字有 10 20 302、程序解释#include vector把这个工具请进来。vectorint nums;创建一个会长大的数字盒子。push_back()把新数字放到盒子最后。for (int x : nums)把盒子里的每个数字依次拿出来看看。我们今天先认识这件工具下节课就专门学习它。第四幕小游戏——我是STL管理员第一题学校开始排队打饭。应该用✅ queue第二题保存100万个学生成绩。人数不知道。应该✅ vector第三题撤销上一步操作。应该✅ stack第四题找第一名。应该✅ priority_queue第五题输入姓名查电话。应该✅ map第六题去掉重复数字。应该✅ set第七题查找速度要特别快。应该✅ unordered_map第八题快速去重。应该✅ unordered_set第五幕课堂挑战请学生思考并说明理由。一个视频网站要保存每天上传的新视频视频数量无法提前确定应该用哪个容器地铁站检票乘客按到达顺序进站应该用哪个容器浏览器的“后退”按钮需要返回上一个网页应该用哪个容器游戏实时显示积分最高的玩家应该用哪个容器班级通讯录根据姓名查电话号码应该用哪个容器统计一篇文章中出现过哪些不同的单词应该用哪个容器判断一个用户名是否已经注册而且要求查询尽可能快应该用哪个容器请学生先说出生活中的对应场景再说出容器名称建立需求→工具的思维。本课总结今天我们没有学习代码大家学会了一件更重要的事情优秀的程序员是先思考这个问题最适合用什么工具。