基本数据结构01-动态数组 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);
    // 输出 0 (false)
    cout << nums.empty() << endl;
    // 输出：10
    cout << nums.size() << endl;

    // 在数组尾部插入一个元素 20
    nums.push_back(20);
    // 输出：11
    cout << nums.size() << endl;

    // 得到数组最后一个元素的引用
    // 输出：20
    cout << nums.back() << endl;

    // 删除数组的最后一个元素（无返回值）
    nums.pop_back();
    // 输出：10
    cout << nums.size() << endl;

    // 可以通过方括号直接取值或修改
    nums[0] = 11;
    // 输出：11
    cout << nums[0] << endl;

    // 在索引 3 处插入一个元素 99
    nums.insert(nums.begin() + 3, 99);

    // 删除索引 2 处的元素
    nums.erase(nums.begin() + 2);

    // 交换 nums[0] 和 nums[1]
    swap(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;
}

以上就是 C++ vector 在本书中的常用方法，无非就是用索引取元素以及 push_back, pop_back 方法，就刷算法题而言，这些就够了。

因为根据「数组」的特性，利用索引访问元素很高效，从尾部增删元素也是很高效的；而从中间或头部增删元素要涉及搬移数据，很低效。

vector 对象大小问题：

1. vector对象的内存构成

• 指向元素数组的指针：该指针指向存放元素的动态分配数组。
• 当前元素数量（size）：记录vector中现有元素的个数。
• 容量（capacity）：表示当前分配的内存能够容纳的元素数量。

2. sizeof运算符的作用

3.若想获取元素数量或总内存大小，可采用以下方法

• 获取元素数量：使用a.size()。
• 获取容量：使用a.capacity()。在 C++ 中，vector 的容量（capacity()）是指其当前分配的内存能够容纳的元素数量，当元素数量超过容量时，会自动重新分配更大的内存空间。
• 计算元素占用的总字节数：使用a.size() * sizeof(int)。