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

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