20.2 — 栈与堆

程序使用的内存通常分为几个不同的区域，称为段。

• 代码段（也称为文本段），已编译的程序位于内存中。代码段通常是只读的。
• BSS 段（也称为未初始化数据段），零初始化的全局和静态变量存储在此处。
• 数据段（也称为已初始化数据段），已初始化的全局和静态变量存储在此处。
• 堆，动态分配的变量从此处分配。
• 调用栈，函数参数、局部变量以及其他与函数相关的信息存储在此处。

在本节课中，我们将主要关注堆和栈，因为大部分有趣的事情都发生在那里。

堆段

堆段（也称为“自由存储区”）跟踪动态内存分配所使用的内存。我们已经在 19.1 节 -- 使用 new 和 delete 进行动态内存分配 中讨论过堆，所以这将是一个回顾。

在 C++ 中，当您使用 `new` 运算符分配内存时，此内存将分配在应用程序的堆段中。

假设一个整型变量是 4 字节

int* ptr { new int }; // new int allocates 4 bytes in the heap
int* array { new int[10] }; // new int[10] allocates 40 bytes in the heap

该内存的地址由 `new` 运算符返回，然后可以存储在指针中。您无需担心如何定位和分配空闲内存给用户的内部机制。但是，值得知道的是，连续的内存请求可能不会导致分配连续的内存地址！

int* ptr1 { new int };
int* ptr2 { new int };
// ptr1 and ptr2 may not have sequential addresses

当动态分配的变量被删除时，内存会“返回”到堆中，然后可以在接收到未来的分配请求时重新分配。请记住，删除指针并不会删除变量，它只是将关联地址处的内存返回给操作系统。

堆有优缺点

• 在堆上分配内存相对较慢。
• 分配的内存会一直保持分配状态，直到它被明确地释放（注意内存泄漏）或应用程序结束（此时操作系统应该会清理它）。
• 动态分配的内存必须通过指针访问。解引用指针比直接访问变量慢。
• 由于堆是一个很大的内存池，因此可以在这里分配大型数组、结构或类。

调用栈

调用栈（通常简称为“栈”）扮演着更重要的角色。调用栈跟踪从程序开始到当前执行点所有活动的函数（那些已被调用但尚未终止的函数），并处理所有函数参数和局部变量的分配。

调用栈是作为栈数据结构实现的。因此，在我们讨论调用栈如何工作之前，我们需要了解什么是栈数据结构。

栈数据结构

数据结构是一种组织数据以使其能够高效使用的编程机制。您已经见过几种类型的数据结构，例如数组和结构体。这两种数据结构都提供了存储数据和高效访问数据的方法。编程中还有许多其他常用的数据结构，其中相当一部分是在标准库中实现的，栈就是其中之一。

想象一下自助餐厅里堆叠的盘子。由于每个盘子都很重，并且它们是堆叠的，你实际上只能做三件事：

1. 查看最顶层盘子的表面
2. 从堆栈上取下最上面的盘子（如果存在，露出下面的盘子）
3. 在堆栈顶部放一个新盘子（如果存在，遮住下面的盘子）

在计算机编程中，栈是一种容器数据结构，可以容纳多个变量（很像数组）。然而，数组允许您以任何顺序访问和修改元素（称为随机访问），而栈则更受限制。可以在栈上执行的操作对应于上面提到的三件事：

1. 查看栈顶元素（通常通过名为 `top()` 的函数完成，但有时也称为 `peek()`）
2. 从栈中取出顶部元素（通过名为 `pop()` 的函数完成）
3. 在栈顶放入新元素（通过名为 `push()` 的函数完成）

栈是一种后进先出（LIFO）结构。最后压入栈的项将是第一个弹出。如果您将新盘子放在堆栈顶部，那么从堆栈中移除的第一个盘子将是您最后压入的盘子。后进先出。当项被压入栈时，栈会变大——当项被弹出时，栈会变小。

例如，以下是一个简短的序列，展示了在栈上压入和弹出是如何工作的：

Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1

盘子类比很好地说明了调用栈的工作原理，但我们可以做一个更好的类比。想象一堆邮箱，都堆叠在一起。每个邮箱只能容纳一个物品，并且所有邮箱最初都是空的。此外，每个邮箱都钉在其下面的邮箱上，因此邮箱的数量不能更改。如果我们不能更改邮箱的数量，我们如何获得类似栈的行为？

首先，我们使用一个标记（比如一张便利贴）来跟踪最底部空邮箱的位置。一开始，这将是最低的邮箱（堆栈的底部）。当我们向邮箱堆栈中压入一个项目时，我们将其放入被标记的邮箱（第一个空邮箱），并将标记向上移动一个邮箱。当我们从堆栈中弹出一个项目时，我们将标记向下移动一个邮箱（使其指向最上面的非空邮箱），并从该邮箱中取出项目。标记下面的任何内容都被认为是“在栈上”。标记处或标记以上的任何内容都不在栈上。

调用栈段

调用栈段包含用于调用栈的内存。当应用程序启动时，`main()` 函数由操作系统压入调用栈。然后程序开始执行。

当遇到函数调用时，该函数被压入调用栈。当当前函数结束时，该函数从调用栈中弹出（此过程有时称为栈展开）。因此，通过查看当前在调用栈上的函数，我们可以看到所有被调用以达到当前执行点的函数。

