stl 队列

基本用法

  • queue<int>q 声明队列

  • front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。

  • back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。

  • push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。

  • push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。

  • pop()：删除 queue 中的第一个元素。

  • size()：返回 queue 中元素的个数。

  • empty()：如果 queue 中没有元素的话，返回 true。

  • emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。

  • swap(queue &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。

stl 优先队列

基本使用

和队列基本操作相同:

  • priority_queueq 声明优先队列
  • top() 访问队头元素
  • empty() 队列是否为空
  • size() 返回队列内元素个数
  • push(x) 插入元素到队尾 (并排序)
  • emplace 原地构造一个元素并插入队列(没用过)
  • pop() 弹出队头元素
  • swap 交换内容(没用过)

结构体重载

friend bool operator<(node n1,node n2){
    return n1.elem<n2.elem;
}

优先队列用来排序的运算符是小于运算符<（似乎stl的都是这样）,因此如果要对结构体进行规则重载，就只需要对小于符号进行重载就可以了。重载时，小于号就是重载为小于，否则重载为大于

stl 双端队列

基本使用

//a) 构造函数
deque<int> ideq
//b)增加函数
 ideq.push_front( x):双端队列头部增加一个元素X
 ideq.push_back(x):双端队列尾部增加一个元素x
//c)删除函数
ideq.pop_front():删除双端队列中最前一个元素
ideq.pop_back():删除双端队列中最后一个元素
ideq.clear():清空双端队列中元素
//d)判断函数
ideq.empty() :向量是否为空，若true,则向量中无元素
//e)大小函数
ideq.size():返回向量中元素的个数

stl map

基本用法

  • map<int, string> mapStudent 声明映射为int->string
  • mapStudent[1] = “student_one” 插入值
  • 遍历映射如下：
for(int nindex = 1; nindex <= nSize; nindex++)  
    cout<<mapStudent[nindex]<<endl;
  • 查找元素如下：
map<int, string>::iterator iter;  
iter = mapStudent.find(1);  
if(iter != mapStudent.end())  
    cout<<"Find, the value is "<<iter->second<<endl;  
else  
    cout<<"Do not Find"<<endl;
  • 删除元素如下
map<int, string>::iterator iter;  
iter = mapStudent.find(1);  
mapStudent.erase(iter);  
//如果要删除1，用关键字删除  
//或者也可以这样删除
int n = mapStudent.erase(1);
//如果删除了会返回1，否则返回0

stl set

去重就用这东西，很香的。


loop(i,1,n){//插入值（和make_pair结合起来用）
    read(ai);read(bi);
    line.insert(make_pair(ai,bi));
}
for(iter=line.begin();iter!=line.end();++iter){//取出值
    L[cnt].Ai=iter->first;
    L[cnt].Bi=iter->second;
}

set用法详解

stl upperbound & lowerbound

upper_bound():在非降序列的a数组内二分查找[l,r)区间内的值为m的元素,返回第一次出现大于要查找的数的地址；

lower_bound():在非降序列的a数组内二分查找[l,r)区间内的值为m的元素,返回第一次出现大于等于要查找的数的地址；

特殊情况：

  • 如果m在区间中没有出现过，那么返回第一个比m大的数的下标。
  • 如果m比所有区间内的数都大，那么返回r。这个时候会越界，小心。
  • 如果区间内有多个相同的m，返回第一个m的下标。

用法:

int loc = lower_bound(a+l,a+r,n)-a

int loc2 = upper_bound(a+l,a+r,n)-a

stl nth_element

nth_element(a,a+k,a+n);就是将a数组中的第k个数字选出来并且放在a数组的第k个位置上，但是不保证其他的数字有序

sort

对于sort重载有如下例子：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 310;
struct student{
    int id;
    int math;
    int chinese;
    int english;
}S[maxn];
bool cmp(struct student a,struct student b){
    if(a.math+a.chinese+a.english>b.math+b.chinese+b.english)return 1;
    else{
        if(a.math+a.chinese+a.english==b.math+b.chinese+b.english){
            if(a.chinese>b.chinese)return 1;
            else if(a.chinese==b.chinese)
                return a.id<b.id;
            else
                return 0;
        }
        else{
            return 0;
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        S[i].id=i;
        scanf("%d%d%d",&S[i].chinese,&S[i].math,&S[i].english);
    }
    sort(S+1,S+1+n,cmp);  # 重载
    for(int i=1;i<=5;i++){
        printf("%d %d\n",S[i].id, S[i].math+S[i].chinese+S[i].english, S[i].chinese);
    }
    return 0;
}

附：快速读入

template<typename T>void read(T &x){
    x=0;char r=getchar();T neg=1;
    while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
    while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
    x*=neg;
}

卡常数专用，替代scanf，cin，速度++！