引言：为什么需要动态数组？

在编程中，数组是最基础也是最常用的数据结构之一。但传统的静态数组有一个致命缺陷：大小固定。一旦创建，就无法改变容量。这在很多实际场景中非常不方便。

动态数组（Dynamic Array）应运而生，它在静态数组的基础上增加了自动扩缩容的功能，让我们可以像使用普通数组一样使用它，而不用担心容量问题。

静态数组 vs 动态数组

静态数组的局限性

// 静态数组 - 大小固定
int arr[10];  // 只能存储10个元素
arr[10] = 11; // 错误！越界访问

静态数组的特点：

• 创建时就要确定大小
• 内存连续分配
• 不支持自动扩容
• 实际开发中很少直接使用

动态数组的优势

// 动态数组 - 自动扩容
vector<int> arr;  // 初始容量为0
for(int i = 0; i < 100; i++) {
    arr.push_back(i);  // 自动扩容，无需担心容量
}

动态数组的特点：

• 自动管理内存
• 支持动态扩容和缩容
• 提供丰富的API接口
• 实际开发中的首选

动态数组的核心原理

1. 底层实现：仍然是静态数组

动态数组的底层仍然是静态数组，只是在外层封装了智能的内存管理：

template<typename E>
class DynamicArray {
private:
    E* data;        // 底层静态数组
    int size;       // 当前元素数量
    int capacity;   // 数组总容量
    // ...
};

2. 自动扩缩容机制

扩容策略：

• 当 size == capacity 时，容量扩大为原来的2倍
• 时间复杂度：均摊O(1)

缩容策略：

• 当 size == capacity/4 时，容量缩小为原来的1/2
• 避免内存浪费

void resize(int newCapacity) {
    E* newData = new E[newCapacity];
    
    // 复制数据
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    
    delete[] data;   // 释放旧数组
    data = newData;  // 指向新数组
    capacity = newCapacity;
}

3. 时间复杂度分析

操作	时间复杂度	说明
随机访问	O(1)	数组的核心优势
尾部添加	O(1) 均摊	可能触发扩容
尾部删除		可能触发缩容
中间插入	O(n)	需要数据搬移
中间删除
按值查找		需要遍历数组

完整代码实现

下面我们手把手实现一个完整的动态数组：

#include <iostream>
#include <stdexcept>
#include <string>

template<typename E>
class DynamicArray {
private:
    E* data;        // 底层数组指针
    int size;       // 当前元素个数
    int capacity;   // 数组容量
    
    static const int INIT_CAP = 1;  // 默认初始容量

    // 调整容量
    void resize(int newCap) {
        E* temp = new E[newCap];
        
        // 复制数据
        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }
        
        delete[] data;  // 释放原数组
        data = temp;
        capacity = newCap;
        
        std::cout << "Resized to: " << capacity << std::endl;  // 调试信息
    }
    
    // 索引检查方法
    bool isElementIndex(int index) const {
        return index >= 0 && index < size;
    }
    
    bool isPositionIndex(int index) const {
        return index >= 0 && index <= size;
    }
    
    void checkElementIndex(int index) const {
        if (!isElementIndex(index)) {
            throw std::out_of_range("Index: " + std::to_string(index) + 
                                   ", Size: " + std::to_string(size));
        }
    }
    
    void checkPositionIndex(int index) const {
        if (!isPositionIndex(index)) {
            throw std::out_of_range("Index: " + std::to_string(index) + 
                                   ", Size: " + std::to_string(size));
        }
    }

