数组

数组是连续存储的线性表，元素可通过下标在 O(1) 时间访问。学习数组时要区分物理容量和当前有效长度：容量决定可存放的上限，有效长度决定可读写的元素区间。

静态数组

const int MAXSIZE = 100;
int a[MAXSIZE];
int length = 0;  // 有效元素为 a[0..length-1]

原生数组大小在定义时确定，不能扩容；访问 a[i] 不检查边界，非法下标会产生未定义行为。遍历和按值顺序查找均为 O(n)。二维数组按行优先连续存储，matrix[i][j] 的偏移与行、列数有关。

插入与删除

在下标 index 插入，须满足 0 ≤ index ≤ length 且数组未满，并从后向前搬移元素；删除须满足 0 ≤ index < length，再从前向后覆盖空位。两者在中间操作均为 O(n)。

void insertAt(int index, int x) {
    if (index < 0 || index > length || length == MAXSIZE) return;
    for (int i = length; i > index; --i) a[i] = a[i - 1];
    a[index] = x;
    ++length;
}
void eraseAt(int index) {
    if (index < 0 || index >= length) return;
    for (int i = index; i + 1 < length; ++i) a[i] = a[i + 1];
    --length;
}

STL array

std::array 是固定长度数组的容器封装：长度为编译期常量，支持 size()、迭代器和 fill()，但没有改变元素数量的 push_back。operator[] 快速但不检查边界，at() 会检查边界。

#include <array>
array<int, 5> a = {1, 2, 3, 4, 5};
a.fill(0);
a.at(1) = 7;

动态数组 vector

std::vector 仍连续存储，支持 O(1) 下标访问；push_back 尾插为均摊 O(1)，中间 insert/erase 通常为 O(n)。size() 是元素数，capacity() 是已分配容量；提前 reserve() 可减少扩容搬迁。

#include <vector>
vector<int> v = {1, 2, 3};
v.push_back(4);
v.reserve(1000);     // 不改变 size
v.erase(v.begin()+1);

扩容和 erase 可能使迭代器、指针和引用失效；循环删除元素时使用 it = v.erase(it)。clear() 清空元素但通常不释放容量。