vector，向量（变长数组）

头文件:

#include<vector>

1、vector的定义

单独定义一个vector：

vector<typename> name;

上面这个定义相当于是一个一维数组name[SIZE]，只不过其长度可以根据需要进行变化。

typename可以是任何基本类型，例如int、double、char、结构体等，也可以是STL标准容器，例如vector、set、queue等。下面是一些简单例子。

vector<int> name;
vector<double> name;
vector<char> name;
vector<node> name;//node是结构体的类型

vector<vector<int> > name;//>>之间要加空格
//两个维都可以变长的二维数组

定义vector数组：

vector<typename> Arrayname[arraySize];

这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是一个vector容器。

这种写法的一维长度已经固定为arraySize，另一维才是变长的。

2、vector容器内元素的访问

（1）通过下标访问

和访问普通的数组是一样的，对一个定义为vector<typename> vi的vector容器来说，直接访问vi[index]即可（如vi[0]、vi[1]）。下标从0到vi.size()-1。

（2）通过迭代器访问

迭代器（iterator）可以理解为一种类似指针的东西，其定义是：

vector<typename>::iterator it;

这样it就是一个vector<typename>::iterator型的变量。可以使用*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);
    }
    //vi.begin()为取vi的首元素地址，而it指向这个地址
    vector<int>::iterator it = vi.begin();
    for (int i = 0; i < 5; i++) {
        printf("%d ", *(it + i));
    }
}
//输出结果：1 2 3 4 5

begin()函数的作用为取vi的首元素地址，end()函数取尾元素的下一个地址。

除此之外，迭代器还实现了两种自加操作：++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的迭代器不支持it < vi.end()写法，因此循环条件只能用it != vi.end();
    for (vector<int>::iterator it = vi.begin(); it != vi.end(); it++) {
        printf("%d ", *it);
    }
}
//输出：1 2 3 4 5

3、vector常用函数

（1）push_back()

push_back(x)就是在vector后面添加一个元素x,时间复杂度为O(1)。

（2）pop_back()

pop_back()用以删除vector的尾元素，时间复杂度为O(1)。

（3）size()

size()用来获得vector中元素的个数，时间复杂度为O(1)。size()返回的是unsigned类型。

（4）clear()

clear()用来清空vector中的所有元素，时间复杂度为O(N),其中N为vector中元素的个数。

（5）insert()

insert(it,x)用来向vector的任意迭代器it处插入一个元素x，时间复杂度为O(N)。

（6）erase()

erase()有两种用法：删除单个元素、删除一个区间内的所有元素。时间复杂度均为O(N)。

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

int main() {
    vector<int> vi;
    for (int i = 1; i <= 5; i++) {
        vi.push_back(i);//将1、2、3、4、5依次插入vi的末尾
    }
    vi.pop_back();//删除vi的尾元素3
    vi.insert(vi.begin() + 2, -1);//将-1插入vi[2]的位置
    vi.erase(vi.begin() + 3);//删除第四个元素
    vi.erase(vi.begin() + 1, vi.begin() + 3);//删除vi[1],vi[2],vi[3]
    for (int i = 0; i < vi.size(); i++) {//size()函数会给出vi中元素的个数
        printf("%d ", vi[i]);
    }
    vi.clear();
}