C++中的vector

在编程过程中，有时经常出现普通数组浪费大量的内存空间或者无法使用邻接矩阵(节点数太多)又害怕使用指针实现邻接表的情况。此时我们应当想到vector。向量vector是一种对象实体, 能够容纳许多其他类型相同的元素,比如：int、char、double、结构体等。因此又被称为容器。与string相同,vector同属于STL(Standard Template Library,标准模板库)中的一种自定义的数据类型, 可以广义上认为是数组的增强版。vector是一个能够存放任意类型的动态数组。如果需要使用vector，必须包含头文件#include还有命名空间”using namespace std;”。

1、vector的定义:vector<typename> name;例如:

vector<int> name;      //声明一个int向量
vector<int> name(10);  //声明一个初始大小为10的int型向量
vector<int> name(10,1);//声明一个初始大小为10且初始值都为1的int型向量
vector<int> name(a);   //声明一个初始大小为a的int型向量
vector<node> name;     //node是结构体的类型

如果typename是vector，定义的时候记得在>>符号之间加上空格:
vector<vector<int> > name;//>>之间要有空格

2、vector数组的定义:vector<typename> arrayname[arraysize];例如:

vector<int> vi[100];//vi[0]~vi[99]中的每一个都是一个vector容器

与vector<vector<int> > name;不同的是，这种写法的一维长度已经固定为arraysize，另一维才是变长的。

3、vector容器内元素的访问

(1)通过下标访问，即vi[0]~vi[size-1]进行访问。
(2)通过迭代器访问,迭代器可以理解为一种类似指针的东西，其定义是:vector<typename>::iterator it;这样得到迭代器it之后，就可以通过*it来访问vector中的元素例如:

#include<iostream>
#include<vector>
using namespace std ;

int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i);
    }
    vector<int>::iterator it=vi.begin();//vi.begin()为取vi的首元素地址，而it指向这个地址
    for(int i=0;i<5;i++){
        cout<<*(it+i);
    }
    return 0;
}

上述程序中出现了去vi的首地址的begin()函数,那么就不得不提到end()函数。与begin()函数不同的是,end()函数作为迭代器的末尾标志,取的是尾元素地址的下一个地址,不存储任何元素。另外，vector的迭代器不支持it<vi.end()的写法，因此循环条件只能用it!=vi.end()。除此之外，迭代器还实现了两种自加操作:it++和++it(自减操作同理)。

(3)定义并初始化动态的二维数组，然后遍历。

vector<vector<int> > array(n);//定义一个存储数塔的动态二维数组
for (int i = 0;i < n;i++) {
    array[i].resize(5);
    for (int j = 0;j < array[0].size();j++) {
        cin >> array[i][j];//初始化
    }
}
vector<int>::iterator it;
vector<vector<int> >::iterator iter;
vector<int> tmp;
for (iter = array.begin();iter != array.end();iter++) {
    tmp = *iter;
    for (it = tmp.begin();it != tmp.end();it++) {
        cout << *it << " ";//遍历
    }
    cout << endl;
}

4、vector常用的函数

(1)push_back(x):在vector后面添加一个元素，时间复杂度为O(1)。
(2)pop_back():用以删除vector的尾元素，时间复杂度为O(1)。
(3)size():用来获得vector中的元素的个数，时间复杂度为O(1)。返回的是unsigned类型。
(4)clear():用来清空vector中的所有元素，时间复杂度为O(N)。N为vector中元素的个数。
(5)insert(it,x):用来向vector的任意迭代器it处插入一个元素x，时间复杂度O(N)。
(6)erase():有两种用法:删除单个元素,删除一个区间内的所有元素。a.erase(it),it为所需要删除元素的迭代器,时间复杂度O(N);a.erase(first,last),first为起始迭代器,而last为删除区间的末尾迭代器的下一个地址。