动态数组与STL vector：像橡皮筋一样伸缩自如的储物柜

什么是动态数组？它解决了什么问题？

在编程中，我们经常需要存储一系列数据。最原始的方式是用静态数组，比如 int a[100]; 表示一个固定大小100的柜子。但问题是：你事先不知道要存多少东西。如果只有10个数据，却申请了100个位置，浪费了90个格子；如果忽然来了200个数据，柜子又装不下了。

动态数组（Dynamic Array）就像一根橡皮筋或伸缩储物柜：一开始只有几个格子，当东西放满时，柜子会自动变长，多出一排格子。你根本不用操心“总共要放多少东西”，只管往里塞，它自己会变大。

在C++中，标准库提供了 vector 这个类来实现动态数组；在Python中，list 本质也是动态数组（虽然名字叫列表，但底层是数组）。很多语言都有类似结构，比如Java的 ArrayList、C#的 List<T>。

动态数组的内部原理：预分配 + 翻倍扩容

动态数组的核心思想是先预留空间，不够了就翻倍。它内部维护三个重要属性：

• size：当前已经存放了多少个元素（就像柜子里实际放了多少东西）。
• capacity：当前柜子的总格子数（包括空着的格子）。
• data：指向底层数组的指针（柜子的地址）。

当你用 push_back（C++）或 append（Python）添加一个元素时：

1. 如果 size < capacity：直接放到下一个空位，size 加1。就像柜子还有空位，直接把新东西放进去。
2. 如果 size == capacity：说明柜子满了，需要扩容。具体步骤：
   • 申请一块新的、更大的内存（通常是旧容量的两倍，比如从4变成8）。
   • 把旧柜子里所有东西搬到新柜子里（复制所有元素）。
   • 释放旧柜子（归还旧内存）。
   • 然后才把新元素放进新柜子的空位。
   • 最后更新 capacity 和 size。

举个例子：假设初始容量为2，依次添加5个元素：

• 添加第1个：size=1，容量=2，直接放。
• 添加第2个：size=2，容量=2，刚好满，直接放。
• 添加第3个：size=2 == 容量=2，触发扩容：新容量=4，复制2个旧元素，释放旧内存，再放入第3个。现在size=3，容量=4。
• 添加第4个：直接放，size=4，容量=4。
• 添加第5个：又满，扩容到容量=8，复制4个元素，再放第5个。

为什么翻倍是好策略？

每次扩容复制整个数组是 O(n) 操作，但扩容次数很少（比如添加n次，大约需要扩容 log₂n 次）。总的复制代价大约是 O(2n)（因为每次复制的是当前已有元素数，总和成倍数增长）。平均下来，每次插入的时间是 均摊 O(1) —— 绝大多数时候直接放，偶尔大搬家，但整体效率依然很高。

生活中的类比：教室里的座位

想象一下你在组织一次活动，不知道会有多少人来。你一开始只摆了10把椅子（初始容量）。每来一个人，就找个空位坐下。当10把椅子坐满时，你马上从隔壁借来10把新椅子，把旧椅子上的同学挪过去，再放新的椅子，现在总共20把椅子。这样反复，直到所有人都坐下。这种“挪动”虽然麻烦，但总共只挪了很少几次。

常见操作（C++ vector 和 Python list）

C++ 特有操作说明

• reserve(n)：只预分配容量，不改变size。例如提前知道要存100个，调用 v.reserve(100) 可以避免多次扩容。
• resize(n)：改变size，如果n大于当前size，会用默认值填充；如果小于则截断。
• at(i)：带边界检查的下标访问，越界会抛出异常，比 v[i] 更安全但略慢。

新手最容易犯的错误

错误1：下标越界

vector<int> v = {1, 2, 3};
cout << v[5];  // 没有检查边界，运行时可能崩溃或访问到垃圾值

正确做法：要么用 v.at(5) 自动检查，要么先判断 if (i < v.size())。

错误2：在循环中插入/删除导致迭代器失效

vector<int> v = {1,2,3,4,5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it);   // 删除后it失效，继续++会导致未定义行为
    }
}

正确做法：用 erase 返回下一个迭代器，或者用 remove_if 配合 erase。

错误3：混淆 size 和 capacity

