vector 怎么变大

第 28 课，共 30 课 · 第 7 部分 · 再往前 · 约 15 分钟

push_back 好像永远放得下：加一个，vector 就多一个格子。它是怎么做到的？这一课看看 vector 背后的那块内存。先看两个数：size() 是现在有几个元素，capacity() 是不用搬家最多能放几个。

main.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v;6    for (int i = 1; i <= 9; i++) {7        v.push_back(i * 10);8        std::cout << "size " << v.size() << "，capacity " << v.capacity() << '\n';9    }10    return 0;11}

输出

size 1，capacity 1
size 2，capacity 2
size 3，capacity 4
size 4，capacity 4
size 5，capacity 8
size 6，capacity 8
size 7，capacity 8
size 8，capacity 8
size 9，capacity 16

capacity 不是一个一个涨的，而是 1、2、4、8、16：每次放不下，就翻一倍。

size 和 capacity

vector 的元素放在堆上的一块连续内存里（第 20 课讲过堆）。这块内存一般比现在要用的大一些：

	意思
`size()`	已经放了几个元素
`capacity()`	这块内存一共能放几个

size 小于 capacity 时，push_back 只是把下一个空位填上，很快。size 等于 capacity 时再 push_back，就得搬家。

注意： 每次翻一倍是 g++ 的做法。C++ 标准只要求「平均下来很快」，有的编译器每次乘 1.5。别让程序依赖 capacity 的具体数。

搬家

放不下的时候，vector 做三件事：

在堆上要一块更大的内存（g++ 是原来的两倍）；
把旧的元素一个一个搬过去；
把旧的那块还掉（就像 delete[]）。

点单步，走到第二个 push_back 和第三个 push_back，看 prices 的格子换到了一块新的内存上：

main.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> prices;6    prices.push_back(12);7    prices.push_back(30);8    prices.push_back(8);9    std::cout << "size " << prices.size() << "，capacity " << prices.capacity() << '\n';10    prices.push_back(45);11    std::cout << "size " << prices.size() << "，capacity " << prices.capacity() << '\n';12    return 0;13}

输出

size 3，capacity 4
size 4，capacity 4

第四个 push_back 不用搬家：capacity 已经是 4，正好还有一个空位。

先猜一猜

用 g++ 编译，这段程序显示什么？

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{1, 2, 3};6    v.push_back(4);7    std::cout << v.capacity() << '\n';8    return 0;9}

输出

搬家以后，旧的引用不能用了

搬家很方便，可有一个坑：你手里如果还拿着一个指向旧内存的引用，搬家以后它指着的是已经还掉的那块。下面的 first 是 v[0] 的引用，然后 push_back 让 v 搬了家：

main.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{10, 20, 30};6    int& first = v[0];7    std::cout << "first：" << first << '\n';8    v.push_back(40);9    std::cout << "first：" << first << '\n';10    return 0;11}

输出

first：10
first：
heap-use-after-free

发生了什么： 停在第 9 行：这块内存已经还回去了（delete 过了；vector、string 变大搬家时，旧的位置也会还回去），不能再用。

我们的引擎停在最后一个 cout 那一行，说 heap-use-after-free：用了已经还掉的堆内存。first 还绑在旧的那块上，新的元素早就搬走了。这和第 20 课 delete 以后还在用是同一种错。在真正的编译器里，这一行可能还显示 10（旧内存还没被别人拿去用），也可能显示一个怪数：这就是未定义行为，最难找的那种。点「看看是怎么出错的」，单步走一遍。

指针和迭代器也一样。下面这段想「每个分数后面补一个加 5 分的」，边走边 push_back：

main.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> scores{70, 80};6    for (auto it = scores.begin(); it != scores.end(); ++it) {7        if (*it < 75) {8            scores.push_back(*it + 5);9        }10    }11    std::cout << scores.size() << '\n';12    return 0;13}

输出

heap-use-after-free

