【信奥业余科普】C++ 的奇妙之旅 | 22：深入 vector——动态数组的使用与底层细节

发表于 2026/05/07

作者 OneCoder

次浏览 22 分钟阅读

上一篇文章介绍了 STL 的整体设计思想——容器、迭代器、算法三层架构。从本篇开始，我们将逐一深入 STL 中最常用的容器。

第一个要详细展开的，自然是 vector——信奥中使用频率最高的容器，没有之一。

往期回顾：

一、 `vector` 是什么？

vector 是 STL 提供的动态数组容器。它的底层就是一段连续的内存空间（和普通数组一样），但它能根据需要自动扩容，不再需要程序员手动管理数组大小。

用一句话概括：vector = 普通数组 + 自动内存管理。

1.1 底层结构：三个指针

普通数组的局限在于大小固定：定义了 int arr[10]，它就只能装 10 个数，多放一个就会导致内存越界。而 vector 可以通过 push_back 不断追加数据，自动扩容。它是怎么做到的？

答案是：vector 的底层，仍然是一个固定大小的普通数组。

它在内部维护了三个指针（即之前学过的内存地址）：

begin：指向底层数组的开头。
end：指向当前最后一个有效元素的下一个位置。
end_of_storage：指向底层数组的物理末尾（即这块空间的容量 Capacity）。

其中，end - begin 就是当前存储的元素个数（即 size()），end_of_storage - begin 就是底层数组的总容量（即 capacity()）。只要 end 还没追上 end_of_storage，就说明还有剩余空间，可以直接放入新元素。

1.2 扩容策略：倍增与拷贝搬迁

当 end 追上了 end_of_storage，说明底层数组已经满了。此时再插入一个新元素，vector 会触发一次重新分配：

向操作系统申请一块两倍大的新连续内存空间（如原来容量为 4，新空间容量变为 8）。
将原来的所有数据逐一拷贝到新空间。
将新元素放入新空间的对应位置。
释放原来那块旧内存，归还给操作系统。
更新三个指针，使它们指向新的内存区域。

从使用者的角度看，只是不断调用 v.push_back(x)，数组好像可以无限增长；但在底层，它经历的是”申请新空间 → 拷贝数据 → 释放旧空间”的过程。

为什么选择倍增而不是每次加 1？ 如果每插入一个元素就重新分配一次，$n$ 次插入就需要 $n$ 次拷贝，总拷贝量为 $1 + 2 + 3 + \cdots + n = O(n^2)$，效率很低。采用倍增策略后，扩容次数变为 $O(\log n)$，总拷贝量为 $1 + 2 + 4 + \cdots + n = O(n)$，分摊到每次插入只有 $O(1)$ 的额外开销。这就是均摊分析的结果。

注意： 倍增策略是大多数主流实现（如 GCC、Clang）的做法。C++ 标准本身并未规定具体的增长倍数，只要求 push_back 的均摊时间为 $O(1)$。

理解了这个底层机制，就能明白为什么在已知数据量时应该用 reserve 预分配空间（后文会详细介绍），以及为什么扩容后原有的指针和迭代器会失效。

本篇将围绕 vector，从创建、操作、遍历到竞赛实用技巧，做一次完整的梳理。

二、创建与初始化

vector 提供了多种初始化方式，适应不同的使用场景：

  
#include <vector>

// 1. 空数组，之后逐个添加
std::vector<int> v1;

// 2. 指定大小，所有元素初始化为默认值（int 的默认值是 0）
std::vector<int> v2(10);            // 10个0

// 3. 指定大小和初始值
std::vector<int> v3(10, -1);        // 10个-1

// 4. 用初始化列表直接赋值（C++11）
std::vector<int> v4 = {1, 2, 3, 4, 5};

// 5. 用另一个 vector 拷贝构造
std::vector<int> v5(v4);            // v5 是 v4 的副本

