vector的内部实现和优化

`vector` 在内存中如何存储数据？和 `array` 的区别？

面试官： 我看你写的代码里经常使用 std::vector。你能简单描述一下 std::vector 在内存中是如何存储数据的吗？它和普通的 C 风格数组（比如 int arr[10]）有什么主要的区别？

回答：

对于这个问题，我并不太了解，我谈一谈我粗浅的看法。
首先，vector 应该是基于数组 array 实现的，其底层就是一块动态分配的、连续的内存数组。这是 vector 能够支持快速随机访问的根本原因。但是，vector 肯定有它自身的优化在。
边界检查：
- array 只管给你分配一段连续的内存，其他的管理你都要自己来，也不会管你数组 idx 是否越界；
- 在 vector 中，如果用 [] 操作符，那么行为和 array 一样，不会管你越界与否；
- 但是，vector 提供了 at() 这个成员函数，vec.at(i) 会进行边界检查。如果 i 越界，vector 会抛出 std::out_of_range 异常。这说明 vector 的安全性更好。
自动初始化：
- 再比如，定义 array 时，程序不会帮我们自动初始化，array 中可能有一些奇怪的原始数据（随机值）；
- 但是，定义 vector 时，程序会帮我们自动初始化。

不过，我没有提到 vector 和 array 最重要的区别：（根据 Gemini 的解释补充）

Vector 的大小是动态可变的，可以不断地 push_back 新的元素，而 array 的大小是固定的。
这就是 vector 的动态扩容机制。

`vector` 的扩容机制 (Reallocation)

面试官 (补充与追问): 你说得很好。vector 最大的特点就是它的大小是动态可变的。我们可以不断地对它 push_back 新的元素。

但是，我们刚才说了，它的底层是一块连续的内存。这就带来一个问题：当这块连续的内存空间被用完之后，vector 是如何处理 push_back 一个新元素的请求的呢？这个过程发生了什么？它对性能有什么影响？

回答：

当内存空间被用完时，vector 会申请一个新的内存空间，而我认为，由于每次只申请一点点空间的重复操作非常麻烦（这涉及内存分配和元素移动），这个新的空间通常是在原空间的基础上翻倍。
对性能的要求：平均下来，每次扩容的操作开销为 O (1)，所以这是很高效的。

我们来把上面粗浅的理解细化、深化

面试官 (总结与深化): 你说得非常好。我来帮你把这个过程的细节和术语补充完整，这也是面试时希望听到的内容。

vector 内部通常会维护三个指针（或者说，等价的信息）：

_start: 指向这块内存的起始位置。
_finish: 指向最后一个有效元素的下一个位置。(_finish - _start 就是 size())
_end_of_storage: 指向这块内存的末尾。(_end_of_storage - _start 就是 capacity())

size() 和 capacity() 的区别：

size(): vector 中当前存储了多少个元素。
capacity(): vector 在不重新分配内存的情况下，总共能存储多少个元素。

扩容 (Reallocation) 的详细步骤： 当你调用 push_back，并且 size() == capacity() 时，就会触发扩容：

分配新内存 (Allocate)：vector 会向系统申请一块新的、更大的内存。这个“更大”通常是多少呢？不同的标准库实现策略不同，但常见的策略就是翻倍（比如 GCC）或者 1.5 倍（比如 MSVC）。
移动旧元素 (Move)：vector 会把旧内存区域中的所有元素，移动 (move)（如果元素的类型支持移动）或者拷贝 (copy) 到新的内存区域中。
释放旧内存 (Deallocate)：将原来的、较小的那块内存空间释放掉。
添加新元素：在新的内存区域的末尾，构造你这次 push_back 的新元素。
更新内部指针：更新 _start, _finish, _end_of_storage 指向新的内存区域。

性能影响：

昂贵的单次操作：单次扩容操作是非常昂贵的，因为它涉及内存分配、所有元素的移动/拷贝、以及内存释放。它的时间复杂度是 O (n)，其中 n 是 vector 的当前大小。
平摊后的 O (1) (Amortized O (1))：正如你所说，虽然单次扩容很慢，但因为它按比例（比如翻倍）增长容量，所以扩容的发生频率会随着 vector 变大而越来越低。将昂贵的扩容开销，平摊到多次廉价的、不触发扩容的 push_back 操作上，其平均时间复杂度被证明是常数时间 O (1)。这就是所谓的 “摊还分析”。

你对 vector 的动态扩容机制已经有了非常深刻的理解。

`vector` 预先分配内存

