C++ Vector 的内存布局

探索一下 C++ 的容器 vector 的内存布局，也算是解答我自己的一些疑虑咯

头图是从网上搜的，尝试寻找出处，未果。很可惜。选曲尝试选择了一首听着比较清淡的曲子泪苔，感觉比较符合头图清新淡雅的神社氛围。希望你喜欢。

先介绍一下 `vector` 的基本情况咯

vector 是由 C++ 标准库提供的一个容器模板类。这里不打算仔细介绍什么是容器，模板，什么是类，我们直接指出：vector 的作用就是一个更好用的数组。“类”是说明它自己带了一些好用的函数，称为“方法”，“模板”就是说它需要接受一个类型作为参数才能成为一个完整的类型，就像数组必须说明是什么东西的数组一样。最后“容器”就是说它是一类经过了特殊优化的模板类，和别的容器一起共用着一些方法与成员，且有一类公共的算法可以用在它们上面。

和传统的数组相比，vector有这样的几个特点：首先它符合 RAII (Resource Allocation Is Initialization) 的要求，即自动管理内存，离开作用域时自动销毁，而传统的数组则不是很满足 RAII 的条件；其次就是 vector 是动态大小的，在使用时不需要在编译期就了解这个东西的大小，程序会根据需求自动分配内存。虽然后者在 C 中也能实现，比如指针+ malloc 或者指针+ new 的组合，然而这样的组合需要直接面对自己创建的裸指针 (Raw Pointer)，一个不小心就很容易造成内存泄漏，所以使用时要特别注意。最后就是，相比起数组这样较基础的数据类型，使用 vector 的内建函数（方法）可以避免自己造一些轮子，会比较方便。

即便 vector 看起来这么好，其实还是有人会担心 vector 会引入额外的运行开销。特别是，有人可能会怀疑：我使用数组或者指针+malloc或者指针+new 得到的内存空间我是明确知道时连续的，那 vector 呢？它经过这样的包装之后，还拥有连续内存空间吗？这篇文章就是打算探讨这个问题。

`vector` 为什么“可能”会比较低效？

我们这里不打算介绍什么复杂的内容，比如什么 allocator 或者内存调度机制。我们只对“指针+malloc”、“指针+new”方法以及vector方法是怎么获取可用内存空间的方法进行简单说明。

不过在进入具体的内存分配过程介绍之前，我们希望能先介绍几个概念：

堆与栈

我们写好的程序在运行时，需要同系统进行交互，借由多种系统调用完成任务。而在程序运行的过程中需要的内存空间则也是由系统进行分配的。一般我们将系统分配的内存空间划分为两块，一块叫堆，而另一块儿叫栈。请注意这里的堆栈并不能直接对应数据结构，请仅将其看作内存空间的称呼。

程序运行时，系统会将调用的函数一个一个压入调用栈中，栈空间内实行先进后出（也是栈这一称呼的来源），连带着函数需要的变量也是一样压入栈内的。然而，栈实际上相对比较小，如果在栈内存放了过多的资源导致栈内空间不足，程序则会出现所谓的栈溢出 (Stack Overflow)。不过好消息是，系统并不会傻傻地将任何东西都放在宝贵的栈空间内，在存储大量内容时，可以把这些内容存储在堆中。

堆和栈都是由系统负责内存分配的，区别在于，栈是严格执行先进后出的，且空间有限，只负责函数调用等，资源会被自动回收；而堆则不同，堆相比栈而言会比较大，里面的资源不需要什么先进后出，然而在程序不再用到里面存储的资源时，系统也不会自动回收它们，取用这些内存资源的方式也是需要通过指针进行读取或写入的。所以相比栈空间，堆空间的运用更需要一些技巧，如果使用比较传统的方式的话。有句话很好地形容了堆：垃圾堆。如果能很好地管理这里的内容，那样就会很好用，否则就会让系统东留一块儿垃圾西留一块儿垃圾，最后变成垃圾堆。所以C/C++编程的一大技巧就是使用好堆上的空间。

那么，我们应该如何，按照上面所述的方法，进行堆上的内存管理呢？

`malloc` 的内存分配方法

传统的指针+malloc方法大概是这样工作的：首先声明一个指针，它不指向什么具体的内存地址（空指针），然后再通过 malloc 中传入的参数来决定从这个指针开始要给它多大的连续空间（一个内存段），最后让这个指针指向这个内存段的头部，从而完成内存分配。这样的方法最大的特点是它不需要编译时就确定好需要多大的内存，而是通过 malloc “动态地” 分配一段内存，然后交给这个指针进行管理。在 C 语言写的程序中，基本都是这么进行运行期间的内存分配的。