public:
    // ========== 构造函数和析构函数 ==========
    
    // 默认构造函数
    DynamicArray() : data(new E[INIT_CAP]), size(0), capacity(INIT_CAP) {}
    
    // 指定初始容量的构造函数
    DynamicArray(int initCapacity) : data(new E[initCapacity]), size(0), capacity(initCapacity) {
        if (initCapacity <= 0) {
            throw std::invalid_argument("Capacity must be positive");
        }
    }
    
    // 拷贝构造函数
    DynamicArray(const DynamicArray& other) : data(new E[other.capacity]), size(other.size), capacity(other.capacity) {
        for (int i = 0; i < size; i++) {
            data[i] = other.data[i];
        }
    }
    
    // 赋值运算符
    DynamicArray& operator=(const DynamicArray& other) {
        if (this != &other) {
            delete[] data;
            data = new E[other.capacity];
            size = other.size;
            capacity = other.capacity;
            for (int i = 0; i < size; i++) {
                data[i] = other.data[i];
            }
        }
        return *this;
    }
    
    // 析构函数
    ~DynamicArray() {
        delete[] data;
    }

    // ========== 增操作 ==========
    
    // 尾部添加元素
    void addLast(E element) {
        // 检查容量，需要时扩容
        if (size == capacity) {
            resize(2 * capacity);
        }
        data[size] = element;
        size++;
    }
    
    // 指定位置插入元素
    void add(int index, E element) {
        checkPositionIndex(index);  // 检查插入位置合法性
        
        // 检查容量
        if (size == capacity) {
            resize(2 * capacity);
        }
        
        // 数据搬移：从后向前移动，为新元素腾出空间
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        
        // 插入新元素
        data[index] = element;
        size++;
    }
    
    // 头部插入元素
    void addFirst(E element) {
        add(0, element);
    }

    // ========== 删操作 ==========
    
    // 删除尾部元素
    E removeLast() {
        if (size == 0) {
            throw std::out_of_range("Cannot remove from empty array");
        }
        
        // 检查是否需要缩容
        if (size == capacity / 4 && capacity > INIT_CAP) {
            resize(capacity / 2);
        }
        
        E deletedVal = data[size - 1];
        data[size - 1] = E();  // 防止内存泄漏
        size--;
        
        return deletedVal;
    }
    
    // 删除指定位置元素
    E remove(int index) {
        checkElementIndex(index);  // 检查索引合法性
        
        // 检查是否需要缩容
        if (size == capacity / 4 && capacity > INIT_CAP) {
            resize(capacity / 2);
        }
        
        E deletedVal = data[index];
        
        // 数据搬移：从前向后移动，填补删除的空位
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        
        data[size - 1] = E();  // 清理最后一个位置
        size--;
        
        return deletedVal;
    }
    
    // 删除头部元素
    E removeFirst() {
        return remove(0);
    }

    // ========== 查操作 ==========
    
    // 获取指定位置元素
    E get(int index) const {
        checkElementIndex(index);
        return data[index];
    }
    
    // 重载[]运算符，支持类似原生数组的访问方式
    E& operator[](int index) {
        checkElementIndex(index);
        return data[index];
    }
    
    const E& operator[](int index) const {
        checkElementIndex(index);
        return data[index];
    }

    // ========== 改操作 ==========
    
    // 修改指定位置元素
    E set(int index, E element) {
        checkElementIndex(index);
        E oldVal = data[index];
        data[index] = element;
        return oldVal;
    }

    // ========== 工具方法 ==========
    
    int getSize() const { return size; }
    bool isEmpty() const { return size == 0; }
    int getCapacity() const { return capacity; }
    
    // 查找元素索引
    int indexOf(E element) const {
        for (int i = 0; i < size; i++) {
            if (data[i] == element) {
                return i;
            }
        }
        return -1;  // 未找到
    }
    
    // 判断是否包含元素
    bool contains(E element) const {
        return indexOf(element) != -1;
    }

    // 显示数组内容（调试用）
    void display() const {
        std::cout << "Size: " << size << ", Capacity: " << capacity << std::endl;
        std::cout << "Elements: [";
        for (int i = 0; i < size; i++) {
            std::cout << data[i];
            if (i < size - 1) std::cout << ", ";
        }
        std::cout << "]" << std::endl;
    }
};

关键设计要点详解

1. 为什么需要两种索引检查？

// 元素索引检查：用于访问已有元素 [0, size-1]
void checkElementIndex(int index) const;

