OI

【模板】STL合集

注：迭代器不开O2太慢，本文已放弃orz

#include<algorithm>

sort

缺省从小到大：

1
2
int a[100];
sort(a+1,a+n+1);//a[1]~a[n]

用cmp函数指针自定义排序顺序：

1
2
3
4
5
6
bool cmp(int a,int b){
    return a>b;
}

//main
sort(a+1,a+n+1,cmp);

cmp函数可以用于结构体的排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//P1093
struct node{
    int ch,en,ma;
    int sum;
    int num;
};

node a[500]={0};
bool cmp(node &a,node &b){
    if(a.sum>b.sum)return 1;
    if(a.sum<b.sum) return 0;
    if(a.ch>b.ch)return 1;
    if(a.ch<b.ch) return 0;
    if(a.num<b.num)return 1;
    return 0;
}
//main:
sort(a+1,a+n+1,cmp);

#include<queue>

queue队列

一般是广搜、最大流时候用。 

1
2
3
4
5
6
queue<TYPE> q;
q.empty();//返回是否为空
q.push(x);
q.pop();
q.front();//返回队首元素
q.back();//返回队尾元素

priority_queue优先队列

一般不想手打，堆优化的时候用
默认大根堆： 

1
2
3
4
5
priority_queue<TYPE> q;
q.empty();//返回是否为空
q.push(x);
q.pop();
q.top();//返回队首元素

小根堆定义：
> >要有空格，不然会>>

1
priority_queue<int,vector<int>,greater<int> >q2;

结构体（以dijkstra堆优化为例）: 

1
2
3
4
5
6
7
8
9
10
11
12
struct node{
    int no;
    ll dist;
    node(int x,ll y){
        no = x;
        dist = y;
    }
    bool operator <(const node &s)const{
        return s.dist<dist;
    }
};
priority_queue<node> q;

另外小根堆可以通过入、出队时取反实现。

#include<string>

由于C中对字符串的操作很尴尬，C++中把string作为一个类，可以和其他STL的模板类一起使用了。所以为了兼容C语言转入的选手，最不济的做法就是把string和cstring互相转化，用STL的时候就string，不用的时候转cstring操作。下面的例子就是这种混编的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int main(){
    char c[100];
    strcpy(c,"abcde");
    string s(c);
    cout<<s;
    
    cin>>s;
    strcpy(c,s.c_str());
    printf("\n%s",c);
    return 0;
}

注：s.c_str()函数返回一个const char*，无法对其操作，必须拷贝下来。

然而，string类比cstring支持更多操作。

#include<map>

map类解决两个类型数据之间的对应关系，用它可以快速实现字符串hash类似的功能。复杂度是$O(logn)$级的。

1
map<TYPE1,TYPE2> m;

比如：

1
map<string,int> m;

使用[ ]运算符可以对map对象进行插入操作。[ ]中是插入的对象，是第一个类型的对象。 

1
2
3
m["abc"]=1;
m["abd"]=2;
printf("%d %d",m["abc"],m["abd"]);

输出：
1 2
两个类型是有顺序的，所以不支持反向的查找；

多对一是可以的： 

1
2
3
m["abc"]=1;
m["bcd"]=1;
//m["abc"]==m["bcd"]

未赋值的将会返回0：

1
2
3
4
5
6
7
8
map<string,int> m1;
printf("%d\n",m1["hgg"]);
    
map<string,double> m2;
printf("%lf\n",m2["hgg"]);
    
map<string,string> m3;
printf("%s\n",m3["hgg"].c_str());

输出：
0
0.000000
(\n)

以P3370字符串hash为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
using namespace std;
const int MAXM=1505;
int main(){
    map<string,int> m;
    char s[MAXM];
    int n;
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        if(m[s]==0){
            m[s]=i;
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}

就很便捷了。