19.vector的原理，怎么扩容
🔬 vector的原理与扩容机制
📖 内容概览
vector是C++ STL中最常用的容器之一，它提供了动态数组的功能，支持快速随机访问和高效的尾部插入/删除操作。本文将详细解析vector的底层实现原理、扩容机制、以及resize()和reserve()方法的使用技巧，并通过代码示例展示其工作过程和优化策略。
🎯 核心概念
🔧 vector的底层实现
vector底层基于连续的动态数组实现，主要包含三个核心成员变量：
pointer start：指向数组首元素的指针pointer finish：指向数组最后一个元素的下一个位置的指针pointer end_of_storage：指向数组容量末尾的指针
📋 关键属性
- size：当前存储的元素数量，计算公式：
finish - start - capacity：当前分配的内存容量，计算公式：
end_of_storage - start - 扩容因子：不同编译器实现不同，VS采用1.5倍扩容，GCC采用2倍扩容
🔄 扩容机制详解
🔄 扩容原理
当vector的size等于capacity时，插入新元素会触发扩容：
- 分配一块更大的内存空间（通常是原容量的1.5倍或2倍）
- 将原数组中的元素拷贝/移动到新内存空间
- 释放原内存空间
- 更新start、finish和end_of_storage指针
- 插入新元素
📊 不同编译器的扩容策略
| 编译器 | 扩容因子 | 扩容方式 |
|---|---|---|
| VS2015 | 1.5倍 | new_capacity = old_capacity + old_capacity / 2 |
| GCC | 2倍 | new_capacity = old_capacity * 2 |
| Clang | 2倍 | new_capacity = old_capacity * 2 |
⚠️ 扩容的性能开销
- 时间复杂度：扩容操作的时间复杂度为O(n)，因为需要拷贝所有元素
- 内存碎片：频繁扩容可能导致内存碎片
- 迭代器失效：扩容后，原vector的所有迭代器、指针和引用都会失效
🛠️ 代码示例与分析
📝 示例1：基本扩容演示
#include <iostream>#include <vector>using namespace std;int main() { vector<int> vec; cout << "初始容量: " << vec.capacity() << endl;
for (int i = 0; i < 10; ++i) { vec.push_back(i); cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << endl; } return 0;}输出结果（GCC环境）： 初始容量: 0 size: 1, capacity: 1 size: 2, capacity: 2 size: 3, capacity: 4 size: 4, capacity: 4 size: 5, capacity: 8 size: 6, capacity: 8 size: 7, capacity: 8 size: 8, capacity: 8 size: 9, capacity: 16 size: 10, capacity: 16
示例2：resize()方法详解
#include <iostream>#include <vector>using namespace std;
int main() { vector<int> vec;
// 插入6个元素 for (int i = 0; i < 6; ++i) { vec.push_back(i + 1); }
// 输出当前元素 cout << "\n当前元素: " << endl; for (int i = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl; // resize到9，小于原容量的2倍（8*2=16） vec.resize(9); cout << "\nresize(9)后: " << endl; cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << endl; // 输出resize后的元素 cout << "元素: " << endl; for (int i = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl;
return 0;}输出结果：
当前元素:1 2 3 4 5 6resize(9)后:size: 9, capacity: 12元素:1 2 3 4 5 6 0 0 0示例3：reserve()方法详解
#include <iostream>#include <vector>using namespace std;
class A {public: A() { cout << "✏️ 构造函数" << endl; }
A(const A &a) { cout << "📋 拷贝构造函数" << endl; }
~A() { cout << "🗑️ 析构函数" << endl; }};
int main() { vector<A> vec; A a, b, c;
cout << "\n=== 不使用reserve() ===" << endl; vec.push_back(a);
cout << "\n=== push_back(b) ===" << endl; vec.push_back(b);
cout << "\n=== push_back(c) ===" << endl; vec.push_back(c);
cout << "\n=== 程序结束 ===" << endl; return 0;}🔍 resize() vs reserve()
resize()方法
- 功能：调整vector的大小，并创建/销毁元素
- 语法：
void resize(size_type n, const value_type& val = value_type()) - 影响：
- 如果n < size：删除多余元素，size减小，capacity不变
- 如果size < n < capacity：添加默认/指定值元素，size增大，capacity不变
- 如果n > capacity：扩容并添加元素，size和capacity都增大
reserve()方法
- 功能：预分配内存空间，但不创建元素
- 语法：
void reserve(size_type n)- 如果n > capacity：扩容到n，size不变，capacity增大
- 如果n <= capacity：无任何影响
使用场景
- resize()：需要明确控制元素数量时使用
- reserve()：已知大致元素数量，提前预分配内存，避免频繁扩容时使用
🛠️ 优化建议
- 提前预分配内存：使用reserve()方法提前分配足够的内存，减少扩容次数
vector<int> vec;vec.reserve(1000); // 提前分配1000个元素的空间
- 避免频繁插入/删除中间元素：vector不适合频繁在中间位置插入/删除元素，建议使用list或deque
- 注意迭代器失效：扩容后，原迭代器失效，需要重新获取
- 合理选择容器：根据实际需求选择合适的容器
📋 总结
- 底层实现：vector基于连续动态数组实现，支持O(1)随机访问
- 扩容机制：当size等于capacity时触发扩容，不同编译器采用不同扩容因子（1.5倍或2倍）
- 扩容开销：扩容是O(n)操作，会导致迭代器失效
- resize()：调整元素数量，会创建/销毁元素
- reserve()：预分配内存，不创建元素，用于优化性能
- 优化策略：提前预分配内存，避免频繁扩容，注意迭代器失效问题 理解vector的底层原理和扩容机制，有助于我们在实际开发中更高效、更安全地使用这个容器，避免常见的性能陷阱和错误。