面试官 (最终问题): 好的，既然我们知道了扩容是昂贵的，那么在某些场景下，我们可能希望避免这种自动的、不可预测的扩容。

假设，我在程序一开始就已经明确知道，我这个 vector 最终会存放 1000 个元素。为了避免在 push_back 的过程中发生多次昂贵的扩容，我可以在一开始就做什么操作，来预先分配好足够的内存空间呢？这个操作对应的 vector 成员函数叫什么？

回答：

我不知道这个预分配内存的函数的名字，但是我在平时用过这个操作，就像下面这样。

1
vector<int> nums(1000);

但是，这和提问的要求并不完全一致，因为在上面的操作之后，nums.size() 和 nums.capacity() 都变成 1000 了，也就是，nums 被 1000 个初始值（这里就是 0）给填满了。

我们现在希望为 nums 预留内存，即 nums.capacity() 为 1000，但是 nums.size() 还是 0。

具体看下面的解释：

你举的这个例子 vector<int> nums(1000); 是一个非常好的尝试，而且在很多场景下它确实能解决问题。

我们来精确地分析一下这行代码做了什么，以及它和我提问的“预分配内存”有什么细微的区别。

`vector<int> nums(1000);` 做了什么？

这行代码会：

向系统申请一块能容纳 1000 个 int 的内存。
在这块内存上，构造 (construct) 1000 个 int 对象，并对它们进行值初始化（对于 int，就是把它们都设置为 0）。
执行完后，nums 的状态是：
- nums.size() -> 1000
- nums.capacity() -> 1000

现在，这个 vector 里已经实实在在地有 1000 个 0 了。如果你接下来想通过 push_back 添加第 1001 个元素，它依然会触发扩容。如果你想修改前 1000 个元素，你需要用 nums[i] = ... 来赋值，而不是 push_back。

我提问的“预分配内存”是什么？

有时候，我们希望 vector 内部有一大块“预留空间”，但我们不希望它现在就被任何实际的元素填满。我们希望 vector 的 size() 依然是 0，但它的 capacity() 已经很大了，这样我们后续的 push_back 操作就不会触发扩容。

实现这个功能的 vector 成员函数叫做 reserve()。

reserve(n) 的作用： 它会检查 vector 当前的 capacity()。

如果 capacity() 已经大于等于 n，它什么也不做。
如果 capacity() 小于 n，它会进行一次内存分配，将 vector 的容量至少扩大到 n。

reserve() 不会改变 vector 的 size()，也不会创建任何新元素。

我们来看对比：

 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
#include <iostream>
#include <vector>

int main() {
    // 使用构造函数
    std::vector<int> vec1(5);
    std::cout << "vec1 size: " << vec1.size() << std::endl;         // 输出 5
    std::cout << "vec1 capacity: " << vec1.capacity() << std::endl; // 输出 5 (或更大)

    std::cout << "-------------------\n";

    // 使用 reserve
    std::vector<int> vec2;
    vec2.reserve(5);
    std::cout << "vec2 size: " << vec2.size() << std::endl;         // 输出 0
    std::cout << "vec2 capacity: " << vec2.capacity() << std::endl; // 输出 5 (或更大)

    // 现在对 vec2 进行 5 次 push_back，不会发生任何扩容
    for (int i = 0; i < 5; ++i) {
        vec2.push_back(i);
    }
    std::cout << "After push_back, vec2 size: " << vec2.size() << std::endl; // 输出 5
    
    return 0;
}

结论：

如果你想创建一个包含 N 个已初始化元素的 vector，用构造函数 vector<T> vec(N);。
如果你想创建一个空的 vector，但为它预留至少能容纳 N 个元素的空间，以优化后续 push_back 的性能，用 vec.reserve(N);。

这是一个非常重要的性能优化技巧。

总结

今天我们深入地探讨了 std::vector 的内部工作原理：

底层存储：动态连续数组。
安全性：at() vs []。
动态扩容：size() vs capacity()，以及摊还 O (1) 的复杂度。
性能优化：使用 reserve() 来避免不必要的扩容。

vector 在内存中如何存储数据？和 array 的区别？

vector 的扩容机制 (Reallocation)

vector 预先分配内存

vector<int> nums(1000); 做了什么？

我提问的“预分配内存”是什么？

总结

相关文章

`vector` 在内存中如何存储数据？和 `array` 的区别？

`vector` 的扩容机制 (Reallocation)

`vector` 预先分配内存

`vector<int> nums(1000);` 做了什么？