std::vector 与栈行为：深入理解动态数组的栈式操作

设想你正在编写一个程序，用户将输入一系列值（如若干测验分数）。此时，输入项数在编译期未知，且每次运行都可能不同。你需要把这些值存入 std::vector，以便后续显示或处理。

根据目前所学，你可以采用以下几种做法：

1. 先询问用户有多少条记录，再创建相应长度的 vector，随后要求用户逐条输入。
   这并非糟糕的方案，但它要求用户提前准确知道条目数，且不能算错。人工数出十几二十项既乏味又易错——既然我们可以自动计数，又何必让用户数？

2. 假设用户不会输入超过某个上限（比如 30），于是创建（或调整）一个 30 元素的 vector，然后让用户持续输入直至完成（或达到 30 条）。由于 vector 的长度表示“已用元素”，最后再把长度调整为实际输入条目即可。
   缺点：用户被限制在 30 条内，无法预知是否足够或过多；若用户想继续输入，则只能作罢。

3. 为解决限制，可在用户达到上限时手动扩容，但这将数组大小管理与程序逻辑混为一谈，显著增加复杂度，极易引入 bug。

根本问题在于：我们试图猜测用户会输入多少项，以便管理 vector 大小。当条目数确实无法预知时，存在更优雅的做法。

在给出答案之前，先做一个简短铺垫。

什么是栈？

类比时间！
设想自助餐厅的一叠盘子，这些盘子异常沉重，每次只能端起最上面一只。由于盘子叠放且沉重，你只能通过以下两种方式修改盘堆：

• 放：将一只新盘子放到最顶端（遮住下面的盘子，如有）。
• 取：从最顶端取走一只盘子（露出下面的盘子，如有）。

不允许从中间或底部取放，因为那需要同时抬起多只盘子。

这种“后放先取”的顺序称为 后进先出（LIFO）。最后放上的盘子最先被取走。

编程中的栈

在编程中，栈 是一种容器数据类型，其元素的插入与删除遵循 LIFO 原则。通常通过两个操作实现：

许多栈实现还支持以下可选操作：

栈在编程中随处可见。课程《使用集成调试器：调用栈》中提到的 调用栈 就是一个栈！当函数被调用时，相关信息入栈；函数返回时，信息出栈。因此，栈顶始终代表当前正在执行的函数。

示例序列：

(栈: 空)
Push 1 → (栈: 1)
Push 2 → (栈: 1 2)
Push 3 → (栈: 1 2 3)
Pop    → (栈: 1 2)
Push 4 → (栈: 1 2 4)
Pop    → (栈: 1 2)
Pop    → (栈: 1)
Pop    → (栈: 空)

C++ 中的栈

某些语言将栈实现为独立容器类型，但这限制了功能。例如，若要打印栈中所有值而不修改栈，纯栈接口无法直接做到。

C++ 则在支持高效尾端插入/删除的现有容器（std::vector、std::deque、std::list）上，以成员函数形式提供栈操作。这样，这些容器既可作为栈，又保留原有能力。

旁注：邮箱列类比

盘堆虽好，但邮箱列更贴切数组实现栈的模型。
想象一摞固定数量的邮箱，每个邮箱只能存一件物品，顶部有毒刺，无法再插入新邮箱。

• 用一张便签标记“栈顶”——始终指向最低空邮箱。初始为空，标记在最底邮箱。
• Push：把物品放入标记邮箱，再将标记上移一位。
• Pop：标记下移一位，取出该邮箱物品，使其变空。
• 标记以下为“栈内”，标记及以上为“栈外”。

把“标记”看作 长度，邮箱总数看作 容量……

std::vector 的栈接口

std::vector 通过以下成员函数实现栈行为：

示例：

#include <iostream>
#include <vector>

void printStack(const std::vector<int>& stack)
{
    if (stack.empty())
        std::cout << "Empty";

    for (auto element : stack)
        std::cout << element << ' ';

    std::cout << "\tCapacity: " << stack.capacity()
              << "  Length: " << stack.size() << '\n';
}

int main()
{
    std::vector<int> stack{}; // 空栈

    printStack(stack);

    stack.push_back(1); // push_back 压入 1
    printStack(stack);

    stack.push_back(2);
    printStack(stack);

    stack.push_back(3);
    printStack(stack);

    std::cout << "Top: " << stack.back() << '\n';

    stack.pop_back(); // pop_back 弹出
    printStack(stack);

    stack.pop_back();
    printStack(stack);

    stack.pop_back();
    printStack(stack);

    return 0;
}

