一：STL容器
1.vector
- 作用：
- 训练：hdu3527：间谍
2.栈
- 训练：poj1028：web导航
include
include
include
4.list
- 常用成员函数（专用）：
- 链接">hdu1276：士兵队列训练——链接
include
include
6.priority_queue
- 链接">练习：poj1442—链接
7.bitset
- 链接">训练：poj2443—链接
8.set/multiset
- 链接">训练：hdu1412—链接
9.map、multimap
- 链接">训练—链接
10.stl常用函数：

一：STL容器

容器通用函数如下：
.size()：容器内的元素个数，无符号整型。
.empty():判断容器是否为空，返回一个bool值。
.front():返回容器第一个元素。
.back():返回容器最后一个元素。
.begin():指向容器第一个元素的指针。
.end（）：指向容器的最后一个元素的下一个位置的指针。
.swap(b):交换两容器内容。
::iterator:迭代器。

迭代器：广义指针，可以是指针或者其他类似操作的对象。模板使得算法独立于存储的数据类型，迭代器使得算法独立于使用的容器类型。比如用迭代器输出vector容器中的元素，代码如下：

for(vector<int>::iterator it = a.begin();it != a.end;it++)
    cout<<*it<<endl;

1.vector

vector(向量),是一个封装了动态大小数组的顺序容器。按严格的线性顺序排序。使用时需要引用头文件#include。

作用：

（1）：创建：可存放各种类型对象。
（2）：增加：增加元素时可以从中间或者尾部增加。
（3）：删除：可删除尾部，指定位置元素，区间，还可以清空整个向量。
（4）：遍历：可以用数组表示法，也可以用迭代器对向量元素进行访问。
（5）：改变向量大小：resize可以改变大小，若比当前向量大，则填充默认值。若比当前向量小，则舍弃后面部分。

训练：hdu3527：间谍

直接点链接—-hdu练习。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
vector<string> x,y,z,ans;

int main(){
    int a,b,c;
    string s;
    while(cin>>a>>b>>c){
        x.clear(),y.clear(),z.clear(),ans.clear();
        for(int i=0;i<a;i++){
            cin>>s;
            x.push_back(s);
        }
        for(int i=0;i<b;i++){
            cin>>s;
            y.push_back(s);
        }
        for(int i=0;i<c;i++){
            cin>>s;
            z.push_back(s);
        }
        for(int i=0;i<b;i++){//判断第二个字符串在第一个中出现，没在第三个中出现的    
            if(find(x.begin(),x.end(),y[i])!=x.end())
                if(find(z.begin(),z.end(),y[i])==z.end())
                    ans.push_back(y[i]);
        }
        if(!ans.size())
            cout<<"No enemy spy\n";
        else{
            for(int i=0;i<ans.size();i++){
                if(i!=0)
                    cout<<" ";
                cout<<ans[i];
            }
            cout<<endl;
        }
    }
    return 0;
}

2.栈

栈（stack）只允许在栈顶操作，不允许在中间插入和删除。不支持数组表示法和随机访问。用到时需要#include。栈的基本操作就是：入栈，出栈，取栈顶，判断栈空，求栈大小。

