1、STL入门1STL Standard Template Library（标准模板库），惠普实验室开发的一系列软件的统称。STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。2STL 在C+标准中，STL被组织为下面的13个头文件：、和。3容器（container）经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器对最
2、常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。容器部分主要由,和组成。4Vector简介 Vector是一种动态数组，是基本数组的类模板。vector 的存储是自动管理的，按需扩张收缩。需要头文件或头文件 其内部定义了很多基本操作，包括插入、删除、访问等，使用起来十分方便。在开启O2优化的情况下，Vector的访问速度甚至能够快过一般的数组，在STL的日益普及下，Vector必将被广泛应用。5Vector的定义与赋值 如图，Vector既然是一类数组，那它就能够当做数组定义、使用、赋值。Vector中可以定义的类型不限，既可以是i
3、nt、char这样的类型，也可以是结构体，甚至是Vector。6Vector的Size与Push_back操作 Push_back(x)是Vector的成员函数，它能够在Vector的末尾加入一个元素x。Size()也是Vector的成员函数，其返回值是Vector中的元素个数。注意，访问不在Vector中的位置是未定义的行为。7Vector的Begin、End与iterator 在每种STL容器中都定义了自己的迭代器类型。迭代器(iterator)是一种检查容器内元素并遍历元素的数据类型。迭代器相当于一种指针，是容器中一个元素的地址，(*迭代器)才会指向具体的元素。迭代器的+、-运算被重载过
4、，详见下页实例。Begin(),End()是Vector的成员函数，返回值分别是Vector中首个元素的迭代器和Vector中末尾元素向后一位的迭代器。8Vector元素的遍历 结合实例，我们可以进一步理解iterator的使用方式。下面的循环中i+也可以改写为i+=1或i=i+1，可以理解为将i指向下一个位置。9Vector应用存图 N个点，M条边，点数不超过100000，边数不超过1000000,再求图上的一些东西。如何存这幅图？邻接矩阵,空间复杂度O(n2)，遍历时间复杂度O(n2)，BOOM！邻接表,空间复杂度O(m)，遍历时间复杂度O(m)，有一定代码量要求，不适合新手。介于两者之间
5、，用fij 表示i点出去的第j条边 空间复杂度O(n2)遍历时间复杂度O(m)。虽然图整体较为稀疏，但由于不知道每个点最多有几条边，故还是需要预开100000*100000的空间 BOOM10Vector应用谁的孙子最多给定一棵树，其中1号节点是根节点，问哪一个节点的孙子节点最多，有多少个。（孙子节点，就是儿子节点的儿子节点。）【输入要求】第一行一个整数N（N100000），表示树节点的个数。此后N行，第i行包含一个整数Ci，表示i号节点儿子节点的个数，随后共Ci个整数，分别表示一个i号节点的儿子节点。11Vector应用谁的孙子最多【输出要求】一行两个整数，表示孙子节点最多的节点，以及其孙子
6、节点的个数，如果有多个，输出编号最小的。【输入样例】52 2 31 401 50【输出样例】1 112Vector的Insert操作 Insert(x,y)是Vector的成员函数，其中，x是一个迭代器，y是一个具体的值。Insert(x,y)在x对应的元素之前插入了一个值为y的元素。13Vector的Erase操作Erase(x),Erase(x,y)是Vector的成员函数，其中，x,y是迭代器。分别能够删除x处的元素或区间x,y)内的元素。由于Vector的分块存储方式，Erase的复杂度为O(Log(size()。14Vector的Clear操作 Clear()是Vector的成员函数
7、，使用后将Vector的Size()设置为0。然而，我们看到，Clear之后，元素并没有被删除，空间也没有释放。因此，Clear是O(1)的。15vector应用链表操作给定一个N个数的数组，M次操作，每次操作为下列操作之一。求最后的数组。操作1：在第X个数之后插入一个数Y。操作2：删除第X个数。【输入要求】第一行两个整数N，M（N，M100000）含义见试题描述。第二行N个整数，表示原来的数组。16vector应用链表操作接下来M行，每行第一个数OPT，表示操作类型。对于操作1，接下来两个数X，Y，含义见题面描述，保证0X当前数的个数，若X=0，表示在数组开头插入。对于操作2，接下来一个数X
8、，含义见题面描述，保证1X当前数的个数。【输出要求】输出若干个数，表示最后的数组。17vector应用链表操作【输入样例】5 31 2 3 4 51 1 62 12 2【输出样例】6 3 4 518Algorithm库函数在Vector的应用 Sort(x,y)对于区间x,y)实现了排序。同样，它也可以用于Vector。类似地，Reverse(x,y)对区间x,y)实现了翻转。它同样能够作用在Vector中。19vector之sort应用排序 给定N个数组，要求先对这N个数组分别进行排序，然后再根据N的数组的字典序对这N个数组进行排序。输出排序的结果。【输入要求】第一行一个整数N，表示数组数。
9、接下来N（N1000）行，每一行先包含一个整数SUM（SUM1000），表示数组的大小，接下来SUM个整数，表示数组中的一个元素。20vector之sort应用排序输出要求】共N行，每行表示一个数组。【输入样例】41 31 12 2 13 2 3 1【输出样例】11 21 2 3321vector之reverse应用序列翻转给定一个N个数的数组，M次操作。每次操作将数组的一段翻转，求最后的数组。【输入要求】第一行两个整数N，M（N，M1000）含义见试题描述。第二行N个整数，表示原来的数组。接下来M行，每行两个整数X，Y（1XYN），表示翻转区间X,Y。22vector之reverse应用序列
10、翻转【输出要求】一行N个整数，表示操作后的数组。【输入样例】5 21 2 3 4 52 44 5【输出样例】1 4 3 5 223在Vector中删除某关键字的元素Remove移动指定区间中的元素直到所有“不删除的”元素在区间的开头（相对位置和原来它们的一样）。它返回一个指向最后一个的下一个“不删除的”元素的迭代器。所以，我们用前面讲到的Erase即可删除某关键字的元素24Vector的比较Vector重载了比较运算符，比较的结果是字典序比较的结果。所谓字典序比较，就是类似于字符串的比较，按位比较，有结果则结束。25SET的基本用法 set 是 STL 中一种标准关联容器，封装了一种高效的平衡
11、检索二叉树红黑树。set是用来存储同一数据类型的集合，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。支持 O(log(size)复杂度的插入、删除、查找操作。虽然存 在一定的常数，但开启 O2 优化后效率非常高。set 不支持插入重复的元素。若要插入重复元素可使用 multiset，其用法与 set 几乎完全相同。set中数元素的值不能直接被改变。26set的构造 直接用类似 STL 其他容器的方式构造Set。Set中的元素可以是任意类型的，但是由于需要排序，所以元素必须有一个序，即大小的比较关系。27set的赋值如图，c+11中，set可以像数组一样赋初值，但是赋值完成后
12、set中的元素是自动排好序的。set没有尾部插入函数push_back()，元素的插入一般使用insert进行动态检索插入。a.insert(x)-在集合中a中插入元素x，x 的类型必须与 set 的元素类型一致。如果插入的元素在 set中已存在则会忽略。28set的begin、end与iterator迭代器(iterator)是一种检查容器内元素并遍历元素的数据类型。set的迭代器是封装了元素节点的指针，(*迭代器)才会指向具体的元素。set 的迭代器仅支持+和，不支持+=和 =。这意 味着无法快速定位到 set 中的第 k 个元素。Begin(),End()是set的成员函数，返回值分别是
13、set中首个元素的迭代器和set中末尾元素向后一位的迭代器。29set的输出set不能像数组的输出那样使用下标输出，需要使用迭代器依次遍历。使用迭代器时，要写成it!=a.end()；输出的是*it。30set的begin()和rbegin()set 中的元素总是保持单调递增。因此：begin()返回的迭代 器指向 set 中的最小值；rbegin()返回的迭代器指向 set 中的 最大值。31set的end()和rend()set 中的元素总是保持单调递增。end()返回的迭代 器指向 set 中的最后元素的后一个位置；rend()返回指向集合中第一个元素的前一个位置的迭代器32set的en
14、d()和rend()set 中的元素总是保持单调递增。end()返回的迭代 器指向 set 中的最后元素的后一个位置；rend()返回指向集合中第一个元素的前一个位置的迭代器33set中size、empty和clearSize()是set的成员函数，其返回值一个无符号整数，表示set中元素的个数。时间复杂度O(1)。empty()返回一个 bool 类型，表示 set 是否为空。时间复杂 度 O(1)。clear()清除 set 中的所有元素。时间复杂度 O(size)。34set应用random 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000
15、之间的随机整数（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成去重与排序的工作。35set应用random输入要求 第1行为1个正整数，表示所生成的随机数的个数：N(N100)第2行有N个用空格隔开的正整数，为所产生的随机数。输出要求 第1行为1个正整数M，表示不相同的随机数的个数。第2行为M-1个用空格隔开的正整数(行尾没有多余的空格)，为从小到大排好序的不相同的随机数。36set应用random输入样例1020 40 32 67 40 20 89 300 400 15
16、输出样例815 20 32 40 67 89 300 40037set中的erase操作用 erase(x)删除元素。其中 x 可以是具体的数或迭代器。删除 set 中不存在的元素 会被忽略。erase(iterator)删除迭代器iterator指向的元素erase(first,second)删除迭代器first,second)之间的元素erase(key_value)删除键值key_value的元素38set中的find操作find(x)返回 x 元素的迭代器，如果找不到 x 就返回 end()的 迭代器。39set应用sumx 考虑一组n个不同的正整数a1,a2,.,an，它们的值在1到
17、1000000之间。给定一个整数x。写一个程序sumx计算这样的数对个数(ai,aj)，1=ij=n并且ai+aj=x。输入要求 标准输入的第一行是一个整数n(1=n=1000000)。第二行有n个整数表示元素。第三行是一个整数x(1=x=2000000)。输出要求 输出一行包含一个整数表示这样的数对个数。40set应用sumx输入样例95 12 7 10 9 1 2 3 1113输出样例3知识点及提示 不同的和为13的数对是(12,1),(10,3)和(2,11)。41lower_bound和upper_boundlower_bound(x)返回 set 中大于等于 x 的最小元素的迭代器。
18、upper_bound(x)返回 set 中大于 x 的最小元素的迭代器。如果找不到也会返回 end()的迭代器。42multiset multiset和set的定义和成员函数都相同。multiset和set的区别是：set插入的元素不能相同，但是multiset可以相同。如果删除元素x,那么在定义的比较关系下和x相等的所有元素都会被删除。count(x)：set能返回或者，multiset是有多少个返回多少个。43multiset应用dec给定N个数Ai，以及一个正整数C，问有多少对i,j，满足Ai-Aj=C。输入要求 第一行输入两个空格隔开的整数N和C 第2至N+1行每行包含一个整数 Ai
19、输出要求 输出一个数表示答案。44multiset应用dec输入样例5 321425输出样例345PAIR的基本用法 pair是一种模版类型，又称二元组。每个pair 可以存储两个值。这两种值无限制。也可以将自己写的struct的对象放进去，或者可以说pair是一个二元组的结构体，定义完成的pair类型可以用在多种场合。定义，例如：pair p;pair p;46PAIR的基本用法 pair是一种模版类型，又称二元组。pair p;pair p;pairchar,pair p;/也可以这样定义一个三元组47pair的使用pair的赋值paira;方式一：make_pair(233,a);方式二
20、：a.first=233;a.second=a;这两种方式都可以实现对a的赋值，建议用方式一48pair的使用pair的使用赋值完成后使用第一关键字要用a.first表示,第二关键字用a.second表示支持以first为第一关键字，second为第二关键字的比较函数(,=,=,!=)49pair应用买蛋糕2 今天是路路的生日，生日蛋糕自然是少不了。路路的朋友们一起去蛋糕店来买蛋糕，可是等一行人到了蛋糕店之后，发现那里是人山人海啊-_-。这下可把店家给急坏了，因为人数过多，需求过大，所以人们要等好长时间才能拿到自己的蛋糕。由于每位客人订的蛋糕都是不同风格的，所以制作时间也都不同。老板为了最大限
21、度的使每位客人尽快拿到蛋糕，因此他需要安排一个制作顺序，使每位客人的平均等待时间最少。这使他发愁了，于是他请你来帮忙安排一个制作顺序，使得每位客人的平均等待时间最少。50pair应用买蛋糕2输入要求 输入有两行。第一行是一个整数n，表示有n种蛋糕等待制作（1n100）。第二行有n个数，第i个数表示第i种蛋糕的制作时间。输出要求 输出包括一行，有n个整数，整数间用空格隔开，行末没有空格，是蛋糕的制作顺序，每个数即是蛋糕的编号。51pair应用买蛋糕2输入样例84 5 3 3 1 4 6 7输出样例5 3 4 1 6 2 7 852MAP&MULTIMAP基本用法Map是STL的一个关联容器，它提
22、供一对一的数据处理能力，map不允许重复元素。其中第一个称为关键字key，每个关键字只能在map中出现一次，第二个称为该关键字的值value，元素的次序由它们的key决定，和value无关。53MAP&MULTIMAP基本用法map内部自建一颗红黑树，这颗树具有对数据自动排序的功能，所以map根据元素的key自动对元素进行排序。这么一来，根据已知的key搜寻某个元素时，时间复杂度为O(1)，而根据已知value搜寻元素时，性能就很糟糕。可起到hash表的作用。54Map的功能自动建立Key value的对应。key 和 value可以是任意你需要的类型。根据key值快速查找记录。快速插入Key
23、-Value 记录。快速删除记录。根据Key修改value记录。遍历所有记录。55Map的定义需要头文件 或 构造函数：map a;map对象是模板类，需要关键字和存储对象两个模板参数。例如 map a;这样就定义了一个用int作为索引,并拥有相关联的指向string的指针。56Map的赋值Map赋值的两种方法：用insert函数插入pair数据、用数组方式插入数据。以上两种用法的区别:用insert函数插入数据，在数据的插入上涉及到map关键字的唯一性这个概念。即当map中有这个关键字时，insert操作无效的。用数组方式它可以覆盖以前该关键字对应的值。时间复杂度皆为O(log n)。57M
24、ap的Begin、End与iterator map的迭代器(iterator)是一种检查容器内元素并遍历元素的数据类型。Begin(),End()是map的成员函数，返回值分别是map中首个元素的迭代器和末尾元素向后一位的迭代器。map 的迭代器仅支持+和。时间复杂度 O(1)58Map的输出map的单个value可以像数组那样使用下标输出。要输出所有元素需要使用迭代器依次遍历。输出it-first对应的关键字key输出it-second对应的为其value。59Map的rbegin()和rend()Map 中的元素总是保持单调递增。begin()返回的迭代 器指向map 中的最小key值；r
25、begin()返回的迭代器指向 map 中的最大key值。Map 中的元素总是保持单调递增。end()返回的迭代 器指向 Map 中的最后元素的后一个位置；rend()返回指向Map中第一个元素的反向迭代器60Map的反序遍历61map中size、empty和clear Size()是map的成员函数，其返回值一个无符号整数，表示map中元素的个数。时间复杂度O(1)。empty()返回一个 bool 类型，表示 map 是否为空。时间复杂度 O(1)。clear()清除 Map 中的所有元素。时间复杂度 O(size)。62Map应用count 有n个自然数，每个数均不超过150000000
26、0（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【输入要求】输入包含n+1行：第1行是整数n，表示自然数的个数。第2到n+1行每行一个自然数。63Map应用count【输出要求】从小到大输出若干行，每行为一个数字和它出现的次数。【数据范围】n30000064Map应用count【输入样例】8 2 4 2 4 5 100 2 100【输出样例】2 34 25 1100 265Map应用drawer 期末考试即将来临，小T由于同时肩负了学习、竞赛、班团活动等多方面的任务，一直没有时间好好整理他的课桌抽屉，为了更好
27、地复习，小T首先要把课桌抽屉里的书分类整理好。小T的抽屉里堆着N本书，每本书的封面上都印有学科名称，学科名称用一个字符串表示，如语文学科的书封面上都印有“chinese”。现在，你的任务是帮助小T找出哪个学科的书最多？66Map应用drawer输入数据 输入文件第一行包含一个自然数N（0N1000）表示抽屉中书的总数。接下来N行每行包含一本书的学科名称，学科名称是一个长度不超过15的由小写英文字母组成的字符串。输出数据 输出文件仅有一行包含一个字符串，表示最多的那种书的学科名称。数据保证答案一定是唯一的。67Map应用drawer【输入样例】5englishchinesephysicschin
28、esechinese输出样例】chinese68Map中的countcount()用来查找Map中某个某个键值出现的次数，这个函数在Map只可能出现0或1次。69Map中的find()find(x)返回 x 元素的迭代器，如果找不到 x 就返回 end()的 迭代器。时间复杂度皆为O(log n)70lower_bound和up_boundlower_bound(x)返回 Map 中key大于等于 x 的最小元素的迭代器，时间复杂度皆为O(log n)。upper_bound(x)返回 Map 中key大于 x 的最小元素的迭代器。如果找不到也会返回 end()的迭代器。71Map中的eras
29、e操作用 erase(x)删除一个元素。其中 x 可以是具体的数或迭代器。删除 Map 中不存在的元素会被忽略。a.erase(begin(),end()效果和a.clear()相同时间复杂度O(n)72Map应用matchn个不同的字符串，每个字符串对应一个数字。q次询问一个字符串对应什么数字。【输入要求】第1行n，q。第2到n+1行，每行一个字符串和一个数字，中间用一个空格隔开。第n+2到n+q+1行，每行一个询问的字符串。【输出要求】q行，每行一个数字【数据范围】n,q20000 每个字符串的长度3073Map应用match【输入样例】5 3fs3fwe 34838fdeewerwer
30、54irjfhid 888847hhhh 10000 00000847hhhhfs3fwe【输出样例】01374MULTIMAP基本用法 multimap简介&功能 multimap与 map 类似，操作大部分也与map一样。所不同的是它允许重复键。即一个关键词可以有很多不同的值。这些值按插入的时间顺序排列。75multimap和map的区别 在multimap中没有定义运算符，因此，multimap进行插入的时候，只能利用insert()函数进行插入。使用find(x)查找返回每种关键词的所有元素的第一个元素的迭代器。76multimap和map的区别指定关键词的遍历：equal_range(x)返回一对iterator的pair，表示关键词x的位置的区间（左闭右开）。这个函数其实map也有。也可用lower_bound和upper_bound实现。77