GCC/Clang 输出：

Empty   Capacity: 0  Length: 0
1       Capacity: 1  Length: 1
1 2     Capacity: 2  Length: 2
1 2 3   Capacity: 4  Length: 3
Top: 3
1 2     Capacity: 4  Length: 2
1       Capacity: 4  Length: 1
Empty   Capacity: 4  Length: 0

注意：

• push_back()/emplace_back() 增加长度，若容量不足则重新分配。
• 上例共触发 3 次重分配：0→1，1→2，2→4。

压栈时的额外容量

观察输出：最后一次重分配时，容量从 2 直接跳到 4（尽管只压入一个元素）。
当压栈触发重分配时，std::vector 通常会多分配一些额外容量，以减少后续重分配次数。

不同编译器策略：

• GCC/Clang：容量翻倍（从 2 到 4）。
• Visual Studio 2022：容量 ×1.5（从 2 到 3）。
  因此，输出可能因编译器而异。

调整大小 ≠ 栈行为

重分配代价高昂（与 vector 长度成正比），应尽量避免。
若预先手动 resize(3)：

std::vector<int> stack(3); // 括号初始化设容量=3

输出：

0 0 0  Capacity: 3  Length: 3
0 0 0 1  Capacity: 6  Length: 4
...

问题在于：括号初始化同时把长度设为 3，栈初始即含 3 个 0，后续压栈在 0 之上追加。
resize() 改变长度，适用于下标访问；对栈行为则不合适。

reserve() 仅改容量，不改长度

reserve() 可在不改变当前长度的情况下重新分配容量：

std::vector<int> stack{};
stack.reserve(6); // 仅预留容量 6，长度仍为 0

输出：

Empty   Capacity: 6  Length: 0
...

此后压栈不再重分配。

关键洞见

提示

• 下标访问：用 resize() 增加元素，确保下标合法。
• 栈操作：用 reserve() 预留容量，避免频繁重分配。

push_back() vs emplace_back()

两者均将元素压栈。若待压对象已存在，二者等价，优先 push_back()。

若需就地构造临时对象，emplace_back() 更高效：

class Foo {
public:
    Foo(std::string_view a, int b) { /* ... */ }
    explicit Foo(int b) { /* ... */ }
};

std::vector<Foo> stack;

// 已有对象
Foo f{ "a", 2 };
stack.push_back(f);        // 推荐
stack.emplace_back(f);

// 需创建临时对象
stack.push_back({ "a", 2 }); // 构造临时对象再拷贝
stack.emplace_back("a", 2);  // 直接构造，无拷贝

// explicit 构造函数
stack.push_back({ 2 });      // 编译错误
stack.emplace_back(2);       // OK

• push_back() 不会调用 explicit 构造函数，而 emplace_back() 可以。
• C++20 前，emplace_back() 不支持聚合初始化。

最佳实践

• 新建临时对象：优先 emplace_back()。
• 其他场景：优先 push_back()。

用栈操作解决挑战

答案显而易见：若事先不知条目数，用栈接口向 std::vector 压入元素即可：

#include <iostream>
#include <limits>
#include <vector>

int main()
{
    std::vector<int> scoreList{};

    while (true)
    {
        std::cout << "Enter a score (or -1 to finish): ";
        int x{};
        std::cin >> x;

        if (!std::cin)
        {
            std::cin.clear();
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
            continue;
        }

        if (x == -1)
            break;

        scoreList.push_back(x);
    }

    std::cout << "Your list of scores:\n";
    for (const auto& score : scoreList)
        std::cout << score << ' ';

    return 0;
}

程序允许用户持续输入分数，完成后打印列表。
无需计数、下标或手动管理长度，让 vector 全权处理存储！

小测验

问题 1
编写程序，实现以下序列，每步输出栈状态：

       (Stack: empty)
Push 1 (Stack: 1)
Push 2 (Stack: 1 2)
Push 3 (Stack: 1 2 3)
Pop    (Stack: 1 2)
Push 4 (Stack: 1 2 4)
Pop    (Stack: 1 2)
Pop    (Stack: 1)
Pop    (Stack: empty)