STL相关

2020-03-09 21:13:07


(由我的hexo博客搬运并同步维护)
最近每次打比赛用到STL的时候都想去查查,来防止写错,因此浪费了大量的时间,遂决定写篇博客,到时候直接在博客查阅。

queue 队列

methods in code

#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属于是自找麻烦)。

#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向量

声明:

vector<T> vec;

获取最后一个元素

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

#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 映射

部分方法

  • 建立
    map<type,type> M;
  • 插入
    M.insert(pair<type,type>(par1,par2));
  • 查找元素
    int a=M.count(par);//只能返回0(不存在)/1(存在)
    map<int,int>::iterator iter=M.find(par);
    //珂以返回元素所在的位置的迭代器  
    //之后你就可以这么写:
    cout<<iter->first<<"->"<<iter->second<<endl;
  • 获取元素
    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 【导弹拦截】

set/multiset

咕咕咕

在写了在写了