在C++标准库中，std::vector是常用的动态数组容器，其底层通过动态申请堆内存实现数组大小的自动增长，开发者也可以手动实现类似的动态数组结构，理解其实现原理对优化程序性能很有帮助。
手动实现动态数组的基础思路
动态数组的核心是需要维护三个关键属性：指向堆内存的指针、当前已存储的元素数量、当前申请的内存可容纳的最大元素数量。当需要添加新元素且当前元素数量达到最大容量时，就需要执行扩容操作。
基础的实现结构如下：
#include <iostream>
#include <cstring>
template <typename T>
class DynamicArray {
private:
T* data; // 指向堆内存的指针
int size; // 当前已存储的元素数量
int capacity; // 当前内存可容纳的最大元素数量
public:
// 构造函数，初始容量设为10
DynamicArray() : data(new T[10]), size(0), capacity(10) {}
// 析构函数，释放堆内存
~DynamicArray() {
delete[] data;
}
// 获取当前元素数量
int getSize() const {
return size;
}
// 获取当前容量
int getCapacity() const {
return capacity;
}
};
常见的动态扩容策略
1. 固定步长扩容
固定步长扩容是指每次扩容时，固定增加一定数量的容量，比如每次增加10个元素的位置。这种策略实现简单，但是当数据量较大时，频繁的扩容操作会带来较多的内存拷贝开销。
固定步长扩容的实现示例：
template <typename T>
void DynamicArray<T>::pushBack(const T& val) {
// 如果当前元素数量达到容量上限，执行扩容
if (size == capacity) {
// 固定步长扩容，每次增加10个容量
int newCapacity = capacity + 10;
T* newData = new T[newCapacity];
// 拷贝原有数据到新内存
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
// 释放旧内存
delete[] data;
data = newData;
capacity = newCapacity;
}
// 添加新元素
data[size++] = val;
}
2. 倍增扩容
倍增扩容是指每次扩容时，将容量扩大为原来的若干倍，通常是2倍或者1.5倍。这种策略可以减少扩容的次数，从均摊时间复杂度的角度来看，添加元素的均摊时间复杂度可以达到O(1)。
倍增扩容的实现示例：
template <typename T>
void DynamicArray<T>::pushBack(const T& val) {
if (size == capacity) {
// 倍增扩容，容量扩大为原来的2倍
int newCapacity = capacity * 2;
T* newData = new T[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
delete[] data;
data = newData;
capacity = newCapacity;
}
data[size++] = val;
}
不同扩容策略的性能考量
我们可以从时间复杂度和内存利用率两个维度对比两种扩容策略：
| 扩容策略 | 均摊时间复杂度 | 内存利用率 | 适用场景 |
|---|---|---|---|
| 固定步长扩容 | O(k)，k为步长 | 较高，扩容幅度小 | 数据量增长平缓、内存资源紧张的场景 |
| 倍增扩容 | O(1) | 较低，可能存在较多预留空间 | 数据量增长不确定、对操作性能要求高的场景 |
需要注意的是，倍增扩容的倍数选择也有讲究，2倍扩容可能会导致之前申请的内存无法被后续复用，而1.5倍扩容在一定程度上可以提高内存的复用率，很多标准库的实现会选择1.5倍作为扩容因子。
标准库vector的扩容实现参考
不同编译器的std::vector实现略有差异，比如GCC的libstdc++中vector的扩容因子是2，而LLVM的libc++中扩容因子是1.5。开发者在使用vector时，如果提前知道需要存储的元素数量，可以调用reserve方法预先申请足够的容量，减少扩容带来的性能开销。
预先申请容量的示例：
#include <vector>
int main() {
std::vector<int> arr;
// 预先申请100个元素的容量，避免后续多次扩容
arr.reserve(100);
for (int i = 0; i < 100; i++) {
arr.push_back(i);
}
return 0;
}
在实际开发中，除非有特殊需求，否则优先使用标准库的std::vector而不是手动实现动态数组，标准库的实现经过了充分的测试和优化，稳定性和性能都更有保障。如果需要自定义动态数组，也需要根据实际的业务场景选择合适的扩容策略，平衡性能和内存占用。