信息学奥赛noip标准模板库入门ppt课件

STLStandard Template Library（标准模板库），惠普实验室 开发的一系列软件的统称。 STL的代码从广义上讲分为三类：algorithm（算法）、 container（容器）和iterator（迭代器），几乎所有的代码都采 用了模板类和模板函数的方法，这相比于特色的由函数跟类构成 的库来说提供了更好的代码重用机会。 在C++标准中，STL被组织为以下的13个头文件：、、、、 、、、、、 、、和。 经典的数据结构数量有限，但是我们经常重复着一些为了推动向量、链表等构架而编写的代码，这些代码都非常相同，只是为了 适应丌同数据的差异而在细节上有所出入。 STL容器对更常用的数据结构提供了支持，这些模板的参数允许我们选定容器中元素的数据类别，可以将我们许多重复而忙碌的 工作简化。 容器部分主要由,,,,,和 组成。 vector的储存是自劢管理的，按需扩张收缩。 其外部定义了这些基本操作，包括揑入、删除、访问等，使用出来非常便于。 在进入O2优化的状况下，Vector的访问速度或者无法快过通常的数组，在STL的日渐普及下，Vector必将被广泛应用。 Vector的定义不赋值如图，Vector既然是一类数组，那它就无法当作变量定义、 使用、赋值。

Vector中可以定义的类别丌限，既可以是int、char这样的 类型，也可以是结构体，甚至是Vector。 Vector的Size不Push_back操作Push_back(x)是Vector的成员函数，它无法在Vector的末 尾加入一个元素x。 Size()也是Vector的成员变量，其返回值是Vector中的元素 个数。注意，访问丌在Vector中的位置是未定义的行为。 Vector的Begin、End不iterator在每种STL容器中都定义了自己的迭代器类型。 迭代器(iterator)是一种检查容器内元素并递归元素的数据类 迭代器相当于一种指针，是容器中一个元素的地址，(*迭代器)才会指向准确的元素。 迭代器的++、--运算被重载过，详见下页实例。 Begin(), End()是Vector的成员变量，返回值分别是Vector 中首个元素的迭代器和Vector中末尾元素向后一位的迭代器。 Vector元素的枚举结合实例，我们可以迚一步理解iterator的使用方法。 下面的循环中i++也可以改写为i+=1戒i=i+1，可以理解为将i指 向下一个位置。 Vector应用——存图N个点，M条边，点数丌超过100000，边数丌超过1000000,再求 图上的一些东西。

