STL和基本数据结构

0.关于1.vector介绍定义常用操作(标记的表示stl通用)例题 2.stack介绍常用操作例题 3.queue介绍常用操作例题 4.priority_queue介绍常用函数例题 5.list介绍常用函数例题 6.set介绍常用函数例题 7.map介绍常用函数例题 8.next_permutation介绍例题

0.关于

STL(StandardTemplateLibrary)是C艹的标准模板库,包含容器,迭代器,配接器,算法,仿函数,空间适配器6个方面组成,第一章只有容器和一个常用算法 容器使用时要#include<容器名称>(优先队列只需要队列)

1.vector

介绍

数组是高级语言基本的数据结构,但C艹的静态数组不能根据需要扩大或缩小空间,虽然能定义足够大,但在空间紧张或需要少量增删是可以利用动态数组的方法更简单的实现. 由于vector本质还是数组,内存空间是连续的,所以增删回造成内存块的复制,所以并不适合大量增删 更多关于vector

定义

基本定义 vector<类型>命名(初始化元素数量,初始化元素);可自己选择如何初始化,给一个参数默认是数量 vector<int>a(100);// 定义一个int类型的a,并初始化100个元素,未指定时int类型默认0,所以a有100个0元素 vector<string>b(10,"hello");//定义一个string类型的b,并初始化10个元素"hello" 复制定义 vector<int>b(a);//用a来定义b,基本等同于复制 vector<string>c(b.begin(),b.end());//c是b的复制,begin和end是迭代器.相当于能遍历的头指针和尾指针 结构体定义 struct point{ int x,y; } vector<point>p;//定义一个存x,y的point类型的动态数组p 套娃定义 vector<int>a[10];//a是有10个元素的数组,每个元素又是一个动态数组,类似于二维数组 vector<int>one; vector<one>two;//套娃起来了

常用操作(标记的表示stl通用)

vector< int >a;

增加 a.push_back(元素数量, 元素);向尾部插入一个元素,或插入规定数量相同元素a.insert(下标位置,元素数量, 元素);在下标位置插入一个元素,或插入规定数量相同元素,下标位置由迭代器begin,end控制 a.push_back(114514);//在a尾部插入114514这个数 a.insert(a.begin()+i,n);//将n插在第i下标处 a.insert(a.end(),114,514);//在a最后插入114个514 删除 a.pop_back();删除末尾元素a.erase(开始位置,结束位置 );包含开始位置不包含结束位置,可以只有开始位置只删一位a.clear();清空a中所有元素，栈和队列不能用这个函数 a.pop_back(7);//删除a中末尾元素 a.erase(a.begin()+i,a.begin()+n);//删除[i,n)所有元素 a.erase(a.begin()+i);//删除下标为i的元素

3.其他

a.size();//a中元素个数a.empty();//a是否为空,返回一个bool类型来判断a.resize(n);//将a数值大小变为nreverse(开始位置,结束位置);//将开始位置到结束位置翻转sort(开始位置,结束位置,排序方法);//将开始位置到结束位置排序,方法可不写,默认升序

例题

圆桌问题 HDU 4841 Problem Description 圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。

Input 多组数据，每组数据输入：好人和坏人的人数n（<=32767）、步长m（<=32767）；

Output 对于每一组数据，输出2n个大写字母，‘G’表示好人，‘B’表示坏人，50个字母为一行，不允许出现空白字符。相邻数据间留有一空行。

Sample Input 2 3 2 4

Sample Output GBBG BGGB

思路: 如想用静态数组,则设置一个足够大的数组初始化全为0,将0代表好人,则需要将一半的人也就是n个人转化成1就可以了.

转化过程需要一个数去记1的数目到n就结束需要一个计步器走一步加1,到3置0且在跳1时不加需要将总步数求余来循环

但如果用静态数组做的话,由于数组的大小不变,每次遍历都要遍历全部,时间耗费更多容易导致超时(但不是不行)

代码:

