[C++STL教程]1.vector容器是什么？可能是全网最好的教程

C++与传统的C语言有一个很大的区别，就是新增了标准模板库 STL（Standard Template Library），它是 C++ 标准库的一部分，不需要单独安装，只需要 #include 对应的头文件即可。

本文将介绍STL中最基础的一个容器：vector

注意：本文仅从入门和实用角度介绍vector的用法。如有不严谨的地方欢迎指正！

引入头文件

在使用vector之前需要用#include <vector>来引入头文件。

如果你是竞赛选手，也可以用万能头#include <bits/stdc++.h>其中包含了<vector>。

vector简介

vector可以理解为动态数组，它的大小会随着元素的增加而自动增大。下标从0开始，大小为n的vector的可用范围是[0, n - 1]。

vector中不仅可以存放int, char等基础数据类型，还可以存放结构体、类等等。

但是一个vector中只能存放一种类型。

初始化

现在我们可以动手来生成一个vector试试：

vector<int> v(3, 5);//生成一个vector，其中有3个值为5的元素

二维数组后面会讲到。

遍历数组

既然是数组肯定少不了遍历嘛对吧~

思路是，先用v.size()获取vector的大小，然后用for循环遍历。

//v.size()返回值为unsigned int
for(int i = 0;i < v.size(); ++ i)
{
	printf("%d", v[i]);
}
//结果为： 5 5 5

在C++11之后，可以使用auto关键字进行遍历，这个在后面会讲到。

插入元素

void push_back(const T& x)

vector有一个叫push_back()的方法，可以在数组尾部插入一个元素且令数组大小+1。

举个例子：

printf("%dn", (int)v.size());//v.size() = 3
for(int i = 1;i <= 3; ++ i)v.push_back(i);
//现在 v 是: 5 5 5 1 2 3
//v.size() = 6

一般只向尾部插入元素，因为向其他位置插入元素的复杂度较高。

删除元素

void pop_back()删除最后一个元素。

void clear()清空vector，大小变为0

void erase(iter l, iter r)清空迭代器指向的区间$[l, r)$的元素。

v.pop_back();
//5 5 5 1 2
v.clear();
//null

其他的一般也用不着。

判断是否为空

bool empty()判断vector是否为空

vector<int> a(3);
//v.empty() == false
a.clear();
//v.empty() == true

一些常用函数(以下 v 指实例对象)

v.resize(n)将vector大小修改为n

v.begin()获取vector第一个元素的迭代器（指针）

v.end()获取vector最后一个元素的后一个位置的迭代器

v.rbegin()获取vector倒数第一个元素的迭代器（指针）

v.rend()获取vector倒数最后一个元素的后一个位置的迭代器

vector<int> v = {1, 2, 3}
cout << *v.begin() << 'n';//1
cout << *v.rbegin() << 'n';//3
cout << *(++ v.begin()) << 'n';//2

注意迭代器只能++或者--，不可以做 += n这种操作！

欢迎在右上角留下邮箱订阅我的博客哦！每周更新优质算法、计算机、互联网文章！

一些实例用法

下面介绍一些vector的实例化用法。

auto关键字遍历vector

有时候用auto关键字是一件很美的事儿，比如在写dfs的时候，不用管子节点的顺序，直接往下递归即可，用auto比用下标来写循环更安全。

需要注意一点，auto默认为浅拷贝，也就是复制出的一个副本来进行遍历，如果想要遍历vector本身，需要加个&，看以下的例子就明白了。

vector<int> v = {1, 5, 2, 4, 3};

for(auto i : v)i = 1;
//v = {1, 5, 2, 4, 3}

for(auto &i : v)i = 1;
//v = {1, 1, 1, 1, 1}

当然你也自己尝试，把地址打出来看看。

而且，用&会比直接浅拷贝更快。

vector排序

给vector排序，需要先引入<algorithm>头文件：

#include <algorithm>
using namespace std;
int main()
{
	vector<int> v = {5, 1, 3, 2, 4};
	sort(v.begin(), v.end());//传入vector的首尾迭代器
	//v = {1 2 3 4 5}
}

这样排序默认是升序的，可以利用reverse(iterator first, iterator last)进行翻转，写法和sort类似：

reverse(v.begin(), v.end());
//v = {5, 4, 3, 2, 1}

如果想在排序的时候一步到位排成降序，可以自定义比较函数，这里不再赘述。

排序并去重

在做离散化时经常用到vector，因为它可以方便的进行排序去重。

unique(iterator first, iterator last)可以将重复的元素移动到末尾的位置，前提是vector升序。

对于vectorv = {1, 1, 2, 5}，unique(v.begin(), v,end())的结果为:v = {1, 2, 5, 1}并返回v.begin() + 3表示去重后的终点位置（即有效数组的最后一个元素的下一个位置）。

vector<int> v = {1, 5, 2, 2, 1, 7, 7};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
//v = {1, 2, 5, 7}

二维数组

起始就是把vector里面存的元素改为vector，就是套娃。

vector<vector<int> > v2;这样会产生一个大小为0的二维数组。

你可以通过resize()为每一个行设置一个大小，从而产生每一行都大小不同的二维数组：

    vector<vector<int> > v2;
    v2.resize(3);
    for(int i = 0;i < 3; ++ i)v2[i].resize(i + 1);

    /*
    v = {
    {0}
    {0, 0}
    {0, 0, 0}
    };
    有点神奇
    */

在做邻接表的时候经常使用vector，但是我习惯于开vector数组，即下面这种写法：

vector<int> g[maxn];

值得注意的一点（性能）

vector虽然可以动态开辟空间，但是这也是有代价的。

vector的空间不是一个一个开的，而是每当元素个数超出了当前的空间，就会开辟一个大小为原先两倍（也有说法是1.5倍）的空间，然后再将原本的数据拷贝过去，这就会增大vector的常数了。

所以如果你的vector大小或者范围已知，所以建议在初始化的时候就规定好大小。比如初始化的时候用vector<int> v(n)，但是注意此时size()已经是n了。