数组：你的第一个数据结构

一排格子，并肩排开

[[dsa-array|数组]]把它的各项存放在连续内存里——一整块连绵的内存，每一项占一个大小相等的格子，格子之间没有空隙。想象沿着墙螺接在一起的一排一模一样的信箱，从 0 开始编号。因为每个箱子大小相同、又紧挨着彼此，第 *i* 个箱子的地址就是一道简单的算术：*起始地址 + i ×（一个箱子的大小）*。计算机不去搜寻第 5 个箱子；它直接*算出*它在哪儿，一步走到。

index:     0     1     2     3     4
         +-----+-----+-----+-----+-----+
array:   |  17 |  42 |   8 |  99 |   5 |
         +-----+-----+-----+-----+-----+
          base  +1    +2    +3    +4   slots  (each the same size)

  v[3]?  address = base + 3 * slot_size  ->  go straight there  (O(1))

下标从 0 开始。因为格子大小相等又相邻，任意下标的地址都是一次计算——所以读取 v[3] 是 O(1)，无论数组多大。

这就是数组的超能力：O(1) 的随机访问。无论数组装 10 项还是一千万项，取出某个已知下标处的项，所花的功都是同样微小而固定的——它的[[time-complexity|时间复杂度]]不随大小增长。正是这一条性质，让数组坐落在你将学到的几乎所有其他数据结构的底层。

代价：往中间插入是 O(n)

正是那让读取瞬时的东西——没有空隙——让插入变得痛苦。假设你想把一个新值塞进中间。那里没有空格；下一项正紧紧顶着它。所以为了腾地方，从那一点到末尾的每一项都得往后挪一格。最坏情况下（插在最前面）你要挪动*全部 n* 项。从中间删除则是镜像：空洞之后的一切都往前挪，把缝隙合上。两者都是 O(n)——工作量随数组大小增长。

insert 7 at index 2:

before:  [ 17 | 42 |  8 | 99 |  5 |    ]
                       ^ everyone from here rightward must move
step:    [ 17 | 42 |    |  8 | 99 |  5 ]   shift 8,99,5 right
after:   [ 17 | 42 |  7 |  8 | 99 |  5 ]   now drop 7 into the gap

  -> up to n items shifted  ->  O(n)

要在中间插入，后面的每一项都要顺移一格。插在最前面要挪动全部 n 项——这就是中间/开头的插入与删除是 O(n) 的原因。

固定数组 vs. 可增长的 std::vector

一个普通的 C++ 数组有固定的大小，你必须事先定好：`int a[5];` 永远恰好是五格。要是来了第六个值，就没地方放了。当你事先知道数量时，这没问题，可真实的程序常常并不知道。解决办法是[[dynamic-array|动态数组]]：一个填满时能*增长*的数组。在 C++ 里就是 `std::vector`，它是你会不断伸手去拿的主力。

#include <vector>

int a[5] = {17, 42, 8, 99, 5};   // fixed: exactly 5 slots, no growing
int x = a[3];                     // O(1) read -> 99

std::vector<int> v = {17, 42, 8}; // dynamic: starts at 3, can grow
v.push_back(99);                  // append at the end (usually cheap)
v.push_back(5);                   // now {17, 42, 8, 99, 5}
int y = v[3];                     // O(1) read, same as the plain array

固定数组不能增长；std::vector 能。两者都提供 O(1) 的下标访问——vector 保住了数组的超能力，同时让你随意 push_back。

它是怎么增长的？当一个 vector 填满时，它会悄悄抓一块更大的内存（通常是原来的两倍），把各项复制过去。这次复制听上去昂贵——偶尔也确实如此——但因为大小每次都*翻倍*，那些昂贵的时刻既稀少又被摊得很薄。在许许多多次 `push_back` 上平均下来，追加表现得仿佛就是 O(1)。你现在还不需要完整的账目；只需相信 `std::vector` 给了你一个可增长的数组，又没放弃瞬时的 O(1) 读取。