#include<iostream> #include <algorithm> #include<string.h> #include<vector> const int maxn = 1e5 + 10; #define re(x) for(int i=0;i<x;++i) #define rey(x) for(int j=0;j<x;++j)//可以用简单的写法使用循环 typedef long long LL; using namespace std; int T, n, a[maxn], m,p; int main() { ios::sync_with_stdio(0); cin.tie(0); vector<int>table;//定义int型的table while (cin>>n,cin>>m) { table.clear();//为了下一次循环而清零 re(2 * n)table.push_back(i);//将table里存入0~2n-1 p = 0;//跳的位置 re(n) { p = (p + m -1) % table.size();//取余来保证p不超过table.size() table.erase(table.begin() + p);//每m人就将其元素删除 } T = 0; re(2 * n) { if (!(i % 50) && i)cout << endl;//输出格式要求一行50 if (T < n && i == table[T]) { T++; cout << "G"; //将0~2n-1个值与剩余table的值比较,如果有,则输出G否则输出B } else { cout << "B"; } } cout << endl << endl; } }

2.stack

介绍

栈是最基本的数据结构之一,特点是先进后出,就像是放盘子,最先放的在下面最后放的在上面,但用的时候会先用上面最后用下面. 更多关于stack

常用操作

没有定义是因为栈不能花里胡哨的初始化

stack<类型>命名;//定义栈 stack< int >s;s.push(n);//将n压如栈中s.top;//返回栈顶元素s.pop;//删除栈顶元素s.size();//返回栈的元素个数s.empty();//返回栈是否为空的判断

例题

*Text Reverse HDU - 1062 伊格纳修斯喜欢用相反的方式写词。 给定由伊格纳修斯编写的单行文本，您应该反转所有单词，然后输出它们。

Input 输入包含几个测试用例。 输入的第一行是单个整数T，它是测试用例的数量。 随后是T行测试用例。 每个测试用例都包含一行并包含多个单词。 一行中最多有1000个字符。Output 对于每个测试用例，您应该输出已处理的文本。Sample Input 3 olleh !dlrow m’I morf .udh I ekil .mcaSample Output hello world! I’m from hdu. I like acm. 思路 用栈把字母存进去在放出来读入一行每次循环应该在字符为\n时结束每个单词直接用" "隔开读的时候按字符读还要能读空白字符用getchar

代码:

#include<iostream> #include <algorithm> #include<string.h> #include<vector> #include<stack> const int maxn = 1e5 + 10; #define re(x) for(int i=0;i<x;++i) #define rey(x) for(int j=0;j<x;++j) typedef long long LL; using namespace std; int T, n, a[maxn], m,p; char c; int main() { ios::sync_with_stdio(0); cin.tie(0); scanf("%d", &T); getchar(); while (T--){ stack<char>s; //构造字符型栈s while (1) { c = getchar(); if (c == ' ' || c == '\n'|| c == EOF) {//读入一个字符,当它是空格,回车,结束符时做下一步 while (!s.empty())//当栈不为空时 { printf("%c", s.top());//输出栈顶元素 s.pop(); //输出栈顶元素 } if (c == '\n' || c == EOF)break;//读到回车或结束符退出当前循环 printf(" "); } else s.push(c);//否则压入栈中 } printf("\n"); } }

3.queue

介绍

队列和栈一样是最基本的数据结构,特点是先进先出,它和栈非常相似 更多关于queue

常用操作

和栈同理

queue<类型>命名;//定义队列 queue< int >q;queues;//定义一个队列front();//返回队首元素，不删除back();//返回队尾元素，不删除push();//入队pop();//出队size();//返回队列大小empty();//判断是否为空，是返回真

例题

