C++的STL总结笔记：STL总结笔记（实用 / 比赛）

文章目录

1 vector模板1039（25：学生-课程表）1047（25：学生-课程表）2 set模板1063（25：求两个set的并集（去重）、交集（去重））1120（20：N个数，每个数的各位求和，输出相同的和（去重））1129（25：set排序）3 map模板1022（30：数字图书馆，查询）【非满分】1054（20：hash，用map）1071（25：提取单词）4 stack5 queue

1 vector

模板

常用定义：

vector<int> vect;vector<int> vects[N];// N个vector//vector<int> vects(N);// N个int

1039（25：学生-课程表）

（1）题目

学生-课程表

（2）代码

#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;const int N_stu = 40000+10;const int N_cour = 2500+10;const int maxn = 26*26*26*10 +10;vector<int> stus[maxn]; //stus[i]：id=i的学生的所有课程int hashTable(char str[]){int id=0;for(int i=0; i<3; i++){id = id*26 + str[i]-'A';}id = id*10 + str[3]-'0';return id;}int main(){int n,k;scanf("%d%d", &n, &k);int index, num;char name[10];int id;for(int i=0; i<k; i++){scanf("%d%d", &index, &num);for(int j=0; j<num; j++){scanf("%s", name);id = hashTable(name);stus[id].push_back(index);}}for(int i=0; i<n; i++){scanf("%s", name);id = hashTable(name);sort(stus[id].begin(),stus[id].end());printf("%s %d", name, stus[id].size());for(int j=0; j<stus[id].size(); j++){printf(" %d", stus[id][j]);}printf("\n");}return 0;}

（3）小结

学生名：3个大写字母+1个数字

用hash存储，将字符串转换为唯一的数如何设计vector类型的变量（stu[maxn]），根据输出

1047（25：学生-课程表）

（1）题目

学生-课程表（比较A1039）

（2）代码

#include<cstdio>#include<vector>#include<cstring>#include<algorithm>#include<string>using namespace std;const int N=40000+10;const int K=2500+10;vector<string> vect[K]; // vect[i]: 课程i的所有学生int main(){int n, k;scanf("%d%d", &n, &k);char name[10];int num;string s;int c;for(int i=0; i<n; i++){scanf("%s%d", name, &num);s = name;for(int j=0; j<num; j++){scanf("%d",&c);vect[c].push_back(s);}}for(int i=1; i<=k; i++){printf("%d %d\n", i, vect[i].size());sort(vect[i].begin(), vect[i].end());for(int j=0; j<vect[i].size(); j++){printf("%s\n", vect[i][j].c_str());}}return 0;}

（3）小结

vector存字符串数组：vector<string>，最好用string中途用到string类型，但又不想cin和scanf混用

则： 输入char[]变量，转换为string类型

char name[10];

