指针 VS 引用
------------

指针和引用是C++语言无法绕过的两个重要语法点。

**指针是C语言最精华的精华，也是最糟粕的糟粕**\ 。因为有了指针，C语言才得以超越同时代的Fortran、Pascal、BASIC、ALGOL等语言，一举确立武林盟主的地位。指针给了C语言强大的能力、无与伦比的灵活性和大量的编程新技术新技巧。但也正因为指针过于强大和灵活，使得其学习和使用的难度极大，而且它还带来了非常严重的安全隐患，历史上曾经给C语言软件开发带来过大量灾难性的问题。几乎所有的C语言教程都会严正警告学习者，不要随意使用指针，不要在程序里滥用指针。指针带来的典型问题有：

1. 函数滥用指针参数，不加以必要的 ``const`` 修饰，导致实参被函数代码篡改。
2. 滥用指针代替数组，超限问题更加频繁和隐蔽。
3. 滥用多重指针，导致常量被篡改。
4. 悬空指针：多个指针指向同一块动态分配的内存，随后通过其中一个释放了内存，其他指针成为悬空指针，导致内存泄漏。
5. 野指针：定义指针变量却未初始化，不用的指针未改为 ``NULL``\ ，或动态分配的内存释放后没有将指针改为 ``NULL``\ ，导致内存访问混乱。
6. 在函数体中声明指针并分配内存，把指针作为函数返回值交给调用者，容易造成内存只分配不销毁，最终导致内存耗尽。

以上是滥用指针最易发生的问题，其他还有许多情况，举不胜举。尤其是初学编程者，在尚未完全掌握的情况下使用指针通常要遭遇严重问题，而且指针引发的问题极难调试。

C++语言为了改善指针滥用的情况，设计了\ :strong:`引用`\ 这一新机制。引用就是对变量增加一个别名，通过这个别名可以直接使用原变量。引用比直接操纵内存地址的指针安全很多，绝大多数以前必须使用指针的场景都可以用引用来代替。另外还有一些别的只能使用指针的场景，C++也提供了一些更加安全便捷的替代方案。


**可以用引用来完全替代指针的场景**


1、用来使函数代码可以修改实参

有时候我们需要函数代码能够修改实参对应的外部变量的值，在C语言里只能采用传指针的方式。但是在C++语言里我们强烈建议用传引用来代替传指针，最典型的例子就是交换两个变量的值。

.. literalinclude:: ../codes/150_swap.cpp
   :language: c++


.. attention::

   和传指针的参数一样，传引用的参数不能用字面量或者表达式给它喂值，它必须接收一个实实在在的变量。


2、用来传递数组作为函数参数

C++引用加模板可以完美实现传递数组作为函数参数，请参阅上一节的介绍：:ref:`模板参数：搞定数组作为函数参数时的种种不爽<ref_140_template_array>`\ 。


3、用来传递大型结构变量作为函数参数

C++函数默认的参数传递方式是传值，调用函数时，实参的值是复制一份喂给形参的。如果参数的类型是一个大规模的结构，复制参数值的开销就很大。C语言采用传指针的方法来解决这一问题，C++则改用传引用的方法，规避了传指针带来的诸多安全隐患。

引用型参数的实参必须是一个可以被引用的实际存在的变量，而不能是字面量或者表达式值。如果希望可以使用字面量或者表达式来给引用型形参喂值，那么在函数参数表中给这个参数加上 ``const`` 修饰即可（函数代码本就不可能去修改一个字面量或者表达式的值）。


4、用作函数返回值

为什么函数会需要返回引用？主要也是为了节约时间和空间。通常C++函数也是用传值的方式来返回值的，函数在返回时要为其返回值创建一个临时变量，然后把具体的值复制到该临时变量里去实现返回。和传参的情况一样，当返回类型是一个大规模结构时这个复制操作的开销会很大。C语言采用返回指针的方法解决这个问题，但是安全隐患太多，C++则采用返回引用的方式来代替返回指针。

.. warning::

   函数如果要返回引用，绝对不能返回在函数内部创建的局部变量的引用，因为引用必须背后有一个实实在在的变量作为支撑。局部变量在函数返回的时候是会被销毁的，如果返回局部变量的引用，那么这个引用就会失效。返回指针也一样，如果函数返回指针，同样是禁止返回指向局部变量的指针的。

   所以返回引用的函数，其返回值只能是另一个在外部实际存在的变量的引用。而在函数内部唯一可以接触到外部变量的地方就只有参数表，因此参数表里必须至少有一个同类型的引用参数可供用作返回值。

.. attention::
   
   由于引用可以视作是它背后那个实际的变量的别名，所以返回引用的函数本身可以成为一种“可赋值”的东西，完全可以有这样诡异的语句存在：\ ``func(a) = b;``\ 。这种特性可以用来实现连续赋值，但是太过诡异了，绝少会需要用到这样的语句。为了避免出现把函数调用作为被赋值对象的尴尬场面，我们可以在函数头的最前面加上常量修饰 ``const``\ 。

总之，函数返回引用的情况比较复杂，一般情况下还是要尽量避免使用，事实上绝大多数情况是可以避免的。


**无法或难以避免使用指针的情况**


1、C-string字符串

C-string字符串本质上是一个字符数组，指针和数组两种方式都可以表示C-string。惯例是在函数参数表中用指针形式 ``char *s`` 来表示这个参数 ``s`` 是一个C-string，用数组形式 ``char a[]`` 来表示这个参数 ``a`` 是一个字符数组，但二者本质上并没有区别，只是为了代码的易读性更好。

