vector

动态数组。在局部区域中（比如局部函数里面）开vector数组，是在堆空间里面开的。在局部区域开数组是在栈空间开的，而栈空间比较小，如果开了非常长的数组就会发生爆栈。故局部区域不可以开大长度数组，但是可以开大长度vector。

#include <vector>
//初始化
vector<node> c;//定义了一个名为c的一维数组，数组存储结构体类型数据，node是结构体类型
vector<int> v(n);// 定义一个长度为n的数组，初始值默认为0，下标范围[0, n - 1]
vector<int> v(n, 1);// v[0] 到 v[n - 1]所有的元素初始值均为1
//注意：指定数组长度之后（指定长度后的数组就相当于正常的数组了）
//方法函数
v.front();// 返回第一个数据 O(1)
v.back();// 返回最后一个数据 O(1)
v.pop_back();// 删除最后一个数据 O(1)
v.push_back(element)// 尾部加入一个数据 O(1)
v.size();//返回实际数据个数 O(1)
v.clear();//删除元素个数 O(N)
v.empty();//判断是否为空 O(1)
v.resize(n, val=0);// 改变数组大小为 n，将新插入的元素赋值为 val
v.reserve(sz);// 提前分配内存大小，防止 push_back 多次拷贝
v.begin();// 返回首元素的迭代器/地址 O(1)
v.end();// 返回最后一个元素后一个位置的迭代器/地址 O(1)
v.insert(it, x);// 向任意迭代器 it 插入一个元素 x O(N)
v.erase(first, last);// 删除 [first, last) 的所有元素 O(N)
v.assign(n, val);// 将 n 个 val 值拷贝到 v 数组中，改变 size 为 n
v.assign(beg, end)// 将另一个容器 [x.begin(), x.end()) 的内容拷贝到 v 中
//访问
v[1];// 下标法 [0, v.size()-1]
vector<int>::iterator it = v.begin();// 迭代器法 声明一个迭代器指向 v 的初始位置，类似指针
for(auto& vv : v);// 智能指针只能遍历完数组

stack

先进先出、后进后出

#include <stack>
//声明
stack<node> s;//node是结构体类型
//方法函数
s.push(element);// 元素 element 入栈，增加元素 O(1)
s.pop();// 移除栈顶元素 O(1)
s.top();// 取得栈顶元素（但不删除） O(1)
s.empty();// 检测栈内是否为空 O(1)
s.size();// 返回元素个数 O(1)
//遍历
//STL 栈只能访问栈顶元素，数组模拟栈更快
int stk[N];
int top=-1;
stk[++top]=element;//入栈
stk[top--];//出栈同时取栈顶值

queue

先进先出

#include <queue>
//定义初始化
queue<int> q;
//方法函数
q.front();//返回队首元素 O(1)
q.back();//返回队尾元素 O(1)
q.push(element);//尾部入队 O(1)
q.pop();//队首出队 O(1)
q.size();//返回元素个数 O(1)
q.empty();//O(1)
//数组模拟队列
int q[N];
int head=0, tail=-1;
q[++tail]=element;//入队
q[head++];//出队同时取栈顶值

deque

首尾都可插入和删除的队列为双端队列，常数很大

#include <deque>
//定义初始化
deque<int> dq;
//方法函数
dq.push_back(x);dq.push_front(x);//插入x到队尾/首 O(1)
dq.back();dq.front();//返回队尾/首元素 O(1)
dq.pop_back();dq.pop_front();//队尾/队首出队 O(1)
dq.erase(iterator it);//删除元素
dq.erase(iterator first, iterator last);//删除 [first,last) 中的元素
dq.empty();//O(1)
dq.size();//O(1)
dq.clear();//清空

priority_queue

保证每次的队首元素都是优先级最大的，底层是通过默认大顶堆来实现的

