数据结构04 动态数组vector

vector是什么

vector翻译为向量，但是这里使用“变长数组”的叫法更容易理解，也即“长度根据需要而自动改变的数组”。

在考试题中，有时会碰到只用普通数组会超内存的情况，这种情况使用vector会让问题的解决便捷许多。

另外， vector还可以用来以邻接表的方式储存图，这对无法使用邻接矩阵的题目(结点数太多)、又害怕使用指针实现邻接表的读者是非常友好的写法也非常简洁。

vector 例子

如果typename 是vector,就是下面这样定义:

vector< vector<int> > name;

这里需要注意的是 > > 之间最好加上空格，用于区分右移运算符。

#include<cstdio>
#include<vector> //①头文件
using namespace std;
struct student{  //②结构体
    int age;
    char name[20];
};

int main(void){
    vector<int> a; //③ int类型
    vector<double> b;//④ double类型
    vector<char> c; //⑤ char类型
    vector<student> d; //⑥ student类型
    return 0;
}

二维数组的定义

我们已经知道一个vector变量相当于定义一个一维数组，如果是定义一个二维数组呢？

定义vector数组的方法:

vector<typename> Arrayname[arraySize];

例如定义一个vector的一维数组a：

vector<int> a[100];

这样a[0]~a[a_size-1]中的每一个元素都是一个vector容器。

注意：这种写法的一维长度已经固定为a_size,另一维才是"变长"的。

vector的成员函数示例

vector容器内元素的访问

vector一般有两种访问方式 , 通过下标访问或通过迭代器访问。

一、通过下标访问

和访问普通的数组是一样的，对一个定义为vector vi 的容器来说直接访问vi[index] 即可(如vi[0]、vi[1])。

当然这里的下标是从0 到 vi.size()-1。访问这个范围外的元素可能会出错。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> a;
    a.push_back(3);
    a.push_back(2);
    a.push_back(5);
    for(int i=0;i<a.size();i++)
        cout << a[i] << " ";
    return 0;
}

二、通过迭代器访问

迭代器( iterator ) 可以理解为一种类似指针的东西,其定义是:

迭代器就是定义一个 vector类型的指针

vector<typename>::iterator it;  

it就是一个vector:: iterator型的变量,其中 typename 就是定义vector时填写的类型。

并且可以通过 *it 来访问vector里的元素。

vector<int> a;
vector<int>::iterator s;
for(int i=0;i<5;i++)
{
    a.push_back(i);
}
s = a.begin();//取a的首元素地址
for(int i=0;i<a.size();i++)
{
    cout << *(s+i) << " ";
}

除此之外，迭代器还实现了两种自加操作: ++it 和 it++。

于是有了另一种遍历vector中元素的写法，详情见右方代码→。

需要注意的是: vector的迭代器不支持 it < v1.end() 写法，因此循环条件只能用 it != vi.end()。

最后需要指出,在常用STL容器中，只有在vector和string中，才允许使用vi.begin()+3这种迭代器加上整数的写法。

vector<int> a;
vector<int>::iterator s;
for(int i=0;i<5;i++)
{
    a.push_back(i);
}
for(s=a.begin();s!=a.end();s++)
{
    cout << *s << " ";
}