[C++知识库]算法竞赛常用STL

参考资料：

• https://blog.csdn.net/weixin_49486457/article/details/123439229
• https://www.cnblogs.com/xzxl/p/7266404.html
• https://blog.csdn.net/qq_36631379/article/details/108833192
• https://www.acwing.com/blog/content/9/
• https://www.cnblogs.com/Anber82/p/11351833.html
• https://blog.csdn.net/qq_18815817/article/details/82431685

1 vector

可用来实现图论中的邻接表

1.1 头文件

#include<vector>

1.2 创建

//方法一
vector<int> a;			//创建空vector
//方法二
vector<int> a(10);		//创建容量为10的vector
//方法三
vector<int> a(10, 1);	//创建容量为10，每个元素初值为1的vector

1.3 常用方法

a.size();		//返回a的大小
a.empty();		//判断a是否为空，是则为true，反之为false
a.clear();		//清空a
a.front();		//返回a中的第一个元素
a.back();		//返回a中的最后一个元素
a.push_back(x)	//在a的尾部插入一个元素x
a.pop_back()	//删除a的最后一个元素，返回值为void

此外，vector还支持比较运算，比较方法为字典序比较。

1.4 常用技巧

1.4.1 遍历vector

for(int i=0;i<a.size();i++){
	cout<<a[i]<<' ';
}

2 pair

不是很常用

2.1 头文件

#include<utility>

2.2 创建

//方法一
pair<int, int> p1(1, 2);
//方法二
pair<int, int> p2;
p2 = make_pair(1, 2);

2.3 访问

p1.first;		//第一个元素
p2.second;		//第二个元素

3 string

3.1 头文件

#include<string>

3.2 创建

string s = "12345";

3.3 常用方法

//substr()不会改变原字符串
s.substr(1, 3);		//返回从下标为1的字符开始，长度为3的子串
s.substr(2);		//返回从下标为2的字符开始，以最后一个字符为结尾的子串

s.push_back('0');	//尾插一个字符'0'

string s = "123";
string b = "hello";
s.insert(1, b, 0, 2);	//将b中从下标为1的字符开始，长度为2的子串插入到s的下标为1的字符之前
						//s = "1he23"

s.clear()			//清空字符串
s.empty()			//判断s是否为空字符串
s.size()			//返回s的大小

stoi(s, n, b)		//将字符串s从下标为n的字符开始的子串当作b进制的数字，转化成十进制的整型。
string s = "1010";
int a = stoi(s, 0, 2);	//a = 10;

to_string(a)	//a为任意类型的数值类型

4 queue&stack

4.1 头文件

#include<queue>
#include<stack>

4.2 创建

queue<int> q;
stack<int> s;

4.3 常用方法

//queue和stack共有的：
a.size();
a.empty();
a.push();
a.pop();
//stack
s.top();		//返回栈顶元素
//queue
q.front();		//返回队首元素
q.back();		//返回队尾元素

5 priority_queue

可以理解为二叉堆，很实用！

5.1 头文件

#include<queue>

5.2 创建

//方法1
priority_queue<int> q;		//默认为大根堆

//方法2：自定义比较函数
struct cmp{		//仿函数
	bool operator()(int a, int b)const{		//重载“()”运算符
		return a>b;
	}
};
priority_queue<int, vector<int>, cmp>;		//小根堆

//方法3：结构体优先队列
struct node{
	int x, y;
	bool operator<(const node& n)const{
		return x>n.x;
	}
};
priority_queue<node> q;

5.3 常用方法

q.size();
q.empty();
q.push(); 
q.pop(); 	//弹出堆顶元素
q.top();	// 返回堆顶元素

6 deque

6.1 头文件

#include<deque>

6.2 创建

deque<int> dq;

6.3 常用方法

dq.size();
dq.empty();
dq.clear();
dq.front();
dq.back();
dq.push_back(); //向最后插入一个元素
dq.pop_back(); //弹出最后一个元素
dq.push_front(); //向队首插入一个元素
dq.pop_front();//弹出第一个元素

7 set

类似数学中的集合

7.1 头文件

#include<set>

7.2 创建

set<int> s;

7.3 常用方法

s.size();
s.empty();
s.clear();
s.insert();
s.find();		//没找到则返回s.end()
s.count();
s.erase(x);
s.erase(s.begin(),s.end());

8 unordered_map

需要支持C++11（没有C++11，用hash_map也行）

8.1 头文件

#include <unordered_map>

8.2 创建

unordered_map<string, double> t;

8.3 常用方法

//插入
t["July"] = 7;
//判断键值是否存在。若存在，则：
t.count("July") != 0;
t.find("July") != t.end();

9 algorithm

9.1 sort

默认升序排序

//方法一
struct NODE{
	int x, y;
	bool operator<(const NODE& n)const{
		if(x==n.x) y<n.y;
		return x<n.x;
	}
}node[maxn];
sort(node, node+maxn)

//方法二
struct NODE{
	int x, y;
}node[maxn];
bool cmp(NODE a, NODE b){
	if(a.x==b.x) a.y<b.y;
	return a.x<b.x;
}
sort(node, node+maxn, cmp);

9.2 unique

int a[10] = {1, 2, 2, 1, 3, 5, 5, 9, 9, 0};
int n = unique(a, a+10)-a;		//n为去重后数组的长度
for(int i=0;i<n;i++) cout<<a[i]<<' ';	//1，2，1，3，5，9，0

9.3 lower_bound

功能：返回指向第一个值不小于val的位置（一般情况下需要保证数组有序）。

//形式一：
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,  const T& val);

//形式二：
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

sort+unique+lower_bound可以实现离散化，代码如下：

int a[7] = {12313987, 5723891, 471823956, 12313987, 75698634, 2141749, 471823956};
int b[7];
memcpy(b, a, sizeof(a));
sort(b, b+7);
int n = unique(b, b+7)-b;
for(int i=0;i<7;i++){
	a[i] = lower_bound(b, b+n, a[i])-b;
	cout<<a[i]<<' ';
}	
//2 1 4 2 3 0 4

9.4 __gcd

int n=35, m=45;
int k = __gcd(n, m);
cout<<k<<'\n';		//最大公约数
cout<<n/k*m;		//最小公倍数

10 杂项

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);