一、vector简介

vector的中文翻译为向量，是一种C++ STL中的序列容器。它的是存储方式和C++语言本身提供的数组一样都是顺序存储，因此vector的操作和数组十分相似。但是和数组不一样的是，数组的存储空间是静态的，一旦配置了就不能改变，而vector的存储空间是动态的，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素，因此也被称为可变长数组。

二、vector存储机制

vector的动态空间实现如下图所示，

为了减少空间配置的时间代价，通常vector配置的空间会比我们标注的需求量更大一些，于是vector总的存储空间就如上图所示分成了两部分，其中工作空间是按我们标注的需求配置的，而备用空间就是额外配置的那一部分空间。

当需要扩充的新的空间时，vector会优先使用备用空间。例如我们现在要在末尾插入6，它会将 $finish$ 迭代器指向的空间用于存储6，最后再调整 $finish$ 迭代器的位置。
当备用空间不足以存放要插入的元素时，vector会在另外较大的空闲空间中配置一块大小为原来两倍的新空间（由于不能保证原空间之后有足有的空闲空间，所以并不是直接在原空间后面接续），然后将原空间中的数据按顺序迁移到新空间，最后释放原来的存储空间。这一过程可以简单记忆为重新配置、移动数据、释放原空间。

下面是以“在备用空间用完的情况下插入新元素3”为例，用图片形式描述前后的存储空间变化。

由于以上过程对使用者而言都是透明的，所以需要非常注意的一点是，一旦vector的空间重新配置，所有指向原vector的迭代器都会失效！

三、vector创建和初始化

初始化比较简单，我们可以根据自己的使用需求来相应的初始化方法。

//vector头文件
#include <vector>
//创建一个空的vector
vector<int> vec1;
//创建一个有n个元素的vector，初始值都为0
vector<int> vec2(n);
//创建一个有n个元素的vector，并将它们值都初始化为x
vector<int> vec3(n, x);
//用vec3来初始化vec4，它们大小和元素的值都相同
vector<int> vec4(vec3);

四、vector基本操作详解

很多人不明白为什么要了解容器本身实现的原理，觉得学会怎么用就够了。其实，学了容器的实现原理会对容器操作会有更加深刻的理解，同时也会对算法思想有或多或少的领悟。

接下来，我们结合这张底层存储示意图仔细分析vector的基本操作。

• 迭代器
  这里简单介绍下面将出现的两种比较陌生的迭代器：
  • $reverse\_iterator$，称为反向迭代器，它的递增方向和我们常用的 $iterator$ 相反，例如 $rit++$表示指向的位置往左移。
  • $const\_iterator$，它不能改变所指向的元素的值，但是可以再指向其他元素，和const关键词标注的 $iterator$ 刚好相反。

//获取第一个元素的迭代器，也就是图中的start
vec.begin();

//获取最后一个下个位置的迭代器，即图中的finish
vec.end();

//返回vector<T>::reverse_iterator类型迭代器，指向finish-1
vec.rbegin();

//返回vector<T>::reverse_iterator类型迭代器，指向start的前一个位置
vec.rend();

//c++11，返回vector<T>::const_iterator类型迭代器，位置同图中start
vec.cbegin();

//c++11，返回vector<T>::const_iterator类型迭代器，位置同图中finish
vec.cend();

• 容量

//获取当前容量大小
vec.size();

//获取包括备用空间在内的总容量大小
vec.capacity();

//最大容量，即最多可以存储多少个当前类型元素
vec.max_size();

//判断vector是否为空，即判断start == finish
vec.empty();

//重新设置vector的容量，大小为n
vec.resize(n);

• 元素访问
  因为vector也是顺序存储，所以它进行元素的随机访问的时间复杂度也为 $O(1)$

//像数组一样用索引进行随机访问，例如vec[0]
operator []

//作用同上，增加异常处理，越界抛出out of range
vec.at(index);

//返回一个元素，即迭代器start指向的元素
vec.front();

//返回最后一个元素，即迭代器finish-1指向的元素
vec.back();

• 修改操作操作
  由于是顺序存储结构，随机插入或随机删除都会引起元素的移动（对末尾元素操作除外），因此它们的时间复杂度都是 $O(n)$。下图是删除元素的底层实现示意，可以用于帮助我们的理解，从图中也可以看出删除操作不会引起总空间的变化。
  

//元素的赋值值操作（类似于初始化）
//将vec赋值为n个x
vec.assign(n, x);
//将[first, last)范围内的元素赋值给vec
vec.assign(first, last);
//传入参数为数组指针，将数组[0, n)中的元素赋值给vec
vec.assign(array, array + n);

//将新元素x插入到finish所在的位置，并将迭代器finish后移，时间复杂度为O(1)
vec.push_back(x);

//清除位于finish-1的元素，时间复杂度为O(1)
vec.pop_back();

//时间复杂度为O(n)，position表示插入位置的迭代器
//在position插入新元素，其值为x
vec.insert(position, x);
//在position插入n个新元素，它们的值都为x
vec.insert(position, n, x);

//时间复杂度为O(n)，下列参数均为迭代器
//清除某个特定位置的元素
vec.erase(position);
//清除[first, last)中的所有元素
vec.erase(first, last);

//交换vec和vec2中的所有元素，
vec.swap(vec2);

//清除所有的元素，事实上调用了erase(begin(), end())
vec.clear();

• 遍历操作

//顺序遍历
//最常用的方式
for (int i = 0; i < vec.size(); i++) cout << vec[i] << endl;
//利用迭代器
vector<int>::iterator it;
for (it = vec.begin(); it != vec.end(); i++) cout << *it << endl;
//c++11
for(auto x : vec) cout << x << endl;

//逆序遍历
//常用方式
for (int i = size() - 1; i >= 0; i--) cout << vec[i] << endl;
//利用反向迭代器
vector<int>::reverse_iterator rit;
for (rit = vec.rbegin(); rit != vec.rend(); rit++) cout << *rit << endl;

• 查找操作
  这个操作主要是利用STL提供的 $find$ 函数。

#include <algorithm>
//需要调用find函数，在[first, last)中查找x，返回的是迭代器
vector<int>::iterator it = find(vec.begin(), vec.end(), x);
//如果找到则输出YES，否则输出NO
if (it != vec.end()) cout << "YES" << endl;
else cout << "NO" << endl;

• 排序和翻转
  主要是调用STL提供的 $sort$ 和 $reverse$ 函数。

#include <algorithm>
//升序排序(默认)
sort(vec.begin(), vec.end());
sort(vec.begin(), vec.end(), less<int>());
//降序排序
sort(vec.begin(), vec.end(), greater<int>());

//元素翻转
reverse(vec.begin(), vec.end());

五、参考资料

1. C++官方的vector文档
2. 《STL源码剖析》
3. 个人混乱的实验代码

---

既然都看到就这里了（我也终于写到这里了），希望你可以做到下面三点哦：

• 点赞，这是对作者辛苦写作的最低成本的鼓励。
• 答应我，把它学会！（别扔进收藏夹吃灰）
• 可以考虑关注一波，STL系列的文章会持续更新。