C++ STL（蓝桥杯应急）_v.push_back(i);

目录

vector

queue

priority_queue

stack

map

set

算法函数

全排列函数next_permutation() 

反转内容reverse(s,s+10) / reverse(s.begin(),s.end())

整数的绝对值 abs(n)

sort()

---

vector

///vector
vector<int> v;
    vector<int> ::iterator i;
    for(int i=0;i<10;i++)
        v.push_back(i);
    for(i=v.begin();i!=v.end();i++)
        printf("%d ",*i);
    printf("\n");
    i=v.begin()+5;
    v.insert(i,12);
    v.erase(i,i+5);
    for(i=v.begin();i!=v.end();i++)
        printf("%d ",*i);

queue

///queue
    queue<int> q;
    for(int i=1;i<10;i++){
        q.push(i);
    }
    printf("%d\n",q.back());
    int a[10];
    for(int i=0;i<10;i++)
        a[i]=i;
    sort(a,a+10,cmp);
    printf("%d",a[9]);
    while(q.size()){
        printf("%d ",q.front());
        q.pop();
    }

priority_queue

• 大顶堆：堆顶元素最大，less<int> priority_queue<int> q;默认大顶堆
• 小顶堆：堆顶元素最小, greater<int>； priority_queue<int,vector<int>,greater<int> > q

应用

求已经加入队列的数的第k大的数是多少

可以用优先队列中的小顶堆来解决。在队列中只保存k个数，这k个数按大小顺序排列，最前面的是“最优”，即是这k个数中最小的（便是第k大）。对于新加入的数，只需要和priority_queue队列中的top比较，如果比top小，那这个数就无意义，不压入队列；如果比这个数大，之前的“最优解”已经不是第k大的数了，所以把它踢出，压入这个新元素，然后priority_queue就会自动再排列，top又变成“最优解”。

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    ///priority_queue
    priority_queue<int,vector<int>,greater<int> > q;
    char s;
    int n,k,t;
    scanf("%d %d",&n,&k);
    getchar();
    while(n--){
        cin>>s;
        if(s=='I'){
            scanf("%d",&t);
            if(q.size()<k)
                q.push(t);
            else{
                if(t>q.top()){
                    q.pop();
                    q.push(t);
                }
            }
        }else{
            printf("%d\n",q.top());
        }
    }
    return 0;
}

stack

练习题： 

“蓝桥杯”练习系统http://lx.lanqiao.cn/problem.page?gpid=T517

#include<bits/stdc++.h>
using namespace std;
string s;
int i,a,b,flag=1;
int f(int x,int y){
	return a*x+b*y;
}
 
int cal(int i,int flag){
    int num=0;
    while(isdigit(s[i])){
        num=num*10+s[i]-'0';
        i++;
    }
    return num*flag;
}
 
int main(){
 
    stack<int> sk;
    cin>>a>>b;
    cin>>s;
    for(i=0;i<s.size();i++){
        flag=1;
        if(s[i]=='-'){
            i++;
            flag=-1;
            sk.push(cal(i,flag));
        }
    else if(isdigit(s[i]))
        sk.push(cal(i,flag));
    if(s[i]==')'){
        int y =sk.top(); sk.pop();
			int x = sk.top(); sk.pop();
			sk.push(f(x,y));
    }
    }
    printf("%d\n",sk.top());
    return 0;
}

map

映射

map<int,int> mp;

mp.clear() 

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    map<char,int> m;
    m.clear();
    m['c']=12;
    m['a']=1;
    m['b']=32;
    m['e']=4;
    m['r']=98;
    map<char,int>::iterator i;
    for(i=m.begin();i!=m.end();i++){
        printf("%c %d",i->first,i->second);
    }
    return 0;
}

 

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    map<int,int> mp;
    int n,a,maxx=0,minn=100000,x,y;
    cin>>n;
    while(scanf("%d",&a)!=EOF){
        mp[a]+=1;
        minn=min(a,minn);
        maxx=max(a,maxx);
    }
    for(int i=minn;i<=maxx;i++){
        if(mp[i]==0)x=i;
        else if(mp[i]==2) y=i;
    }
    cout<<x<<" "<<y<<endl;
    return 0;
}

set

集合，自动去重，自动由小到大排序

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    set<int> s;
    for(int i=5;i<10;i++)
        s.insert(i);
    s.insert(2);
    s.insert(5);
    set<int>::iterator i;
    for(i=s.begin();i!=s.end();i++)
        cout<<*i<<" "<<endl;
    return 0;
}

算法函数

全排列函数next_permutation() 

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int a[6]={1,2,3,4,5,6};
    do{
        for(int i=0;i<6;i++)
            cout<<a[i]<<" ";
        printf("\n");
    }
    while(next_permutation(a,a+6));
    return 0;
}

 

反转内容reverse(s,s+10) / reverse(s.begin(),s.end())

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    vector<int> v;
    for(int i=0;i<10;i++){
        v.push_back(i);
    }
    reverse(v.begin(),v.end());
    for(int i=0;i<10;i++)
        cout<<v[i]<<endl;
    return 0;
}

整数的绝对值 abs(n)

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int a=-21;
    cout<<abs(a)<<endl;
    return 0;
}

 

sort()

sort(a,a+10) //由小到大

sort(a,a+10,greater<int>()) //由大到小

结构体排序 

#include<bits/stdc++.h>
using namespace std;
 
typedef struct{
    int number;
    string name;
}Student;
 
bool cmp(Student x,Student y){
    return x.number<y.number;
}
 
int main(){
    Student s[2];
    s[0].name="sss";
    s[0].number=5;
    s[1].name="yyy";
    s[1].number=2;
    sort(s,s+2,cmp);
    printf("%d",s[0].number);
    return 0;
}