C++容器——vector学习

vector 的本质是一个动态数组：

  • 自动扩容：当你往里添加元素，空间不够时，它会自动找一块更大的地方搬家。
  • 连续存储：它在内存里是排成一排的，这使得访问速度非常快。
  • 灵活：可以随时在末尾增加或删除元素。
C++
vector<int> nums;               // 创建一个存整数的空 vector
vector<int> nums2 = {1, 2, 3};  // 创建并初始化为 1, 2, 3
vector<int> nums3(5, 10);       // 创建 5 个元素，值全是 10

使用 push_back 把元素扔进末尾。

C++
nums.push_back(10); // 现在 nums 是 [10]
nums.push_back(20); // 现在 nums 是 [10, 20]
  • 删除最后一个：pop_back() ，该方法为void，不返回值。
  • 清空所有：clear()
  • back() 获取最后一个元素的引用。

C++11以后，for循环遍历可这样写：

C++
for (int x : nums) {
    cout << x << " ";
}

vector 中的 size 与 capacity ：

  • Size (大小)：你现在实际存了多少个元素。
  • Capacity (容量)：这个“抽屉”目前总共能装多少个元素（不扩容的前提下）。

由此引出 reserve() 方法与 resize() 方法：

当你往 vector 里不断 push_back 元素时，它内部会发生以下连锁反应：

  1. 发现空间满了（Size == Capacity）。
  2. 找一块更大的新内存。
  3. 把旧数据全部复制到新内存。
  4. 释放旧内存。

如果你的数据量很大（比如 100 万个），频繁执行这套动作会产生严重的性能开销。

  • reserve(n) 会提前准备好能装下 n 个元素的空间。
  • 调用 reserve 如果参数比当前容量小，它通常什么都不做，不会帮你释放内存。
  • 它只改变 Capacity（容量），不改变 Size（大小）。
  • 它不会创建任何对象，只是开辟了一块原始内存。

resize(n) 开辟n个内存并填充默认值的元素。

如果 resize 指定的大小超过了当前的 capacity（容量），vector 会立刻触发“搬家”流程（重新分配内存）。

当你执行 v.resize(n) 且 n > v.capacity() 时，后台会发生以下故事：

  1. 申请新内存：vector 会找一块能至少装下 n 个元素的新连续空间。
    • 注意：它不一定只申请 n 个，通常会多申请一些（按 1.5 或 2 倍幂增长），为未来的增长留余地。
  2. 搬运旧数据：把原本已有的数据，从老家搬（移动或拷贝）到新家的前几个位置。
  3. 初始化新成员：在紧接着旧数据后面的位置，创建 n - size() 个新元素，并按默认值（如 0）进行初始化。
  4. 释放老家：把原来的那块旧内存归还给系统。
  5. 更新状态：将 size 和 capacity 都更新为新的数值。

如果你现在的 capacity 已经是 200 了，你调用 reserve(100)，会发生什么？

答案是：什么都不会发生。 reserve 只能增加容量，不能减小容量。它非常大方，如果你想变大，它帮你办；如果你想变小，它会为了保证性能而选择无视你的请求（因为它觉得频繁缩小内存、搬家太浪费时间了）。

小知识： 如果你真的想把多余的容量退还给系统（比如 200 的容量只用了 3 个，太浪费了），你应该调用： v.shrink_to_fit();

如果 resize 的值小于当前的 size，会发生什么？

  1. size 会变小，尾部的元素会被销毁。
  2. capacity 通常保持不变。 也就是说，vector 占用的那块地盘还在，它只是把靠后的房间“清空”了，并没有把房子退给开发商。

迭代器常见坑：迭代器失效（迭代器这一块后续会再开一篇总结）

情况 A：扩容导致的失效

如果你保存了一个指向 vector 元素的迭代器，然后又往 vector 里塞了很多数据导致它触发了扩容（搬家），那么你手里的那个迭代器就失效了——因为它还指向那个已经被释放的老地址。

情况 B：删除导致的失效

当你删除中间的一个元素时，该元素之后的所有迭代器都会失效，因为后面的元素都往前挪了一位。

C++
auto it = v.begin() + 1;
v.push_back(100); // 如果这里触发了扩容
// std::cout << *it; // ❌ 崩溃！it 指向的是旧内存

v.begin() 本质上是返回了一个迭代器对象，各类容器在逻辑上对元素进行有顺序逻辑操作的时候，都是对迭代器对象的操作。

这种统一的接口被称为泛型编程。这意味着如果以后想把代码里的 vector 改成 list（因为你发现需要频繁在中间插入），你只需要改一下变量定义，而不同容器对应的 insert 代码几乎不需要大改。