STL(初阶)

STL(初阶)

一、介绍

stl:c++标准模板库
容器:string vector queue stack set map list
函数:sort reverse next_permutation

二、容器

<一>string

1、定义
头文件:#include<cstring>
string s;
string s="abc";
string s("abc");
string s(5,'a');    //填充5个a
string s("123456",3);    //取字符串前3位“123”
string s("123456",2,4);   //取字符串第2位起的后4位
s=""   //清空字符串
s=a+"123";   //string类型的a与其他字符串相加
2、输入输出
cin>>s;   cout<<s;
s=cin.get();   //读入一个字符
getline(cin;s);   //读入一行
3.迭代器(自行类比于指针)
string::iterator it = s.begin();     //指向首位   //可用于遍历字符串逐个读取字符(在其他容器中同理)

//常用for循环模板:(逐个输出字符)
//eg.
string::iterator it = s.begin(); 
for(it = s.begin(); it!=s.end(); it++)
    cout << (*it) << endl;
 
 //或者合并起来写:
 for(string::iterator it = s.begin(); it!=s.end(); it++)
 
 //也可以用auto来替代:(写起来较方便)
 for(auto it = s.begin(); it!=s.end(); it++)    //auto可自动识别数据类型
4.常用函数
-clear()     //清空字符串   //可用于多组输入初始化
-length()    //获取字符串长度
   s.length()=s.size();
-push_back() //跟加字符    //等同于+=
    //若需多次用到 可先宏定义  (其他同理)
    #define push_back pb
-append()   //跟加字符串   //等同于+=
-find()     //查找字符串位置 ( 找到返回首字符位置  找不到返回-1 )
           //可用于寻找字符串中特定位置开始的多个子串位置
 //eg.
 while(s.find("a",p)!=-1)
 {
     
       p=s.find("1",p+1);   //寻找下一个
       cout<<p<<endl;
 }
-erase()   //可用于删除指定位置的字符串
   s.erase(a,b);  //删除[a,b]区间的字符串(注意第一个下标位置是默认为0)

/*
比较大小可以直接用> 、 < 、 ==
*/

<二>vector 动态数组 内存连续

1.定义
头文件:#include<vector>
vector<类型>名称;
vector<int>v1;
vector<int>v1[100];
vector<string>v2("1234");  //具象化定义
vector<int>v3(5,2);  //具象化定义
vector<int>v4(v3);   //拷贝已有数组
2.常用函数
-v1.push_back(x);   //把x加到v1末尾
-v1.pop_back(x);   //清除v1最后一个元素
-v1.clear();   //清空v1所有元素
-v1.size();    //返回v1中元素个数
-v1.empty;   //判断v1是否为空
-v1.erase(x);   //删除x位置的元素,传回下一个元素的位置
  v1.erase(a,b);   //删除[a,b)区间的元素,传回下一个数据的位置
-v1.front();   //传回第一个数据
-v1.back();    //传回最后一个数据,不检查这个数据是否存在
-v1.insert(x,y);   //在x位置插入y,传回新元素位置
  v1.insert(x,n,y);   //在x位置插入n个y,无返回值
  v1.insert(x,a,b);   //在x位置插入[a,b)区间的数据,无返回值
*-其他
v1.max_size();  //返回容器最大值的个数
v1.begin();   //指向迭代器中的最后一个数据地址
v1.end();   //指向迭代器中的第一个数据地址

<三>queue 队列 先进先出(FIFO)

1.定义

头文件:#include
构造:queue<类型>名称;
eg. queueqe;

2.常用函数
-qe.push();   //在队列末尾加入一个元素
-qe.pop();   //删除队列最后一个元素
-qe.front();   //返回队列第一个元素
-qe.back();   //返回队列最后一个元素
-qe.size();   //返回队列中元素个数
-qe.empty();   //判断队列是否为空(空返回真值 非空返回假值)

<四>stack 堆栈 先进后出 (FILO)

1.定义

头文件:#include
构造:stack<类型>名称;
eg. stackst;

2.常用函数
-st.push();   //在栈顶加入一个元素
-st.pop();   //删除栈顶元素
-st.top();   //返回栈顶元素
-st.size();   //返回堆栈中元素个数
-st.empty();   //判断堆栈是否为空(空返回真值 非空返回假值)

<五>priority_queue 优先队列

#include
priority_queue<int>q;默认大的出列
struct node{
     
	int x,y;
	friend bool operator<(const node &a,const node &b){
     
		return a.x<b.x;//使大的先出列 
	}
};//重载运算符
priority_queue<node >q;
priority_queue<int, vector<int>, greater<int> > q;小的出列 
有多种排序依据
则按需要重载运算符

<六>set 集合 元素有序不重复(类似于数组但会自动去重)

1.定义

头文件:#include
构造函数:sets;
multisetm; //不去重

2.迭代器