// 6. 用迭代器范围初始化（可以截取一部分）
std::vector<int> v6(v4.begin(), v4.begin() + 3);  // {1, 2, 3}

一个常见的初学者误区：

  
std::vector<int> v(10);   // 创建了10个元素，值都是0
std::vector<int> v{10};   // 创建了1个元素，值是10

圆括号 () 表示”10 个元素”，花括号 {} 表示”元素就是 10”。两者含义完全不同。

三、常用操作一览

3.1 增加元素

  
std::vector<int> v;
v.push_back(10);     // 在末尾追加 → {10}
v.push_back(20);     //             → {10, 20}
v.push_back(30);     //             → {10, 20, 30}

// C++11 的 emplace_back，效果类似 push_back
// 对于复杂对象（如结构体），它直接在容器内存中构造，省去一次拷贝
v.emplace_back(40);  //             → {10, 20, 30, 40}

3.2 删除元素

  
v.pop_back();         // 删除最后一个元素 → {10, 20, 30}

// 删除指定位置（使用迭代器）
v.erase(v.begin());   // 删除第一个元素   → {20, 30}

// 删除一个范围 [begin, begin+2)
v.erase(v.begin(), v.begin() + 2);  // → {}

v.clear();            // 清空所有元素

3.3 访问元素

  
std::vector<int> v = {10, 20, 30, 40, 50};
v[2];           // 30（下标访问，不检查越界）
v.at(2);        // 30（下标访问，越界时抛出异常）
v.front();      // 10（第一个元素）
v.back();       // 50（最后一个元素）

v[i] 与 v.at(i) 的区别： 正常使用时效果完全相同。但当 i 超出范围时，v[i] 是未定义行为（可能读到垃圾数据或崩溃），而 v.at(i) 会抛出异常。竞赛中通常用 v[i]，调试时可临时改用 v.at(i) 来定位越界问题。

3.4 大小与容量

  
v.size();       // 当前元素个数
v.empty();      // 是否为空
v.capacity();   // 底层已分配的数组大小（≥ size）
v.resize(n);    // 调整元素个数为 n（多截断，少补默认值）
v.reserve(n);   // 预分配至少 n 个元素的空间（不改变 size）

size() 和 capacity() 容易混淆：

size()：实际存放的元素个数
capacity()：底层数组的总容量，即触发下一次扩容前还能容纳多少

  
std::vector<int> v;
v.reserve(100);
// v.size() == 0, v.capacity() >= 100
// 空间已分配，但里面没有任何元素

reserve(n) 与 vector<int> v(n) 的区别：

初学者容易把”预分配空间”和”创建 n 个元素”混为一谈，两者的差别在于 size 是否改变：

  
// 方式一：初始化时指定大小 → 创建了 n 个元素
std::vector<int> v1(5);       // size=5, capacity≥5, 内容: {0,0,0,0,0}
v1[3] = 42;                   // 合法，元素已存在

// 方式二：reserve → 只分配空间，不创建元素
std::vector<int> v2;
v2.reserve(5);                // size=0, capacity≥5, 内容: {}
v2[3] = 42;                   // 未定义行为！size 仍为 0
v2.push_back(42);             // 正确用法，size 变为 1

简单来说：v(n) 是”造好 n 个房间并住满人（默认值）”，reserve(n) 是”盖好 n 个房间的地基，但里面没人”。竞赛中，如果需要用下标直接读写，用 vector<int> v(n)；如果需要用 push_back 逐个追加但想避免扩容开销，用 reserve。

四、遍历方式

  
std::vector<int> v = {10, 20, 30, 40, 50};

// 方式一：下标循环（最直观）
for (int i = 0; i < (int)v.size(); i++) {
    std::cout << v[i] << " ";
}

// 方式二：迭代器（通用方式，适用于所有容器）
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

// 方式三：范围 for 循环（C++11，最简洁）
for (int x : v) {
    std::cout << x << " ";
}

// 方式四：范围 for + 引用（需要修改元素时）
for (int& x : v) {
    x *= 2;  // 将每个元素翻倍
}