stacks:创建一个空栈s，数据类型为int。
push（x）：x入栈。
pop() : 出栈
top() : 取栈顶（未出栈）
empty() : 判断栈是否为空，若空则返回true。
size() : 求栈大小，返回栈中的元素个数。
训练：poj1028：web导航
链接—-poj。 ```cpp
include
include
include
using namespace std;

int main(){ stackbackward;//后向栈 stackforward;//前向栈 string c; string cur=”http://www.acm.org/“; while(cin>>c&&c!=”QUIT”){ if(c==”VISIT”){ backward.push(cur); cin>>cur; cout<<cur<<endl; while(!forward.empty())//前向栈不为空则清空 forward.pop(); }else if(c==”BACK”){ if(backward.empty()) cout<<”Ignored”<<endl;
else{ forward.push(cur); cur=backward.top(); backward.pop(); cout<<cur<<endl; } }else{ if(forward.empty()) cout<<”Ignored”<<endl;
else{ backward.push(cur); cur=forward.top(); forward.pop(); cout<<cur<<endl; } } } return 0 ; }

<a name="DfBE2"></a>
# 3.queue
队列只允许从队尾入队，从队头出队，不允许从中间插入和删除，不支持数组表示法和随机访问。同样，使用queue需要#include<queue>。队列的基本操作就是：入队，出队，取队头，判断队空，求队列大小。

   - queue<int>q:创建一个空队q，数据类型为int。
   - push（x）：x入队。
   - pop() : 出队
   - top() : 取队头（未出队）
   - empty()  : 判断队是否为空，若空则返回true。
   - size() : 求队列大小，返回队列中的元素个数。
<a name="KEYUQ"></a>
## 训练：poj1915：骑士移动
链接---[poj-queue](http://poj.org/problem?id=1915)
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
const int maxn=310;
using namespace std;
struct point{
    int x,y;
    int step;
};//到达的点，和需要的步数 
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={1,-1,2,-2,2,-2,1,-1};
//int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
bool vis[maxn][maxn];
int sx,sy,ex,ey,tx,ty,L;

int bfs(){
    if(sx==ex&&sy==ey) return 0;
    memset(vis,false,sizeof(vis));//初始化 
    queue<point>Q;//定义个队列 
    point start,node;
    start.x=sx;
    start.y=sy;
    start.step=0;//队列初始化 
    Q.push(start);//压进队列
    int step,x,y;
    while(!Q.empty()){
        start=Q.front(),Q.pop();//取队列的头元素，同时把这个元素弹出 (队列从后往前进，先进的先出)
        x=start.x;
        y=start.y;
        step=start.step;//把队列头元素的x,y,step取出 
        for(int i=0;i<8;i++){//扩展 
            tx=x+dx[i];
            ty=y+dy[i];
            if(tx==ex&&ty==ey) return step+1;
            if(tx>=0&&tx<L&&ty>=0&&ty<L&&!vis[tx][ty]){
                node.x=tx;
                node.y=ty;
                node.step=step+1;
                Q.push(node);//满足条件的进队列 
                vis[tx][ty]=true;
            }
        }
    }
}

int main(){
    int N;
    scanf("%d",&N);
    while(N--){
        scanf("%d",&L);
        scanf("%d%d",&sx,&sy);
        scanf("%d%d",&ex,&ey);
        printf("%d\n",bfs());
    }
    return 0; 
}

4.list

list是一个双向链表，可以在常数时间内插入和删除。不支持数组表示法和随机访问。使用时引入#include。

常用成员函数（专用）：

merge(b)：将链表b与调用链表合并，合并前，两个链表必须已经排序，合并后经过排序的链表被保存在调用记录里，b为空。
remove(val):从链表中删去val的所有节点。
splice(pos,b):把链表b的内容插入pos前面，b为空。
reverse（）：链表反转。
sort() :链表排序。
unique（）：将连续的相同元素压缩为单个元素。不连续的相同元素无法压缩。因此一般先排序后去重。
hdu1276：士兵队列训练——链接
```cpp
include
include
using namespace std;