ACboy needs your help again! HDU - 1702 ACboy was kidnapped!! he miss his mother very much and is very scare now.You can’t image how dark the room he was put into is, so poor 😦. As a smart ACMer, you want to get ACboy out of the monster’s labyrinth.But when you arrive at the gate of the maze, the monste say :" I have heard that you are very clever, but if can’t solve my problems, you will die with ACboy." The problems of the monster is shown on the wall: Each problem’s first line is a integer N(the number of commands), and a word “FIFO” or “FILO”.(you are very happy because you know “FIFO” stands for “First In First Out”, and “FILO” means “First In Last Out”). and the following N lines, each line is “IN M” or “OUT”, (M represent a integer). and the answer of a problem is a passowrd of a door, so if you want to rescue ACboy, answer the problem carefully!Input The input contains multiple test cases. The first line has one integer,represent the number oftest cases. And the input of each subproblem are described above.Output For each command “OUT”, you should output a integer depend on the word is “FIFO” or “FILO”, or a word “None” if you don’t have any integer. Sample Input 4 4 FIFO IN 1 IN 2 OUT OUT 4 FILO IN 1 IN 2 OUT OUT 5 FIFO IN 1 IN 2 OUT OUT OUT 5 FILO IN 1 IN 2 OUT IN 3 OUT Sample Output 1 2 2 1 1 2 None 2 3 思路 为什么不想想晚上吃什么呢 代码 #include<cstdio> #include<cstring> #include<stack> #include<queue> #include<algorithm> using namespace std; stack<int> s ; queue<int> q; int main() { int n,t,a; char str1[105],str2[105]; while(scanf("%d",&t)!=EOF) { while(t--) { scanf("%d%s",&n,str1); if(strcmp(str1,"FIFO")==0)//strcmp比较str1和FIFO,一样返回1,否则返回0 { while(!q.empty()) { q.pop(); } while(n--) { scanf("%s",str2); if(str2[0]=='I')//判断str2是否是IN { scanf("%d",&a); q.push(a); } else { if(!q.empty()) { printf("%d\n",q.front()); q.pop(); } else printf("None\n"); } } } else//栈,和队列原理一样 { while(!s.empty()) { s.pop(); } while(n--) { scanf("%s",str2); if(str2[0]=='I') { scanf("%d",&a); s.push(a); } else { if(!s.empty()) { printf("%d\n",s.top()); s.pop(); } else printf("None\n"); } } } } } return 0; }

4.priority_queue

介绍

优先队列是队列的拓展,它是可以自动排序的队列,每次插入删除后都会动态调整 但默认是重写<达到自己目的,所以想让优先度大,也是< 关于方法重写 更多关于priority_queue

常用函数

priority_queue< 类型 >命名;q.size();//返回q里元素个数q.empty();//返回q是否为空的判断q.push(k);//在q的末尾插入kq.pop();//删掉q的第一个元素q.top();//返回q的第一个元素

例题

看病要排队 HDU - 1873看病要排队这个是地球人都知道的常识。 不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。 现在就请你帮助医院模拟这个看病过程。Input 输入数据包含多组测试，请处理到文件结束。 每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。 接下来有N行分别表示发生的事件。 一共有两种事件： 1:“IN A B”,表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10) 2:“OUT A”,表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)Output 对于每个"OUT A"事件，请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治，则输出"EMPTY"。 诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。Sample Input 7 IN 1 1 IN 1 2 OUT 1 OUT 2 IN 2 1 OUT 2 OUT 1 2 IN 1 1 OUT 1Sample Output 2 EMPTY 3 1 1 思路 创建优先队列,然后按照自己想要的规则排序,判断输入IN或OUT并读数据 *优先度大的要让自己更小,相同则编号小的小 代码 #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> const int maxn = 1e5 + 10; #define re(x) for(int i=0;i<x;++i) #define rey(x) for(int j=0;j<x;++j) typedef long long LL; using namespace std; int T, n, a[maxn], m, * p, flag = 1; struct Rqu { int prior, num; friend bool operator<(Rqu a, Rqu b) { if (a.prior != b.prior)return a.prior < b.prior;//prior大的优先度大 else return a.num > b.num;//num小的优先度大 } }; int main() { string s; ios::sync_with_stdio(0); cin.tie(0); while (cin >> T) { Rqu x; int num = 0; priority_queue <Rqu> q[3];//创建3个优先队列 while (T--) { cin >> s; if (s[0] == 'I') {//只需要判断第一个字符是什么就行 ++num; cin >> m; cin >> n; x.prior = n; x.num = num; q[m - 1].push(x); } else { cin >> m; if (q[m - 1].empty())cout << "EMPTY" << endl; else { cout << q[m - 1].top().num << endl; q[m - 1].pop(); } } } } }

5.list

介绍