方式三中 x 是元素的拷贝，修改不影响原容器；方式四中 x 是引用（回顾第20篇），修改会直接生效。

五、 `size()` 的类型陷阱

这是信奥中一个容易导致隐蔽 bug 的问题。

v.size() 返回的不是 int，而是 size_t——一种无符号整数。

  
std::vector<int> v;  // 空 vector，size() == 0

// 危险！v.size() - 1 不是 -1，而是一个极大的数
for (int i = 0; i < v.size() - 1; i++) {
    // 这个循环会执行极多次
}

无符号数 0 - 1 不会变成 -1，而是回绕成 $2^{64} - 1$。

为什么这段代码不会报错？ 因为 size_t 本质上就是 unsigned long long（64位系统）的别名，它和 int 一样是整数类型。当有符号的 int 和无符号的 size_t 一起运算时，C++ 会自动把 int 隐式转换成无符号类型，然后再计算。所以编译能通过，但计算结果与预期完全不同——你以为在做有符号减法得到 -1，实际上编译器悄悄按无符号规则算出了一个巨大的数。

为什么要这样设计？ “大小”和”个数”在逻辑上永远不可能是负数，用无符号类型可以在类型系统层面表达这一约束。此外，size_t 正是 C/C++ 中 sizeof 运算符的返回类型，定义为”足以表示任何对象大小的无符号整数”。在 64 位系统上，int 最大值约 21 亿，而 size_t 是 64 位无符号，能表示远大于此的范围。容器的元素个数不可能超过内存所能容纳的上限，所以 size_t 是最自然的选择。

设计本身是合理的，但它带来了一个副作用：与有符号的 int 混合运算时，隐式转换会悄悄改变运算规则，导致回绕 bug。解决办法是主动把无符号转回有符号：

  
// 方法一：强制转换为 int
for (int i = 0; i < (int)v.size() - 1; i++) { ... }

// 方法二：避免减法
for (int i = 0; i + 1 < (int)v.size(); i++) { ... }

六、性能特点

操作	时间复杂度	原因
尾部插入 `push_back`	均摊 $O(1)$	直接写入末尾，偶尔扩容
尾部删除 `pop_back`	$O(1)$	只移动 end 指针
下标访问 `v[i]`	$O(1)$	起始地址 + 偏移量直接定位
中间插入 `insert`	$O(n)$	后续元素全部后移
中间删除 `erase`	$O(n)$	后续元素全部前移
查找 `std::find`	$O(n)$	无排序保证，逐一遍历

核心结论： vector 擅长尾部操作和随机访问，不擅长中间的插入和删除。

七、竞赛中的实用技巧

7.1 预分配空间

数据量大时（$10^6$ 级别），用 reserve 避免反复扩容：

  
std::vector<int> v;
v.reserve(1000000);
for (int i = 0; i < 1000000; i++) {
    v.push_back(i);  // 不会触发任何扩容
}

7.2 `clear` 不释放内存

v.clear() 将 size 变为 0，但 capacity 不变。反复填充和清空时，用 clear 比重新创建更高效。

7.3 二维 `vector`：邻接表

图论题中存储边的标准方式：

  
int n = 5;
std::vector<std::vector<int>> adj(n);
adj[0].push_back(1);  // 节点0 → 节点1
adj[0].push_back(3);  // 节点0 → 节点3

// 遍历节点 0 的邻居
for (int neighbor : adj[0]) {
    std::cout << neighbor << " ";  // 1 3
}

与 int adj[1000][1000] 相比，vector 邻接表只存实际存在的边，对稀疏图节省大量空间。

7.4 配合 `sort` 使用

  
#include <algorithm>
std::vector<int> v = {30, 10, 50, 20, 40};
std::sort(v.begin(), v.end());          // 升序：{10, 20, 30, 40, 50}
std::sort(v.begin(), v.end(), std::greater<int>());  // 降序

