vector

摘要：本文系统介绍 C++ 标准库中 std::vector 动态数组的核心用法，涵盖其基本概念与内存结构、常用构造函数、迭代器与范围 for 遍历方式、容量管理接口、增删查改等常用操作，并重点分析迭代器失效的成因与注意事项，最后通过杨辉三角示例帮助理解动态二维数组的构造与使用。

一、vector的介绍

C 语言中的数组大家都熟悉：固定大小，内存连续。普通的静态数组的大小是在定义时就确定的，如果空间不够，需要手写扩容函数再去申请空间扩容。

而 C++ 中的 std::vector 就是一个动态数组，封装了内存上的一块区域，能够自动扩容，是 C++ 最常用的容器之一。

使用时要加上 #include <vector>

特点：空间一定连续，和普通数组一样，支持随机访问。

vector 中维护 3 个指针（64 位环境下对象占 24 个字节）：

_start：数据起始地址

_finish：最后一个有效元素的下一位

_ebd_of_storage：缓冲区末端

二、vector的构造函数

且在变量名之前需要加上数据类型。

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

int main() {
vector<int> v1;
vector<int> v2(6, 3);
vector<int> v3(v2);
vector<int> v4(v2.begin(), v2.end());
}

三、vector的迭代器和范围for遍历

迭代器接口：

和 string 的迭代器使用类似：

vector<int> v1(5, 4);
vector<int>::iterator it = v1.begin();
while (it != v1.end()) {
cout << *it << " ";
++it;
}
cout << endl;

或者使用 auto 自动识别类型：

vector<int> v1(5, 4);
auto it = v1.begin();
while (it != v1.end()) {
cout << *it << " ";
++it;
}
cout << endl;

范围for遍历：

vector<int> v1(5, 4);
auto it = v1.begin();
for (auto& e : v1) {
cout << e << " ";
}
cout << endl;

四、vector的容量问题

接口：

vector的内存扩容和环境有关，vs下capacity是按1.5倍增长的，g++是按2倍增长的，不要固化的

认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。

reserve 只负责开辟空间。如果确定知道需要用多少空间，提前调用 reserve 可以缓解 vector 增容带来的代价缺陷，避免因空间不足而反复扩容导致效率变低。

五、vector容器的常用接口

其中和string不一样的是，vector没有自己的成员函数.find()，而是<algorithm>中的泛型算法，vector 本身没有 .find() 成员。

详细的接口使用在：https://cplusplus.com/reference/vector/vector/

六、vector的迭代器失效问题

在 C 语言的内存操作函数中，使用 malloc 申请内存后，会遇到空间不够的情况，这时就会使用 realloc 去扩容，而扩容函数的策略是，如果内存剩下的空间还是不够，就会在堆上重新开辟新空间，再把新空间返回，从而成功扩容。

但是对于迭代器，其底层就是一个指针，而迭代器失效，实际就是迭代器原本指向的区域被释放，而指针指向一个被释放的空间，就会使程序崩溃。

我们看一下 vector 中的接口，push_back、insert、resize、reserve、assign 都是能够引起 vector 大小变化的函数，从而就可能导致底层空间的改变，使迭代器失效。如：

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

int main() {
vector<int> v1(5, 4);
auto it = v1.begin();
// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
// v.resize(100, 8);
// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容
//量改变
// v.reserve(100);
// 插入元素期间，可能会引起扩容，而导致原空间被释放
// v.insert(v.begin(), 0);
// v.push_back(8);
// 给vector重新赋值，可能会引起底层容量改变
v1.assign(100, 8);
while (it != v1.end()) {
cout << *it << " ";
++it;
}
cout << endl;
}

特殊的访问失败：数组的删除操作——erase

#include <iostream>
using namespace std;
#include <vector>
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// 使用find查找3所在位置的iterator
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// 删除pos位置的数据，导致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此处会导致非法访问
return 0;
}

在erase删除操作中，删除后pos之后的位置会往前移，但如果pos恰好是最后一个位置，那么返回的就是end的位置，而end位置是没有数据的，这就会导致迭代器失效。

需要注意的是，string经过扩容后也可能会出现迭代器失效的问题。

七、动态二维数组的理解

在使用vector时，我们会定义vector中的数据类型，但如果我们将数据类型定义为vector <int> 呢？

等于是将数组中的每个数据设定为另一个数组，这样我们就得到了动态二维数组。

我们以杨辉三角为例：

void test2vector(size_t n)
{
// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>
bit::vector<bit::vector<int>> vv(n);
// 将二维数组每一行中的vector<int>中的元素全部设置为1
for (size_t i = 0; i < n; ++i)
vv[i].resize(i + 1, 1);
// 给杨辉三角出第一列和对角线的所有元素赋值
for (int i = 2; i < n; ++i)
{
for (int j = 1; j < i; ++j)
{
vv[i][j] = vv[i – 1][j] + vv[i – 1][j – 1];
}
}
}

bit::vector<bit::vector<int>> vv(n)
;
构造一个
vv
动态二维数组，
vv
中总共有
n
个元素，每个元素

都是
vector
类型的，每行没有包含任何元素。

假设 n=5，那么内部就是这样的：