发生了什么： 停在第 7 行：这块内存已经还回去了（delete 过了；vector、string 变大搬家时，旧的位置也会还回去），不能再用。

push_back 让 scores 搬了家，it 还指着旧的那块，下一次 *it 就出事了。范围 for 背后也是迭代器（上一课），所以 for (int s : scores) 里面也不要往 scores 里加东西。

注意： 规矩是：会让 vector 变大的操作（push_back、insert、resize……）之后，之前拿到的引用、指针、迭代器都当作不能用了，要用就重新取。

下标不会失效

下标说的是「第几个」，跟元素在哪块内存上没关系，所以搬家以后照样能用。要记住「是哪一个」，就存下标：

main.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{10, 20, 30};6    std::size_t first = 0;7    v.push_back(40);8    v.push_back(50);9    v[first] += 1;10    std::cout << "第一个：" << v[first] << '\n';11    return 0;12}

输出

第一个：11

reserve：提前要好位置

要是知道大概会放多少个，可以先 reserve(n)：一次要一块够放 n 个的内存，之后放到 n 个以内都不用搬家。

main.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v;6    v.reserve(100);7    std::cout << "size " << v.size() << "，capacity " << v.capacity() << '\n';8    for (int i = 0; i < 100; i++) {9        v.push_back(i);10    }11    std::cout << "size " << v.size() << "，capacity " << v.capacity() << '\n';12    return 0;13}

输出

size 0，capacity 100
size 100，capacity 100

reserve 只要内存，不放元素：之后 size() 还是 0，v[0] 也还不能用。放 100 个，一次也没搬家。不 reserve 的话，capacity 从 1 翻到 128，要 8 次内存，后面 7 次还得搬家。

先猜一猜

clear() 删掉所有元素。这段程序显示什么？

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{1, 2, 3, 4, 5};6    v.clear();7    std::cout << v.size() << " " << v.capacity() << '\n';8    return 0;9}

clear() 只把元素删掉，那块内存留着，以后再放东西不用重新要。所以 size 是 0，capacity 还是 5。

输出

小技巧： reserve 不是必须的：不写它程序也对，翻倍搬家平均下来已经很快。元素特别多、又知道个数的时候再用它。

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。

练习 1

数一数要了几次内存

往空的 v 里依次 push_back 1 到 20。每次 push_back 以后，如果 capacity() 变了，就是要了一块新内存。最后显示 要了 6 次内存。

要显示

要了 6 次内存

exercise1.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v;6    int grows = 0;7 8    std::cout << "要了 " << grows << " 次内存\n";9    return 0;10}

输出

点「运行」或按 Ctrl+Enter

练习 2

修好它：搬家以后的引用

这段程序在 push_back 之前拿了一个引用，搬家以后还在用它。改好它（用下标，或者 push_back 之后再取），让它显示 最后一个：60。

要显示

最后一个：60

exercise2.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{20, 40};6    int& last = v.back();7    v.push_back(60);8    std::cout << "最后一个：" << last << '\n';9    return 0;10}

输出

点「运行」或按 Ctrl+Enter

练习 3

先要好 50 个位置

先 reserve 50 个位置，再放进 1 到 50 的平方。最后显示 size、capacity 和最后一个元素，像下面这样。

要显示

size 50，capacity 50
最后一个：2500

exercise3.cpp

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> squares;6 7    return 0;8}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

size() 是放了几个，capacity() 是那块内存能放几个；g++ 放不下时翻一倍：1、2、4、8……
放不下时 vector 搬家：要一块更大的内存、搬过去、还掉旧的。
搬家以后，之前拿到的引用、指针、迭代器都指着还掉的内存，再用是未定义行为（引擎停下：heap-use-after-free）。
范围 for 和迭代器循环里不要往同一个 vector 里加东西。
下标不会失效：要记住「哪一个」就存下标。
reserve(n) 提前要好能放 n 个的内存，不改 size()；clear() 删元素，不还内存。