#include <queue>
//定义初始化
//设置优先级
priority_queue<int> pq; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, greater<int>> q; // 小根堆, 每次取出的元素是队列的最小值
struct node {
    int x, y;
    bool operator < (const Point &a) const {//直接传入一个参数，不必要写friend
        return x < a.x;//按x升序排列，x大的在堆顶
    }
};
priority_queue<Point> q;//优先队列的排序规则和sort的排序规则相反
//方法函数
q.top();//访问堆顶元素 O(1)
q.push(element);//入队 O(logN)
q.pop();// 堆顶出队 O(logN)
q.size();//堆内元素个数 O(1)
q.empty();//O(1)

map

映射，键对于值，键值对。map特性：底层红黑树实现，map会按照键的顺序从小到大自动排序，键的类型必须可以比较大小，查询删除等操作复杂度为O(logN)，空间占用大。unordered_map底层哈希表实现，查找速度快。multimap 键可以重复，即一个键对应多个值。

#include <map>
#include <unordered_map>
#include <multimap>
//定义初始化
map<string, int> mp;
//方法函数
mp.find(key);//返回键为 key 的迭代器，不存在则返回 mp.end() O(logN)
mp.erase(it);//删除迭代器对应的键和值 O(1)
mp.erase(key);//删除映射的键值对 O(logN)
mp.erase(first, last);//删除 [first,last) 迭代器对应的键值对 O(last-first)
mp.size();//返回映射数 O(1)
mp.clear();//清空 O(N)
mp.insert({key,val});mp.insert(make_pair(key,val));//插入元素，插入时要构造键值对 O(logN)
mp.empty();//O(1)
mp.begin();mp.end();//返回迭代器 O(1)
mp.rbegin();mp.rend();//返回指向最后一个元素/第一个元素上一个元素的逆向迭代器 O(1)
mp.count(key);//查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0
mp.lower_bound(key);//返回一个迭代器，指向键值>= key的第一个元素
mp.upper_bound(key);//返回一个迭代器，指向键值> key的第一个元素
//查找元素一般用find() 或 count() 先判断存在与否，再索引对应值（适用于这两种容器）
//迭代器进行正反向遍历
for(auto it=mp.begin(); it!=mp.end(); ++it){
    cout<<it->first<<" "<<it->second<<"\n";
}
mp[key]=val;//添加元素或访问已存在元素可以用 mp[key]

set

set里面的元素不重复 且有序。multiset:元素可以重复，且元素有序。unordered_set ：元素无序且只能出现一次。unordered_multiset ： 元素无序可以出现多次。

#include <set>
//定义初始化
set<int> s;
//重载<运算符
set<int, greater<int> > s2; // 从大到小排序，默认为 less<int>
//结构体内重载<运算符
//函数方法
s.begin();s.end();//返回迭代器 O(1)]
s.rbegin();s.rend();//返回指向最后一个元素/第一个元素上一个元素的逆向迭代器 O(1)
s.clear();//清空 O(N)
s.empty();//O(1)
s.insert(element);//插入
s.size();// O(1)
s.erase(iterator it);//删除迭代器 it 指向的元素
s.erase(first, last);//删除 [first,last) 迭代器对应的键值对
s.find(element);//查找 element, 有则返回迭代器，否则返回 s.end()
s.count(element);//查找set中的元素出现的个数，由于set中元素唯一，此函数相当于查询element是否出现
mp.lower_bound(k);//返回一个迭代器，指向键值>= k的第一个元素 O(logN)
mp.upper_bound(k);//返回一个迭代器，指向键值> k的第一个元素 O(logN)
//访问
//迭代器
for(set<int>::iterator it = s.begin(); it != s.end(); it++) cout << *it << " ";
//智能指针
for(auto i : s) cout<<i<<"\n";

pair

pair只含有两个元素，可以看作是只有两个元素的结构体。

#include <utility>
//1.初始化定义 
pair<string,int> p("wangyaqi",1);//带初始值的 
pair<string,int> p;//不带初始值的 
//2.赋值 
p = {"wang", 18}; 
p = make_pair("wang", 18); 
p = pair<string, int>("wang", 18);
//访问
p.first;p.second;

string

支持比较运算符，支持拼接运算符 + 。