list是双向链表,内存空间不连续,可以很快的插入删除,但遍历就要命(因为不能用下标,遍历用迭代器 关于迭代器 1、功能：对于存储空间非连续的情况，利用迭代器来对非数组的数据结构进行遍历。 2、定义：迭代器是一种检查容器内元素并遍历元素的数据类型，它提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围 3、迭代器特点 （1）迭代器类似于C语言里面的指针类型，它提供了对对象的间接访问 （2）指针是C语言中的知识点，迭代器是C++中的知识点。指针较灵活，迭代器功能较丰富 （3）迭代器提供一个对容器对象或者string对象的访问方法，并定义了容器范围 4、格式： （1）每种容器类型都定义了自己的迭代器类型，如动态数组vector的迭代器：vector< int>:: iterator iter 和vector相似,但list擅长频繁增删,而vector适合随机访问 更多关于list

常用函数

remove_if() 按指定条件删除元素sort() 给list排序unique() 删除list中重复的元素reverse(lst[v].begin(), lst[v].end()); // 倒转lstpush_front(val); //加在列表前push_back(val); //加在列表后pop_front(); //删除最前元素pop_back(); // 删除最后元素front();//获得首个元素back();//获得最后元素empty();//判断list是否为空clear();//清空listsize();//list大小swap(l1,l2);或l1.swap(l2)//两个list的交换l1.merge(l2，greater()); //l2变空，l1包含原来l1和l2的元素并升序排l1.insert(l1.begin(),100);//在l1的开始位置插入100。l1.insert(l1.begin(),2,200);//在l1的开始位置插入2个100。l1.insert(l1.begin(),l2.begin(),l2.end());//在l1的开始位置插入l2的从开始到结束的所有位置的元素。l1.erase(l1.begin()); 将l1的第一个元素删除。l1.erase(l1.begin(),l1.end()); 将l1的从begin()到end()之间的元素删除。

例题

士兵队列训练问题 HDU - 1276 某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。Input 本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。Output 共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。Sample Input 2 20 40Sample Output 1 7 19 1 19 37 思路当列表的size大于3则继续循环在3循环和2循环之间反复横跳,可以用if的简写遍历使用迭代器迭代器删除元素时要迭代器重新赋值(自动指向下一个元素),不然迭代器也会被删输出格式注意最后不能有空格,每行输出结束换行 代码 #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> const int maxn = 1e5 + 10; #define re(x) for(int i=0;i<x;++i) #define rey(x) for(int j=0;j<x;++j) typedef long long LL; using namespace std; int T, n, a[maxn], m, * p, flag = 1; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> T; while (T--) { cin >> n; list<int>li; list<int>::iterator it; int flag = 2; re(n)li.push_back(i+1); while (li.size()>3) { int num = 0; for (it=li.begin();it!=li.end();) { ++num% flag ? it++: it = li.erase(it);//num若是flag的倍数就it++,否则删除it } flag = flag == 2 ? 3 : 2;//2和3反复横跳 } for (it = li.begin(); it != li.end();it++) { /*if (it != li.end())cout << *it<<" "; else cout << *it ;//i != end其实可以看成i < length */ if (it != li.begin())cout << " "; cout << *it; } cout << endl; } }

6.set

介绍

集合有个最大特点，就是一种元素只出现一次且是排好序的(默认是从小到大) 更多关于set

常用函数

insert(a);//插入a元素begin(); //返回第一个元素迭代器end(); //返回最后一个元素下一位置迭代器rbegin(); //返回最后一个元素的迭代器rend(); //返回第一个元素的前一个迭代器count(b);//返回b元素的个数erase(b);//删除集合中的b元素clear(); //删除set容器中的所有的元素empty(); //判断set容器是否为空size(); //返回当前set容器中的元素个数swap(s1,s2);//交换两个集合变量lower_bound();//返回指向大于等于某值的第一个元素的迭代器upper_bound();//返回大于某个值元素的迭代器equal_range(b);/*返回第一个大于等于b和第一个大于b两个迭代器

例题

产生冠军 HDU - 2094有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。 球赛的规则如下： 如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。 如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。 根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。Input 输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。Output 对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。Sample Input 3 Alice Bob Smith John Alice Smith 5 a c c d d e b e a d 0Sample Output Yes No 思路设立2个集合,一个存全部的,一个存输的如果全部的总人数比输的总人数多1,就代表有人没输过我在写的时候把No写成NO,一直WA(令人智熄) 代码 #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; #define re(x) for(int i=0;i<x;++i) #define rey(x) for(int j=0;j<x;++j) typedef long long LL; int T, n, m, a[maxn], flag = 1; int main() { ios::sync_with_stdio(0); cin.tie(0); set<string>all,lose; string x,y; while (cin>>T&&T) { re(T) { cin >> x; all.insert(x); cin >> x; all.insert(x); lose.insert(x); } if (all.size() - lose.size() == 1)cout << "Yes" << endl; else cout << "No" << endl; all.clear(); lose.clear(); } }

7.map

介绍

图是键值关联容器例[x]=y,可以将x视为数组下标,但只能出现一次(集合性质) 用平衡二叉树来储存和访问导致它比结构体数组效率高到不知道那里去

更多关于map

常用函数

map<类型1, 类型2> 命名;类型1是键,类型2是值 map<int, string> m;m[114]=“514”;建议使用这种插入方式it=m.find(类型1);it是迭代器(没写创建过程)m.erase(it);删除it指的那个元素it->second或it->first迭代器指向值或键

例题

Shopping HDU - 2648Every girl likes shopping,so does dandelion.Now she finds the shop is increasing the price every day because the Spring Festival is coming .She is fond of a shop which is called “memory”. Now she wants to know the rank of this shop’s price after the change of everyday.Input One line contians a number n ( n<=10000),stands for the number of shops. Then n lines ,each line contains a string (the length is short than 31 and only contains lowercase letters and capital letters.)stands for the name of the shop. Then a line contians a number m (1<=m<=50),stands for the days . Then m parts , every parts contians n lines , each line contians a number s and a string p ,stands for this day ,the shop p 's price has increased s.Output Contains m lines ,In the ith line print a number of the shop “memory” ‘s rank after the ith day. We define the rank as :If there are t shops’ price is higher than the “memory” , than its rank is t+1.Sample Input 3 memory kfc wind 2 49 memory 49 kfc 48 wind 80 kfc 85 wind 83 memorySample Output 1 2 思路一开始输入n和店名是无作用的用店名为键,涨的价为值 代码 #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; #define re(x) for(int i=0;i<x;++i) #define rey(y) for(int j=0;j<y;++j) typedef long long LL; int T, n, m, a[maxn], flag = 1; int main() { ios::sync_with_stdio(0); cin.tie(0); map<string, int>shop; map<string, int>::iterator it; string s; while (cin >> n) { re(n)cin >> s;//读取什么都不做 cin >> T; while (T--) { int rank = 1; re(n) { cin >> m; cin >> s; shop[s] += m;//第一次会被当成赋值 } for (it = shop.begin(); it != shop.end(); it++) { if (it->second > shop["memory"])++rank;//遍历所有,如果有价格比它高的,则排名下降 } cout << rank << endl; } shop.clear(); } }

8.next_permutation

介绍

next_permutation会按照字典序上升返回所有组合,如abc,用next_permutation()会得到6个组合abc,acb,bac,bca,cab,cba,它的排列范围是[开头,结尾),如果一开始不是最小字典序,可以先sort排序得到最小序列…使用方式一般是do{ }while(next_permutation(开始位置,结束位置)) 更多关于next_permutation

例题

Ignatius and the Princess II HDU - 1027Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, “I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too.” Ignatius says confidently, “OK, at last, I will save the Princess.” “Now I will show you the first problem.” feng5166 says, “Given a sequence of number 1 to N, we define that 1,2,3…N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it’s easy to see the second smallest sequence is 1,2,3…N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It’s easy, isn’t is? Hahahahaha…” Can you help Ignatius to solve this problem?Input The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub’s demand. The input is terminated by the end of file.Output For each test case, you only have to output the sequence satisfied the BEelzebub’s demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.Sample Input 6 4 11 8Sample Output 1 2 3 5 6 4 1 2 3 4 5 6 7 9 8 11 10 思路next_permutation一般和do while更配将m不断减1,减到0结束可以将数字放数组里next_permutation会覆盖本身的内存空间 代码 #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; #define re(x) for(int i=0;i<x;++i) #define rey(y) for(int j=0;j<y;++j) typedef long long LL; int T, n, m, a[maxn], flag = 1; int main() { ios::sync_with_stdio(0); cin.tie(0); while (cin>>n,cin>>m) { re(n)a[i] = i + 1; do { if (!--m)break; } while (next_permutation(a, a + n)); re(n - 1)cout << a[i]<<" "; cout << a[n - 1] << endl;; } }