数据结构电子讲义

预备二 动态内存分配

XMUT.SE.DS2022年9月12日大约 20 分钟

预备二 动态内存分配

不想看完的看这里

  1. 你必须学会动态内存分配，否则数据结构学不下去
  2. 动态分配的内存以指针的形式返回，你完全掌握指针的相关知识
  3. C++用new，C语言用malloc来分配动态内存，这两者是不同的，C++的更复杂，还需要区分new和new[]。
  4. 分配的内存需要手动回收，C++用delete，C语言用free，C++同样需要区分delete和delete[]
  5. C++new和C语言malloc最大的区别在于它会调用构造函数，同理delete也会调用析构函数。
  6. 理解了C/C++的内存模型，你才算一只脚踏入了门槛（另一只脚是理解编译器）。

预习问题

为什么要使用动态内存。 这本来是一个很简单的问题，但事实上这个问题很难回答——对于面向OJ编程的各位来说。 要理解这点，你们首先要明白，变量在计算机里是如何体现的。这涉及到操作系统的ABI（百科open in new window，Wikiopen in new window）约定。

这里我们先提几个问题供大家思考，详细的说明我们会放在最后。

问题一：

const char* s = "Hello World!";

这段你们熟悉的代码，你能告诉我占用了多少内存吗？

问题二： 我们都知道局部变量出了函数就无法访问了，那么请问，如果我把一个指针指向一个局部变量并返回，是不是就可以继续访问这个局部变量呢？

问题三： 你试过在函数内申请一个很大的数组吗？比如100000*100000个int，这可行吗？如果不可行，为什么？

问题四： 总所周知全局变量是所有函数都可以访问的，那么请问，我们把所有局部变量都换成全局的可以吗？不从代码阅读的角度出发，仅从内存使用的角度考虑。

从内存的角度思考问题

相信你们有不少人会有这种疑问，为什么要学C语言，好像没什么用处。

这个问题可能有很多回答，但从我们的角度，最重要的一点是要让大家学会从内存的角度分析和思考。 你们学过JavaScript了，显然你们会发现JavaScript并没有恼人的指针，非常友好。 但这种友好是以隐藏细节为代价的，他令你们知其然不知其所以然。

如果拿汽车行业做比喻，大学培养的是设计师，最不济也要是个修理工，如果只是会开车就行，那去驾校就行了，为什么要来大学呢。

因此C语言是必须的，因为他最贴近底层，指针有助于你们更好的从内存角度分析和思考。 同时这也是（我们的）数据结构必须掌握的基本技能。

请记住，基本功决定你的上限。

为什么需要动态内存分配

现在我们从一个最简单的例子来说明为何需要动态内存分配。

你们很多人在课设上做的是游戏。以扫雷为例，我们知道扫雷的雷区尺寸是可以选择的：

初级    中级

如果是你来设计，你要怎么设计？

我相信很多同学很简单地用一个全局变量int mine[100][100]来处理。 因为我们无法预计用户可能会申请多大的雷区，因此我们分配了100x100的空间来存放雷区。 即便是高级（30x16）这也是足够了。

但这种方式一眼看过去就知道是有问题的，在大多数场合下，总是有大量的内存处于闲置状态。 这种方法面向OJ足够了，但对行业里的应用是不可以的。

我们需要有一种机制，可以根据需要弹性地分配内存。需要初级时，就分配9x9的空间，需要中级时，就分配16x16的空间。

直接用变量作为下标申请数组不行吗？

可以，也不可以。 你确实可以在gcc里写出这样的代码：

#include <iostream>
using namespace std;
int main(){
    int w,h;
    cin >> w >> h;
    int mine[h][w];
    return 0;
}

但是：

  1. 这套在VC里行不通，所以这不是标准C++所支持的（实际上是C99支持的）。
  2. 你不知道代价是什么。例如你可以试试输入100000 100000看看会有什么结果。

实际上上面所说的原因只是使用动态内存非常小的一个原因。 当你深入理解了内存模型，操作系统内存隔离，虚拟内存等内容之后，你就会发现使用它是如此的自然，以至于在这里都无法给出有说服力的理由。 你能想象我们要给喝水、呼吸找个理由吗？ 当然随着本课程里学习的深入，你也会发现动态内存分配是不可或缺的。

从更有效利用内存的角度，动态内存分配是必须的，这是对动态内存分配的第一层理解。

分配内存

C++里可以用new操作符来进行内存的分配：

int* p = new int;
int* p_array = new int[100];

*p = 100;
for(int i=0; i<100; ++i){
    p_array[i] = i;
}

new有两种用法，第一行申请的是单个变量，第二行申请了一个数组。注意这两种用法应该被看成是不同的运算符（一个是new，一个是new []）。 后面你会看到销毁的时候，也需要考虑这样的因素。