在程序中处理C-string时，我们推荐使用数组表示法。有一种流传甚广的说法，当需要依次遍历一个C-string里的所有字符时，用指针比用数组下标更快。于是我们需要面对一大堆令人头晕的 ``*p++``，``(*p)++`` 和 ``*(p++)`` 表达式。实际上在现代计算机系统下，这点速度差异根本感觉不出来，而数组的方括号运算符 ``[]`` 比起指针运算要直白和安全多了。在算法编程中强烈建议使用数组方式。

只有一个地方是只能使用指针形式而不能使用数组形式的，那就是函数的返回值。C++函数不支持返回数组，如果要返回C-string就只能是返回 ``char *`` 类型。要返回其他类型的数组也一样，只能返回第一个元素的指针，当然这种情况非常罕见。

我们可以用这样的代码来模拟实现库函数 ``strcpy()``\ ，这里我们用数组运算而不是指针运算来定位字符（事实上库函数本身也是用这种方式的）。

.. literalinclude:: ../codes/150_strcpy.cpp
   :language: c++

.. hint::

   在自己编程时我们更建议用C++的string类来表示字符串，不要使用C-string。大多数情况下二者的处理速度不会有显著差异。

2、动态内存管理

动态内存管理，就是在程序运行时根据需要动态地分配和释放内存空间。动态数据结构，例如可变长数组、链表、二叉树等的实现都依赖于动态内存管理。不幸的是动态内存管理只能使用指针，没有其他可替代方式。

C++提供了专门的动态内存管理运算（\ ``new, delete``\ ）来代替C语言的动态内存管理库函数（定义在 ``cstdlib`` 库中）。相比之下C++的动态内存管理运算更加方便和安全。但是现在还有一些笔试题中会出现C语言的动态内存函数，所以对它们有所了解还是有必要的。下面列出常用场景下两种方式各自的语句对比。

1. 动态变量

.. code-block:: c++

   #include <cstdlib>

   int *p1 = NULL, *p2 = NULL;
   p1 = (int *)malloc(sizeof(int));        // 使用C库函数分配一块一个int变量长的动态内存并让指针p1指向它
   p2 = new int;                           // 使用C++的new运算符申请一个动态int变量并让指针p2指向它
   
   // ...
   
   free(p1);                               // 使用C库函数释放p1所指向的动态内存
   p1 = NULL;
   delete p2;                              // 使用C++的delete运算符释放p2所指向的动态变量
   p2 = NULL;

.. important::

   * 每一个指针在声明时必须有效初始化，要么赋予有效的值，要么初始化为 ``NULL``\ ，避免野指针。
   * 每一个 ``new`` 必须对应一个 ``delete``\ ，动态申请的内存用完了必须释放回系统，有借有还，避免内存耗尽。
   * 每一个 ``delete`` 后必须跟有新的赋值，如果这个指针不再使用了就赋为 ``NULL``\ ，避免野指针。


2. 动态数组

.. code-block:: c++
   
   #include <cstdlib>

   int *a1 = (int *)malloc(20 * sizeof(int));      // C库函数的做法
   int *a2 = new int[20];                          // C++ new运算的做法
   
   // ...
   
   free(a1);                                       // C库函数的释放法
   a1 = NULL;
   delete [] a2;                                   // C++ delete运算符的释放法
   a2 = NULL;

3. 动态二维数组

.. code-block:: c++
   
   #include <cstdlib>
   
   int **b1 = (int **)malloc(10 * sizeof(int *));
   for (int i = 0; i < 10; i++)
           b1[i] = (int *)malloc(20 * sizeof(int));
   
   int **b2 = new int *[10];
   for (int i = 0; i < 10; i++)
           b2[i] = new int[20];
   
   // ...
   
   for (int i = 0; i < 10; i++) free(b1[i]);
   free(b1);
   b1 = NULL;
   
   for (int i = 0; i < 10; i++) delete [] b2[i];
   delete [] b2;
   b2 = NULL;


3、动态数据结构

前面已经说过，动态数据结构的实现往往依赖于动态内存管理，因此难以绕过指针的使用。

可变长的顺序数据结构，比如顺序表、顺序栈等，它们的底层都是基于数组来构造的。C++的数组一旦定义好之后，它的长度就不会变了。例如一个长度为100的整型数组 ``int a[100]``\ ，声明完之后它就最多能容纳100个整型数。如果用这样一个数组来构造了一个顺序表，当插入表中的元素超过100个时，它就没办法容纳了。所以如果无法事先知道可能要插入表中的元素数量，那么就不方便用这样的静态数组来构造顺序表。通常这种时候我们就会用动态数组来构造所需的数据结构，初始的时候用一个比较小的长度来分配空间，一旦不够用了就可以new一个新的更大的空间出来，把原先的元素复制过去，然后把原先分配的空间释放掉，再让表头指针指向新分配的空间。这样一通操作用动态内存管理和内存块复制来实现并不难，而且速度很快。虽然不是很必要，我们甚至还可以实现当元素数量很少的时候缩减空间。

而所有的链式数据结构都是动态数据结构，它们的实现离不开指针和动态内存技术。另外有时候在解决一些算法难题的时候有可能需要自行设计一些非标准的数据结构，它们可能需要具备可变长度的能力，也可能全部或部分地使用链式存储结构。

在算法编程中，我们对如何使用内存来构造合适的数据存储结构有以下一些建议：

1. 能使用顺序结构的，就不要使用链式结构；
2. 能够用静态的数组解决问题，且数组长度不至于必须使用全局变量的，就用静态数组，不要用动态数据结构；
3. 静态数组长度过长或无法确定时，用C++的STL容器，尽量不要用全局变量；
4. 对STL容器的使用不熟练的，用动态内存管理来分配数组。