STL相关

（由[我的hexo博客](http://www.xjdesyxx.top/2020/02/26/stl/)搬运并同步维护） 最近每次打比赛用到STL的时候都想去查查，来防止写错，因此浪费了大量的时间，遂决定写篇博客，到时候直接在博客查阅。 ## queue 队列 ### methods in code ```cpp #include<stdio.h> #include<queue> struct node{int x,y;}; std::queue<node> Q; int main() { Q.push((node){1,1}),Q.push((node){2,2}); printf("size:%d\n",Q.size());//=>size:2 printf("队首x元素:%d\n队尾x元素:%d\n",Q.front().x,Q.back().x); //=>队首x元素:1 //=>队尾x元素:2 while(!Q.empty())Q.pop(); return 0; } ``` ## priority_queue 优先队列 `priority_queue` 默认是大根堆（降序队列），也就是 `priority_queue<T,vector<T>,less<T>>` 类型，要定义小根堆，则需要使用 `priority_queue<T,vector<T>,greater<T>>` 来定义，要注意的一点是，使用 `greater<T>` 时必须重载 `>` 而不是 `<` （自定义类型就老老实实倒着重载小于号就行了，重载大于号再用greater属于是自找麻烦）。 ```cpp #include <cstdio> #include <queue> using namespace std; struct node { int a, b, c; node(int a, int b, int c) { a = a, b = b, c = c; } // 自定义类型使用emplace必须定义构造函数 bool operator<(const node &other) const { return a < other.a; } }; priority_queue<node> Q, P; int main() { Q.emplace(1, 2, 3); // emplace 插入必须有构造函数，直接按顺序写参数即可。 Q.push({2, 3, 1}); // 比 emplace 多一次构造 Q.top(); // 访问队头元素 Q.size(); // 返回队列内元素个数 Q.pop(); // 弹出队头元素 Q.swap(P); // 交换 P、Q 中的内容 } ``` ## vector向量 声明： ```cpp vector<T> vec; ``` 获取最后一个元素 ```cpp vec.back(); vec.end()-1; vec.rbegin(); vec.at(vec.size()-1) ``` ## string 字符串 见洛谷博客:https://www.luogu.com.cn/blog/xjzsq/stlstring-zi-fu-chuan ## pair ``` cpp #include<cstdio> #include<algorithm>//iostream也可 using namespace std; int main() { pair<int,int> x,y;//珂以是任意类型复合（包括pair套pair，例子见下方） x=make_pair(2,1),y=x;//支持make_pair和变量间赋值 printf("%d,%d\n",x.first,x.second); pair<pair<int,int>,int> z(make_pair(1,2),3);//珂以在定义时跟括号赋初值 printf("%d %d %d\n",z.first.first,z.first.second,z.second); } ``` ## map 映射 ### 部分方法 - 建立 ``` cpp map<type,type> M; ``` - 插入 ``` cpp M.insert(pair<type,type>(par1,par2)); ``` - 查找元素 ```cpp int a=M.count(par);//只能返回0（不存在）/1（存在） map<int,int>::iterator iter=M.find(par); //珂以返回元素所在的位置的迭代器 //之后你就可以这么写： cout<<iter->first<<"->"<<iter->second<<endl; ``` - 获取元素 ```cpp cout<<M[par1];//珂以输出par2 //或者珂以使用迭代器 for(map<type,type>::iterator iter=M.begin();iter!=M.end();iter++) cout<<iter->first<<"->"<<iter->second<<endl; //然后就珂以顺序输出每一组par1->par2 //当然也珂以对元素赋值： M[par1]=par2; ``` ## lower_bound/upper_bound ### 原理与使用 内部由二分实现，其实就是二分查找，操作对象必须是有序数组。 lower_bound(g+1,g+n+1,val)-g是返回g[1..n]中第一个大于等于val的值的位置，而upper_bound(g+1,g+n+1,val)-g是返回g[1..n]中第一个大于val的值的位置。 ### 应用举例 1. 查找数组中 $a[i]\in[x,y]$ 的元素个数：`upper_bound(a+1,a+n+1,y)-lower_bound(a+1,a+n+1,x);` 2. 实现某些需要对有序数组进行二分查找的操作：[P1020 【导弹拦截】](https://www.luogu.com.cn/blog/xjzsq/p1020) ## set/multiset ### 咕咕咕 ### 在写了在写了