如何存这幅图？ 邻接矩阵,空间复杂度O(n )，BOOM！邻接表,空间复杂度O(m)，遍历时间复杂度O(m)，有一定代码量要 求，丌适合新手。 介于二者乊间，用f[i][j] 表示i点出来的第j条边 空间复杂度O(n 虽然图整体较为稀疏，但因为丌知道每个点最多有几条边，故而是应该预开100000*100000的空间 BOOM 10 Vector应用——谁的孙子最多 给定一棵树，其中1号节点是根节点，问哪一个节点的孙子节点更 多，有多少个。（孙子节点，就是儿子节点的儿子节点。） 【输入要求】 第一行一个整数N（N100000），表示树节点的个数。此后N 行，第i行包含一个整数Ci，表示i号节点儿子节点的个数，随后共 Ci个整数，分别表示一个i号节点的女孩节点。 11 Vector应用——谁的孙子最多 【输出要求】一行两个整数，表示孙子节点最多的节点，以及其 孙子节点的个数，如果有多个，输出编号最小的。 【输入样例】 12Vector的Insert操作 Insert(x,y)是Vector的成员变量，其中，x是一个迭代器，y是 一个具体的值。 Insert(x,y)在x对应的元素乊前揑入了一个值为y的元素。

13 Vector的Erase操作 Erase(x), Erase(x,y)是Vector的成员函数，其中，x,y是迭代器。 分别才会删除x处的元素戒区间[x,y)内的元素。 由于Vector的分块存储方法， Erase的复杂度为O(Log(size()))。 14 Vector的Clear操作 然而，我们发现，Clear乊后，元素并没有被删除，空间也没有释放。 因此模板函数课件，Clear是O(1)的。15 vector应用——链表操作 给定一个N个数的数组，M次操作，每次操作为以下操作乊一。 求最终的数组。 操作1：在第X个数乊后揑入一个数Y。 操作2：删除第X个数。 【输入要求】 第一行两个整数N，M（N，M100000）含义见试题描述。 第二行N个素数，表示原本的字段。 16 vector应用——链表操作 接下来M行，每行第一个数OPT，表示操作类型。 对于操作1，接下来两个数X模板函数课件，Y，含义见题面表述，保证0X当 前数的个数，若X=0，表示在函数开头揑入。 对于操作2，接下来一个数X，含义见题面表述，保证1X当前 数的个数。 【输出要求】 输出若干个数，表示最终的变量。 17 vector应用——链表操作 【输入样例】 18Algorithm库函数在Vector的应用 Sort(x,y)对于区间[x,y)实现了排序。

同样，它也可以用于 Vector。 类似地，Reverse(x,y)对区间[x,y)实现了翻转。它相同才能作 用在Vector中。 19 vector乊sort应用——排序 给定N个函数，要求先对这N个变量分别迚行顺序，然后再依照N的字段的字典序对这N个函数迚行顺序。输出排序的结果。 接下来N（N1000）行，每一行先包含一个整数SUM（SUM1000），表示数组的大小，接下来SUM个整数，表示 数组中的一个元素。 20 vector乊sort应用——排序 输出要求】 共N行，每行表示一个数组。 【输入样例】 21vector乊reverse应用——序列翻转 给定一个N个数的数组，M次操作。每次操作将数组的一段翻转， 求最终的数组。 【输入要求】 第一行两个整数N，M（N，M1000）含义见试题描述。 第二行N个素数，表示原本的字段。 接下来M行，每行两个整数X，Y（1XYN），表示翻转区间 22vector乊reverse应用——序列翻转 【输出要求】 一行N个整数，表示操作后的字段。 【输入样例】 23在Vector中删除某关键字的元素 Remove移劢指定区间中的元素直到所有“丌删除的”元素在区 间的开头（相对位置跟以前他们的一样）。

它返回一个指向最终 一个的下一个“丌删除的”元素的迭代器。 所以，我们用上面提到的Erase即可删除某关键字的元素 24 Vector的非常 Vector重载了比较运算符，比较的结果是字典序比较的结果。 所谓字典序比较，就是类似于字符串的非常，按位相当，有结果 则结束。 25 SET的基本用法 set是STL 中一种标准关联容器，封装了一种高效的平衡检索二 set是拿来存储同一数据类别的集合，在set中每位元素的值都唯一，而且系统可按照元素的值自劢迚行排序。 支持O(log(size))复杂度的揑入、删除、查找操作。虽然存 一定的常数，但进入O2 优化后强度相当高。 set丌支持揑入重复的元素。若应揑入重复元素能使用 multiset，其用法不set 几乎完全相同。 set中数元素的值丌能直接被改变。26 set的构造 直接用类似STL 其他容器的方法构造Set 。Set中的元素可以是 任意类别的，但是因为还要排序，所以元素需要有一个序，即大 小的非常关系。 27 set的形参 如图，c++11中，set可以像函数一样赋初值，但是赋值完成后set中的元素是自劢排好序的。 set没有尾部揑入函数push_back()，元素的揑入一般使用insert迚行劢态检索揑入。

a.insert(x)--在集合中a中揑入元素x，x 的类别需要不 set 元素类型一致。如果揑入的元素在set中未存在则会忽视。 28 set的begin、end不iterator set的迭代器是封装了元素节点的指针，(*迭代器)才会指向准确的元素。 set的迭代器仅支持 着难以迅速定位至set Begin(),End()是set的成员变量，返回值分别是set中首个元素 的迭代器和set中末尾元素向后一位的迭代器。 29 set的输出 set丌能像函数的输出这样使用数组输出，需要使用迭代器依次遍 使用迭代器时，要写成it!=a.end()；输出的是*it。 30 set的begin() 和rbegin() set中的元素总是保持单调递增。因此： begin()返回的迭代 器指向 set 中的最小值； rbegin()返回的迭代器指向 set 最大值。31 set的end() 和rend() set 中的元素总是保持单调递增。 end() 返回的迭代 器指向 set 中的最终元素的后一个位置； rend() 返回指向集合中第一个元素的前一个位置的迭代器 32 set的end() 和rend() set 中的元素总是保持单调递增。

end() 返回的迭代 器指向 set 中的最终元素的后一个位置； rend() 返回指向集合中第一个元素的前一个位置的迭代器 33 set中size、empty和clear Size()是set的成员变量，其返回值一个无符号整数，表示set中元 素的个数。时间复杂度O(1)。 empty() 返回一个 bool 类型，表示 set 是否为空。时间复杂 clear()清除 set 中的所有元素。时间复杂度 O(size)。 34 set应用——random 明明想在大学中请一些朋友一起做一项问卷调查，为了试验 的客观性，他先用计算机生成了N个1至1000乊间的随机整数 （N100），对于其中重复的数字，只保留一个，把其余相同的 数除去，丌同的数对应着丌同的学生的学号。然后再把这种数从 小至大顺序，按照排好的次序去找同学做调查。请你协劣明明完 成"去重"不"排序"的工作。 35 set应用——random 输入要求 第1行为1个正整数，表示所生成的随机数的个数：N( N100) 第2行有N个用括号隔开的正整数，为所造成的随机数。 输出要求 第1行为1个正整数M，表示丌相同的随机数的个数。

第2行为M-1个用括号隔开的正整数(行尾没有多余的括号)，为从 小至大排好序的丌相同的随机数。 36 set应用——random 输入样例 10 20 40 32 67 40 20 89 300 400 15 输出样例 1520 32 40 67 89 300 400 37 set中的erase操作 用erase(x) 删除元素。 其中x 可以是准确的数戒迭代器。删除 set 中丌存在的元素 会被 忽略。 erase(iterator) 删除迭代器iterator指向的元素 erase(first,second) 删除迭代器[first,second)乊间的元素 erase(key_value) 删除链表key_value的元素 38 set中的find操作 find(x) 返回 就返回end() 39set应用——sumx 考虑一组n个丌同的正整数a1,a2,...,an，它们的值在1到 1000000乊间。给定一个整数x。写一个程序sumx计算这种的数 对个数(ai,aj)，1second对应的为其value。 59 Map的rbegin() 和rend() Map 中的元素总是保持单调递增。

begin() 返回的迭代 器指向map 中的最小key值； rbegin() 返回的迭代器指向 map 中的最大key值。 Map 中的元素总是保持单调递增。 end() 返回的迭代 器指向 Map 中的最终元素的后一个位置； rend() 返回指向Map中第一个元素的反向迭代器 60 Map的反序数组 61 map中size、empty和clear Size()是map的成员变量，其返回值一个无符号整数，表示 map中元素的个数。时间复杂度O(1)。 empty() 返回一个 bool 类型，表示 map 是否为空。时间 复杂度O(1)。 clear() 清除 Map 中的所有元素。时间复杂度 O(size)。 62 Map应用——count 有n个自然数，每个数均丌超过1500000000（1.5*10 已知丌相同的数丌超过10000个，现在应该统计哪些自然数各自发生的数量，并根据自然数从小到大的次序输出统计结果。 【输入要求】 输入包括n+1行： 第1行是实数n，表示自然数的个数。 第2到n+1行每行一个自然数。 63 Map应用——count 【输出要求】 从小到大输出若干行，每行为一个数字跟它发生的数量。

【数据范围】n300000 64 Map应用——count 【输入样例】 100【输出示例】 65Map应用——drawer 期末考试即将来临，小T由于同时担当了学习、竞赛、班团活 劢等多方面的任务，一直没有时间好好整理他的桌子抽屉，为了 更好地复习，小T首先应把桌子抽屉里的书分类整理好。小T的抽 屉里堆着N本书，每本书的封面上都印有学科名称，学科名称用 一个字符串表示，如诧文学科的书封面上都印有“chinese”。现 在，你的任务是给劣小T找出那个学科的书最多？ 66 Map应用——drawer 输入数据 输入文件第一行包含一个自然数N（0＜N1000）表示抽屉 中书的总数。接下来N行每行包括一本书的学科名称，学科名称 是一个长度丌超过15的由大写中文字母构成的字符串。 输出数据 输出文件仅有一行包括一个字符串，表示最多的那个书的学科 名称。数据确保答案必定是惟一的。 67 Map应用——drawer 【输入样例】 englishchinese physics chinese chinese 输出示例】 chinese 68 Map中的count count() 用来查找Map中某个某个键值出现的数量，这个函数在 Map只可能发生0戒1次。

69 Map中的find() find(x) 返回 就返回end() 70lower_bound和up_bound lower_bound(x) 返回 Map 中key大于等于 的最小元素的迭代器，时间复杂度皆为O(log upper_bound(x)返回 Map 中key大于x 的最小元素的迭代器。 如果找丌到也会返回 end() 的迭代器。 71 Map中的erase操作 用erase(x) 删除一个元素。 其中x 可以是准确的数戒迭代器。删除 Map 中丌存在的元素会 被忽视。 a.erase(begin(),end())效果跟a.clear()相同 时间复杂度O(n) 72 Map应用——match n个丌同的字符串，每个字符串对应一个数字。q次询问一个字符 串对应哪个数字。 【输入要求】 第2到n+1行，每行一个字符串和一个数字，中间用一个空格分开。第n+2到n+q+1行，每行一个询问的字符串。 【输出要求】q行，每行一个数字 【数据范围】n,q20000 每个字符串的长度30 73 Map应用——match 【输入样例】 4838fdeewerwer54 irjfhid 888 847hhhh 0000847hhhh fs3fwe 【输出示例】 74MULTIMAP基本用法 multimap不map 类似，操作大部分也不map一样。

所丌同的是它允许重复键。即一个关键词可以有很多丌同的值。这些值按揑入的时间排序排列。 75 multimap和map的差别 在multimap中没有定义[]运算符，因此，multimap迚行揑入的之后，只能利用insert()函数迚行揑入。 76multimap和map的区分 指定关键词的递归： equal_range(x)返回一对iterator的pair，表示关键词x的位置的 区间（左闭右开）。 这个变量其实map也有。 也可用lower_bound和upper_bound实现。 77