不定长数组：vector
vector就是一个不定长数组。不仅如此，它把一些常用操作“封装”在了vector类型内部。 例如，若a是一个vector，可以用a.size( )读取它的大小，a.resize( )改变大小，a.push_back( )向 尾部添加元素，a.pop_back( )删除最后一个元素。
vector是一个模板类，所以需要用vectora或者vectorb这样的方式来声明一 个vector。Vector是一个类似于inta[]的整数数组，而vector就是一个类似于 stringa[ ]的字符串数组。vector看上去像是“一等公民”，因为它们可以直接赋值，还可以作为 函数的参数或者返回值，而无须像传递数组那样另外用一个变量指定元素个数。（n=strlen(a);）
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
木块问题（The Blocks Problem，Uva 101）
从左到右有n个木块，编号为0～n-1，要求模拟以下4种操作（下面的a和b都是木块编 号）。
- move a onto b: 把a和b上方的木块全部放回初始的位置，然后把a放到b上面
- move a over b: 把a上方的木块全部放回初始的位置，然后把a放在b所在木块堆的最上方
- pile a onto b: 把b上方的木块部放回初始的位置，然后把a和a上面所有的木块整体放到b上面
- pile a over b: 把a和a上面所有的木块整体放在b所在木块堆的最上方
一组数据的结束标志为"quit"，如果有非法指令(a和b在同一堆)，应当忽略。
输出:所有操作输入完毕后，从左到右，从下到上输出每个位置的木块编号。
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
int n;
vector<int> pile[];
void find_block(int x,int &xp,int &j){
for(int i=;i<n;i++){
for(j=;j<pile[i].size();j++){
if(pile[i][j]==x) {
xp=i;
return;
}
}
}
}
//把第p堆高度为h的木块上方的所有木块移回原位
void clear_above(int p,int h){
for(int i=h+;i<pile[p].size();i++){
int x=pile[p][i];
pile[x].push_back(x);
}
pile[p].resize(h+);
}
//把第p堆高度为h及其上方的木块整体移动到p2 堆的顶部
void pile_onto(int p,int h,int p2){
for(int i=h;i<pile[p].size();i++){
pile[p2].push_back(pile[p][i]);
}
pile[p].resize(h);
}
void print(){
for(int i=;i<n;i++){
printf("%d:",i);
for(int j=;j<pile[i].size();j++) printf(" %d",pile[i][j]);
printf("\n");
}
}
int main(){
int a,b;
string s1,s2;
cin>>n;
for(int i=;i<n;i++) pile[i].push_back(i);
while(){
cin>>s1;
if(!s1.compare("quit")) break;
cin>>a>>s2>>b;
int pa,pb,ha,hb;
find_block(a,pa,ha);
find_block(b,pb,hb);
if(pa==pb) continue;//在同一堆，忽略
if(!s2.compare("onto")) clear_above(pb,hb);
if(!s1.compare("move")) clear_above(pa,ha);
pile_onto(pa,ha,pb);
}
print();
return ;
}
数据结构的核心是vectorpile[maxn]，所有操作都是围绕它进行的。vector就像一个 二维数组，只是第一维的大小是固定的（不超过maxn），但第二维的大小不固定。上述代码 还有一个值得学习的技巧：输入一共有4种指令，但如果完全独立地处理各指令，代码就会 变得冗长而且易错。更好的方法是提取出指令之间的共同点，编写函数以减少重复代码。
vector头文件中的vector是一个不定长数组，可以用clear( )清空，resize( ) 改变大小，用push_back( )和pop_back( )在尾部添加和删除元素，用empty( )测试是否为 空。vector之间可以直接赋值或者作为函数的返回值，像是“一等公民”一样。