C++动态数组扩容自定义扩容策略实现-C++-PHP中文网

C++动态数组扩容自定义扩容策略实现

P粉602998670

发布： 2025-08-26 12:32:01

原创

436人浏览过

动态数组扩容通过调整容量平衡性能与内存，常见策略有倍增、线性及1.5倍增长，结合函数指针可灵活切换，提升特定场景下的效率表现。

c++动态数组扩容自定义扩容策略实现

在C++中，动态数组扩容是实现类似

std::vector

登录后复制

功能的核心机制。当现有容量不足以容纳新元素时，需要重新分配更大的内存空间，并将原有数据迁移过去。自定义扩容策略可以优化性能，适应不同场景下的内存和速度需求。

扩容的基本原理

动态数组通常包含三个核心指针或变量：

data：指向堆上分配的内存首地址
size：当前已存储的元素个数
capacity：当前可容纳的最大元素数量（无需扩容）

当插入元素时，若

size == capacity

登录后复制

，则触发扩容。扩容步骤如下：

根据策略计算新的容量
分配新内存块
将旧数据复制或移动到新内存
释放旧内存
更新
```
data
```
登录后复制
、
```
capacity
```
登录后复制

常见扩容策略对比

不同策略在内存使用和时间开销之间权衡：

立即学习“C++免费学习笔记（深入）”；

倍增策略（如×1.5或×2）：常见于STL容器，摊还插入时间O(1)，但可能浪费较多内存
线性增长（如+固定值）：内存友好，但频繁扩容导致性能下降
Fibonacci增长：折中方案，增长速度介于线性和指数之间

自定义策略实现示例

下面是一个支持自定义扩容策略的动态数组模板：

来画数字人直播

来画数字人自动化直播，无需请真人主播，即可实现24小时直播，无缝衔接各大直播平台。

查看详情

template<typename T>
class DynamicArray {
private:
    T* data;
    size_t size;
    size_t cap;
<pre class='brush:php;toolbar:false;'>// 扩容策略函数指针
size_t (*growth_strategy)(size_t);

void reallocate() {
    size_t new_cap = growth_strategy(cap);
    T* new_data = new T[new_cap];

    for (size_t i = 0; i < size; ++i) {
        new_data[i] = std::move(data[i]);
    }

    delete[] data;
    data = new_data;
    cap = new_cap;
}

登录后复制

public: explicit DynamicArray(size_t initial_cap = 10, size_t (*strategy)(size_t) = default_strategy) : data(new T[initial_cap]) , size(0) , cap(initial_cap) , growth_strategy(strategy) {}

~DynamicArray() {
    delete[] data;
}

void push_back(const T& value) {
    if (size == cap) reallocate();
    data[size++] = value;
}

void push_back(T&& value) {
    if (size == cap) reallocate();
    data[size++] = std::move(value);
}

T& operator[](size_t index) { return data[index]; }
const T& operator[](size_t index) const { return data[index]; }
size_t length() const { return size; }
size_t capacity() const { return cap; }

// 默认策略：容量翻倍
static size_t default_strategy(size_t current) {
    return current == 0 ? 1 : current * 2;
}

// 线性增长策略
static size_t linear_strategy(size_t current) {
    return current + 10;
}

// 1.5倍增长策略
static size_t multiplicative_strategy(size_t current) {
    return current == 0 ? 1 : current + (current >> 1); // current * 1.5
}

登录后复制

};

使用示例与策略选择

根据应用场景选择合适的策略：

int main() {
    // 使用默认翻倍策略
    DynamicArray<int> arr1(8);
<pre class='brush:php;toolbar:false;'>// 使用1.5倍增长，减少内存浪费
DynamicArray<int> arr2(8, DynamicArray<int>::multiplicative_strategy);

// 使用线性增长，适用于小数据量且内存敏感场景
DynamicArray<int> arr3(8, DynamicArray<int>::linear_strategy);

for (int i = 0; i < 100; ++i) {
    arr1.push_back(i);
}

return 0;

登录后复制

}

选择策略时考虑：