// 位置索引检查：用于插入操作 [0, size]  
void checkPositionIndex(int index) const;

理解示例：

现有数组: [10, 20, 30, 40]
元素索引:  0   1   2   3   (只能访问这些位置)
位置索引: 0   1   2   3   4  (可以在这些位置插入新元素)

2. 内存泄漏防护

在删除元素时，必须将对应位置置为默认值：

data[size - 1] = E();  // 重要！

如果不这样做，对于包含指针的对象，这些指针可能一直保持有效，导致内存无法被回收。

3. 扩缩容策略的数学原理

为什么是2倍扩容和1/4缩容？

这种策略保证了操作的时间复杂度为均摊O(1)。简单分析：

• 插入n个元素的总操作次数：n次插入 + n次复制 ≈ 3n
• 均摊到每次插入：3n/n = 3 → O(1)

测试和使用示例

#include <iostream>

void testDynamicArray() {
    std::cout << "=== 动态数组测试 ===" << std::endl;
    
    // 创建动态数组，初始容量为3
    DynamicArray<int> arr(3);
    
    std::cout << "\n1. 添加元素测试：" << std::endl;
    for (int i = 1; i <= 5; i++) {
        arr.addLast(i);
        arr.display();
    }
    
    std::cout << "\n2. 插入元素测试：" << std::endl;
    arr.add(1, 99);      // 在索引1插入99
    arr.addFirst(-1);    // 头部插入-1
    arr.display();
    
    std::cout << "\n3. 删除元素测试：" << std::endl;
    std::cout << "删除索引3: " << arr.remove(3) << std::endl;
    std::cout << "删除头部: " << arr.removeFirst() << std::endl;
    std::cout << "删除尾部: " << arr.removeLast() << std::endl;
    arr.display();
    
    std::cout << "\n4. 访问和修改测试：" << std::endl;
    std::cout << "arr[0] = " << arr[0] << std::endl;
    arr[0] = 100;  // 使用[]运算符修改
    std::cout << "修改后 arr[0] = " << arr[0] << std::endl;
    
    std::cout << "\n5. 查找测试：" << std::endl;
    int index = arr.indexOf(99);
    if (index != -1) {
        std::cout << "元素99的索引: " << index << std::endl;
    }
    
    std::cout << "\n6. 拷贝测试：" << std::endl;
    DynamicArray<int> arrCopy = arr;  // 调用拷贝构造函数
    std::cout << "原数组: ";
    arr.display();
    std::cout << "拷贝数组: ";
    arrCopy.display();
}

int main() {
    try {
        testDynamicArray();
    } catch (const std::exception& e) {
        std::cerr << "错误: " << e.what() << std::endl;
    }
    return 0;
}

与标准库vector的对比

我们实现的DynamicArray与C++标准库的std::vector功能相似，但std::vector更加完善：

我们的实现包含：

• 基本增删查改操作
• 自动扩缩容
• 基本的异常安全

std::vector的额外特性：

• 迭代器支持
• 更高效的内存操作（如std::move）
• 异常安全保证
• 算法库集成
• 更完善的类型特性

实际应用场景

1. 数据收集：不确定数据量大小的场景
2. 算法实现：栈、队列等数据结构的底层存储
3. 缓冲区管理：需要动态调整大小的缓冲区
4. 游戏开发：动态对象管理

总结

动态数组是计算机科学中最重要的数据结构之一，它：

• 底层基于静态数组，保持了随机访问的O(1)时间复杂度
• 通过自动扩缩容，解决了固定容量的限制
• 均摊时间复杂度优秀，大部分操作都是O(1)
• 实现相对简单，但需要考虑很多边界情况

理解动态数组的实现原理，不仅有助于我们更好地使用标准库中的vector，也为学习更复杂的数据结构（如哈希表、优先队列等）打下了坚实的基础。

记住：数据结构的核心价值在于在特定场景下做出合适的时空复杂度权衡。动态数组在需要频繁随机访问和动态大小的场景中，是一个极佳的选择。