这样的内存分配方法，在 C 语言兴起的时候，是非常伟大的。然而这个方法存在着很多的问题：首先就是指针操作的复杂性。使用 malloc 时必须留意管理内存资源的指针。在内存不再被使用时必须调用 free 函数来释放资源，且在 free 之后就不能再次调用这个资源来。很多程序运行崩溃，都是由指针造成的，或者是忘记删除已经不需要的资源，或者是引用了空指针或者悬垂指针。另外就是使用 malloc 分配的内存实际上也没有那么动态：如果你声明了 100 字节的内存，那就一定而且只有 100 字节的连续内存可以用：如果你实际上用不到 100 字节，那多余的空间会被浪费，不过这样还好；而当你用了超过 100 个字节的数据，却尝试将它们放在 100 个字节的内存段中时，多出来的部分会直接被截断，也就是说多出来的部分就消失了。最后，很致命的一点是，malloc 是一个很不智能的函数。它没有类型（返回 void*）,不调用构造函数，且必须要手动计算好分配的字节数，然后传给它。这实在是一个坏消息。而即便你注意了资源的声明与使用，使用裸指针管理资源的过程也比较繁琐：你需要使用一些诸如 memcpy 这样的函数来管理内存，这些函数操作非常精细，它会要求操作的字节数量。有机会在程序运行的时候分配内存，这很好，但也许会显得有点太麻烦了。

所以，我更愿意称使用 malloc 进行内存管理更适合 “高级用户”。一般而言，除非有很明确的需求，否则不会考虑使用老式的 malloc 进行内存分配，特别是在我们讨论的 C++ 语境下。那么 new 又如何呢？

`new` 的内存分配方法

相比于 malloc，new 更加智能，更加符合C++的思路。它会自动调用构造函数，不需要手动计算内存量（编译器会帮你计算好），且它是强类型的，它分配的内存空间会有一个明确的类型，而不是 void* 这样模棱两可的东西。然而，这里的“智能”，也只有这种程度了。究其原因，还是因为使用裸指针的原因。由于使用指针，就必须在不再使用资源时手动 delete 掉它（malloc 使用 free 释放，new 使用 delete 释放）。仅此一点就使 new 也不是一个特别理想的方法。它解决了一些 malloc 的痛点，但是没有解决使用裸指针带来的最根本的问题。

也许有朋友会讲：你提到的是裸指针，而我记得 C++ 标准在 C++11 时引入了智能指针。它是符合 RAII 规则的裸指针的包装，也就是说在不使用时可以自动销毁来释放资源。为什么不使用智能指针解决这些问题呢？

没错，智能指针的引入确实能有效改善这个问题，如果需要使用指针进行操作时，换用智能指针确实是一种很好的方法。但是我们只是希望拿一块内存存储数组那样的东西，使用智能指针也许有点太重量级了。也许有人中意智能指针以及使用指针方式来进行内存管理，不过这里就不多介绍智能指针了。那既然 malloc 和 new 都不是非常令人满意的答案，vector 就能解决这些问题吗？

`vector` 的内存分配方法

我们首先给出肯定的回复：Yes, vector 是“我需要一块我不知道内存大小的连续内存段”的非常好的解决方案。实际上也许 vector 会比想象中的更好用。vector 首先是符合 RAII 的，这使得我们不需要特别关注声明的资源：这些资源在离开其作用域时就自动被销毁了。不用再担心内存泄漏，也不用担心空指针之类。另外 vector 虽然实际上是将资源放在堆上的，对 vector 的操作实际上就像是在栈上操作它一样，对它的操作要比指针操作之类要直观的多。最后，使用 vector 不用担心空间不足：当 vector 内的空间不足以容纳新的东西时，vector 会自动增加其容量，来容纳这些新的东西。这个操作在编程侧是近乎无感的：你可以直接把 vector 当做一个无限容量的容器，你要做的事情就是往里装就 OK 了。使用 vector 是很符合直觉的，给代码作者的心智负担也

也许有人会担心：vector 就一点问题都没有？很可惜， vector 也是需要正确使用的，否则就是会很低效。这一点主要体现在 vector 的自动扩容上。vector 的扩容机制是这样的：如果容量不够，就在当前容量上乘2（或1.5，取决于具体实现）来容纳新东西。乍一听没什么问题，而实际上扩容是一个很复杂也很慢的过程。我们下面会更深入地聊聊这个问题。另外，vector 的内存真的是连续的吗？可以通过什么方法来看到其内存布局吗？我们后面也会尝试使用程序来把内存地址打印到屏幕上，看看是个什么样子。最后，当你很明确自己需要的就是固定长度的内存区域时，vector 自动增长内存空间的做法可能就不合适了。这时你也许会更想使用数组的现代包装 std::array，而非 vector。

