C++ STL专题1——Vector（不定长数组）

• 什么是Vector？

Vector中文翻译为向量。在C++算法中，Vector存在于 C++标准模板库 ，也就是我们口中的 STL （Standard Template Library）。简单的讲，Vector是一个可以用来存放任意类型的动态数组，可以实现增加，压缩数据。Vector因为可以存放任意类型的对象，而也被比作一个 容器。

• 如何使用Vector呢？

如果我们需要使用Vector，我们在头文件上首先要加上以下两条：

#include <vector>
using namespace std;

我们如果需要定义一个名字为vec，类型为int的动态数组，即可在代码中这样写：

vector<int> vec;

• Vector中的一些简易的函数操作

1.  vec.push_back(a) 在动态数组尾部添加数据a
2.  vec.pop_back( ) 删除动态数组尾部的最后一个数据
3.  vec.size( ) 查询动态数组此时存放了多少个元素
4.  vec.empty( ) 查询动态数组此时是否为空，若为空则返回1，否则返回0
5.  vec.clear( ) 清空整个动态数组
6.  vec.front( ) 返回动态数组中的第一个元素
7.  vec.resize(a) 重新定义动态数组的大小，即为只保存下标为0~a-1的元素
8.  vec.erase(a) 删除a位置的数据，传回下一个数据的位置

• UVA101 The Blocks Problem

题目链接： https://uva.onlinejudge.org/external/1/101.pdf

思路：对于四种操作，我们会发现有共同点。并且每个木块堆的高度是不确定的，所以我们使用Vector会十分方便。我们用一个动态数组名叫vec[MAXN]，用来保存每一个木块堆的高度。

代码如下：

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int n,pa,pb,ha,hb,n1,n2;
string s1,s2;
vector<int> vec[30];//定义动态数组 
inline void find_block(int c,int& p,int& h)
{
  for(p=0;p<n;p++)
    for(h=0;h<vec[p].size();h++)
      if(vec[p][h]==c) return ; 
}
inline void back_above(int p,int h)//把第p堆高度为h的木块上方的所有木块放回原位 
{
  for(register int i=h+1;i<vec[p].size();i++)
  {
    int j=vec[p][i];
    vec[j].push_back(j);
  }
  vec[p].resize(h+1);//只保留下标0~h的元素 
}
inline void onto(int p1,int h,int p2)//把第p1堆高度为h及其以上的木块全部移到p2堆的顶部 
{
  for(register int i=h;i<vec[p1].size();i++)
  {
    int j=vec[p1][i];
    vec[p2].push_back(j);
  }
  vec[p1].resize(h);
}
int main()
{
  cin>>n;
  for(register int i=0;i<n;i++) vec[i].push_back(i);//开始时编号为i的木块都在第i个位置 
  while(cin>>s1>>n1>>s2>>n2)
  {
    find_block(n1,pa,ha);//找到木块n1所在的堆和高度，并且用引用的形式接受 
    find_block(n2,pb,hb);//找到木块n2所在的堆和高度，并且用引用的形式接受 
    if(pa==pb) continue;//非法指令 
    if(s2=="onto") back_above(pb,hb);//共同点1 
    if(s1=="move") back_above(pa,ha);//共同点2 
    onto(pa,ha,pb);//其他指令 
  }
  for(register int i=0;i<n;i++)
  {
    printf("%d:",i);
    for(register int j=0;j<vec[i].size();j++) printf(" %d",vec[i][j]);
    printf("\n");
  }
  return 0;
}

• UVA10763 Foreign Exchange

题目链接： https://uva.onlinejudge.org/external/107/p10763.pdf

思路：这道题简单来说，本质上就是看看是否能两两配对，若出现一组或多组无法配对的情况则不满足条件。由于数据范围很大，所以直接使用邻接表的思路来存储是完全不行的。所以使用Vector是个很好的选择。在这道题中，我们会使用到一个叫find的函数。我们先来了解一下：

• find( )

find存在于头文件 algorithm 中，同时需要加上 using namespace std 。

find( )的格式即为：find(起始位置，结束为止，查找的元素)，也就是在一个指定的区间内寻找一个元素。在C++中规定，find( )返回的是要查找的元素第一次出现的位置；若未找到则返回end。函数返回的是迭代器或指针，即位置信息。所以若想保存这个位置，需要申请 迭代器 来保存下来。即：

vector<int>::iterator s=find(起始位置，结束为止，查找的元素）;

• 什么是迭代器

迭代器，是用于遍历一个数据集中的每个元素的东西。这些数据集可能是容器或者容器的子集。迭代器的主要优点是它们为任意类型的容器提供一个小巧并且通用(注意通用很重要)的接口。例如，迭代器接口的一个操作是让它依次遍历数据集的每个元素。这个操作是依赖容器的内总部结构独立完成的。迭代器之所以有效是因为容器类提供它自己的迭代器类型来做“正确的事”，容本身的迭代器了解容器的内部结构。迭代器的接口几乎相当于普通的指针。让一个迭代器递增只需调用＋＋操作符。使用*操作符可以得到迭代器引用的数据值。因而迭代器可以被任为是一种智能指针。

代码如下：

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> vec[500001];
int a,b,s,n,num;
int main()
{
  while(cin>>n&&n)
  {
    memset(vec,0,sizeof(vec));//多组数据，清空数组 
    num=0;
    for(register int i=0;i<n;i++)
    {
      cin>>a>>b;
      vector<int>::iterator s=find(vec[a].begin(),vec[a].end(),b);
      if(s!=vec[a].end())
      {
        num--;
        vec[a].erase(s);//若存在，则删除这个配对关系 
      }
      else
      {
        num++;
        vec[b].push_back(a);
      }
    }
    if(num) cout<<"NO"<<endl;//说明存在未配对成功的配对 
    else cout<<"YES"<<endl;
  }
  return 0;
}

参考与引用：

https://www.cnblogs.com/-Mr-y/p/7985987.html

https://blog.csdn.net/accelerator_/article/details/9983249

https://www.cnblogs.com/chenzhefan/p/5649429.html

https://blog.csdn.net/huangyimin/article/details/6133650

本人喜爱诗句分享赏析：

• 曾经沧海难为水，除却巫山不是云。——元稹《离思五首·其四》

元稹巧妙地使用了孟子的典故： 观于海者难为水 和神话传说 巫山云雨 ，表达了对亡妻韦丛的追悼。现今也用来比喻对于心上人的山盟海誓，表达自己对爱情的忠贞。