排序后可配合 std::lower_bound 做 $O(\log n)$ 二分查找。

7.5 `vector<bool>` 的特殊性

vector<bool> 将每个 bool 压缩到 1 bit（而非 1 字节），8 个 bool 共用 1 字节。

为什么这么设计？ bool 只需要表示 true/false 两个状态，1 bit 就够了，但普通 bool 变量占 1 字节（8 bit），浪费了 7 bit。当数据量大时，差距非常明显：1000 万个 bool 按 1 字节存需要约 10MB，压缩到 1 bit 后只需约 1.2MB。vector<bool> 的设计初衷就是在大规模布尔数据场景下节省内存。

但这个优化破坏了 vector 的常规行为。 问题的根源在于：内存的最小可寻址单位是字节（byte），而不是位（bit）。一个字节有自己的内存地址，但字节内部的单个 bit 没有独立地址。

对于普通的 vector<int>，v[i] 返回的是元素的真正引用 int&，你可以对它取地址、绑定指针，一切正常。但 vector<bool> 的元素只占 1 bit，没有独立的内存地址，所以 v[i] 无法返回真正的 bool&，只能返回一个代理对象（proxy object）——它表现得像引用，但本质上不是。

底层是如何定位某一个 bit 的？ 虽然单个 bit 没有地址，但它所在的字节有地址。vector<bool> 内部维护的是一个字节数组，通过两步计算定位到目标 bit：

定位字节：i / 8（整数除法），确定第 i 个 bit 在第几个字节中。
定位位偏移：i % 8（取余），确定它是该字节中的第几位。

例如，访问 vb[5] 时：5 / 8 = 0（在第 0 个字节中），5 % 8 = 5（是该字节的第 5 位）。

找到目标 bit 后，用位运算来读写：

读取第 5 位：(byte >> 5) & 1         // 右移后取最低位
写入 true ：byte |=  (1 << 5)        // 用「或」将该位置 1
写入 false：byte &= ~(1 << 5)        // 用「与非」将该位清 0

代理对象正是封装了这套”字节地址 + 位偏移 + 位运算”的逻辑。当你写 vb[5] = true 时，代理对象在内部执行上述位运算来修改对应的 bit。

但这里有一个关键问题：底层内存中并不存在一个独立的 bool 变量与 vb[5] 对应——数据实际上是字节数组中某个 bit。vb[0] 返回的是一个临时的代理对象，它的类型不是 bool，而是 std::vector<bool>::reference。因此：

  
std::vector<bool> vb = {true, false, true};
bool* p = &vb[0];   // 编译错误！vb[0] 返回的是临时代理对象，不是 bool 变量
                     // 既不能对临时对象取地址，类型也不匹配（代理对象 ≠ bool）

竞赛建议：需要正常引用/指针操作时，用 vector<int> 或 vector<char> 代替。

结语

vector 是 STL 中最基础也最常用的容器。它的核心优势在于：连续内存带来的高效随机访问，以及自动扩容带来的使用便利。但它并非万能——中间插入删除效率低，查找需要遍历。理解它的性能边界，才能在面对不同问题时做出正确的容器选择。

下期预告： vector 可以在任意位置插入和访问，功能强大。但有些场景下，我们恰恰需要限制这种自由——只允许一端操作。下一篇文章，我们将介绍 stack（栈）和 queue（队列），理解”主动限制”背后的设计逻辑。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

信奥业余科普, C++的奇妙之旅

科普计算机科学基础 GESP CSP C++ STL vector

本文由作者按照 CC BY-NC-SA 4.0 进行授权

一、 vector 是什么？

1.1 底层结构：三个指针

1.2 扩容策略：倍增与拷贝搬迁

二、 创建与初始化

三、 常用操作一览

3.1 增加元素

3.2 删除元素

3.3 访问元素

3.4 大小与容量

四、 遍历方式

五、 size() 的类型陷阱

六、 性能特点

七、 竞赛中的实用技巧