从代码中你可以看到，我们都是使用一个指针指向申请的这个开辟的空间。对于动态分配的内存，我们只能通过指针指向这些内存来进行访问（为什么？）。

接下来我们就可以通过这两个指针来访问申请到的内存了。

分配了多少空间？

你认为上面的两行代码共分配了多少字节的空间？

对于C语言，他用malloc来分配空间：

#include <stdlib.h> // C语言必须引入这个头文件，因为malloc是系统函数

int* p = (int*)malloc(sizeof(int));
int* p_array = (int*)malloc(sizeof(int)*100);

注意这里的区别，从语义上说，new是C++语言的语法的一部分。编译器在处理的时候能够知道申请的是什么类型（要占用多少空间）。因此你不必额外考虑类型所占的空间是多大。 但malloc是系统库函数，他无法知道要分配的是什么类型。malloc也不关心分配出来的空间你怎么解读和使用，他就是简单分配这么大的空间（以字节为单位）。 因此你必须考虑分配的类型，这也是为什么会乘一个sizeof(int)的原因。

可以看malloc的申明：

void* malloc(size_t size);

你只能传入一个size尺寸，他返回给你一个void*指针，非常简单纯粹。

void* 指针

void*指针是无类型指针，所以才需要强制类型转换成int*，这样才能赋值给p。

C++的new则要复杂的多，最重要的是他涉及构造函数的调用。C++不是故意搞这么复杂、非要另辟蹊径搞一套的，其实是不得不这么做。C++的new和Java的new更接近。

值得注意的是，在C++里你一样可以用malloc，但你需要像C语言那样用它。

内存的回收

C/C++的一大罪状是没有垃圾(Garbage Collection, GC)收集机制。也就意味着你需要自己回收内存。

如果从面向OJ的角度出发，这不是必须的，进程退出时操作系统会统一回收内存，这也是为何你们在C语言OJ里不回收也能通过的原因。 但如果从实际应用的角度出发这就是无法接受的了，现实中进程常常是常驻的，如果你一直申请内存而不释放，可以想象的是内存总会有耗尽的一天。

对于C++，我们需要用delete来回收new出去的内存。

int* p = new int;
int* p_array = new int[100];

delete p;          //用delete回收new分配的内存
delete[] p_array;  //用delete[]回收new[]分配的内存

请注意正如new有两种不同的用法（new和new []）一样，回收的时候，你需要用对应的delete进行回收（delete和delete[]）。 这两者不能混用。

C语言则通过free函数来回收malloc的内存：

#include <stdlib.h> // C语言必须引入这个头文件，因为malloc是系统函数

int* p = (int*)malloc(sizeof(int));
int* p_array = (int*)malloc(sizeof(int)*100);

free(p);        // 两者没有区别
free(p_array);

注意free和malloc一样，都是系统库函数，它也不关心里面放的是什么类型，只是简单回收内存。 而C++的delete也是语法的一部分，它会唤醒变量的析构函数。

什么？回收竟然不需要知道尺寸？

你会发现free和delete似乎漏掉了一个最重要的参数，即要销毁的空间有多大。 (你可能会认为delete知道要销毁的尺寸，但显然delete[]是无法知道的，否则应该是delete[100])

这里你可以思考下，为什么要这样设计？这种设计又该怎么实现？ 对于后者你可以这样理解，你有从操作系统获取一整块大内存的方法，但现在你要根据用户的malloc请求将其分割成不同的尺寸分配出去，同时也需要在free的时候回收以便再次使用。

请动起来

动态内存分配是无比重要的知识，如果不能完全掌握，你在数据结构的学习里将寸步难行。因为从第二章开始，我们就要使用它。这种使用是贯穿整个学习过程的。

因此请你切实完成OJ上的指引三：动态内存分配。注意我们OJ上的内存分配都会进行回收判定。如果你分配了内存但没有回收，你会无法通过测试。 所以全错的一大可能是你没有回收内存。

除此之外，你应该尽可能的使用动态内存分配改写你之前写过的代码来达到熟练掌握的目的。

延伸阅读：进程的内存模型（*）

本节可以不看。不影响学习。

前面说过，要从内存的角度来思考和分析。 这里简单介绍一下进程的内存模型，使大家有个简单的认识。 当然详细的内容你们需要RTFM和STFW。

我们可以简单把你要使用的内存变量分成五类：

  1. 局部变量（栈上内存）
  2. 全局变量
  3. 动态分配内存（堆上）
  4. 静态变量
  5. 常量（值不会改变的变量）

其中从你们熟悉的x86/64 windows的视角来看，你可以将全局变量，静态变量和常量看成同一种东西。

现在就要问这几个问题？

  1. 什么是变量
  2. 谁管这些变量的分配？
  3. 怎么分配？

我们一个个来回答。首先：

变量到底是什么？