vector<int> v;
v.reserve(10);       // 容量10，size=0
cout << v.size();    // 输出0
v[0] = 5;            // 错误！size还是0，不能用下标访问

reserve 只分配内存，不创建对象。必须用 push_back 或 resize 才能访问。

错误4：在循环中同时遍历和插入

for (int i = 0; i < v.size(); i++) {  // 插入后size变化，循环次数不正确
    if (条件) {
        v.push_back(新值);
    }
}

正确做法：可以用一个临时数组收集要插入的值，最后统一插入；或者用索引从后往前遍历。

完整可运行示例：学生成绩管理系统

下面用C++和Python分别写一个完整例子：读取多个学生成绩，然后显示所有成绩和平均分。

C++ 版本

#include <iostream>
#include <vector>   // 使用vector必须包含
using namespace std;

int main() {
    // 创建一个动态数组保存学生成绩
    vector<int> scores;   // 空vector，存放int类型成绩

    // 模拟输入：先手工添加几个成绩
    scores.push_back(85);   // 添加85分
    scores.push_back(92);
    scores.push_back(78);
    scores.push_back(96);

    cout << "共有 " << scores.size() << " 个成绩" << endl;
    cout << "当前容量: " << scores.capacity() << endl;

    // 遍历所有成绩
    cout << "成绩列表: ";
    for (int i = 0; i < scores.size(); i++) {
        cout << scores[i] << " ";
    }
    cout << endl;

    // 计算平均分
    int sum = 0;
    for (int x : scores) {   // 范围for循环，更简洁
        sum += x;
    }
    double average = (double)sum / scores.size();
    cout << "平均分: " << average << endl;

    // 在末尾增加一个新成绩
    scores.push_back(88);
    cout << "添加新成绩后，大小: " << scores.size() << endl;

    // 删除最后一个成绩（模拟去掉最低分？）
    scores.pop_back();   // 删除88
    cout << "删除最后一个后，大小: " << scores.size() << endl;

    // 清空所有成绩
    scores.clear();
    cout << "清空后大小: " << scores.size() << ", 容量: " << scores.capacity() << endl;
    // 注意：clear不释放容量，但可以通过 shrink_to_fit 回收

    return 0;
}

Python 版本

# 创建一个动态数组保存学生成绩
scores = []   # 空列表

# 添加成绩
scores.append(85)
scores.append(92)
scores.append(78)
scores.append(96)

print(f"共有 {len(scores)} 个成绩")

# 遍历
print("成绩列表:", end=" ")
for x in scores:
    print(x, end=" ")
print()

# 计算平均分
average = sum(scores) / len(scores)
print(f"平均分: {average}")

# 在末尾增加
scores.append(88)
print(f"添加后大小: {len(scores)}")

# 删除最后一个
scores.pop()
print(f"删除后大小: {len(scores)}")

# 清空
scores.clear()
print(f"清空后大小: {len(scores)}")

动态数组 vs 静态数组 vs 链表

为了帮你更清楚地选择用哪种结构，下面这张表总结了三者的特点：

一句话选择指南：

• 大部分情况用动态数组（vector / list）就行。
• 如果需要在任意位置频繁插入删除，而且不常随机访问，用链表。
• 如果大小完全确定且不变，用静态数组可以省内存。

底层原理再深入：扩容因子

C++ 的 vector 不同编译器采用的扩容因子不同。Visual Studio 通常用 1.5倍，g++ 用 2倍。2倍扩容的均摊代价更小，但可能浪费更多内存（最坏情况有一半空间空闲）。1.5倍则更节省内存但扩容次数略多。Python 的 list 也是约1.125倍增长（早期版本是4倍、后来调整），更注重内存效率。

相关指引

学完动态数组，你可以继续探索：

• 双向链表（list）：std::list 在C++中是一个双向链表，中间插入删除很快，但没有随机访问。
• 循环链表：把链表的头尾相连，适合循环队列等场景。
• 栈和队列：动态数组和链表都可以用来实现栈和队列。
• 迭代器失效：当 vector 扩容或插入删除时，原来保存的迭代器、指针、引用可能会失效，这是C++中的一个难点。
• std::array：C++11 引入的固定大小数组，提供容器接口但大小固定，是静态数组的包装。

动态数组是编程中最常用的数据结构之一，掌握它的原理和用法，就能解决绝大多数数据存储问题。