C++ 标准模板库（STL）：vector

1. vector

1. vector

变长数组，长度根据需要而自动变化的数组。
当普通数组会超过内存的情况，这种情况使用vector会让问题的解决便捷许多。
vector可以用来以邻接表的方式存储图

1.1 vector的定义

定义一维变长数组

vector<typename> name;

这个的typename可以是任何基本类型，也可以是STL标准容器模板。

需要注意：如果typename是一个STL容器，定义的时候要在>>符号之加上空格！

vector<int> name;

vector<node> name; //node是结构体

vector<vector<int> > name; // >>之间要加空格，防止被编译器误认为是移位符号！

定义二维变长数组
- Arrayname中的每一个元素都是一个vector。
- 可以把二维vector数组当作两个维都可以变长的二维数组理解。

vector<typename> Arrayname [arraySize];

与vector<vector > name不同，vector Arrayname [arraySize];的一维长度已经被固定为arraySize，仅剩另一维是变长的。

1.2 vector容器内元素的访问

通过下标访问

直接通过vi[index]

通过迭代器访问

迭代器可以理解为类似指针的东西
```
vector<typename>::iterator it;
```
可以通过it*来访问vector里的元素。

代码实例

#include <stdio.h>

#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();

    for(int i = 0; i<5; i++){

        printf("%d ",*(it + i));

    }

    return 0;

}

#include <stdio.h>

#include <vector>

using namespace std;

int main() {

    vector<int> vi;

    for(int i = 1; i<= 5; i++){

        vi.push_back(i);

    }

    for(vector<int>::iterator it = vi.begin();it != vi.end(); it++){

        printf("%d ",*it);

    }

    return 0;

}

！可以看到vi[i]和*(vi.begin()+i)是等价的。

！begin()是作为取vi的首元素，end()是作为尾元素地址，且end()作为迭代器末尾元素，不储存任何元素。

！vector的迭代器不支持 it < vi.end() 写法，因此循环条件只能用 it != vi.end()。

! 只有在vector和string中，才允许使用vi.begin()+3这种迭代器加上整数的写法。

1.3 vector 常用函数实例解析

push_back()

在vector后面添加一个元素x，时间复杂度为\(O(1)\)

#include <stdio.h>

#include <vector>

using namespace std;

int main() {

    vector<int> vi;

    for(int i = 1; i<= 3; i++){

        vi.push_back(i);//将1、2、3依次插入vi末尾

    }

    for(int i=0; i<vi.size(); i++){

        printf("%d ", vi[i]);//size给出vi中元素的个数

    }

    return 0;

}

pop_back()

在vector删除末尾元素x，时间复杂度为\(O(1)\)

#include <stdio.h>

#include <vector>

using namespace std;

int main() {

    vector<int> vi;

    for(int i = 1; i<= 3; i++){

        vi.push_back(i);//将1、2、3依次插入vi末尾

    }

    vi.pop_back(); //删除vi的末尾元素

    for(int i=0; i<vi.size(); i++){

        printf("%d ", vi[i]);//size给出vi中元素的个数

    }

    return 0;

}

size()

所有容器都有的返回元素个数，是unsigned类型，一般就用%d

clear()

用来清空vector中所有元素，时间复杂度为\(O(N)\)

#include <stdio.h>

#include <vector>

using namespace std;

int main() {

    vector<int> vi;

    for(int i = 1; i<= 3; i++){

        vi.push_back(i);//将1、2、3依次插入vi末尾

    }

    vi.clear();

    printf("%d\n",vi.size());

    return 0;

}

insert()

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

#include <stdio.h>

#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.insert(vi.begin() + 2,-1);//在vi[2]的为止插入-1

    for(int i=0; i<vi.size();i++){

        printf("%d ",vi[i]);

    }

    return 0;

}

erase()

删除单个元素

#include <stdio.h>

#include <vector>

using namespace std;

int main() {

    vector<int> vi;

    for(int i = 5; i<= 9; i++){

        vi.push_back(i);//将5、6、7、8、9依次插入vi末尾

    }

    vi.erase(vi.begin() + 3); //删除vi[3]位置的元素

    for(int i=0; i<vi.size();i++){

        printf("%d ",vi[i]);

    }

    return 0;

}

删除一个区间内的所有元素(左闭右开)

#include <stdio.h>

#include <vector>

using namespace std;

int main() {

    vector<int> vi;

    for(int i = 5; i<= 9; i++){

        vi.push_back(i);//将5、6、7、8、9依次插入vi末尾

    }

    vi.erase(vi.begin() + 1,vi.begin() + 4); //删除vi[1]到v[4]位置的元素（左闭右开），即删去vi[1]、vi[2]、vi[3]

    for(int i=0; i<vi.size();i++){

        printf("%d ",vi[i]);

    }

    return 0;

}

1.4 vector的常见用途

存储数据
用邻接表存储图

巴特西