这个问题看似很容易回答，变量就是内存里的一块空间嘛。

但我们就要接着来问，如何把变量与具体的这块空间联系起来呢？

其实很简单，机器在执行的时候，并不知道什么变量名称，它只知道地址。所以当代码变成机器码的时候，变量就变成了对应的内存地址。

那么我们继续问，那么所有变量对应的地址是固定的吗？如果不固定，那怎么保证找到正确的地址呢？

这里我们需要对变量做一个简单的区分：局部变量和动态分配的内存，属于动态的变量，他们的值会改变。而全局变量，静态变量和常量，他们的地址不会改变。

固定地址的变量

全局变量、静态变量和常量的地址是固定的，地址即变量，变量即地址。 链接器会负责在链接时为这些变量分配合适的地址空间。 操作系统加载后程序后，会把这些空间分配出来，程序就可以直接用这些空间了。

因此对这三种固定地址的变量，首先分配这个词不是很合适，它没有分配，而是就在那里，因为它的生命周期贯穿整个进程的始终。 所以进程加载后就会占用对应的区域，直到进程退出。至于他们的地址，是由链接器决定的。 操作系统则保证这些区域可用。

注意，因为这三种变量需要编译器和链接器介入，因此必须在编译期就知道需要多大空间，所以他们的空间是不可以动态改变的！

这样我们排除了三种变量，只需要关注局部变量和动态分配内存这两部分即可。

局部变量

你可能会觉得局部变量也可以使用固定的地址来表示，但你只要想一想递归的情况，就知道这是行不通的。

每一层递归，变量都不能相互干扰，这说明函数变量的地址是递归层次的深入而变化的。

另一个理由是容量上的，如果所有变量占用固定地址，那他们就跟全局变量没有区别，此时内存很可能放不下。

那么局部变量是如何确定地址的呢？这还涉及到函数调用的机制。目前你们不需要太深入的了解。 你可以这样理解，当调用并进入某个函数时，会有一个基本地址被刷新。

想象一下你要把多种物品放入一个箱子里，又希望他们相互之间能分开，不至于混在一起。 那么正确的做法是放完某一类物品，你就用一块板子隔开，然后在这块板子上新的一类物品。 以此类推，就可以把东西全部分隔开了。

函数调用也是类似的，每来一个新函数，我们的都会用一个板子（基址）把上一个函数的内容隔开。 所以局部变量的地址=基址+偏移。由于每个函数要分配多少个变量在编译期就可以确定。因此这些局部变量的偏移量是固定的。 我们只需要修改基址就可以保证每个函数的变量都不会相互覆盖。

这在几乎所有的ABI里都通过函数的调用栈来实现，你们现在无需过多纠结其中的细节，你们只需要知道： 调用函数的时候，会把当前的基址存起来，然后盖上板子（修改基址以避开当前（父函数）的变量），然后在这些板子上放新的东西（被调用函数的局部变量）。 从函数中退出时，我们简单把板子连同上面的东西一起拿走就行（恢复基址到父函数的基址）。

理解了这个过程，你就明白为什么说局部变量不需要清理了，因为退出函数的时候，恢复基址的操作就相当于清理了所有局部变量的空间。

存放局部变量的这个空间称为栈区。因为大部分的系统上它都是用栈实现的。

如何验证这一点

写个递归函数：

#include <iostream>
using namespace std;

void f( int level ){
    int i[2];
    long long rbp;
    asm(
            "mov %%rbp, %0\n\r"
            :"=r"(rbp)
       );
    if(level == 0){
        return;
    }
    printf("&i:0x%llx\trbp:0x%llx\n",(long long)i, rbp);
    f(level-1);
}

int main()
{
    f(10);
    return 0;
}

你会发现数组i的地址不断缩小。如果你多分配一些变量，你会发现每次缩小的间隔跟你函数中分配的局部变量的空间大小有关系。 再对比rbp(x64下的基址寄存器)的值，你应该能分析出一些什么。

要注意的是linux现在默认开启了地址随机化，这是出于安全考虑，因此你每次启动时看到的内容有可能差别很大。

局部变量用起来很方便，也是大家接触的第一种变量类型。但它有很大的局限性。

原因在于栈区相比动态内存分配的堆区是偏小的，而且栈区的主要功能并不是局部变量，它还有其他用途，也要占用空间。 此外栈区以线程为单位，每开一个线程，都要分配额外的栈区，这使得栈区的空间更加捉襟见肘。 因此在栈上申请太大的空间是不合适的，很可能跑着跑着栈爆了，你的程序也就挂了。 这点在调试版的代码里更明显，因为调试版的需要占用更多的栈空间来存放调试信息。

动态内存

动态内存就是我们上面提到的new或者malloc的内存了。这些内存由系统（实际上是C/C++ Runtime Libaray, CRT）进行管理。 但你需要手动释放。