我们上面的邮箱类比与调用栈的工作方式相当类似。栈本身是一块固定大小的内存地址。邮箱是内存地址，我们压入和弹出栈的“项目”被称为**栈帧**。栈帧跟踪与一个函数调用相关的所有数据。我们稍后会详细讨论栈帧。“标记”是CPU中一个称为栈指针（有时缩写为“SP”）的寄存器（一小块内存）。栈指针跟踪当前调用栈的顶部在哪里。

我们可以进一步优化：当我们从调用栈中弹出一个项目时，我们只需要向下移动栈指针——我们不需要清理或清零被弹出栈帧使用的内存（相当于清空邮箱）。这部分内存不再被认为是“在栈上”（栈指针将在这个地址或这个地址以下），因此它不会被访问。如果稍后我们将新的栈帧压入相同的内存，它将覆盖我们从未清理过的旧值。

调用栈在行动中

让我们更详细地研究调用栈是如何工作的。以下是调用函数时发生的步骤序列：

1. 程序遇到函数调用。
2. 构造并压入一个栈帧到栈中。栈帧包括：

• 函数调用之后的指令地址（称为**返回地址**）。这是 CPU 在被调函数退出后如何记住返回到哪里。
• 所有函数参数。
• 任何局部变量的内存
• 函数修改过的需要返回时恢复的任何寄存器的保存副本

3. CPU 跳转到函数的起始点。
4. 函数内部的指令开始执行。

函数终止时，会发生以下步骤：

1. 寄存器从调用栈中恢复。
2. 栈帧从栈中弹出。这将释放所有局部变量和参数的内存。
3. 处理返回值。
4. CPU 在返回地址处恢复执行。

返回值的处理方式可能因计算机体系结构而异。有些体系结构将返回值作为栈帧的一部分。另一些则使用 CPU 寄存器。

通常，了解调用栈的所有细节并不重要。然而，理解函数在被调用时实际上是被压入栈中，并在返回时被弹出（展开），这为您理解递归以及调试时有用的一些其他概念提供了基础。

技术说明：在某些架构上，调用栈向远离内存地址 0 的方向增长。在其他架构上，它向内存地址 0 的方向增长。因此，新压入的栈帧可能比之前的栈帧具有更高或更低的内存地址。

一个快速简单的调用栈示例

考虑以下简单的应用程序

int foo(int x)
{
    // b
    return x;
} // foo is popped off the call stack here

int main()
{
    // a
    foo(5); // foo is pushed on the call stack here
    // c

    return 0;
}

在标记点，调用栈如下所示：

a

main()

b

foo() (including parameter x)
main()

c

main()

栈溢出

栈的大小是有限的，因此只能容纳有限的信息。在 Windows 上的 Visual Studio 中，默认栈大小为 1MB。对于 Unix 变体上的 g++/Clang，它可能高达 8MB。如果程序试图在栈上放置太多信息，就会导致栈溢出。**栈溢出**发生在栈中所有内存都已分配的情况下——在这种情况下，进一步的分配开始溢出到内存的其他部分。

栈溢出通常是由于在栈上分配了过多变量和/或进行了过多嵌套函数调用（函数 A 调用函数 B 调用函数 C 调用函数 D 等）造成的。在现代操作系统上，栈溢出通常会导致操作系统发出访问冲突并终止程序。

这是一个很可能导致栈溢出的程序示例。您可以在系统上运行它，然后观察它崩溃：

#include <iostream>

int main()
{
    int stack[10000000];
    std::cout << "hi" << stack[0]; // we'll use stack[0] here so the compiler won't optimize the array away

    return 0;
}

这个程序试图在栈上分配一个巨大的（很可能是 40MB）数组。由于栈不够大，无法处理这个数组，因此数组分配会溢出到程序不允许使用的内存区域。

在 Windows（Visual Studio）上，该程序产生以下结果：

HelloWorld.exe (process 15916) exited with code -1073741571.

-1073741571 是十六进制的 c0000005，这是 Windows 操作系统访问冲突的代码。请注意，因为程序在此之前就终止了，所以“hi”永远不会打印。

这是另一个会因不同原因导致栈溢出的程序：

// h/t to reader yellowEmu for the idea of adding a counter
#include <iostream>

int g_counter{ 0 };

void eatStack()
{
    std::cout << ++g_counter << ' ';

    // We use a conditional here to avoid compiler warnings about infinite recursion
    if (g_counter > 0)
        eatStack(); // note that eatStack() calls itself

    // Needed to prevent compiler from doing tail-call optimization
    std::cout << "hi";
}

int main()
{
    eatStack();

    return 0;
}

在上述程序中，每次调用 `eatStack()` 函数时，一个栈帧都会被压入栈中。由于 `eatStack()` 调用自身（并且从不返回到调用者），最终栈将耗尽内存并导致溢出。

栈有优缺点

• 在栈上分配内存相对较快。
• 在栈上分配的内存只要在栈中就保持有效作用域。当它从栈中弹出时，就会被销毁。
• 栈上分配的所有内存都在编译时已知。因此，可以直接通过变量访问这些内存。
• 由于栈相对较小，因此通常不宜做任何占用大量栈空间的事情。这包括分配或复制大型数组或其他内存密集型结构。