int main(){ int T,n; list a; list::iterator it; scanf(“%d”,&T); while(T—){ scanf(“%d”,&n); a.clear(); int k=2;//第一次删喊“2”的 for(int i=1;i<=n;i++) a.push_back(i);//存每个士兵的编号 while(a.size()>3){ int cnt=1; for(it=a.begin();it!=a.end();){ if(cnt++%k==0)//删除喊“k”的士兵 it=a.erase(it);//it指到下一个的地址 else it++;//it指到下一位的地址 } k=(k==2?3:2); } for(it=a.begin();it!=a.end();it++){ if(it!=a.begin()) printf(“ “); printf(“%d”,*it); } printf(“\n”); } return 0; }


<a name="mUAgh"></a>
# 5.deque
deque是一个双端队列，可以在两端进出队，支持数组表示法和随机访问，经常在序列两端操作时应用。使用前#include<deque><br />成员函数：<br />push_fornt(x)/push_back(x) :从队首或队尾入队。<br />pop_front/pop_back:从队首或队尾入队。<br />front()/back():返回队首或队尾元素。<br />size（）：返回队中元素个数。<br />empty（）：判断是否为空，空返回TRUE。<br />clear（）：清空队列。
<a name="sBcQy"></a>
## 练习：hdu6375--[链接](http://acm.hdu.edu.cn/showproblem.php?pid=6375)
```cpp
#include<cstdio>
#include<deque>
using namespace std;
const int maxn=15e4+10;
int n,m;
deque<int> d[maxn];

void read(int &x){
    char ch=getchar();x=0;
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++)
            d[i].clear();
        int k,u,v,w;
        while(m--){
            read(k);
            switch(k){
            case 1:
                read(u),read(w),read(v);
                if(w==0)
                    d[u].push_front(v);
                else
                    d[u].push_back(v);
                break;    
            case 2:
                read(u),read(w);
                if(d[u].empty())
                    printf("-1\n");
                else{
                    if(w==0){
                        printf("%d\n",d[u].front());
                        d[u].pop_front();
                    }
                    else{
                        printf("%d\n",d[u].back());
                        d[u].pop_back();
                    }
                }
                break;
            case 3:
                read(u),read(v),read(w);
                if(w)
                    d[u].insert(d[u].end(),d[v].rbegin(),d[v].rend());
                else
                    d[u].insert(d[u].end(),d[v].begin(),d[v].end());
                d[v].clear();
                break;
            }
        }
    }
    return 0;
}

6.priority_queue

优先队列，优先级高的先出队，默认最大值优先。内部实现为堆。也可自定义顺序。优先队列没法删除指定元素，只能删除堆顶元素。若想删除指定元素可采用懒操作。使用前#include
成员函数和上面差不多。

练习：poj1442—链接

#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;
int a[30010];

int main(){
    int n,m,x;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    int cnt=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        while(cnt<=x){
            if(!q1.empty()&&a[cnt]<q1.top()){
                q2.push(q1.top());
                q1.pop();
                q1.push(a[cnt]);
            }
            else
                q2.push(a[cnt]);
            cnt++;
        }
        printf("%d\n",q2.top());
        q1.push(q2.top());
        q2.pop();
    }
    return 0;
}

7.bitset

bitset是一个多元二进制数，这里开始用到了位运算。~(取反)，&（与），|（或），^(异或)，<<(左移运算符)等。
成员函数如下：
count():统计多少位是1.
any():若至少一位是1，则TRUE。
none（）：若全是0，则返回TRUE。
set（）；所有位初始化为1.
set（k）；初始第k位为1.
set（k，val）；将第k位值改为val，即s【k】=val。
reset系列就是set里一样的功能，1改成0.
flip（）;将所有位取反。
flip（k）；第k位取反。
size（）；返回大小，也就是几位。
to_string（）；返回他转换为string的结果。

训练：poj2443—链接

#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
const int maxn=10010;
bitset<1010>s[maxn];

int main(){
    int N,Q,num,x,y;
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&num);
        while(num--){
            scanf("%d",&x);
            s[x][i]=1;
        }
    }
    scanf("%d",&Q);
    while(Q--){
        scanf("%d%d",&x,&y);
        if((s[x]&s[y]).count())
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

8.set/multiset

四种关联容器：set,multiset,map,multimap。将值和键关联在一起。都是可翻转的经过排序的容器。内部采用红黑树实现。
set是有序集合，键和值统一，不允许重复。multiset是有序多重集合。键和值允许多个值的键相同。二者的相同点是双向访问，不允许随机访问，默认升序。使用前#include
成员函数：
size/empty/clear/begin/end/find/count:功能与前面类似。
insert（x）：x插入集合。
erase（x）：删除所有等于x的元素。
erase（it）：删除it迭代器指向的元素。
lower_bound/upper_bound :返回大于或等于x的最小元素位置，大于x的最小元素位置。

训练：hdu1412—链接

#include<cstdio>
#include<set>
using namespace std;
int n,m,x;
set<int> sum;

int main(){
    while(~scanf("%d%d",&n,&m)){
        sum.clear();
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            sum.insert(x);
        }
        for(int j=0;j<m;j++){
            scanf("%d", &x);
            sum.insert(x);
        }
        for(set<int>::iterator it=sum.begin();it!=sum.end();it++){
            if(it!=sum.begin())
                printf(" ");
            printf("%d",*it);
        }
        printf("\n");
    }
    return 0;
}

9.map、multimap

类似映射，键和值可以是不同的类型，此外。map可当做哈希表使用。其他和set系列相似。

训练—链接

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;

int main(){
    map<string,int>mp;
    int cnt=0;
    string s;
    while(getline(cin,s)){
        mp[s]++;
        cnt++;
    }
    for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
        cout<<it->first<<" ";
        printf("%.4f\n",100.0*(it->second)/cnt);
    }
    return 0;
}

10.stl常用函数：

现在不急，先记住sort，next-permutation和前面这些用到的就行。
入门阶段，不急，不会就先放一下。

算法入门

算法入门（2）-STL应用

一：STL容器

1.vector

作用：

训练：hdu3527：间谍

2.栈

训练：poj1028：web导航

include

include

include

4.list

常用成员函数（专用）：

hdu1276：士兵队列训练——链接

include

include

6.priority_queue

练习：poj1442—链接

7.bitset

训练：poj2443—链接

8.set/multiset

训练：hdu1412—链接

9.map、multimap

训练—链接

10.stl常用函数：