1. c/c++ 中的指针

学习内容来自Youtube的mycodeschool频道

1.1 内存结构

在现代计算机结构中，内存单元(RAM)，它主要用来存储程序中用到的变量。凡是整个程序中，所用到的需要被改写的量（包括全局变量、局部变量、堆栈段等），都存储在RAM中。
Memory单元可以看成一系列的用隔板隔开的房子，每个最小的单元是一个Byte(字节)，里面存放8个Bit(比特)。当我们在程序中申明(declare)一个新的变量时，计算机会为这个变量分配(allocate)一个唯一的地址，其分配地址的大小取决与，变量的类型(datatype)和编译器种类(compiler)。
在现代编译系统中，int(4 bytes), char(1 bytes), float(4 bytes), 所有类型的指针变量都是(8 bytes)，它只与操作系统的寻址能力有关，64位的计算机都是8字节存储指针变量。

// 申明一个整型变量a，内存地址从204开始到207，分配4个字节
// 与此同时在计算机内部有一个lookup table，会记录变量a，int类型，其实内存地址204
int a;
// 申明一个字符变量c，内存地址从209，分配4个字节
char c
// 变量a赋值为5，在相应的内存地址就会写上5(在计算机内部是二进制)
a = 5;
a++;

1.2 基本指针操作

这里就会有疑问，我们可以直接通过访问地址来修改变量么？是的，c/c++中的指针就可以帮助我们访问内存空间。
Pointer：variable that stores address of other variable
指针：指针是一个变量，它存放着其他变量的地址

我们知道：
p -> address
*p -> value at adress
int a;
// asterisk(*)
int *p;
// now p has address of a, p equal to 204
p = &a; // & is called ampersand
a = 5;
print p; // 204(address of a is 204)
print &a; // address of variable a is 204
print &p;// address of variable p is 64
print *p; // 5; operator "Dereferencing", get value at this particular address
*p = 8; // motify the value at p(204) as 8
print a; // 8, the value is motified as 8

1.3 指针的算术运算

如下所示，指针变量p存放int型变量a的地址204，那么p+1的地址是208，因为一个int型变量占空间是4 bytes，p+1是p指向地址的下一个整数。

int a = 10;
int *p = &a;
printf("%d\n", p);// address is 204
printf("%d\n", p+1);// address is 204+4 bytes=208

1.4 指针类型

如上图所示，int型变量在计算机内部占用4个字节，每个字节有八个比特。最高位是符号位(sign bit)。

int a = 1025;
int *p = &a;

printf("%d\n", p);: 打印出的地址是200，虽然它是从地址200-203，但是200是它的初始地址
printf("%d\n", *p);:计算机知道它是4个字节的int型，所有会查看地址200-203总共4个字节，计算其数值

int a = 1025;
int *p = &a;
printf("Address = %d, value = %d\n", p, *p);
// 类型的强制转换
char * p0;
p0 = (char*)p;
printf("Address = %d, value = %d\n", p0, *p0);

打印结果：

Address = 1440680572, value = 1025
Address = 1440680572, value = 1

在p被强制转换成“char地址”型后，并赋值给p0后，计算机知道如果要打印*p0，就只需要看一个字节的内容，也就是1。

// 指针算术运算+1
printf("Address = %d, value = %d\n", p+1, *(p+1));
printf("Address = %d, value = %d\n", p0+1, *(p0+1));

打印结果：

Address = 1549654656, value = 1549654712
Address = 1549654653, value = 4

因为之前p是 int*，地址加一指向下一个int变量，打印出来是垃圾数据；当p转换成 char*后，加一后指向下一个字节的地址。1025 = 00000000 00000000 00000100 00000001

1.5 空指针

空指针可以给它赋值任意类型的指针变量。但是要注意两点，赋之后的空指针(此时赋值之后，其实不再是空)不可以做算术运算，不可以被解析

void * p1;
printf("Address = %d\n", p1);
p1 = &a;
printf("Address = %d\n", p1+1);
printf("value = %d\n", *p1);

错误❌输出：

error: arithmetic on a pointer to void
ISO C++ does not allow indirection on operand of type 'void *'

其他的用于可以参考 YongXMan的博客