最后，vector 实际上也提供了和 C 的裸指针相容的对象，通过调用 vector::data() 方法即可获得 vector 内存段对应的裸指针。这样一来，需要精细操作或者与老 API 做兼容时也很方便。

连续的内存空间很重要吗？

上面我们一直强调“连续的内存空间”，也许有人会好奇，连续的内存空间很重要吗？答案是肯定的：连续的内存空间可以有效提高内存寻址速度，从而提高访问和读写的速度。事实上，有连续内存空间，自然也就有非连续的内存空间。如果一个内存段是连续的，那么就意味着从内存段头部开始，需要取用第5个元素就只需要令头指针向右（或者某个方向，取决于你）偏移4个元素，就可以取到这个元素了。典型的拥有连续内存结构的数据结构有传统的数组，以及我们这里介绍的 vector。而非连续内存结构的数据结构里，非常有代表性的一个就是链表。使用链表上的第5个元素需要先从头节点向后寻找第一个节点，找到之后再跳转到第二个，不断进行这样的跳转直到找到第五个元素。使用链表的好处是链表可以极大程度利用内存空间，因为不受连续的大段内存空间的条件约束，代价便是寻址速度相比数组或 vector 会慢很多。

另一个角度讲，vector 可能会低效的原因也在于此。由于 vector 需要保证内存是连续的，当它遇到内存不足时，便需要做下面的事：

在内存中寻找一块新的地址，这个地址有一段连续的足够大的内存来存放老数据以及即将到来的新数据；
把老数据复制到新的地址下；
把新数据添加到老数据的后面。

这个过程最耗时的部分是第三步。设想这样一个情况，操作系统在给程序分配内存时分配地非常零散，且希望最最高效地利用内存，以至于内存空间内部只有长度为 1, 2, 4, 8, 16, 32 这6段长度的内存，它们的地址相隔甚远，且你拥有的一个 vector 目前只保存了长度为1的数据（也就被系统分配到长度为1的地址下）。现在你打算向里面补充新数据，比如，你要往里面添加31个新数据，但是这个过程中需要做一些特别的判断，以至于编译器不能帮你做优化，直接分配给你32位长度的内存。

现在，在你向后补充第一个元素时，vector 会尝试寻找长度大于2的一个内存空间，它找到了第三块内存（长度为4）；你又向后补充了一个元素，此时 vector 发现内存不够，但是直接扩张大小也可以，此时就不需要寻址，直接声明后面的两位内存被使用即可；你又打算向后补充三位数据。这时 vector 发现内存又不够了，它寻址到第四块内存（长度为8），然后把第三块内存中的数据一个个复制到第四块内存中，然后再把新的三位数据补充到后面。

发现问题了吗？vector 的机制让编译器不太愿意把本就很大的内存空间直接交给 vector。当你要往 vector 里填充大量数据时，让它这样自己一点点增长长度的做法会非常耗时。好消息是，我们可以通过 vector::reserve 提前告诉 vector 我们需要大概多少的内存，以便编译器一开始就找好一个够大的地方。而且这样的机制也算是强有力地说明了 vector 具有连续内存结构。

在？看看内存结构

下面我们就来尝试用代码打印出 vector 里元素的内存地址吧。我们向一个 vector 中填充5个元素，每次填入时检查 vector 的状态：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v;

    for (int i = 0; i < 5; ++i) 
        // We use "push_back" push an element to the back of a vector
        v.push_back(i);
        std::cout << "Added: " << i
                  << ", Size: " << v.size()
                  << ", Capacity: " << v.capacity()
                  << ", Address of first element: " << &v[0] << '\n';
    }

    // Check contiguity
    std::cout << "Contiguous memory check:\n";
    for (size_t i = 0; i < v.size(); ++i)
        std::cout << "Address of v[" << i << "] = " << &v[i] << '\n';

    return 0;
}

得到的结果如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Added: 0, Size: 1, Capacity: 1, Address of first element: 0x56041b4592b0
Added: 1, Size: 2, Capacity: 2, Address of first element: 0x56041b4596e0
Added: 2, Size: 3, Capacity: 4, Address of first element: 0x56041b4592b0
Added: 3, Size: 4, Capacity: 4, Address of first element: 0x56041b4592b0
Added: 4, Size: 5, Capacity: 8, Address of first element: 0x56041b459700
Contiguous memory check:
Address of v[0] = 0x56041b459700
Address of v[1] = 0x56041b459704
Address of v[2] = 0x56041b459708
Address of v[3] = 0x56041b45970c
Address of v[4] = 0x56041b459710

