杂 - [杂项] Cpp STL - 《【芝士】码不动代码》

[0.x]前言
目录
[1.x]vector
[2.x]queue/priority_queue
[3.x]deque
[4.x]set/multiset
[5.x]map
[6.x]bitset
[7.x]algorithm
- [7.1.x]操作

[0.x]前言

本文针对 $[杂项] Cpp STL - 图1$ 的 $[杂项] Cpp STL - 图2$ 容器

参考书目：《算法竞赛进阶指南》

所有容器都前闭右开（类比声明了数组a[n]后调用a[n]属于越界行为）

$[杂项] Cpp STL - 图3$ 的迭代器相当于指针，语法类似，使用方式为???::iterator ??=???

[1.x]vector

[1.1]性质

大小会随着元素的数量变化（节约空间）
支持随机访问（支持下标访问）
不支持 $[杂项] Cpp STL - 图4$ #card=math&code=O%281%29&id=EMAjz)插入

[1.2]声明

#include<vector>//头文件
using std::vector;
vector<int> a;//a[i]中i所在的维动态伸缩
vector<int> b[10];//b[i][j]中j所在的维动态伸缩
//其中<int>可以换成<bool>/<char>/<string>/....且支持结构体

[1.3.x]操作

[1.3.1]size/empty

cout << "vector型变量a的长度为" << a.size();
if(a.empty()){
    cout << "vector型变量a为空";
}else{
    cout << "vector型变量a不为空";
}

[1.3.2]clear

a.clear();//清空vector型变量a

[1.3.3]begin/end

vector<int>::iterator it = a.begin();
cout << "vector型变量a的第一个元素为" << *it;
cout << "vector型变量a的第一个元素为" << a[0];//两行等效
it = a.end();
cout << "vector型变量a的最后一个元素为" << *--it;
cout << "vector型变量a的最后一个元素为" << a[a.size()-1];//两行等效

[1.3.4]front/back

从front与begin类似，只不过一个返回元素一个返回迭代器，即*a.begin()与a.front()等效，当然也等效于a[0]

而back与end略有区别，*--a.end()或a[a.size()-1]与a.back()等效(一般情况下)

vector<int>::iterator it = a.begin();
cout << "vector型变量a的第一个元素为" << *it;
cout << "vector型变量a的第一个元素为" << a[0];
cout << "vector型变量a的第一个元素为" << a.front();//三行等效
it = a.end();
cout << "vector型变量a的最后一个元素为" << *--it;
cout << "vector型变量a的最后一个元素为" << a[a.size()-1];
cout << "vector型变量a的最后一个元素为" << a.back();//三行等效

一般begin/end用于循环，而front和back只能用来返回顶部和底部。

[1.3.5]push_back/pop_back

a.push_back(x);//把元素x插入到vector类型变量a的尾部
a.pop_back;//把vector类型变量a尾部元素推出

[2.x]queue/priority_queue

[2.1]性质

不支持随机访问
priority_queue满足元素有序（默认降序，堆顶部（看作大根二叉堆）为 $[杂项] Cpp STL - 图5$ ），如果储存元素类型不属于数字类型或者**string**类型需要定义比较规则。

[2.2]声明

#include<queue>//头文件
using std::queue;using std::priority_queue;
queue<int> q1;//循环队列
queue< pair<int,int> > q2;
priority_queue<int> q3;//优先队列
priority_queue< pair<int,int> > q4;

[2.3.x]操作

注意：由于循环队列和优先队列操作略有不同，所以以下变量q为循环队列，p_q为优先队列。

[2.3.1]push/pop

q.push(x);//把元素x插入到queue类型变量q的尾部
q.pop();//把队首元素弹出
p_q.push(x);//把元素x插入到priority_queue类型变量p_q
p_q.pop();//把堆顶元素弹出，即有序数列的首元素

[2.3.2]front/back & top

cout << "queue型变量q的第一个元素为" << q.front();
cout << "queue型变量q的最后一个元素为" << q.back();
cout << "priority_queue型变量p_q的堆顶元素为" << p_q.top();

[3.x]deque

咕咕咕

[4.x]set/multiset

[4.1]性质

set储存有序集合
multist储存有序多重集合
重载相关类似priority_queue
迭代器只支持++和--，时间复杂度都在 $[杂项] Cpp STL - 图6$ #card=math&code=O%28logn%29&id=kxjft)，注意不要越界
默认升序

[4.2]声明

