数据结构：动态数组vector

vector 是 C++ 标准库的动态数组。

在C语言中一般初学者会使用malloc，int[n]等方式来创建静态数组，但是这种方式繁琐且容易出错。我们做算法题一般使用动态数组vector， 并且在刷题网站的题目给的输入一般也是vector类型。

 示例：vector的初始化如下：

#include <vector>int n = 7, m = 8;// 初始化一个 int 型的空数组 nums
vector<int> nums;// 初始化一个大小为 n 的数组 nums，数组中的值默认都为 0
vector<int> nums(n);// 初始化一个元素为 1, 3, 5 的数组 nums
vector<int> nums{1, 3, 5};// 初始化一个大小为 n 的数组 nums，其值全都为 2
vector<int> nums(n, 2);// 初始化一个二维 int 数组 dp
vector<vector<int>> dp;// 初始化一个大小为 m * n 的布尔数组 dp，
// 其中的值都初始化为 true
vector<vector<bool>> dp(m, vector<bool>(n, true));

vector的操作示例：

 

#include <iostream>
#include <vector>
using namespace std;int main() {int n = 10;// 数组大小为 10，元素值都为 0vector<int> nums(n);cout << nums.empty() << endl;  // 输出 0 (false)cout << nums.size() << endl;   // 输出：10nums.push_back(20);   // 在数组尾部插入一个元素 20cout << nums.size() << endl;  // 输出：11cout << nums.back() << endl;  // 得到数组最后一个元素的引用     输出：20nums.pop_back();     // 删除数组的最后一个元素（无返回值）cout << nums.size() << endl;     // 输出：10nums[0] = 11;        // 可以通过方括号直接取值或修改cout << nums[0] << endl;       // 输出：11nums.insert(nums.begin() + 3, 99);      // 在索引 3 处插入一个元素 99nums.erase(nums.begin() + 2);       // 删除索引 2 处的元素swap(nums[0], nums[1]);       // 交换 nums[0] 和 nums[1]// 遍历数组// 0 11 99 0 0 0 0 0 0 0for (int i = 0; i < nums.size(); i++) {cout << nums[i] << " ";}cout << endl;
}

另外，根据数组的特性，利用索引访问元素很高效，从尾部删除元素也是很高效的；但是从中间或者头部删除或增加元素需要数据搬移，很低效。