Set::iterator it;迭代器
Set::reverse_iterator it;反向迭代器

3.常用函数:
-s.insert(x);   //插入x
-s.erase(x);    //删除x
-s.find(x);    //查找x的位置  找到返回x的位置  否则返回end()
-s.begin();    //最小的位置
-s.end();      //最大的位置
-s.size();    //返回集合中元素的个数
-s.clear();   //清空所有元素
-s.count(x);   //返回容器中值为x的元素个数
-s.lower_bound(x);返回>=x的第一个元素的位置 否则返回end()
-s.upper_bound(x);返回>x的第一个元素的位置 否则返回end()

<七>map 字典(key-value键值对,按key有序排列,可以像数组一样通过[ ]访问)

1.定义

头文件:#include
构造函数:map<类型,类型>mp; //可以嵌套

2.常用函数:
-mp.erase(x);  //删除键值为x的元素 
   mp.erase(mp.begin());   //删除首元素
   mp.erase(mp.begin(),mp.begin()+3);   //删除区间内元素
-mp.find(x);   //查找键值为x的元素 找到返回位置 否则返回end()
-mp.insert(pair<int,string>(123,"abc"));  //添加数据
-mp.size();   //返回元素个数
-mp.clear();   //清空
-mp.count(x);   //判断x是否出现, 返回值为0或1
-mp.lower_bound(x);  //返回键值>=x的第一个位置
-mp.upper_bound(x);   //返回键值>x的第一个位置

mp["abc"]=1;   //也可以这样直接赋值

map<string,int>::reverse_iterator it;   //迭代器
For(it=m.rbegin();it!=m.rend();it++){
        //遍历map
}

<八>list 双向链表(内存不连续)

1.定义

头文件:#include
构造函数:listls

2.常用函数:
-ls.push_back(x);   //后插 
-ls.push_front(x);   //前插
-ls.pop_back(x);   //后删
-ls.pop_front(x);   //前删
-ls.insert(x,y);   //在x位置插入y,传回新元素位置
  ls.insert(x,n,y);   //在x位置插入n个y,无返回值
  ls.insert(x,a,b);   //在x位置插入[a,b)区间的数据,无返回值
-ls.erase(x);   //移除x位置上的元素,返回下一个元素的位置
  ls.erase(a, b);	//移除[a, b)区间内的所有元素,返回下一个元素的位置

三、函数

<一>sort (比qsort快)(默认从小到大升序排序)

hznu 2052
#include  
using namespace std;  
const int maxn = 100010;
int a[maxn], n;
int main(){
     
	cin>>n;  
	for(int i = 0; i < n; i++)
	    cin>>a[i];   //输入n个数 
	sort(a, a + n);   //sort函数 范围为a数组[0,n]  (若为sort(a+1,a+n),则范围为[1,n]) 
	for(int i=0;i<n;i++)
	    cout<<a[i]<<" \n"[i == n - 1];   //输出  [i == n - 1]正则表达式  如果i == n - 1 输出\n  否则输出空格
	return 0;
}

#hznu final F#

#include
using namespace std;
struct yeah{
     
	long long a;
	int b,c; 
	bool operator < (const yeah &r) const {
       //重载运算符 
		if(a == r.a)   //如果威力值相等就按照姿势优美值优先降序输出
			return b > r.b;
		else   //否则威力值大的优先降序输出
			return a > r.a;
	}
};
int main()
{
     
	int n,i;
	scanf("%d",&n);
	yeah x[n];
	for(i=0;i<n;i++)
	    scanf("%lld",&x[i].a);		
	for(i=0;i<n;i++)
	    scanf("%d",&x[i].b);
	for(i=0;i<n;i++)
		scanf("%d",&x[i].c);
	sort(x,x + n);  //利用sort函数排序
	for(i=0;i<n;i++)
	{
     
		if(x[i].c==1)
		{
     
			printf("%d ",x[i].b);
		    break;
		}
	}
	for(i=0;i<n;i++)
	{
     
		if(x[i].c==2)
		{
     
			printf("%d ",x[i].b);
		    break;
		}
	}
	for(i=0;i<n;i++)
	{
     
		if(x[i].c==3)
		{
     
			printf("%d\n",x[i].b);
		    break;
		}
	}
	printf("%d %d",x[0].b,x[0].c);
	return 0;
}

<二>reverse(翻转数组、容器)

int x[1005];
reverse(x+1,x+1+n);
vector<int>ve;
reverse(ve.begin(),ve.end());

<三>next_permutation

//求全排列中字典序更大的一个序列,不存在更大时返回false
int x[105];
int n=5;
for(int i=1;i<=n;i++)x[i]=i;
do{
     
	for(int i=1;i<=n;i++)printf("%d ",x[i]);
	puts("");
}while(next_permutation(x+1,x+1+n));

四、基本例题

1、HDU-1702(queue和stack结合)

