STL是C++的标准模板库，英文全称是Standard Template Library，它稍微有点复杂，操作很多，但是非常实用。STL的目的是标准化常用的组件，这样就不用重新开发了，可以使用现成的组件来提高编程效率。它是由Alexander Stepanov等人在惠普实验室工作时所开发出来的，从根本上说，STL是vector，set，map等容器的集合。
本实训主要设置了六个关卡来教学和实践vector，set和map：
- 第一关：介绍向量
vector的相关操作并设计了一些任务，同时需要调用vector的相关操作来完成； - 第二关：设计了一个二维动态数组的应用，使用
vector能够非常方便解决该问题； - 第三关：介绍集合
set的相关操作，并运用这些基本操作解决设定的小任务； - 第四关：基于
set求解一段英语文本中的出现的26个英文字母（区分大小写）； - 第五关：介绍键值对映射
map的一些操作，运用map维护一个学生成绩管理系统，并提供查询功能； - 第六关：运用键值对映射
map统计一段英语文本中的26个英文字母出现的次数（区分大小写）。
第1关：STL模板之动态数组：向量vector的操作
任务描述
本关任务：仔细阅读下文向量vector的相关操作，并使用vector完成对n个整数序列的插入、删除和排序功能。
相关知识
为了完成本关任务，你需要掌握：1.向量的概念；2.插入元素；3.删除元素；4.基于sort对向量排序；5.遍历向量；6.清空向量。
向量的概念
向量vector：是一种顺序容器，与数组类似，但它比数组更优越。数组不能动态拓展，在程序运行的时候可能造成内存浪费和访问越界。而vector正好可以弥补这一缺陷，可动态分配和拓展内存，它的随机访问快，在中间插入和删除慢，但在末端插入和删除快。
向量作为基本数组的类模板，被包含在vector头文件中，定义方式如下（注意搭配algorithm和using namespace std一起使用）：
vector<int> v1，定义一个元素为类型为int整型的向量v1vector<string> v2(10)，定义一个元素为类型为string字符串类型的向量v2，初始存储空间大小为10，每个元素初始为空串vector<node> v3，定义一个元素为类型为node类型的向量v3，其中node一般是结构体等自定义数据类型
插入元素
往向量插入一个元素通过调用push_back()方法实现（在向量末尾插入），另外也可以通过下标访问的方式直接在指定位置插入元素（前提是该位置已经被分配内存空间），如下实例：
1 vector <int> vec; // 创建一个整型向量vec 2 vec.push_back(1); // 向vec插入一个元素1 3 vec.push_back(2); // 向vec插入一个元素2 4 vec[1] = 3; // 直接在位置1插入元素3，原来的元素2被元素3覆盖了 5 // 目前vec包含 1, 3两个元素
删除元素
向量的删除与插入相对应，包含队尾删除和指定位置删除：队尾删除通过调用pop_back()方法，注意，它并不会返回被删除的元素；指定位置的删除是基于迭代器iterator 实现的，迭代器相对应数组的指针，指向向量的存储地址，通过调用erase(iterator pos)方法删除迭代器位置pos所在的元素，基于上述vec的实例如下：
1 vec.pop_back(); // 删除了元素3 2 vector<int>::iterator pos = vec.begin(); //定义一个vector<int>的迭代器pos，并指向vec的首地址 3 cout<<*pos; // 与指针一样，通过*访问地址上的值，输出为1 4 vec.erase(pos); // 删除迭代器地址pos及其元素，目前pos为vec首地址，元素值为1，删除之后元素为空，不包含任何元素了
基于sort对向量排序
向量是基于数组的类模板，同样可以用sort函数完成排序，使用方式如下：
sort(vec.begin(), vec.end()); // 默认从小到大排序
遍历向量
向量的遍历可以通过下标访问和迭代器访问的方式：
1 for(int i=0;i<vec.size();i++) // size()返回当前向量vec的大小 2 cout<<vec[i]; 3 for(vector<int>::iterator it=vec.begin();it!=vec.end();it++) 4 cout<<*it;
清空向量
向量的清空通过调用clear()方法实现，清空后向量大小变为0：
1 vec.clear()
编程要求
本关的编程任务是补全右侧代码片段main中Begin至End中间的代码，具体要求如下：
- 创建一个整型类型的向量
vec； - 读取数据：序列个数
n，以及n个整数并插入向量vec； - 通过
erase操作删除向量vec中的重复元素：保留第一次出现的元素，删除之后出现的重复元素； - 使用
Algorithm模板函数sort对向量vec里的元素从小到大排序； - 遍历向量
vec并输出：元素中间空格隔开，末尾加换行符\n； - 调用
clear清空向量。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
7
1 2 3 1 2 3 4
预期输出：
1 2 3 4
0
输入格式：
第一行：序列个数n
第二行：n个整数序列
输出格式：
第一行：遍历并输出向量，中间空格隔开，末尾换行\n
第二行：非学员输出，数值0用于检测向量是否清空
开始你的任务吧，祝你成功！
1 // 2 // main.cpp 3 // step1 4 // 5 // Created by ljpc on 2018/7/23. 6 // Copyright ? 2018年 ljpc. All rights reserved. 7 // 8 9 #include <iostream> 10 #include <algorithm> 11 #include <vector> 12 using namespace std; 13 14 int main(int argc, const char * argv[]) { 15 16 17 // 请在这里补充代码，完成本关任务 18 /********* Begin *********/ 19 // 1.构建整型向量vec 20 vector<int> vec; 21 22 // 2.读取数据：序列个数n，以及n个整数并存入向量vec 23 int n; 24 cin>>n; 25 for(int i=0; i<n; i++) { 26 int m; 27 cin>>m; 28 vec.push_back(m); 29 } 30 31 // 3.删除向量vec中的重复元素 32 sort(vec.begin(),vec.end()); 33 auto last = std::unique(vec.begin(),vec.end()); 34 vec.erase(last,vec.end()); 35 36 37 // 4.使用Algorithm模板函数sort对vec排序：从小到大 38 sort(vec.begin(),vec.end()); 39 40 // 5.遍历向量vec并输出，元素中间空格隔开，末尾加换行符'\n' 41 for(vector<int>::iterator it=vec.begin();it!=vec.end();it++) cout<<" "<<*it; 42 cout<<endl; 43 44 // 6.清空向量vec 45 vec.clear(); 46 47 /********* End *********/ 48 printf("%d\n", int(vec.size())); 49 50 return 0; 51 }
第2关：STL模板之动态数组：向量vector的应用
任务描述
本关任务：在一座城池中有N个谷仓，每个谷仓分别有Ni袋粮食并堆成了一列，重量分别为Wj，为了应对外敌，通常需要在谷仓间调动粮食，每次调动只会选择粮堆最上面的一袋粮食运走，并放在目的谷仓粮堆的最上面。
相关知识
为了完成本关任务，你需要掌握：1.向量的相关操作，2.嵌套使用向量模拟二维动态数组。
向量的相关操作
粮食调动是在粮堆的最上面进行的操作，涉及的向量操作为push_back和pop_back，详细的向量具体操作和运用请参考STL模板之动态数组：向量vector的操作。
嵌套使用向量模拟二维动态数组
谷仓的数量在不同的测试用例下是不同的，每个谷仓中的粮食袋数是动态变化的，因此，可以使用二维的动态数组来求解，既方便又节约内存。
- 第一步：定义一个以粮食重量
int为数据类型的动态数组vector<int>； - 第二步：定义一个以粮食重量向量
vector<int>为数据类型的动态数组vector<vector<int> > vec。
这样，vec的第一维下标就表示谷仓的ID，第二维就是对应谷仓的各袋粮食的重量。
编程要求
本关的编程任务是补全右侧代码片段main中Begin至End中间的代码，具体要求如下：
-
创建一个
vector<vector<int> > vec二维动态向量，读取各个谷仓的初始粮食状况； -
基于向量的
push_pack和pop_back等基本操作，实现M次调动粮食； -
输出最后各个谷仓
ID、该谷仓中各袋粮食的重量以及总的重量（请严格遵循测试样例的输出格式）。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
5
3 79 32 29
4 42 41 92 6
6 68 37 63 11 34 79
2 63 36
3 27 74 67
6
move 1 2
move 3 0
move 3 0
move 4 2
move 1 4
move 2 0
预期输出：
0 79 32 29 36 63 67 306
1 42 41 83
2 68 37 63 11 34 79 6 298
3 0 0
4 27 74 92 193
输入格式：
第一行整数N：谷仓数量
接下来N行，依次为各个谷仓ID=[0,1,...,N−1]的初始信息：第一个数字为该谷仓的初始粮食袋数Ni，后面接着Ni袋粮食的重量Wj
接下来一行整数M：调动粮食次数
接下来M行，每行move a b：将谷仓a粮堆的最后一袋粮食调动到谷仓b粮堆的最上面
输出格式：
输出N行，按顺序输出谷仓ID=[0,1,...,N−1]的最终状态信息：ID W0 W1 ... Wj Wsum，若谷仓空了，则输出为ID 0 0
注意：每行所有数字中间空格隔开，末尾换行\n
开始你的任务吧，祝你成功！
1 // 2 // main.cpp 3 // step2 4 // 5 // Created by ljpc on 2018/7/23. 6 // Copyright © 2018年 ljpc. All rights reserved. 7 // 8 9 #include <iostream> 10 #include <algorithm> 11 #include <vector> 12 using namespace std; 13 14 int main(int argc, const char * argv[]) { 15 16 17 // 请在这里补充代码，完成本关任务 18 /********* Begin *********/ 19 vector<vector<int> > vec; 20 int n; 21 scanf("%d", &n); 22 while (n--) { 23 vector<int> tmp; 24 int m; 25 scanf("%d", &m); 26 while (m--) { 27 int x; 28 scanf("%d", &x); 29 tmp.push_back(x); 30 } 31 vec.push_back(tmp); 32 } 33 int q; 34 scanf("%d", &q); 35 while (q--) { 36 char str[20]; 37 int a, b; 38 scanf("%s %d %d", str, &a, &b); 39 if(!vec[a].empty()){ 40 vec[b].push_back(vec[a].back()); 41 vec[a].erase(vec[a].end()-1); 42 } 43 } 44 for (int i=0; i<vec.size(); i++) { 45 int tot = 0; 46 printf("%d ", i); 47 if (vec[i].empty()) { 48 printf("0 "); 49 } 50 else{ 51 for (int j=0; j<vec[i].size(); j++) { 52 printf("%d ",vec[i][j]); 53 tot += vec[i][j]; 54 } 55 } 56 printf("%d\n", tot); 57 } 58 }
第3关：STL模板之关联容器：集合set的操作详解
任务描述
本关任务：仔细阅读下文集合的相关操作，并使用set完成N次插入或删除元素操作，以及集合的遍历和查找等要求。
相关知识
为了完成本关任务，你需要掌握：1.集合的概念，2.插入元素，3.删除元素，4.遍历集合，5.查找元素，6.清空集合。
集合的概念
集合set就是数学上的集合，其中的每个元素没有重复的，但是set中的元素在数据结构中是有序存储的（默认升序），为了高效的实现插入、删除和查找等操作，这与数学上的集合中元素无序性有点区别。
集合set也是STL中的一种标准关联容器，其底层数据结构是基于平衡搜索树（红黑树）实现的，插入删除等操作都是通过迭代器指针实现的，不涉及内存操作，因此效率非常高。
集合set被包含在set头文件中，基本定义方式如下：
set<int> st，定义了一个元素类型为int整型的集合st
插入元素
往集合中插入一个元素通过调用insert()方法实现：
1 set<int> st; // 创建一个整型集合st 2 st.insert(1); // 向st插入一个元素1 3 st.insert(2); // 向st插入一个元素2
删除元素
集合元素的删除通过调用erase()方法实现，传入的参数可以是待删除的元素，也可以是待删除元素的地址：
1 set<int>::iterator it = st.begin(); // 定义一个迭代器，初始为st的首地址 2 cout<<*it; // 输出为元素1 3 st.erase(it); // 删除it指向的元素1 4 st.erase(2); // 删除元素2
遍历集合
集合的遍历通过迭代器的方式进行，首先让迭代器指针指向集合的首地址，然后逐步移动迭代器指针，直到集合的尾地址：
1 for(set<int>::iterator it = st.begin();it!=st.end();it++) 2 cout<<*it;
查找元素
在集合中查找指定元素通过find()方法实现，若找到了则返回该元素在集合中的地址，否则返回集合的尾地址：
1 it = st.find(2); //查找指定元素2，it结果为st.end()，因为2已经被删除了
集合清空
集合的清空通过调用clear()方法实现，清空后集合的大小st.size()变为0：
1 st.clear() 2 cout<<st.size(); // 结果为0
编程要求
本关的编程任务是补全右侧代码片段main中Begin至End中间的代码，具体要求如下：
-
创建一个空的集合
st，数据类型为int； -
读取数据：第一行整数N，后面N行插入或删除操作，按指定要求输出相应信息；
-
遍历集合：首先在一行输出集合的大小，然后在下一行输出集合所有元素，中间空格隔开，末尾换行；
-
读取数据：整数M以及M次查找操作，并按指定要求输出相应信息；
-
清空集合
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
7
insert 2
insert 7
insert 1
erase 3
erase 1
insert 5
erase 7
2
find 7
find 5
预期输出：
3 not in set
print set: 2
2 5
find 7 not in set
find 5 in set
0
输入格式：
第一行整数N
接下来N行插入或删除操作
整数M
接下来M行查找操作
输出格式：
插入删除阶段：若待删除的元素x不在集合中，则输出：x not in set
遍历集合阶段输出两行，第一行print set: set.size()，第二行集合所有元素x1 x2 x3 ...
查找阶段：若找到元素x，则输出find x in set，否则输出find x not in set
非学员输出0
开始你的任务吧，祝你成功！
1 // 2 // main.cpp 3 // step5 4 // 5 // Created by ljpc on 2018/7/25. 6 // Copyright 2018年 ljpc. All rights reserved. 7 // 8 9 #include <iostream> 10 #include <cstring> 11 #include <string> 12 #include <algorithm> 13 #include <map> 14 using namespace std; 15 16 int main(int argc, const char * argv[]) { 17 18 19 // 请在这里补充代码，完成本关任务 20 /********* Begin *********/ 21 // 1.创建一个空的键值对映射mp: 键string->值int 22 map<string,int> mp; 23 // 2.读取和处理数据：插入n个学生信息（姓名 成绩），并按指定要求输出 24 int n1,i; 25 cin>>n1; 26 string s1,s2; 27 int n2; 28 pair<string,int> p; 29 map<string,int>::iterator it; 30 for(i=0;i<n1;i++){ 31 cin>>s1>>s2>>n2; 32 if(s1=="insert"){ 33 p.first=s2; 34 p.second=n2; 35 it=mp.find(p.first); 36 if(it==mp.end()) 37 mp.insert(p); 38 else 39 cout<<s2<<" has been recorded\n"; 40 } 41 } 42 /*if(it==mp.end()){ 43 for(i=0;i<n1;i++){ 44 p.first=s2; 45 p.second=n2; 46 mp.insert(p); 47 } 48 } 49 else 50 cout<<s2<<" has been recorded\n";*/ 51 52 // 3.读取和处理数据：删除m个学生信息（姓名），并按指定要求输出 53 int n3; 54 cin>>n3; 55 string s3,s4; 56 /*cin>>s3; 57 if(s3=="erase"){ 58 cin>>s4; 59 p.first=s4; 60 it=mp.find(s4); 61 if(it!=mp.end()){ 62 for(i=0;i<n3;i++){ 63 mp.erase(s4); 64 } 65 } 66 else 67 cout<<s4<<" has not been recorded\n"; 68 }*/ 69 for(i=0;i<n3;i++){ 70 cin>>s3>>s4; 71 if(s3=="erase"){ 72 p.first=s4; 73 74 it=mp.find(p.first); 75 if(it!=mp.end()) 76 mp.erase(p.first); 77 else 78 cout<<s4<<" has not been recorded\n"; 79 } 80 81 } 82 // 4.遍历映射mp，并按指定要求输出 83 cout<<"print map: "<<mp.size()<<"\n"; 84 for(it=mp.begin();it!=mp.end();it++){ 85 cout<<it->first<<" "<<it->second<<"\n"; 86 } 87 // 5.查找q个学生信息，并按指定要求输出 88 int n4; 89 cin>>n4; 90 string s5,s6; 91 92 for(i=0;i<n4;i++){ 93 cin>>s5>>s6; 94 if(s5=="find"){ 95 it=mp.find(s6); 96 if(it!=mp.end()){ 97 cout<<s6<<" score "<<it->second<<"\n"; 98 } 99 else 100 cout<<s6<<" cannot been found\n"; 101 } 102 } 103 104 // 6.清空集合 105 mp.clear(); 106 /********* End *********/ 107 printf("%d\n", int(mp.size())); 108 109 return 0; 110 }