1.6 pointer to pointer

指向指针变量的指针

int x = 5;
int *p = &x;
*p = 6;
int **q = &p;
int ***r = &q;
printf("%d\n", *p); //  p保存着x的地址，解析p得到x变量的值，输出：6
printf("%d\n", *q); //  q存放着p的地址，解析q得到p变量的值，输出：225
printf("%d\n", *(*q)); //  输出：6
printf("%d\n", *(*r)); //  输出：255
printf("%d\n", *(*(*r))); //  输出：6

在实际运用中，有很多场景，比如删除二叉树的时候，头节点的地址给指针变量 TreeNode* head = new TreeNode(1)，类比于上图就是 TreeNode(1)存放在地址225， TreeNode* head记录地址225并位于内存215。当我们调用后序遍历删除函数 _deleteNode(TreeNode* head)，函数执行后内存225的内容就是垃圾数据了，此时若head还记录着地址225就有潜在的危险⚠️，因此正确的方式是传递 TreeNode** head_ref到函数 deleteNode(TreeNode** head_ref)中，实际调用 _deleteNode(*head_ref)，并在结束后 *head_ref=NULL， head_ref就是 q存放着 TreeNode* head的地址215，解析它就得到 head。

1.7 Pointers as function arguments - call by reference

1.7.1 一个自加函数的例子

Albert是一个初级程序员，有一天他写了如下的函数，希望一个数可以自加1

void Increment(int a){
    a += 1;
}

int main(int argc, char const *argv[])
{
    int a;
    a = 10; 
    Increment(a);
    printf("%d\n", a);
    return 0;
}

他所希望的输出是 a=11但是实际的输出却是 a=10，Albert对此不能理解。
实际上在主函数 main()中的a和在子函数 Increment(int a)中的a，都是local variable。如果在主函数中调用Increment(int a)，此时在Increment(int a)函数内部会在新建一个int型变量，并把a的值传递给函数内部新建的int变量，子函数结束后这个int变量生存周期结束，自动销毁。所以Increment(int a)中的a无法影响到main()函数中的a。两个变量的地址不一样可以证明上述的事实。

void Increment(int a){
    a += 1;
    printf("Address of a in Increment function is %d\n", &a);
}

int main(int argc, char const *argv[])
{
    int a;
    a = 10; 
    Increment(a);
    printf("Address of a in main function is %d\n", &a);
    return 0;
}

输出：

Address of a in Increment function is 1360300604
Address of a in main function is 1360300636

1.7.2 系统为一个应用分配的内存空间

当一个应用／程序在系统上运行，会为它分配相应的内存空间，这个内存空间可以分成4部分。

1. code(Text)
   这个部分存放着所以顺序执行的代码段，以文字的形式
2. static/Global
   一个不在函数里面申明的变量就是全局变量，它可以在程序的任何地方被访问或者修改，不同于local变量，只能在特定的函数或者代码区域才能被访问／修改。
3. Stack
   所有的local变量都存放在这个区域
4. Heap
   动态内存区域

前三个区域的内存大小在程序执行前就已经分配好大小了，是固定的了，而动态内存区域会在程序执行时动态的增加或者减少。

1.7.3 为什么要使用动态内存分配

转载引用于博主-岁月斑驳7
实例化一个类有两种方式：

// 假设有一个类A

// 方式一：直接定义法
A a;
// 方式二：动态内存分配法
A * a = new A();

两者有什么差别呢？
实际上，方式二即等价于如下代码：

A * a = new A();

等价于

A * a;
a = new A();

方式一就是直接将a放入栈区(局部变量，大小受限，自动释放)；

方式二则是在堆区(动态内存，大小任意，手动释放)分配一块内存，然后用指针a去指向这块内存；

那么我们很容易就知道为什么要使用动态内存分配来实例化一个类。

原因：

1.可以动态的申请空间，以便动态确定对象所需要的内存；
2.便于储存大型对象，通常情况下栈区的大小容不下过于庞大的对象；
3.传递指针比传递整个对象更方便高效；

举几个生动形象的例子解释以上三条原因：

