跳至内容
Topos Uranos
中文 (中国)

向量

摘要

std::array 要求在编译时就知道它有多少个元素；而大多数问题在数据到来之前并不告诉我们这一点。本课介绍 std::vector，即随数据而增长的序列：如何创建它，如何用 push_back 向它添加元素，以及如何用它读取长度未知的数列。接下来是一切集合编程中的三种规范遍历（累积、过滤和变换），分别用循环和库中的算法来写；然后是把向量传给函数，以及为什么返回一个新向量的代价很低。最后讲向量的内部：它的大小和容量，填满时被换成另一个两倍大的内存块，以及指向元素的引用因此可能指向已释放的内存。

学习目标

  1. 创建 std::vector，用 push_back 向它添加元素并遍历它，用它读取一串长度未知的数据。
  2. 编写这样的函数：为了读取向量而按常量引用接收它，为了修改向量而按引用接收它，并在结果是序列时返回一个新向量。
  3. 实现累积、过滤和变换的遍历，在问题中识别出与之对应的模式，并在库允许时用 std::ranges::count、std::ranges::max 或 std::ranges::fold_left 加以简写。
  4. 用一个例子说明向量的大小与容量的区别，以及为什么添加另一个元素时，指向某个元素的引用可能失效。

会增长的序列

创建并填充向量

数组一课介绍了带下标的序列：同一类型的元素，一个接一个，从零开始编号。它的固定大小的现代形式 std::array<int, 7> 把大小写在类型里，编译器必须知道它。然而，编写程序计算一个班的平均成绩的人，并不知道班上会有多少学生。由此需要一种序列，它的大小是又一个数据，在执行期间可以改变：这就是向量 std::vector<T>，来自头文件 <vector>，其中 T 是元素的类型。

C++ 程序
#include <print>#include <vector>​int main(){    std::vector<int> squares{};    std::println("开始时：大小 {}，为空：{}", squares.size(), squares.empty());    for (int k{1}; k <= 5; ++k) {        squares.push_back(k * k);    }    std::println("{}", squares);    std::println("大小 {}，第一个 {}，最后一个 {}", squares.size(), squares[0], squares.back());    squares[1] = 0;    squares.pop_back();    std::println("{}", squares);}
输出
开始时：大小 0，为空：true[1, 4, 9, 16, 25]大小 5，第一个 1，最后一个 25[1, 0, 9, 16]

第 6 行创建一个空的整数向量：与数组不同，不必事先说明它会有多少个元素。size() 返回它有多少个元素，empty() 说明它是否一个元素也没有。第 8 至 10 行的循环用 push_back 添加五个平方数，这个函数把它的实参放在末尾，并使大小加一。第 11 行用前一课对数组使用过的范围格式输出整个向量。按下标访问和以往一样，squares.back() 是 squares[squares.size() - 1] 的简写。第 13 行给一个已有的元素赋值，第 14 行用 pop_back 删除最后一个元素。概括起来，本课的操作如下。

  • v.push_back(x) 把 x 添加到末尾；v.pop_back() 删除最后一个（向量为空时，这是未定义行为）。
  • v.size() 是大小，类型为 std::size_t，即数组一课介绍过的表示大小的无符号整数；v.empty() 等价于 v.size() == 0。
  • v[i] 和 v.at(i) 给出下标为 i 的元素，下标必须满足 i < v.size()；v.front() 和 v.back() 给出第一个和最后一个元素，并要求向量非空。
  • v.resize(n) 使向量恰有 n 个元素：删除末尾多出的元素，或在末尾添加像用空花括号那样初始化的元素（对数字而言是零）。

和数组一样，v[i] 不保证任何检查，而 v.at(i) 保证：下标为 7 而只有五个元素时，它以消息 vector::_M_range_check: __n (which is 7) >= this->size() (which is 5) 终止程序，消息中给出了下标和大小。造成这种终止的机制，即异常，将在 C++ 程序设计 II 中学习。

花括号与圆括号

本课程一切都用花括号初始化，而向量是本课程中第一个把花括号换成圆括号就会改变结果的类型。用花括号时，写出的值就是元素；用圆括号时，第一个数是元素的个数，第二个数（如果有）是每个元素的值。

C++ 程序
#include <print>#include <vector>​int main(){    const std::vector<int> a{5};    const std::vector<int> b(5);    const std::vector<int> c{3, 7};    const std::vector<int> d(3, 7);    std::println("{} {} {} {}", a, b, c, d);}
输出
[5] [0, 0, 0, 0, 0] [3, 7] [7, 7, 7]

a 有一个元素，即 5；b 有五个零；c 有 3 和 7；d 有三个 7。因此，花括号中的列表说的是“这些就是元素”，而圆括号留给需要同一个值的 n 份副本的场合，比如一个全部为零的计数器向量。

空向量的最后一个元素

空向量是一种正当的情形（没有数据的输入，没有任何元素通过的过滤），凡是含有向量大小的式子都必须在这种情形下检查一遍；其中最具欺骗性的是 v.size() - 1。由于 v.size() 是无符号整数，在它为 0 时减去 1 得到的不是 −1-1，而是发生回绕，正如在整数及其表示一课中看到的那样，一直绕到 std::size_t 的最大值。

C++ 程序
#include <cstddef>#include <print>#include <vector>​int main(){    const std::vector<int> values{};    std::println("values.size() - 1 = {}", values.size() - 1);    // 错误的界：向量为空时，条件为真。    for (std::size_t i{0}; i <= values.size() - 1; ++i) {        std::println("{}", values[i]);    }}
输出
values.size() - 1 = 18446744073709551615/usr/include/c++/15/bits/stl_vector.h:1282: constexpr std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::const_reference std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::operator[](size_type) const [with _Tp = int; _Alloc = std::allocator<int>; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

系统以信号 6 终止了程序。

输出的第一行是 18 446 744 073 709 551 61518\,446\,744\,073\,709\,551\,615，即 264−12^{64} - 1，这是本平台上 std::size_t 的最大值。由此可知，循环条件 0 <= 18446744073709551615 为真，第一轮读取了一个没有元素 0 的向量的 values[0]：这是未定义行为。观察到的情况取决于选项，和数组一样：不加优化编译时，GCC 15 的库会检查 operator[] 的下标，并用一个断言终止程序，断言写的是 __n < this->size()；加上优化后这项检查就消失了，而循环不能及时停下，试图在没有任何元素的地方读取（已在 Linux 上用 -O2 验证：由于空向量没有内存块，程序以段错误结束，没有任何说明原因的消息）。改正的办法是把界写成不含减法的形式 i < values.size()，它在向量为空时从一开始就为假；在看似需要减法的地方，先询问 values.empty()。