放置动态内存的区域被称为堆区，这个堆和我们后面会讲的数据结构的堆并没有关系。只是体现其“随用随取，用过放回”的特点。

堆区相对栈区最大的特点是生命周期可控，且可以分配更大的空间。

堆区是所有语言都提供的变量申明方式，只是有些语言下你感受不到进行了分配。例如JavaScript里的List和Object。

到这里，我们会发现，所有变量类型都各司其职，不可相互替换。

  1. 全局变量可以跨函数使用，但无法自由伸缩，浪费内存。
  2. 局部变量作用域仅限局部，生命周期不可控，同时尺寸受限。
  3. 动态内存分配可以跨函数，可以自由伸缩，但需要用户自行管理。

从使用需求上，动态内存分配有其不可替代的作用，这是对动态内存分配的第二层理解。

现在我们看开头的几个问题：

问题一

const char* s = "Hello World!";

这段你们熟悉的代码，你能告诉我占用了多少内存吗？

局部变量s占用一个指针的空间（32位是4bytes，64位是8bytes），分配在栈上。"Hello World!"是常量，占13个字节（注意\0），在常量区。

问题二： 我们都知道局部变量出了函数就无法访问了，那么请问，如果我把一个指针指向一个局部变量并返回，是不是就可以继续访问这个局部变量呢？

不能，因为这块栈上空间已经被回收了，可能已被分配做他用。访问已经废弃的内存是非常危险的行为。

问题三： 你试过在函数内申请一个很大的数组吗？比如100000*100000个int，这可行吗？如果不可行，为什么？

不行，堆会被撑爆，大块数据请用静态分配或者用堆分配。

问题四： 总所周知全局变量是所有函数都可以访问的，那么请问，我们把所有局部变量都换成全局的可以吗？不从代码阅读的角度出发，仅从内存使用的角度考虑。

不行，这样做不仅会占用大量内存，而且无法处理递归问题。

进程的内存模型

现在可以看这张Linux进程的内存模型open in new window（原文在这里open in new window，但图已经裂了）了，相信你现在应该容易理解它了：

linux layout

等等，所有程序都共用一个地址模型，不会相互干扰吗？

好问题！恭喜华生发现了盲点。

答案是不会。请注意，从应用程序的视角看，他们的内存模型都是一样的，不仅如此，他们还能够完全使用所有4G（32bits）或128TB（64bits）的内存。

之所以会如此，是因为应用程序看内存是加了滤镜的，这个滤镜就是虚拟内存。详细可以看这里open in new window。 更多细节可以看这里open in new window[1]

操作系统通过硬件MMU进行虚拟内存管理，MMU和虚拟内存是现代CPU和操作系统的标配。 用户进程访问的内存需要映射之后才能转换为真实的物理内存。

因此进程A可以用0x12345678的内存，进程B也可以用0x12345678的内存，这两块相同地址的内存，经过虚拟内存映射后会指向不同的物理地址。 通过这种方式，所有在操作系统里跑的进程，都会认为自己占用了全部的内存空间（有利于链接器实现），但他们相互之间又可以隔离开来（不会互相干扰，安全性大大提升）。 甚至还可以让多个进程的空间映射到同一个物理内存，这就是动态链接库的实现原理[2]。

从上面动态内存分配的第一层和第二层理解，我们明白了动态内存的必要性，但他们不能回答一个问题：需要内存我直接使用不就行了吗，为什么还需要申请？ 比如我需要100M内存，那我任意指定一块内存，直接用不行吗，为什么还要调用函数返回指针去用呢？为什么还必须销毁呢？

答案是不行，因为操作系统如果不给你要使用的这块内存分配页表（也就是虚拟内存映射表），它就不可用。 你可以任意访问一块内存，比如0x0，写入数据试试，你会得到一个Segmentation fault

因此你要使用内存，需要先向操作系统申请。 当然从实现细节上说，并不是malloc做了这个操作。 内存管理有两个层次，一个层次是操作系统，以页为单位进行管理（4k）。 第二个层次是CRT（例如glibc），会根据用户的需要进行更细粒度的管理。

由此我们得到了动态内存分配的第三层理解： 操作系统管理着内存，你不申请，就不能随便用！

  1. 鉴于CSDN作者之间的引用状态，无法区分原作者是谁，请见谅。 ↩︎

  2. 从这里你可以窥见计算机这门学科的特点，不同层次之间有着大量的约定和细节，这些细节是：1.你如果不了解，就会一头雾水。2.你完全有能力了解，只要你愿意去了解。 比如如果你不了解操作系统虚拟内存的细节，那么你是无法理解链接器是如何实现的，也无法理解动态链接库如何共享代码。 ↩︎

数据结构电子讲义
Copyright © 2023 XMUT.SE.DS