STL #2

---

Stack

Stack(栈)，是 LIFO (last-in first-out) 的一种数据结构。
使用 stack 需要

#include <stack>

声明

stack<int> s;
stack<TJJ> T;

函数

s.push();    //在栈中压入一个元素
s.top();     //取出栈顶元素（不删除）
s.pop();     //弹出栈顶元素
s.empty();   //是否为空
s.size();    //元素个数

---

例子 十进制转二进制

#include <iostream>
#include <stack>
using namespace std;
stack<int> result;
int main() {
    int n;
    cin>>n;
    while (n) {
        result.push(n%2);
        n/=2;
    }
    cout<<"转换后的二进制共有"<<result.size()<<"位"<<endl<<"转换后的二进制为:";
    while (!result.empty()) {
        cout<<result.top();
        result.pop();
    }
    return 0;
}

---

Queue

Queue(队列)，一个FIFO（先入先出）的数据结构。
使用 queue 需要

#include <queue>

声明

#queue<int> q;
#queue<TJJ> T;

函数

q.empty();   //判断队列空，当队列空时，返回true。
q.size();    //返回队列中的元素个数。
q.push();    //将一个元素置入queue中。
q.front();   //返回queue内的第一个元素(也就是第一个被置入的元素)。
q.back();    //返回queue中最后一个元素(也就是最后被置入的元素)。
q.pop();     //移除队列头部的一个元素。 

---

例子 SPFA

#include "iostream"
#include "vector"
#include "queue"
using namespace std;
struct node{
    int num,value;  
};
vector<node> v[101];
queue<int> q;
bool used[101];
int dis[101];
int main(){
    ios::sync_with_stdio(false);
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;++i){
        int t1,t2,t3;
        cin>>t1>>t2>>t3;
        v[t1].push_back((node){t2,t3});
    }
    q.push(1);

---

    used[1]=true;
    while (!q.empty()){
        int now=q.front();
        q.pop();
        for (vector<node>::iterator i = v[now].begin(); i != v[now].end(); ++i){
            if (dis[i->num]>dis[now]+i->value) {
                dis[i->num]=dis[now]+i->value;
            }
            if (!used[i->num]){
                used[i->num]=true;
                q.push(i->num);
            }
        }
    }
    cout<<dis[n];
    return 0;
}

---

Deque

Deque(double-ended queue)即双端队列。是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。
使用 deque 需要

#include <deque>

函数

函数还是那么些，反正这玩意儿我们基本上用不着所以就不说了吧~（逃）

---

Priority_queue

priority_queue(优先队列)，调用了 STL 中的 make_heap()，pop_heap()，push_heap()，也相当于一个堆。
使用 priority_queue 需要

#include <queue>

声明

priority_queue <int> q  //默认是大根堆。
priority_queue <int, vector<int>, greater<int> > q
//第二个参数是容器，可以是 vector，deque 但不能为 list
//第三个参数是比较，greater<int> 就是小根堆了，注意> >不能写在一起，否则会变成右移

---

例子 合并果子

#include<iostream>
#include<queue>
using namespace std;
int main () {
    int minh=0,min1,min2;
    priority_queue<int, vector<int>,greater<int> > q;
    cin>>n;
    for (int i=1;i<=n;i++){
        int value;
        cin>>value;
        q.push(value);
    }
    for (int i=n+1;i<=2*n-1;i++){
        min1=q.top();
        q.pop();
        min2=q.top();
        q.pop();
        q.push(min1+min2);
        minh+=min1+min2;
    }
        cout<<minh;
    return 0;
}

---

Set

Set(集合)，set 中不会有重复的元素，所有的操作都会在 logn 的时间内完成。
使用 set 需要

#include <set>

声明

set<int> s;

函数

//函数什么的大都差不多啦
s.insert();

---

例子 明明的随机数

#include <iostream>
#include <set>
using namespace std;
set<int> s;
int main() {
    int n;
    cin>>n;
    while (n--) {
        int temp;
        cin>>temp;
        s.insert(temp);
    }
    cout<<s.size()<<endl;
    for (set<int>::iterator i=s.begin();i!=s.end();++i){
        cout<<*i<<" ";
    }
    return 0;
}

---

Algorithm

algorithm意为"演算法",是C++的标准模版库（STL）中最重要的头文件之一，提供了大量基于迭代器的非成员模版函数。
常用函数

swap(a[1],a[2]);//交换两个变量的值
sort(begin,end);//排序
stable_sort(begin,end);//稳定排序
max(a,b);//二者中的最大值
max_element();//给定范围内的最大值
min(a,b);
min_element();//给定范围内的最小值
next_permutation();//下一个排列
prev_permutation();//上一个排列
lower_bound();//返回给定范围内的第一个大于等于给定元素的迭代器。
upper_bound();//返回给定范围内的第一个大于给定元素的迭代器。

---

例子

//全排列
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main (){
    int n;
    scanf("%d",&n);
    vector<int> q;
    for (int i=1;i<=n;i++){
        q.push_back(i);
    }
    do{
        for (vector<int>::iterator i=q.begin();i!=q.end();++i){
            printf("%d ",*i);
        }
        printf("\n");
    }while(next_permutation(q.begin(),q.end()));
    return 0;
}

---

//自定义结构体的排序 #1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct tjj{
    int height;
    int length_of_neck;
    bool operator < (const tjj& b) const {
        if (height>b.height) return true;
        if (height==b.height&&length_of_neck>b.length_of_neck) return true;
        return false;
    }
};
vector<tjj> TJJ;
int main() {
    int n;
    cin>>n;
    while (n--) {
        int h,t;
        cin>>h>>t;
        TJJ.push_back((tjj){h,t});
    }
    sort(TJJ.begin(),TJJ.end());
    return 0;
}

---

//自定义结构体的排序 #2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct tjj{
    int height;
    int length_of_neck;
};
bool cmp(const tjj& a,const tjj& b){
    if (a.height>b.height) return true;
    if (a.height==b.height&&a.length_of_neck>b.length_of_neck) return true;
    return false;
}
vector<tjj> TJJ;
int main() {
    int n;
    cin>>n;
    while (n--) {
        int h,t;
        cin>>h>>t;
        TJJ.push_back((tjj){h,t});
    }
    sort(TJJ.begin(),TJJ.end(),cmp);
    return 0;
}

---

其实还有很多没有说到的东西，就靠大家自己查资料了。

---

終わり

腹黑猫
2014.11.29