一、vector的内存预分配策略
vector是C++ STL中最常用的动态数组容器，它的核心优势在于能够动态扩容。但每次扩容都要付出性能代价，所以vector采用了一套聪明的内存预分配策略。
当我们创建一个vector时，它并不会立即分配所有需要的内存。相反，它会按需分配，并且在每次扩容时采用几何增长的策略（通常是当前容量的1.5倍或2倍）。这样可以减少频繁的内存分配操作，提高效率。
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec; // 初始容量为0
std::cout << "初始容量: " << vec.capacity() << std::endl; // 输出: 0
vec.push_back(1); // 第一次扩容，容量变为1
std::cout << "第一次扩容后容量: " << vec.capacity() << std::endl; // 输出: 1
vec.push_back(2); // 第二次扩容，容量变为2
std::cout << "第二次扩容后容量: " << vec.capacity() << std::endl; // 输出: 2
vec.push_back(3); // 第三次扩容，容量变为4（假设增长因子为2）
std::cout << "第三次扩容后容量: " << vec.capacity() << std::endl; // 输出: 4
return 0;
}
为什么采用几何增长？
如果每次扩容只增加固定大小（比如每次+1），那么在频繁插入数据时，会导致大量内存重新分配和数据拷贝，严重影响性能。而几何增长能保证均摊时间复杂度为O(1)。
二、迭代器失效的原因
vector的迭代器本质上是指向底层数组的指针，因此当vector发生扩容时，原有的迭代器可能会失效。常见的失效场景包括：
- 插入元素导致扩容：如果插入操作导致vector扩容，所有迭代器、指针和引用都会失效。
- 删除元素导致位置变化：删除元素后，被删除位置之后的迭代器会失效。
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2; // 指向元素3
vec.push_back(6); // 可能导致扩容，it失效！
// std::cout << *it << std::endl; // 危险！未定义行为
it = vec.begin() + 2; // 重新获取迭代器
std::cout << "重新获取迭代器后的值: " << *it << std::endl; // 输出: 3
vec.erase(vec.begin() + 1); // 删除元素2，后面的迭代器可能失效
// std::cout << *it << std::endl; // 危险！可能失效
return 0;
}
如何避免迭代器失效？
- 在插入或删除操作后，重新获取迭代器。
- 使用
reserve()预分配足够的内存，减少扩容次数。
三、解决方案：reserve与shrink_to_fit
为了避免频繁扩容，我们可以使用reserve提前分配足够的内存。此外，shrink_to_fit可以释放多余的内存，使容量与当前元素数量匹配。
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec;
vec.reserve(100); // 预分配100个元素的空间
std::cout << "预分配后的容量: " << vec.capacity() << std::endl; // 输出: 100
for (int i = 0; i < 50; ++i) {
vec.push_back(i); // 不会触发扩容
}
std::cout << "插入50个元素后的容量: " << vec.capacity() << std::endl; // 输出: 100
vec.shrink_to_fit(); // 释放多余内存
std::cout << "收缩后的容量: " << vec.capacity() << std::endl; // 输出: 50
return 0;
}
适用场景：
reserve适用于已知元素数量的场景，比如读取文件前预分配空间。shrink_to_fit适用于内存敏感的场景，比如长期运行的服务器程序。
四、应用场景与总结
应用场景：
- 高性能计算：避免频繁扩容，提高数据处理速度。
- 游戏开发：预分配内存减少卡顿。
- 嵌入式系统：严格控制内存使用。
技术优缺点：
- 优点：动态扩容、随机访问高效、内存预分配优化。
- 缺点：插入/删除中间元素较慢（O(n)），迭代器可能失效。
注意事项：
- 避免在循环中频繁
push_back，尽量使用reserve。 - 迭代器失效后必须重新获取。
shrink_to_fit不保证立即释放内存，取决于具体实现。
总结：
vector是C++中最灵活的动态数组，合理使用内存预分配和迭代器管理可以大幅提升性能。理解其底层机制，能帮助我们写出更高效的代码。
评论