#include <string>
string s;
//读入
//读入字符串，遇空格，回车结束
cin >> s;
//读入一行字符串（包括空格），遇回车结束
getline(cin, s);//getline(cin, s)会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或 cin.get()
//正确读取
cin >> n;
getchar(); //cin.get()
getline(cin, s);//可正确读入下一行的输入
//支持排序
sort(s.begin(),s.end());  //按ASCII码排序

bitset

类似数组，并且每一个元素只能是０或１，每个元素只用１bit空间。一般会使用bitset来优化时间复杂度，大概时间复杂度会除64或32。bitset还有开动态空间的技巧，bitset常用在01背包优化等算法中。

#include <bitset>
//初始化
bitset<N> a;//a有n位，每位都为0
bitset<N> a(b);//a是unsigned long型u的一个副本
bitset<N> a(s);//a是string对象s中含有的位串的副本
bitset<N> a(s,pos,N);//a是s中从位置pos开始的n个位的副本
//支持位运算
//访问通过 []
//方法函数
b.any();//b中是否存在置为1的二进制位，有 返回true
b.none();//b中是否没有1，没有 返回true
b.count();//b中为1的个数
b.size();//b中二进制位的个数
b.test(pos);//测试b在pos位置是否为1，是 返回true
b[pos];//返回b在pos处的二进制位
b.set();//把b中所有位都置为1
b.set(pos);//把b中pos位置置为1
b.reset();//把b中所有位都置为0
b.reset(pos);//把b中pos位置置为0
b.flip();//把b中所有二进制位取反
b.flip(pos);//把b中pos位置取反
b.to_ulong();//用b中同样的二进制位返回一个unsigned long值
// 动态长度bitset实现
const int N = 1e6 + 5; // 开空间的上限，一般为数据范围附近的值
template <int len = 1>
void bitset_(int sz) { // sz即为想要开的大小
	if (len < sz) { bitset_<min(len * 2, N)>(sz); return; }
	bitset<len + 1> dp;
	// 具体算法的实现
}

库函数

所有 beg 和 end 都是迭代器/地址，end 指向最后一个元素后一个位置

accumulate

//求和，init为对序列元素求和的初始值。cmp为自定义求和函数 O(N)
//返回值类型：与init 相同
#include <numeric>
accumulate(beg, end, init, add);
ll res = accumulate(st + 1, st + 4, 1ll, [](ll a,node b) {
    return a + b.num;
});

inner_product

#include <numeric>
// 向量内积 O(n)  返回 v1(bg1, ed1) \cdot v2(bg2, bg2+ed1-bg1) +val O(N)
inner_product(bg1,ed1,bg2,val)

fill

#include <algorithm>
//对一个序列进行初始化赋值 O(N)
fill(beg, end, num);

lower_bound + upper_bound

#include <algorithm>
//二分查找 O(logN)
//在a数组中查找第一个大于等于x的元素，返回该元素的地址
lower_bound(a, a + n, x);
//在a数组中查找第一个大于x的元素，返回该元素的地址
upper_bound(a, a + n, x);
//如果未找到，返回尾地址的下一个位置的地址

max+min

#include <algorithm>
//找多个元素的最大值和最小值 O(1)
//找到a,b,c,d的最大值和最小值
mx = max({a, b, c, d});
mn = min({a, b, c, d});

nth_element

#include <algorithm>
//寻找第序列第n小的值 平均 O(N)
//nth为一个迭代器，指向序列中的一个元素。第n小的值恰好在nth位置上。
//执行nth_element()之后，序列中的元素会围绕nth进行划分：nth之前的元素都小于等于它，而之后的元素都大于等于它
//常用于线性求序列中的第 k 大，常用于实现替罪羊树
nth_element(beg, nth, end)

reverse

#include <algorithm>
//翻转序列 O(N)
reverse(beg,end)

sort + stable_sort

#include <algorithm>
//原型： O(NlogN) 排序
sort(beg, end);
sort(beg, end, cmp);
//stable_sort能够保证相等元素的相对位置，排序时不会改变相等元素的相对位置

unique

#include <algorithm>
// 消除有序序列重复元素，返回消除完重复元素的下一个位置的地址 O(N)
unique(beg, end);