可以看到，在添加元素时，vector 的 size 指示 vector 有多少的元素，而 capacity 指示了 vector 还有多少的空间。当空间不足时，vector 的空间会扩大一倍来容纳新的元素，同时头元素的位置也会发生变化。而在元素填入结束后，通过检查地址可以发现这些元素在地址上是连续的（一个 int 的大小是4，注意到使用了16进制所以 8 后面是 c 也就是 12，c 后面就进一位因为达到了16）。

这是一个很简单的小例子，但是用来说明 vector 的内存结构应该已经足够。

做个 Benchmark 看看

也许一个简单的 Benchmark 可以展示一下 vector 和传统的数组相比效率如何。下面我们初始化一个 vector 和一个数组，它们有同样的大小，并且执行累加操作，最后记录累加的用时。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <ctime>

const int SIZE = 10000000;

int main() {
    std::vector<int> vec(SIZE, 1);
    int* arr = new int[SIZE];
    for (int i = 0; i < SIZE; ++i)
        arr[i] = 1;

    // Benchmark vector
    clock_t start_vec = clock();
    long long sum_vec = 0;
    for (int i = 0; i < SIZE; ++i)
        sum_vec += vec[i];
    clock_t end_vec = clock();

    // Benchmark array
    clock_t start_arr = clock();
    long long sum_arr = 0;
    for (int i = 0; i < SIZE; ++i)
        sum_arr += arr[i];
    clock_t end_arr = clock();

    std::cout << "Vector sum: " << sum_vec
              << ", Time: " << (end_vec - start_vec) << " ticks\n";

    std::cout << "Array sum:  " << sum_arr
              << ", Time: " << (end_arr - start_arr) << " ticks\n";

    // Don't forget to delete[] the array!
    delete[] arr;
    return 0;
}

我们先不开启优化并尝试运行几次，看看结果：

1
2
3
4
5
6
7
8
9
> g++ test.cpp -o test && ./test
Vector sum: 10000000, Time: 21530 ticks
Array sum:  10000000, Time: 16693 ticks
> ./test
Vector sum: 10000000, Time: 21059 ticks
Array sum:  10000000, Time: 16560 ticks
> ./test
Vector sum: 10000000, Time: 20729 ticks
Array sum:  10000000, Time: 15812 ticks

我们再开启 O3 优化然后看看结果：

1
2
3
4
5
6
7
8
9
> g++ test.cpp -o test -O3 && ./test
Vector sum: 10000000, Time: 2684 ticks
Array sum:  10000000, Time: 2122 ticks
> ./test                            
Vector sum: 10000000, Time: 4091 ticks
Array sum:  10000000, Time: 3686 ticks
> ./test
Vector sum: 10000000, Time: 3205 ticks
Array sum:  10000000, Time: 2813 ticks

看来不开启优化的时候，两个方法的差距还是比较明显的，而当开启优化之后，两种方法的差距并不大。然而，使用 vector 最大的优势在于心智负担小，不用担心奇怪的内存问题，而且如果使用 vector::at 方法还能自动进行边界检查，在遇到越界问题时会抛出异常，避免程序以奇怪的，错误的方式运行。

总结

希望这篇小短文能帮助你了解 vector 的特点，或者打消你对 vector 性能的顾虑。vector 是用来说明 C++ Zero-overhead principle（零成本抽象原则）的一个很好的例子。vector 提供了一个动态数组的抽象，它会以最低成本来实现这个东西的特性，避免引入过多额外的性能开销，让调用者可以放心使用，不必担忧性能问题。对零成本抽象感兴趣可以查看 CppReference的介绍，里面介绍了这一原则的具体情况。

当然，每次使用新的特性，总是会引入一点点的开销。或许你会考虑，辛苦一下自己，让程序能再跑快点。这本身没什么问题，但是要指出的是，警惕提前优化。如果 vector 并不是制约程序运行效率的关键部分（也就是所谓的性能瓶颈），那么就先不要管它。当程序遇到了这个瓶颈，且只能通过优化数据结构才能提高性能时，再考虑把 vector 修改为别的容器或者数据类型，这样做也许会更实际一些。

当然，如果这个小短文有什么问题，请直接指出来。本人也不是科班出身，写这篇笔记纯粹是记录一下学习过程。欢迎交流讨论。欢迎大佬拷打，动作轻一些就更好了。

那么最后，一如既往，祝您身心健康。

先介绍一下 vector 的基本情况咯

vector 为什么“可能”会比较低效？

堆与栈

malloc 的内存分配方法

new 的内存分配方法

vector 的内存分配方法