#include<set>
using std::set;using std::multiset;
set<int> s;
multiset<int> ms;

[4.3.x]操作

注意：s表示有序集合，ms表示有序重复集合

[4.3.1]size/empty/clear

同理vector

[4.3.2]begin/end

同理priority_queue

[4.3.3]insert

s.insert(x);//将元素x插入到集合s中，如果s中已经存在元素x则不变化
ms.insert(x);//将元素x插入到集合ms中，如果s中已经存在元素x则再插入一个

[4.3.4]find

$[杂项] Cpp STL - 图7$ #card=math&code=O%28logn%29&id=vICup)查找元素(返回迭代器)，不存在则返回end()
有序多重集合返回第一个该元素的迭代器

set<int>::iterator it = s.find(x);//*it为元素x，it为其迭代器
multiset<int>::iterator it = ms.find(x);//*it为元素x，it为其迭代器

[4.3.5]lower_bound/upper_bound

?? = s.lower_bound(x);//O(logn)查找>=x的元素中最小的，返回迭代器（需要保证序列升序）
?? = s.upper_bound(x)//O(logn)查找>x的元素中最小的，返回迭代器（需要保证序列升序）
?? = ms.lower_bound(x)//O(logn)查找>=x的元素中最小的第一个，返回迭代器（需要保证序列升序）
?? = ms.upper_bound(x)//O(logn)查找>x的元素中最小的第一个，返回迭代器（需要保证序列升序）

如果需要应用在降序数列里，可以传输比较规则greater<int>()。

[4.3.6]erase

set<int>::iterator it;
s.erase(it);//O(logn)删除it所指向的元素
ms.erase(it);//O(logn)删除it所指向的元素
int x;
s.erase(x);//O(k+logn)删除所有x元素
ms.erase(x);//O(k+logn)删除所有x元素

[4.3.7]count

s.count(x);//返回集合s中等于x的元素的个数
ms.count(x);//返回集合s中等于x的元素的个数

[5.x]map

[5.1]性质

支持任意类型的key-value映射，但key需要有比较规则
迭代器取值以后得到二元组pair<key_type,value_type>

[5.2]声明

map<string,int> mp;//string类-int类映射，可以替换类型

[5.3.x]操作

[5.3.1]size/empty/clear/begin/end

同前

[5.3.2]insert/erase

同前
insert需要插入对应的二元组
erase可以是二元组或迭代器

mp.insert(make_pair(x,y));//插入x-y的映射
mp.erase(make_pair(x,y));//删除x-y的映射
mp.erase(it);//删除it所指的映射

[5.3.3]find

同前， $[杂项] Cpp STL - 图8$ #card=math&code=O%28logn%29&id=Xbtoy)查找目标为key

[5.3.4]`[]`

mp[str] = a;
mp[ch] = flag;
...
//使用[]前最好先用find查询是否存在映射，否则会浪费空间

[6.x]bitset

咕咕咕

[7.x]algorithm

注意：以下操作都作用在序列上，都在前闭后开区间 $[杂项] Cpp STL - 图9$ #card=math&code=%5Bl%2Cr%29&id=GauxF)中的元素进行操作

[7.1.x]操作

[7.1.1]reserve

vector<int> a;
reverse(a.begin(),a.end());//翻转vector类型变量a
int b[100];
reverse(b+1,b+n+1);//翻转数组b中1~n的序列

[7.1.2]unique

vector<int> a;
cout << "vector型变量a去重后的元素个数为" << unique(a.begin(),a.end()) - a.begin();
int b[100];
cout << "数组b去重后的元素个数为" << unique(b+1,b+n+1) - (b+1);//去重后元素存放在下标1~n，未去重的部分保留

[7.1.3]random_shuffle

vector<int> a;
random_shuffle(a.begin(),a.end());//打乱vector类型变量a
int b[100];
random_shuffle(b+1,b+n+1);//打乱数组b中1~n的序列

[7.1.4]next_permutation/prev_permutation

//按照字典序输出全排列(起始数列升序)
do{
    for(int i = 1;i <= n;i++){
        cout << a[i] << " ";
    }cout << endl;
}while(next_permutation(a+1,a+n+1));
//按照字典序倒着输出全排列(起始数列降序)
do{
    for(int i = 1;i <= n;i++){
        cout << a[i] << " ";
    }cout << endl;
}while(prev_permutation(a+1,a+n+1));

[7.1.5]sort

略

[7.1.6]lower_bound/upper_bound

同前，需要数列升序