题意:每个问题的第一行是一个整数N(命令数),一个单词“FIFO”或“FILO”。下面的N行,每行是“IN M”或“OUT”,(M表示整数),若为IN则往容器中放入数据,若为OUT则取出数据。
输入:多组输入,第一行一个整数N,接下来N行
输出:若为OUT输出对应数据,若没有数据可取则输出“None”
思路:判断类型->判断命令->1.in->存入 2.out (1)空->None (2)非空->取出

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

AC代码:

#include    //万能头文件(POJ上不能用)
using namespace std;
queue<int>qe;
stack<int>st;
int main()
{
     
	int n;
    while(cin>>n)
	{
     
		while(n--)
		{
     
			qe=queue<int>();   //初始化
            st=stack<int>();   //初始化
			int m;   //命令数
			string s,ss;
			cin>>m>>s;
			while(m--)
			{
     
				if(s=="FIFO")
			    {
     
			    	cin>>ss;
			    	if(ss=="IN")
			    	{
     
			    	    int x;
			    	    cin>>x;
				        qe.push(x);   //存入
					}
				    else if(ss=="OUT")
				    {
     
				    	if(qe.empty())   //队列为空则返回“None”
				    	cout<<"None";
				    	else
				    	{
     
				    		cout<<qe.front();   //否则输出第一个数据
				    		qe.pop();   //输出后取出
						}
				    	cout<<"\n";
					}
			    }
			    else if(s=="FILO")
			    {
     
			    	cin>>ss;
			    	if(ss=="IN")
			    	{
     
			    		int x;
			    		cin>>x;
			    		st.push(x);   //存入
					}
					else if(ss=="OUT")
					{
     
				    	if(st.empty())   //堆栈为空则返回“None”
				    	cout<<"None";
				    	else
				    	{
     
						    cout<<st.top();   //否则输出栈顶数据
				    	    st.pop();   //输出后取出
						}
				    	cout<<"\n";
					}	
				}
			}
		}
	 } 
    return 0;
}

//初始化容器有多种方法 除了代码中在每组开头重新定义空容器外 也可以用以下方法 通过遍历数据逐一清除;
/*
		while(!qe.empty())
		qe.pop();
		while(!st.empty())
		st.pop();
*/

2.HDU 2034 (set)

题意:集合相减
输入:每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数,然后紧跟着n+m个元素,前面n个元素属于集合A,其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.
如果n=0并且m=0表示输入的结束,不做处理。
输出:针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合,则输出“NULL”,否则从小到大输出结果,为了简化问题,每个元素后面跟一个空格.
思路:设个set存a集合->从b集合找a集合中的重复元素->找到就删除->最后判断并输出

Sample Input
3 3 1 2 3 1 4 7
3 7 2 5 8 2 3 4 5 6 7 8
0 0

Sample Output
2 3
NULL

#include
using namespace std;
set<int>a;
int main()
{
     
	int n,m;
	while(cin>>n>>m)
	{
     
		if(n==0&&m==0)
		break;
		//a=set();
		for(int i=0;i<n;i++)
		{
     
			int aa;
			cin>>aa;
			a.insert(aa);//把数据a放入a集合 
		}
		for(int i=0;i<m;i++)
		{
     
			int bb;
			cin>>bb;
			if(a.find(bb)!=a.end())
			a.erase(bb);//删除重复数据 进行集合减法 
		 } 
		 if(a.empty())
		 cout<<"NULL";
		 else 
		 {
     
		 	while(!a.empty())  //一边输出一边逐个清空set 
		 	{
            //min_element和max_element自行csdn看 
		 		set<int>::iterator it = min_element(a.begin(),a.end());
                printf("%d ",*it);
                a.erase(*it);
			}
		 }
		 cout<<"\n";
	}
    return 0;
}

3.HDU 1004 (map)

题意:输入多种气球颜色,输出出现次数最多的
输入:输入包含多个测试用例。每个测试用例从一个数字N(0 输出:对于每种情况,在一行上打印最常见问题的气球颜色。保证每个测试用例都有一个唯一的解决方案。
思路:利用map将气球颜色作为键值并累加出现次数 最后输出最大值者

Sample Input
5
green
red
blue
red
red
3
pink
orange
pink
0

Sample Output
red
pink

#include
using namespace std;
int main(){
     
	int n,max;
	char x[20];
	map<string,int> mp;
	string key,value;
	while(cin>>n){
     
		if(n==0)
		break;
		mp.clear();
		for(int i=0;i<n;i++){
     
			cin>>x;
			mp[x]++;  //把颜色作为键值直接++
		}
		map<string,int>::iterator b,c;
		b=c=mp.begin();
		for(;b!=mp.end();b++){
     
			if(b->second>c->second)c=b;
		}
		cout<<c->first<<endl;
	}
	return 0;
} 

你可能感兴趣的