常用STL

发表于

虽然有时会炸，但STL为我们节省了大量的精力。

作为广大oier喜闻乐见的工具，有必要对常用的STL容器掌握

Vector 动态数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
头文件 #include <vector>
创建vector对象 vector<int>v;
尾部插入 v.push_back(a);
使用下标访问(下标从0开始)
cout<<v[0];
使用迭代器访问

vector<int>::iterator it;
for(it=v.begin();it!=v.end();it++)
cout<<*it<<endl;

插入元素
在第i+1个元素前插入a
v.insert(v.begin()+i,a)；

删除元素
删除第i+1个元素
v.erase(v.begin()+i);

删除区间[i,j-1]
v.erase(v.begin()+i,v.end()+j);

大小v.size();

清空v.clear();

Stack 栈

1
2
3
4
5
6
7
8
9
10
11
12
头函数 #include <stack>
创建 stack<int>S;
入栈 s.push(x);
出栈 s.pop();
访问栈顶 s.top();
判断栈空 s.empty();
栈的大小 s.size();
限制栈的大小

#define STACK_SIZE  100  
............
if(s.size()<STACK_SIZE)s.push(x);

Queue 单向队列

1
2
3
4
5
6
7
8
头文件 #include <queue>
创建 queue<int>Q;
入队 Q.push(x);
出队 Q.pop();
访问队首 Q.front();
访问队尾 Q.back();
判断队空 Q.empty();
元素个数 Q.size();

Priority_queue 优先队列

优先队列默认为一个大根堆(队首总是最大的)

1
2
3
4
5
6
7
8
9
10
11
12
13
头文件 #include <queue>
定义小根堆 priority_queue<int,vector<int>,greater<int> >q;
创建 

priority_queue<int> q;
等价于priority_queue<int,vector<int>,less<int> >;

q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
q.back();//返回q的末尾元素

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<queue>
using namespace std;
struct node
{
    int x,y;
    bool operator < (const node & a) const
    {
        return x<a.x;
    }
}k;
priority_queue <node> q;
int main()
{
    k.x=10,k.y=100; q.push(k);
    k.x=12,k.y=60; q.push(k);
    k.x=14,k.y=40; q.push(k);
    k.x=6,k.y=80; q.push(k);
    k.x=8,k.y=20; q.push(k);
    while(!q.empty())
    {
        node m=q.top(); q.pop();
        printf("(%d,%d) ",m.x,m.y);
    }
}

结果(14,40) (12,60) (10,100) (8,20) (6,80)

Set 集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
头文件 #include <set>
构造 set<int>T;
插入 T.insert(x);
删除 T.erase();
清空 T.clear();
大小 T.size();
遍历元素

for(set<int>::iterator it=T.begin();it!=T.end();++it)
cout<<(*it)<<endl;

查找
存在返回该元素的迭代器
不存在返回T.end();

#include<cstdio>
#include<set>
using namespace std;
set<int> Demo;
int main(){
	Demo.insert(1);
	set<int>::iterator it=Demo.find(1);
	if (it==Demo.end()){
		printf("No Find\n");
	}else{
		printf("Find\n");
	}
	return 0;
}

统计个数 T.count(x)返回集合中等于x的个数

Map 映射

map是一个key-value映射，可以理解为超级数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
头文件 #include <map>
声明
map<long long,bool>vis;
map<pair<int,int>,vector<int>>test;
操作
size/empty/clear/begin/end
迭代器
map的迭代器与set一样，也是双向访问迭代器，不支持随机访问，支持*解除引用和++与--
对map的迭代器解除引用后，得到一个二元组pair<key,value>
插入与删除
map<int,int>h;
h.insert(make_pair(1,1));
map<int,int>::iterator it=h.begin();
pair<int,int>p=*it;
h.erase(it);
cout<<p.first<<p.second;
查找
h.find(x)在h中查找key为x的二元组，并返回指向该二元的迭代器，若不存在，返回h.end()
[]操作符
string str;
map<string,int>a;
cin>>str;
a[str]=666;
cout<<a[str];

Bitset 二进制

bitset可看作是一个多位的二进制数，每8位占1个字节，支持基本的位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bitset>
bitset<616>s; //616位的二进制数s
～s 返回对s取反的结果
& | ^返回两个位数相同的bitset按位与，或，异或的结果
>> << 左移，右移若干位
== !=比较相等与否

s[k]s的第k位，可取值，也可赋值
s.count()返回有多少位1
若s的所有位都是0，s.any()返回false,s.none()返回true
若s至少一位为1，s.any()返回true s.none()返回false

s.set()所有位变1
s.reset()所有位变0

Algorithm算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<algorithm>
reserve翻转
翻转数组a[1]~a[n]
reserve(a+1,a+n+1);
sort快速排序
排a[1~n],从小到大
sort(a+1,a+n+1);
比较函数
struct Node{
    int m,n;
}k[8];
bool cmp(Node a,Node b){
    return a.m<b.m;
}
sort(k+1,k+n+1,cmp);
结构体内部的重载
struct Node{
    int a,b;
    bool operator < (const Node &c) const{
        return a<c.a;
    }
}k[101];
sort(k,k+100);