std::vector 的重新调整大小与容量

在上一组课程中，我们介绍了容器、数组以及 std::vector，并讨论了如何访问数组元素、获取数组长度以及如何遍历数组。虽然示例均以 std::vector 为例，但这些概念普遍适用于所有数组类型。

本章剩余课程将聚焦于 std::vector 与大多数其他数组类型的根本区别：实例化后仍可改变自身大小。

固定长度数组与动态数组

大多数数组类型存在一个显著限制：长度必须在实例化时已知，且之后不可更改。这类数组称为固定长度数组（fixed-size arrays） 或 定长数组（fixed-length arrays）。std::array 和 C 风格数组均属于固定长度数组（下一章将详细讨论）。

相反，std::vector 是动态数组（dynamic array），又称可变长数组（resizable array），即实例化后仍可改变大小。这一特性使 std::vector 与众不同。

运行时调整 `std::vector` 大小

实例化后，可调用成员函数 resize() 并传入新的期望长度来调整 std::vector：

#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 0, 1, 2 };   // 创建含 3 个元素的 vector
    std::cout << "The length is: " << v.size() << '\n';

    v.resize(5);                // 调整为 5 个元素
    std::cout << "The length is: " << v.size() << '\n';

    for (auto i : v)
        std::cout << i << ' ';

    std::cout << '\n';
    return 0;
}

输出：

The length is: 3
The length is: 5
0 1 2 0 0

两点说明：

调整大小时，现有元素值被保留。
新增元素执行值初始化（类类型默认构造，其他类型零初始化）。
本例中，两个新增 int 元素被零初始化为 0。

vector 也可缩小：

#include <iostream>
#include <vector>

void printLength(const std::vector<int>& v)
{
    std::cout << "The length is: " << v.size() << '\n';
}

int main()
{
    std::vector v{ 0, 1, 2, 3, 4 }; // 初始长度 5
    printLength(v);

    v.resize(3);                    // 调整为 3 个元素
    printLength(v);

    for (int i : v)
        std::cout << i << ' ';

    std::cout << '\n';
    return 0;
}

输出：

The length is: 5
The length is: 3
0 1 2

`std::vector` 的长度与容量

设想一排 12 栋房子：

长度（length）：当前实际居住 12 户。
容量（capacity）：房子一排最多可建 12 栋。

再如一盒鸡蛋现有 5 枚：

长度：5 枚。
容量：12 枚。
盒中还可再放 7 枚而不会溢出。

对 std::vector 而言：

长度（length / size）：当前“在用”元素数。
容量（capacity）：已分配存储空间可容元素数。

获取 `std::vector` 容量

通过成员函数 capacity() 获取：

#include <iostream>
#include <vector>

void printCapLen(const std::vector<int>& v)
{
    std::cout << "Capacity: " << v.capacity() << " Length: " << v.size() << '\n';
}

int main()
{
    std::vector v{ 0, 1, 2 }; // 初始长度 3
    printCapLen(v);

    v.resize(5);              // 调整至 5 个元素
    printCapLen(v);

    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

作者机器输出：

Capacity: 3  Length: 3
0 1 2
Capacity: 5  Length: 5
0 1 2 0 0

初始 3 元素 → 容量 3，长度 3。
resize(5) 需 5 个元素，原容量不足，于是重新分配空间至容量 5。
最终容量 5，长度 5。

大多数时候无需关心 capacity()，下文示例将频繁使用以观察 vector 存储变化。

存储重新分配及其代价

当 std::vector 改变所管理存储量时，称为重新分配（reallocation）。过程概览：

按目标容量申请新内存，元素值初始化。
将旧内存元素复制（或移动，如支持）到新内存，旧内存归还系统。
更新 vector 的容量与长度。

外部看来 vector 已“调整大小”，内部实则内存及元素全部替换！

相关内容
运行时申请新内存过程称为动态内存分配，详见课程 19.1《使用 new 与 delete 进行动态内存分配》。

重新分配通常需复制所有元素，代价高昂。因此应尽量避免不必要的重新分配。

关键洞见
重新分配代价高昂，请避免不必要的重新分配。

为何要区分长度与容量？

std::vector 虽可重新分配，但如《巴特比》所言，“它宁愿不这么做”，因为代价太大。若仅记录长度，每次 resize() 都会触发昂贵重分配。
分离长度与容量，使 vector 能智能决定何时重分配。

示例：

#include <iostream>
#include <vector>

void printCapLen(const std::vector<int>& v)
{
    std::cout << "Capacity: " << v.capacity() << " Length: " << v.size() << '\n';
}

int main()
{
    std::vector v{ 0, 1, 2, 3, 4 }; // 长度 5
    printCapLen(v);

    v.resize(3); // 缩小至 3 元素
    printCapLen(v);

    v.resize(5); // 恢复至 5 元素
    printCapLen(v);

    return 0;
}

输出：

Capacity: 5  Length: 5
0 1 2 3 4 
Capacity: 5  Length: 3
0 1 2 
Capacity: 5  Length: 5
0 1 2 0 0

初始化 5 元素 → 容量 5，长度 5。
resize(3) 仅改长度，未重分配，容量仍为 5。
resize(5) 因现有容量已足，无需重分配，仅把长度改回 5，并值初始化后两位。

通过区分长度与容量，本例避免了两次重分配。下节课将示范逐个添加元素时节省重分配的优势。

基于长度而非容量的索引

可能令你惊讶的是，operator[] 与 at() 的合法下标范围以长度为准，而非容量。

上例中，容量 5、长度 3 时，仅下标 0–2 有效。长度 3（含）到容量 5（不含）之间的元素虽存在，但其下标视为越界。

警告
下标仅在 0 到 vector 长度之间有效（与容量无关）！

收缩 `std::vector`

增大 vector 会提升长度，并按需提升容量。
缩小 vector 仅降低长度，不会降低容量。

为少量不再需要的元素重新分配内存并不划算；但若大量元素不再需要，浪费可观。
std::vector 提供 shrink_to_fit() 成员函数，请求把容量缩减到与长度一致。该请求非强制性，实现可忽略、部分满足或完全满足。

示例：

#include <iostream>
#include <vector>

void printCapLen(const std::vector<int>& v)
{
    std::cout << "Capacity: " << v.capacity() << " Length: " << v.size() << '\n';
}

int main()
{
    std::vector<int> v(1000); // 为 1000 元素分配空间
    printCapLen(v);

    v.resize(0);      // 缩至 0 元素
    printCapLen(v);

    v.shrink_to_fit();
    printCapLen(v);

    return 0;
}

作者机器输出：

Capacity: 1000  Length: 1000
Capacity: 1000  Length: 0
Capacity: 0  Length: 0

调用 shrink_to_fit() 后，vector 重新分配容量为 0，释放了 1000 个元素占用的内存。

小测验

问题 1
std::vector 的长度与容量分别代表什么？

问题 2
为何长度与容量要分开？

问题 3
std::vector 的有效下标基于长度还是容量？

固定长度数组与动态数组

运行时调整 std::vector 大小

std::vector 的长度与容量

获取 std::vector 容量