scanf(“%s”, name）;

string str;

str = name; //char[]变为string

2 set

模板

常用定义：

set<int> st;vector<set<int> > vects(N);//N个set，(N)用小括号！！！//排序set<int, greater<int> > st;//降序set<int, cmp> st;// cmp自定义

1063（25：求两个set的并集（去重）、交集（去重））

（1）题目

求两个set的并集（去重）、交集（去重）

（2）代码

#include<cstdio>#include<set>#include<vector>using namespace std;const int N=100;vector<set<int> > vects(N); // N个set，用小括号double simi(int index1, int index2){int nc=0,nt=0;set<int>::iterator it = vects[index1].begin();// nt = set2的大小// 遍历set1：对于*it, 如果set2中存在，则nc++，否则nt++nt = vects[index2].size();for(; it!=vects[index1].end(); it++){if(vects[index2].find(*it) == vects[index2].end()){//查找失败nt++; //set2中没有set1中有的元素（set1-set2）}else{nc++;}}double r = ((double)nc/nt) *100;return r;}int main(){int n;scanf("%d", &n);for(int i=1; i<=n; i++){int m;scanf("%d", &m);for(int j=0; j<m; j++){int t;scanf("%d", &t);vects[i].insert(t);}}int k;scanf("%d", &k);for(int i=0; i<k; i++){int index1, index2;double r;scanf("%d%d", &index1, &index2);r = simi(index1, index2);printf("%.1f%%\n", r);}return 0;}

（3）小结

用auto定义it（只能在C++11中）

auto it = vects.begin();求交集、并集、差集

遍历set1：

对于set1中元素 x ，判断set2中有没有（set.find(x)）输出结果为 %

double r = … *100;

printf("%.2f%%", r); //80.20%

1120（20：N个数，每个数的各位求和，输出相同的和（去重））

（1）题目

N个数，每个数的各位求和，输出相同的和（去重）

（2）代码

#include<cstdio>#include<set>using namespace std;set<int> st;int friend_sum(int num){int sum=0;while(num!=0){sum += num%10;num /= 10;}return sum;}int main(){//freopen("in.txt", "r", stdin);int n;scanf("%d", &n);for(int i=0; i<n; i++){int t;scanf("%d", &t);int sum;sum = friend_sum(t);st.insert(sum);}set<int>::iterator it = st.begin();printf("%d\n", st.size());for(; it!=st.end(); it++){if(it!=st.begin()){printf(" ");}printf("%d",*it);}//fclose(stdin);return 0;}

（3）小结

对于一个正整数n，得到各位上的数字【从个位开始】

int a[100];//存储每一位【a[0]：个位】int i=0;while(n!=0){a[i] = n%10;n /= 10;i++;}

当题目没有明确N的大小：

可能只需要for循环，不需要创建存储空间

可能用vector存储a[n]的输出格式（没有多余空格）

a[1]空格a[2]空格a[3]

for(int i=0; i<n; i++){if(i!=0){printf(" ");}printf("%d",*it);}

1129（25：set排序）

（1）题目

set排序

（2）代码

#include<cstdio>#include<set>using namespace std;const int N = 50000+10;typedef struct{int data;int freq; //访问次数}Node;// freq[]降序，再set<int>升序struct cmp{bool operator()(const Node &node1, const Node &node2){if(node1.freq==node2.freq){return node1.data < node2.data;}else{return node1.freq > node2.freq;}}};set<Node,cmp> st; //输出rec[]不重复int freq[N];int main(){//freopen("in.txt", "r", stdin);int n,k;scanf("%d%d", &n, &k);for(int i=0; i<n; i++){int t;scanf("%d", &t);set<Node,cmp>::iterator it;if(i!=0){//从第二个开始// 输出，取set的前k个printf("%d: ",t);it = st.begin();int j=0;for(; it!=st.end() && j<k; it++,j++){if(it!=st.begin()){printf(" ");}printf("%d",*it);}printf("\n");}it = st.find(Node{t,freq[t]});freq[t]++;if(it!=st.end()){//查找成功st.erase(it);//由于set的cmp operator()重载，set中的元素变为const，不能修改，只能删除再插}st.insert(Node{t, freq[t]});}//fclose(stdin);return 0;}

（3）小结

iterator的定义，必须和指向的STL定义完全相同

set<int,cmp> st;

set<int,cmp>::iterator it = st.begin();

排序：STL+sort()、set+内部、prior_queue+内部

多于一次排序（当…相等，再比较…时）时：必须使STL容器存储结构体struct才不会出错

如：以下情况set会出错（freq[]和set<int>中元素分开）

int freq[N]; //访问次数struct cmp{// freq[]降序，再set<int>升序bool operator()(const int &a, const int &b){if(freq[a]==freq[b]){return a < b;}else{return freq[a] > freq[b];}}};set<int,cmp> st;

以下情况不会出错

typedef struct{int data;int freq; //访问次数}Node;// freq[]降序，再set<int>升序struct cmp{bool operator()(const Node &node1, const Node &node2){if(node1.freq==node2.freq){return node1.data < node2.data;}else{return node1.freq > node2.freq;}}};set<Node,cmp> st;

排序：set+内部、prior_queue+内部 重载operator()会使 元素变为const，不可再修改

如：Node结构体的元素的值不可再修改，只能删除再插入新的Node

struct cmp{bool operator()(const Node &node1, const Node &node2){if(node1.freq==node2.freq){return node1.data < node2.data;}else{return node1.freq > node2.freq;}}};set<Node,cmp> st;

set只输出前k项

it = st.begin();int j=0;for(; it!=st.end() && j<k; it++,j++){...}

3 map

模板

查询：map<key, value> mp； value可以为多个

常用定义：

map<string, set<int> > mp;//value多个，有序且唯一，设为set

1022（30：数字图书馆，查询）【非满分】

（1）题目

数字图书馆：查询

（2）代码

#include<cstdio>#include<string>#include<iostream>#include<map>#include<set>using namespace std;map<string, set<int> > title, author, keyWords, publisher, year;// 参数为STL，都用引用，快些void query(map<string, set<int> > &mp, string &str){map<string, set<int> >::iterator it1;it1 = mp.find(str);if(it1!=mp.end()){//查找成功set<int>::iterator it2 = mp[str].begin();for(; it2!=mp[str].end(); it2++){printf("%d\n",*it2);}}else{printf("Not Found\n"); //失败} }int main(){//freopen("in.txt", "r", stdin);int n;cin>>n;for(int i=0; i<n; i++){int id;cin>>id;string str;cin.ignore();// cin>>id后会有个'\n'，getline(cin, str);title[str].insert(id);getline(cin, str);author[str].insert(id);// key words没有明确输入几个while(cin>>str){keyWords[str].insert(id);char ch = getchar(); //为空格 或 \nif(ch=='\n') break;}getline(cin, str);publisher[str].insert(id);getline(cin, str);year[str].insert(id);}int m;cin>>m;for(int i=0; i<m; i++){int num;scanf("%d: ",&num);string str;getline(cin, str);printf("%d: %s\n",num,str.c_str());switch(num){case 1:query(title, str);break;case 2:query(author, str);break;case 3:query(keyWords, str);break;case 4:query(publisher, str);break;case 5:query(year, str);break;default:break;}}//fclose(stdin);return 0;}

（3）小结

没有明确输入几个（一行输入，空格分开）

while(cin>>...){...char ch = getchar(); //为空格 或 \nif(ch=='\n') break;}或while(scanf(...)){...char ch = getchar(); //为空格 或 \nif(ch=='\n') break;}

当超时时，将自己写的函数的参数改为引用

特别：函数的参数为：STL时（string、vector、map等）当所有数据都显示 超时时， 可能没删freopencin / scanf 后接 gets / getline 会多读一个空格或只读\n，必须加cin.ignore()

int n;string str;scanf("%d", &n);// 必须先忽略一个字符cin.ignore();//getline(cin, str);printf("n:%d\n",n);printf("s:%s\n", str.c_str());

1054（20：hash，用map）

（1）题目

hash：用map

（2）代码

#include<cstdio>#include<map>using namespace std;int main(){//freopen("in.txt", "r", stdin);int m,n;scanf("%d%d", &m, &n);map<int, int> mp;// 默认=0for(int i=0; i<n; i++){for(int j=0; j<m; j++){int t;scanf("%d", &t);mp[t]++;}}map<int , int>::iterator it;for(it=mp.begin(); it!=mp.end(); it++){if(it->second > (m*n/2)){printf("%d\n", it->first);break;}}//fclose(stdin);return 0;}

（3）小结

hash：直接定址，当MAXN较大时，不能用数组，如下

int arr[MAXN];

最好用map

map<int, int> mp;

1071（25：提取单词）

（1）题目

提取单词

（2）代码

#include<cstdio>#include<string>#include<iostream>#include<map>#include<cctype>using namespace std;string str, word="";int main(){//freopen("in.txt", "r", stdin);getline(cin,str);map<string, int> mp;for(int i=0; i<str.length(); i++){char ch = str[i];if(isalnum(str[i])){str[i] = tolower(str[i]);word += str[i];if(i==str.length()-1){//易漏，当最后一个是字母结尾，map容易漏最后一个wordmp[word] ++;}}else{if(word!=""){mp[word] ++;}word = "";}}int max0 = 0;map<string, int>::iterator it, it_max;for(it=mp.begin(); it!=mp.end(); it++){if(it->second > max0){//max0相同，按字典序的第一个（map按key）it_max = it;max0 = it->second;}}printf("%s %d\n",it_max->first.c_str(), it_max->second);//fclose(stdin);return 0;}

（3）小结

灵活用头文件<cctype>

判断一个字符是否为 [0-9 A-Z a-z]，bool isalnum(ch)

#include<cctype>char ch;if(isalnum(ch)){...}

map的key有序：ascII，从小到大段错误：

数组太小

数组越界

也可能答案错误（有情况没考虑到）

4 stack

5 queue