17370845950

vector 的扩容触发条件和实际增长策略

vector 不是每次 push_back 都重新分配内存，而是在容量不足时按特定规则扩容。标准未强制要求具体倍数，但主流实现（libstdc++、libc++、MSVC）均采用「约 1.5 倍」或「2 倍」增长，例如 libstdc++ 在多数版本中用 old_capacity + old_capacity / 2（即 1.5 倍），而非简单翻倍。

这意味着：连续插入 n 个元素时，实际内存分配次数是 O(log n) 级别，但每次扩容涉及旧数据拷贝，代价不可忽略。若已知大致规模，应优先调用 reserve() 预留空间。

• reserve(100) 只改变 capacity()，不改变 size()
• resize(100) 会将 size() 设为 100，必要时默认构造新元素，也可能触发扩容
• 对 vector 要格外小心——它是特化模板，底层常以位为单位存储，data() 不可用，迭代器行为也不同

安全遍历 vector 的三种常用方式及适用场景

遍历时核心关注点是：是否需要索引、是否可能修改元素、是否在循环中增删元素。错误的遍历方式极易导致越界或迭代器失效。

• 基于范围的 for 循环最简洁：

  for (const auto& x : v) { /* 只读 */ }

  或

  for (auto& x : v) { x = ...; /* 可写 */ }

  —— 但无法获取下标，且不能在循环体内调用 push_back 或 erase
• 用索引访问（operator[] 或 at()）适合需下标逻辑：

  for (size_t i = 0; i < v.size(); ++i) { v[i] *= 2; }

  注意 v.at(i) 会做边界检查并抛 std::out_of_range，而 v[i] 不检查
• 使用迭代器时，删除元素必须用 erase 返回的新迭代器：

  for (auto it = v.begin(); it != v.end(); ) { if (*it % 2 == 0) it = v.erase(it); else ++it; }

  直接 ++it 后 erase(it) 是未定义行为

vector 扩容后原有迭代器/指针/引用全部失效

这是最容易被忽视的陷阱。只要发生扩容（包括隐式扩容），所有指向该 vector 元素的 iterator、pointer、reference 都变为悬空（dangling），后续解引用必出错。

• 以下代码在扩容后访问 p 是未定义行为：

  std::vector v = {1, 2, 3};
  int* p = &v[0];
  v.reserve(100); // 可能触发扩容
  printf("%d", *p); // 危险！p 已失效

• 若需长期持有某元素地址，应改用索引（size_t idx）代替指针；或确保在生命周期内不扩容（如提前 reserve 并不再插入）
• data() 返回的指针同样遵循此规则：仅当 !empty() 且未扩容时有效

clear() 不释放内存，shrink_to_fit() 也不保证释放

clear() 仅销毁所有元素并将 size() 置为 0，capacity() 保持不变。想真正归还内存给系统，需调用 shrink_to_fit() —— 但它只是请求，标准允许实现忽略该请求。

• 常见做法是交换空 vector：

  v.clear();
  std::vector(v).swap(v); // 强制释放内存

• 该技巧利用临时对象的析构释放内存，适用于 C++11 及以后
• 注意：频繁调用 shrink_to_fit 或 swap 技巧可能带来额外开销，应权衡内存与性能需求

vector 的动态性便利背后藏着几处硬约束：扩容时机不可控、迭代器易失效、内存释放非自动。写代码时别只盯着 push_back 和 size()，多看一眼 capacity()，少用裸指针存元素地址，遍历时避开边循环边修改的惯性操作。