正常
动态数组：一块会搬家的内存
兄弟们，咱们马上就要开始标准库的学习了，在您点开了咱们的数据结构库支持之前，我相信，您应该不会对 int a[100] 这个说辞感到陌生了。（哈？陌生，看看C语言的教程吧！），咱们也稍微使用了一下 std::vector<int>。好像都是数组，对吧。差别在哪？前者的格子在咱们写下这行代码的那一刻就定死了，编译进可执行文件后一个字节都多不出来，这我相信大家都不会有意见；但是很奇怪，后者却可以连塞一百万个数不炸。多出来的内存从哪来？
从堆上借的。
是的，从堆上借的。而且借的从来不是同一块——装满了就换一块更大的，把所有元素整体搬过去。std::vector 的全部秘密就这一句话。这一篇咱们把它摊开：内存住在哪、谁在计数、搬家怎么搬、搬一次多贵、搬完之后哪些东西会悄悄失效。把这些立住，再去读实现层的深讲、去碰链表和哈希表，脚下都是地基。
静态数组为什么在业务场景非常多用？
笔者想了想，其实有三点：长度定死、栈太小、加不了
您要是做后端开发，来了数据登记，总不可能说：就只有 10 个用户在这一秒提交了表单，肯定是不定长的，对吧！有时候一个都没有，有时候几百个。
如果是嵌入式来的朋友，我这样说：写代码的时候，咱们经常不知道运行时会来多少数据——传感器一秒发多少帧、日志攒多少行、用户输多少个数，全是运行时的事，编译期定长度等于闭眼押注。
归根结底，问题还是出在 int a[100] 这种写法上：咱们写下方这行代码时，长度就成了类型的一部分，编译期就得给定。想改，没门兄弟们！
第二是空间。这样声明的数组默认住在栈上，而栈是很小的：Windows 默认 1 MiB，Linux 常见 8 MiB。咱们真跑一个（MSVC x64）：
C++
#include <cstdio>
int main() {
int big[2 * 1024 * 1024]; // 2 MiB，超出默认 1 MiB 的栈
big[0] = 41;
std::printf("big[0] = %d\n", big[0]);
return 0;
}一行输出都没有，进程直接死在起跑线上。
text
EXIT_CODE:-1073741571嗯，这个退出码我是在 Windows 上跑的（笔者上班的时候摸鱼只有 Windows 能用）：这个数就是 Windows 的 0xC00000FD，栈溢出状态码。Linux 下换汤不换药，栈超限同样崩，只是死法换成段错误。栈是给局部变量和函数调用准备的快车道，容量小，由操作系统在建线程时一次性划拨，想改要去链接器选项或线程属性里专门开口子；拿它装运行时才知道大小的数据，是用错了房间。
笔者真的见过有人跟我刚，说我打OI这样写的，直到看到他的样板代码，我直接说——大哥，放在 bss / data 段跟放在栈上不是一回事情！如果您是OJ选手，开大数组记得要么static修饰，要不就丢全局去，我建议丢全局，因为不用打static关键字。
第三，就算长度蒙对了，咱们中途想再多装一个，也没有余地。数组在内存里是连成一排的格子，后面紧挨着别人的地盘，想加长得连别人的地一起占，不现实。
数据住堆上，手里攥一个指针
三个滔天门槛指向了同一个解法：数据搬到堆上。堆是一大片按需申请的内存，new 多大都能谈（物理内存允许的话），什么时候还、还多少也归咱们管。栈上只留一个小小的句柄：
C++
int* data = new int[8]; // 堆上分配 8 个 int
data[0] = 41; // 用法跟数组一模一样
delete[] data; // 用完必须释放用法上咱们看不出 data[0] 和 a[0] 有区别，下标访问走的是同一套地址算术。区别全在背后：a 的格子编译时就分好、函数返回自动回收；data 的格子运行时借、必须手动还，忘了还就是内存泄漏。
不过这个裸写法马上暴露两个新问题。头一个：借了 8 格，第 9 个数据来了怎么办？再借一块更大的、把旧元素搬过去、把旧内存还掉，这个动作咱们下一节专门拆。第二个更隐蔽：函数中途 return 或者抛了异常，delete[] 就被跳过了，泄漏照旧。裸指针管资源，出错的路径太多。咱们先解决"怎么装得下"，封装和自动回收的事，结尾交给 RAII。
两个数字分清楚：装了几个，最多装几个
咱们把裸指针和它的计数包在一起，动态数组的雏形就出来了：
C++
struct IntVec {
int* data; // 堆上那块连续内存的起点
size_t size; // 装了几个（前 size 格是有效元素）
size_t cap; // 最多装几个（整块内存的格数）
};size 和 cap 是两码事，这是咱们理解动态数组要建立的第一个直觉：size 说现在有几个活元素，cap 说这块内存一共借了几格。中间空着的那截不还回去，留给下一次 push_back 直接用；立刻还掉、下次再借，分配器一来一回的开销比留着高。
有了这两个数，咱们往尾部加元素就分成两种情况：
C++
void push_back(IntVec& v, int x) {
if (v.size < v.cap) {
v.data[v.size] = x; // 还有空位：写一格，计数加一
v.size += 1;
return;
}
grow(v); // 容量满：扩容，下一节的事
v.data[v.size] = x;
v.size += 1;
}余量充足时，push_back 干的活就是写一格、size 加一，这就是它便宜的全部原因。std::vector 的本体也胖不到哪去，咱们真跑一下：
text
sizeof(std::vector<int>) = 24 bytes24 字节，64 位机上正好三个指针的宽度。肉全在堆上，对象自己瘦得只剩计数。这三个指针具体怎么摆（起点、尾后、仓底），怎么由它们推出 size() 和 capacity()，本卷 vector 深入 一篇有完整推导，咱们这里记住结论就够。
满了就搬家：换一块更大的内存
size 追上 cap 的那一刻，就是搬家的时刻。咱们要做的就三步：借一块更大的新内存，把旧元素搬过去，把旧内存还掉。
C++
void grow(IntVec& v) {
size_t ncap = v.cap == 0 ? 1 : v.cap * 2; // 新容量翻倍
int* nd = new int[ncap]; // 申请更大的新缓冲
for (size_t i = 0; i < v.size; ++i) {
nd[i] = v.data[i]; // 旧元素逐个拷贝过去
}
delete[] v.data; // 释放旧缓冲
v.data = nd;
v.cap = ncap;
}代码朴素，但有两个细节值得咱们盯住。新家的大小是 cap * 2 而不是 cap + 1，这个倍数是整个设计的灵魂，下一节拿计时数据说话。搬迁循环写的是逐元素赋值；对 int 这种平凡类型，标准库实际走的是整块拷贝（memmove 一族）；元素换成复杂对象，搬迁还牵扯构造与析构怎么配对，那是另一档讲究，vol8 的 Vector，扩容与搬迁 专门拆它。
咱们让 std::vector 自己演示一遍搬家。连塞 40 个数，容量一变就打一行（MSVC x64 真跑）：
text
born : size=0 capacity=0 data=0000000000000000
push #1 : size=1 capacity=1 data=0000016D1A7AF410
push #2 : size=2 capacity=2 data=0000016D1A7AF430
push #3 : size=3 capacity=3 data=0000016D1A7B6C90
push #4 : size=4 capacity=4 data=0000016D1A7B6B10
push #5 : size=5 capacity=6 data=0000016D1A7B6DB0
push #7 : size=7 capacity=9 data=0000016D1A7B7380
push #10 : size=10 capacity=13 data=0000016D1A7A5B60
push #14 : size=14 capacity=19 data=0000016D1A7AC890
push #20 : size=20 capacity=28 data=0000016D1A7AF410
push #29 : size=29 capacity=42 data=0000016D1A7AF490咱们把两列一起读。容量列：1, 2, 3, 4, 6, 9, 13, 19, 28, 42，每次约乘 1.5，这是 MSVC STL 的策略；libstdc++ 和 libc++ 乘 2，序列是 0, 1, 2, 4, 8, 16, 32（对照见 vector 深入）。倍数标准没规定，各家自己定，但都严格大于 1——为什么，下一节见分晓。
咱们再看地址列：容量一变，data 就换。每次扩容都是整体搬家，旧缓冲整块作废。还有个耐人寻味的细节：push #20 拿到的地址 ...AF410，跟 push #1 一模一样。
欸！这还真不是巧合——1.5 倍策略下，前面退掉的旧块大小正好够后面的扩容复用，分配器把刚还回来的房子又租给了咱们。为什么 1.5 有这个性质而 2 没有，vector 深入 里有一段漂亮的推导，这里咱们记住现象就够。
这一幕您也可以亲手复现，咱们把演示放到了在线编译器：
Compiler Explorer
扩容现场：容量序列与缓冲地址
您在线跑一遍：GCC 的 libstdc++ 是翻倍策略（1, 2, 4, 8, …），跟文章里 MSVC 的 1.5 倍序列不一样，两家策略的差别本身就是重点；再看 data 那一列，每次扩容地址都在换。
翻倍，还是加一：搬家的价钱差三个数量级
回到 grow 里那个倍数。直觉上似乎 cap + 1 更省内存：要几个借几个，一格不多占。咱们把两种策略各自塞 20 万个数，计时真跑（MSVC /O2，各三轮）：
text
appending 200000 ints, 3 runs each (times in microseconds):
run 1: +1 growth = 2016464 us x2 growth = 676 us
run 2: +1 growth = 1868235 us x2 growth = 662 us
run 3: +1 growth = 1869491 us x2 growth = 590 us加一策略约 1.9 秒，翻倍策略不到 1 毫秒，差三个数量级。推导不复杂，咱们先算加一策略：第 N 个元素进来前要搬走全部 N-1 个旧元素，总共搬 0+1+2+…+(N-1) ≈ N²/2 次，N 取 20 万就是两千亿次拷贝；翻倍策略只在容量 1, 2, 4, 8, … 这些点上搬家，每次的搬运量加起来 1+2+4+…+N/2 < N，20 万元素总共搬不到 40 万次。平方级对线性级，数据量一大就是秒级对微秒级。
所以标准给 push_back 的复杂度承诺写的是摊还常数（amortized constant）。摊还两个字是关键：单个 push_back 触发搬家时，实打实是 O(n)。直觉的讲法是咱们把偶尔一次贵搬家摊到之前一串便宜的写入头上，平均每次仍是常数。上面那张图画的正是这个形态：绝大多数 push_back 是高度 1 的矮柱，容量边界上偶尔一根高柱，而高柱的间隔一次比一次远，平均高度被稀释回常数。
咱们提前知道要装多少的话，reserve(n) 能一次借够、整段免掉搬家，热路径上的毛刺也就不存在了。shrink_to_fit、resize 这些跟容量打交道的接口，细节都在 vector 深入 那篇，本篇不铺开。
中间插一个：后半段集体挪座
到这里咱们手里这个动态数组看着处处便宜：下标访问一步到位（基地址加偏移乘格子宽度，纯算术），尾部追加摊还常数。代价藏在中间。往头部插一个数试试（真跑）：
text
before insert at front: 0 1 2 3 4 5 6 7
after insert at front: 99 0 1 2 3 4 5 6 78 个老元素，每个都往后挪了一格。这是连续存储定下的约束：格子必须连成排，第 0 格要腾给新元素，后面 8 个只能依次右移；删除同理，中间挖走一个，后面全部左移补洞。插的位置越靠前，挪得越多，平均一次中间插入或删除是 O(n) 次元素移动。尾插便宜、头插贵，这是"连续"的一体两面：它给了咱们 O(1) 随机访问和漂亮的缓存局部性，也定死了中间操作的搬运义务。
那有没有插中间谁都不用挪的结构？有。代价是咱们找第 i 个元素不能一步命中，得从头顺着问过去。那就是链表，本系列的下一篇。
搬完家，旧地址全作废
最后一件事故，也是新手踩得最狠的坑。咱们看代码：
C++
std::vector<int> v;
v.reserve(2);
v.push_back(41);
v.push_back(1);
int* p = &v[0]; // 缓存一个指针
v.push_back(99); // 容量已满，触发扩容
*p = 100; // 往旧地址写咱们看 p：它指向旧缓冲的第一格。搬家发生时旧缓冲已经被 delete，p 从此指向一块已归还的内存。*p = 100 这行是未定义行为：可能崩，可能看起来没事，也可能悄悄把 100 写进分配器已经转租给别人的格子，污染一个毫无关系的对象。三种结局标准一个都不保证，这正是 UB 讨厌的地方：它最喜欢在测试时装没事，上线后搞破坏。
咱们用 AddressSanitizer 把这一幕逮个正着（MSVC，/fsanitize=address）：
text
==18800==ERROR: AddressSanitizer: heap-use-after-free on address 0x123562da0010
WRITE of size 4 at 0x123562da0010 thread T0WRITE of size 4，正是一个 int 的写入宽度，地址就是旧缓冲那格。没有 ASan 的话，这个程序在真机上大概率"正常跑完"，错误沉在水底。引用和迭代器也一样。不管咱们手里拿的是 &v[0] 这样的指针、v.front() 返回的引用，还是循环里正走着的迭代器，触发搬家的那次操作一过，手里这些全部作废。
哪种操作让什么失效、哪种不失效（reserve 没超容量就不失效，swap 甚至一个都不失效），完整的失效规则表在 vector 深入。这里咱们先把"搬家等于旧地址全废"这个因果立住，那张表读起来就不再是死记的条目。
这个事故也备了一份在线版，您跑一遍就记得牢：
Compiler Explorer
扩容后的悬空指针：搬家前后地址对比
您先原样跑：before/after 两行里 p 和 v.data() 从相同变成不同，旧指针就此悬空，而程序大概率正常跑完。再在运行选项里加上 -fsanitize=address 重跑，ASan 会当场抓到这次越界写。
雏形加上 RAII、模板和异常安全，就是 std::vector
回头看咱们这一路搭的东西：堆上一块连续内存、size 和 cap 两个数、满了翻倍搬家。std::vector 的骨架就是它，再往上添三样工装：RAII 让析构自动还内存，泄漏这条路被堵死；模板把格子从 int 泛化成任意类型；异常安全处理"搬一半坏了怎么办"，以及元素的移动构造够不够 noexcept 会不会拖慢搬迁。这三样在项目里各有归宿：想看实现层全貌，读本卷 vector 深入：三指针、扩容与迭代器失效；想亲手把雏形搓成真容器，去 vol8 的 mini STL 实战，从裸缓冲开始一步一步来。
primer 的下一站是链表：一种永远不搬家的结构，代价是找元素得顺着问路。连续与离散、随机访问与顺序访问，这对取舍把数据结构的选择题撑开了大半，咱们下篇见。
参考资源
- cppreference：std::vector——复杂度承诺与迭代器失效规则的权威出处
- 本卷
vector 深入——三指针推导、三家扩容策略的数学、完整失效表 - vol8
mini STL 实战(二)：Vector，扩容与搬迁——亲手实现版，对象搬迁的完整讲究