动态数组的扩容收缩机制

动态数组是一种可变大小的数据结构，它可以在运行时根据需要调整其容量。这种特性在实际应用中非常有用，尤其是在处理数据量不确定或变化频繁的情况下。本文将探讨动态数组如何进行扩容和收缩操作，以确保高效地管理内存资源。

扩容机制

当一个动态数组需要添加元素而当前存储空间不足以容纳新元素时，就需要执行扩容操作。以下是几种常见的扩容方法：

1. 线性倍增法

这是最常用的方法之一。当数组达到其容量上限时，可以将其大小调整为原大小的常数倍（例如2倍），以增加额外的空间来存储新的数据。

void resize(vector<int>& arr, int newSize) {
    if (newSize <= capacity_) {
        return; // 不需要扩容
    }
    int* newElements = new int[newSize];
    for (int i = 0; i < size_; ++i) {
        newElements[i] = arr[i];
    }
    delete[] arr;
    arr = newElements;
    capacity_ = newSize; // 更新容量
}

2. 指数倍增法

这种方法可以减少频繁扩容带来的性能开销，但它需要额外的空间来存储数组的当前大小和下一次预计的大小。

void resize(vector<int>& arr, int newSize) {
    if (newSize <= capacity_) {
        return; // 不需要扩容
    }
    if (capacity_ == 0 || newSize / capacity_ > 2) {
        capacity_ = newSize * 2;
    } else {
        capacity_ *= 2; // 增加2倍的容量
    }
    int* newElements = new int[capacity_];
    for (int i = 0; i < size_; ++i) {
        newElements[i] = arr[i];
    }
    delete[] arr;
    arr = newElements;
}

3. 定制化扩容策略

对于某些特定的应用场景，可能需要定制化的扩容策略。例如，可以根据数据分布来决定何时进行扩容。

void resize(vector<int>& arr, int newSize) {
    if (newSize <= capacity_) {
        return; // 不需要扩容
    }
    // 根据具体需求自定义扩容逻辑
    int newCapacity = calculateOptimalCapacity(newSize);
    int* newElements = new int[newCapacity];
    for (int i = 0; i < size_; ++i) {
        newElements[i] = arr[i];
    }
    delete[] arr;
    arr = newElements;
}

收缩机制

动态数组在某些情况下也可能出现空间浪费的情况，此时可以考虑执行收缩操作以释放多余的空间。常见的收缩方法包括：

1. 带有阈值的收缩

如果当前大小远小于最大容量（例如小于50%），则可以选择适当减少容量。

void shrink(vector<int>& arr) {
    if (size_ < capacity_ / 2) { // 当前大小低于一半时收缩
        int newCapacity = size_;
        int* newElements = new int[newCapacity];
        for (int i = 0; i < size_; ++i) {
            newElements[i] = arr[i];
        }
        delete[] arr;
        arr = newElements;
        capacity_ = newCapacity; // 更新容量
    }
}

2. 动态调整阈值策略

可以根据历史数据或统计信息动态地调整收缩阈值，以提高效率。

void shrink(vector<int>& arr) {
    if (size_ < getDynamicThreshold(capacity_)) { // 根据历史数据设置阈值
        int newCapacity = size_;
        int* newElements = new int[newCapacity];
        for (int i = 0; i < size_; ++i) {
            newElements[i] = arr[i];
        }
        delete[] arr;
        arr = newElements;
        capacity_ = newCapacity; // 更新容量
    }
}

3. 混合策略

可以结合上述两种方法，当数组大小满足一定条件时才进行调整。

void shrink(vector<int>& arr) {
    if (size_ < min(capacity_ / 2, getDynamicThreshold(capacity_))) { // 结合使用阈值和比例限制
        int newCapacity = size_;
        int* newElements = new int[newCapacity];
        for (int i = 0; i < size_; ++i) {
            newElements[i] = arr[i];
        }
        delete[] arr;
        arr = newElements;
        capacity_ = newCapacity; // 更新容量
    }
}

总结

动态数组的扩容收缩机制是保证高效内存管理的重要手段。通过合理设计和调整这些策略，可以在保证性能的同时避免不必要的资源浪费。不同的应用场景可能需要选择不同的方法或组合多种策略来实现最优效果。