1. 每个人都要吃盐，盐不够了再去买显然比把这辈子要吃的盐一次性买下来要明智；
2. 如果你是卖盐的，储存了很多盐，你只需要建一个仓库把盐放进去，然后自己记住仓库地址即可，而不需要把盐全部放在自己的家中；
3. 如果要去很远的地方谈卖盐的生意，只需要选一些有代表性的信息(地址)给对方就可以了，不需要把整个仓库搬过去给对方看。

补充说明：
在第一种方式中，&A 取到的是栈区的地址，作用域有限，出了作用域这个地址也失效了，而动态分配的内存在堆区，所以你需要手动去释放delete free。动态区域的变量，可以手动控制它的作用域，很适合有些递归函数

1.7.4 栈帧(stack frame)

参考资料 简书博客

如图所示，系统为我们之前的程序所开辟的内存空间。200-300是Code(text)和Static/global这两个区，300-600是栈区，600-800是堆区。

1. 在栈内存空间中，有一种特别的数据结构-call stack(调用栈)，它可以保证程序顺序执行和正确的调用子函数。
2. 每一个要执行的函数都会为它在栈中分配一段内存空间，并把函数所有的参数，要执行的指令，函数返回的地址放在这段空间中，它被命名为stack frame(栈帧)。

以main函数为例，在其栈帧中，为local variable-int a = 10分配一个内存，接下来在main函数中要调用子函数Increment(int a)，系统会保存此刻main函数中所有的变量和数值，并记录好返回地址，方便子函数结束后恢复现场。

然后会创建新的stack frame给子函数Increment(int a)，根据指令，会创建一个新的int变量a，并把main函数中的a=10的值，传递给这个新的a，然后这个a再自加一变成11，执行结束，系统接下来会抹除stack frame所有内容，并根据之前main函数的stack frame所记录的地址，返回到调用子函数的地方，接下来执行后续的指令，同样main函数会暂停，系统为printf函数创建stack frame，执行结束后消除，再返回main函数。这一系列的创建stack frame然后再消除，就是call stack的过程。

至此我们就理解了，local variable只能存活在它对应的函数内，所以Increment(int a)中的a不会影响到main函数中的a，main中的a还是10。接下来归纳总结：

1. main function is calling function;
2. Increment(int a) function is called function;

When we call a function in the calling function, the arguments in calling function is known as actual argument, in the called function, the arguments is known as formal argument. So when Increment(int a) is called, a in calling function(as actual argument) is mapped to a in called function(as formal argument) and pass the value to formal argument. so if we have called function like Increment(int x), a is mapped to x.

1.7.5 call by value or reference

这种传递参数的方式，叫做值传递(call by value)。在被调用函数中，参数要先复制，再通过值传递，接受调用函数中参数的值，这种方式会造成不必要的，变量复制，浪费空间。如果Albert想要让main函数中的a自加一，它可以通过如下的方式：

void Increment(int* p){
    *(p) = *(p) + 1;
}

int main(int argc, char const *argv[])
{
    int a;
    a = 10; 
    Increment(&a);
    printf("a= %d\n", a);
    return 0;
}

这种方式叫做按引用传递(call by reference)，可以直接修改main函数中变量的值。

在Increment(int* p)的栈帧中，创建local variable p，main函数中的a的地址传递给p，在Increment(int* p)中修改p指向的值，就是修改main中a的值。
在c++中还有跟优雅的写法，避免过多的指针操作符：
引用传递（引用作为参数）

void swap_cpp(int & a, int & b){
    int temp = a;
    a = b;
    b = temp;
}

1.8 指针和数组

在c/c++中，指针和数组有着密切的联系，数组是在内存空间一段连续的区域。

// 初始化一个长度为5的整数数组
int A[5] = {2,4,5,8,1};
// 借助数组内存空间的连续性，我们可以有如下的访问方式：
下标为i的元素的_
地址：&A[i] or (A+i)
数值：A[i] or *(A+i)

数组名是A，它表示整个数组的 base address，它是整个数组的起始地址，通过遍历可以访问整个数组元素。

还要注意的一点是：

int A[5] = {0,1,2,3,4};
int* p = A;
p++;// 有效的
A++;// 无效的，A不能做指针算术运算

在现代c++中，原始的数组非常容易越界，造成非法访问，所以一般都用动态数组vector。