Day 18 - 指标不能乱指会出事

WHY POINTERS?

index - in
dynamic allocation

Basic of Pointers

pointer 是一种变数，而且就跟 array variable 一样，他也是用来储存记忆体位置的一个变数。

Declaration

type pointed* pointer name;
type pointed *pointer name

两种差别是 * 黏在谁的身上。

Instance:

int *ptrInt;
double* ptrDou;

Pointer 可以 point 到任何一种 type 上，但是要记得，同一种 type 只能 point 到那一种 type 的变数上。

Size

在 32 bit 中，一个 pointer 是 4 bytes，

在 64 bit 中，一个 pointer 是 8 bytes。

Assignment

pointer 的 assignment 公式如下:

pointer name = &variable name;

Instance:

int a = 0;
int *ptr = &a; 

// when ptr point to a
// means that ptr stores a's address in memory

切记，当 pointer 储存 a 的时候， type 必须要一样才行，因为他们并不会 cast。

让我们来看看记忆体:

如果我们今天宣告了一个 int, 一个 double，

再把 aPtr , bPtr 个别 point 给他们两个

int a = 5;
double b = 10.5;

int aPtr = &a;
double bPtr = &b;

【记忆体配置】

Address	Identifier	Value
0x20c644	a	5
0x20c
...
0x20c64c	bPtr	0x20c660
0x20c650	bPtr
...
0x20c658	aPtr	0x20c644
0x20c65c	aPtr
0x20c660	b	10.5
0x20c664	b	10.5

cout << &a; // 0x20c644
cout << &b; // 0x20c660
cout << &aPtr; // 0x20c658 是a指标的位置
cout << &bPtr; // 0x20c4c 是b指标的位置
cout << aPtr << endl; // 0x20c644
cout << bPtr << endl; // 0x20c660

Address Operators

分为两种:

&: The address-of operator, returns a variable's address.
- 只能 return 一个变数的 address (也就是不能有 &100、&a++)
- 不能放在等号的左边 (&a = x; WRONG)
*: The dereference operator, returns the pointed variable (return 他的值).
- 只能放在 pointer variable 前面
- 不能放在 usual variable 前面
- 不能改变 variable 的地址

Instance:

#include<iostream>
using namespace std;

int main()
{
	int a = 5;

	cout << &a << " " ; // 就会跑出a的位置 

	int *aPtr = &a;
	
	cout << aPtr << " "; //aPtr 本身会储存一个 address 
	cout << &aPtr << " "; //&aPtr 会是 他自己的 address
	cout << *aPtr << " "; //*aPtr 会 return a (也就是被指的那个变数) 
	return 0;
}

上面跑出来的结果会长这样:

0x6ffe1c 0x6ffe1c 0x6ffe10 5

小测验 →

【当 x 是一个 variable 的时候】

*&x 就会 return 甚麽呢?

可以先看 &x 他储存的是 x 的 address，

* 的概念又是把某个 address 储存的值 return 出来，

所以*&x 就会得到 x 啦 !

那

【当 x 是一个 pointer 的时候】

&*x 会 return甚麽呢?

首先，x 是一个 pointer，所以它是用来储存某一个变数的 address，

*x 就会是存在 x 上的 variable 我们假设他是 a，所以这句电脑就会 return a。

&*x 就会再提取 *x 的 address，最後就会回到 x 也就是存放 a 的 address 的地方。

Null pointers (nullptr)

What happens if you write this?

int* ptr;
cout << *ptr;

答案就是，

如果你指向一个未知的地址，你就会得到未知的值。

为了避免发生这种状况，我们就需要初始化，也就是把它宣告成 nullptr

int* p2 = nullptr;
cout << "value of p2 = " << *p2 << "\n"; // -> 0
cout << "address of p2 = " << &p2 << "\n" // -> 0x123456
cout << "the variable pointed by p2 = " << *p2 << "\n" // -> runtime error 因为没有变数被指(空的)

!写程序好习惯!

在宣告指标的时候，一定要初始化(nullptr)
当在 compile 的时候，记得检查你的 array & pointer

当你在宣告 pointer 的时候，* 不等於平常用的 *

宣告小经验:

int* p, q; // p = int*, q is not;
int *p, *q; // two pointers
int* p, *q; // two pointers
int* p, * q // twp pointers

// 但是通常会一行 写一个指标

当你在宣告 reference 的时候，& 不等於平常用的 &

Using pointers in function

Instance: swap function (把 x 跟 y 互换)

void swap(int x , int y);
int main()
{
	int a = 10, b = 20;
	cout << a << " " << b << endl;
	swap(a, b);
	cout << a << " " << b << endl;
}
void swap(int x, int y)
{
	int temp = x;
	x = y;
	y = temp;
}

由於 C++ 中函式回传的 default scheme 是把值传进去，而非直接传入 variable (也就是说只有 10 & 20 被传到函式里)，所以在 void() 结束後， x & y 的值就会马上被消灭了。也就达不到把 a b 的值互换的效果。

要解决这个问题，我们可以用 call by reference 或是 call by pointer 解决这种问题。

1. Call by reference

A reference is a variable's alias (别名)，所以基本上，使用 reference 跟使用 variable 两者是无异的。

int c = 0;
int& d = c; // declare d as c's reference
d = 20; 
cout << c; // -> 20 (因为 d & c 本质上是一样的东西)

但是如果你写成 int& d = 100 就会是错的。

那要怎麽改 swap 呢??

void swap(int& x , int& y);
int main()
{
	int a = 10, b = 20;
	cout << a << " " << b << endl;
	cout << &a << "\n";
	swap(a, b);
	cout << a << " " << b << endl;
}
void swap(int& x, int& y) // x = a 的别名; y = b 的别名
{
	cout << &x << "\n";
	int temp = x;
	x = y;
	y = temp;
}

这段程序的结果会长:

10 20
0x6ffe0c
0x6ffe0c
20 10

从上面蓝色的两行可以证明， x 其实跟 a 是在同一个位置。

使用 reference 的时机: 其实大部分就只有在 call by reference 的时候会使用。(当有时候在 block 里面变数会消失但是你之後还想要继续使用这个变数的时候。)

2. Call by pointer

Call by pointer 可以说是 call by reference 的原理
相反的 call by reference 可以说是 call by pointer 的捷径

那如果改成 call by pointer 的方式，要怎麽写呢?

void swap(int* ptrA, int* ptrB) //所以传入的值要是 &a &b(也就是a b的位置)
{
	int temp = *ptrA; // *ptrA = ptrA 储存的变数位置上的值
	*ptrA = *ptrB;
	*ptrB = temp;
}

如果要做 swap 的话，通常只会用 reference。

那如果程序被改成:

void swap(int* ptrA, int* ptrB) //所以传入的值要是 &a &b(也就是a b的位置)
{
	int* temp = ptrA; // temp 现在变成指标，储存 ptrA 指标上的地址
	ptrA = ptrB; // 把 ptrA 换成 ptrB (a地址 -> b地址)
	ptrB = temp; // 把原本放在 temp 中的 a地址，转换到 b 上
}

简而言之，这几行程序会把 ptrA 与 ptrB 的 value 互换而已，因此 a 与 b 都不会改变他们的值。

要怎麽知道甚麽时候该用 reference? 甚麽时候用 pointer?

大部分的时间会用 call by reference (改变 argument 改变 return value)
当你要用 pointer 的时候 (废话)

3. Returning a pointer

function 可以 return pointer 吗?

可以，但他就是回传一个 address

Instance:

#include<iostream>
using namespace std;

int* firtNeg(int a[], const int n){
	for(int i = 0; i < n; i++){
		if (a[i] < 0)
			return &a[i]
	} // what if about a[i] > 0?  ->!後面会说! 
}
int main()
{
	int a[5] = {0};
	for(int i = 0; i < 5; i++)
		cin >> a[i];
	int* ptr = firstNeg(a, 5);
	cout << *ptr << " " << p << "\n"; // 因为 ptr 是 address，所以要用 * 找那个 address 的值
	return 0; 
}

这个例子的优点是，我们可以同时得到 ptr 的 address 还有 value。

但如果我们只有 return value 的话，就没办法取得 address。

Dynamic memory allocation (DMA) 动态记忆体配置

为什麽要有指标的理由!

What is dynamic memory allocation?

在以前，我们在宣告一个 array 的时候，我们会这样写:

const int ARRAY_LEN = 100;
int a[ARRAY_LEN] = {0};

这样的 allocation 方式，称作为 static memory allocation，让电脑可以在 compile 以前就知道他需要配置多少的记忆体空间给这段程序。(以上面这段为例，就是 100 * 4 = 400 bytes)

那如果我们不确定阵列要多大(也就是 dynamic memory allocation)，要怎麽办 ?

我们之前有说过，这样写是不行的

int arrayLen = 0;
cin >> arrayLen;
int a[arrayLen] = {0};

这时候，我们就需要学习新的语法了!

a operator new (in C = melloc)

new int : 电脑会 allocate 一个 4 byte 的空间，但是 returned address 不会被记录。
int* a = new int; 这个时候 a 就会把 new int 的位置记录下来。
int* a = new int(5);这个时候 new int 的值就会变成 5。
int* a = new int[5];这个时候会 allocate 20 bytes。(也就是五个整数)
但是如果我们是用 int* a = new int[5];要初始化的话就要用 loop 输入。

上面的那段错误程序，就可以改成

int arrayLen = 0;
cin >> arrayLen;
int* a = new int[arrayLen];

在动态的记忆体配置里面，如果你 allocate 了一个 space，那个 space 会是没有名字的。

就像是 new int → 就不会有名字

因此，我们就需要使用指标帮助我们记住他的地址，让我们可以在找他做事。

那我们要怎麽用?

int len = 0;
cin >> len; // 3
int* a = new int[len]; // a 就是一个阵列
for(int i = 0; i < len; i++)
	a[i] = i + 1;

instance:

Fibonacci sequence

double fibRepetitive(int n) // find the nth number in Fib-sequence
{
	if(n == 1)
		return 1;
	else if (n == 2)
		return 2;
	
	double* fib = new double[n]; // dynamic allocate
	fib[0] = 1;
	fib[1] = 1;
	for (int i = 2; i < n; i++)
		fib[i] = fib[i - 1] + fib[i - 2];
	
	double result = fib[n - 1];
	delete[] fib; //
	return result;
}

Memory leak (漏洞)

但是 dynamic allocation 并不是无敌的，有时候会发生 memory leak

Instance:

void func(int a)
{
	double b;
} // after running, system releases 4(i) + 8(d) bytes 
int main()
{
	func(10);
	return 0;
}

在 void 跑完之後， system 会把 a b 的两个记忆体位置格式化。

(但是前提是，system 知道 a b 的位置)

那如果换成 dynamic allocate

void func()
{
	int* bPtr = new int[3];
}
// 8 bytes for bPtr are released
// 12 bytes for int are not
int main()
{
	func();
	return 0;
}

动态配置的那些 int ，在 void 跑完之後，他就不会被清掉(只有在程序被 shut down 之後才会清掉)，也就是说这些记忆体的空间都被浪费掉了。

就像是开 chrome 的时候你的记忆体会飙升一样。

出事了阿伯!

#include<iostream>
using namespace std;

int main()
{
	for (int i = 0; ;i++) // 无穷回圈 -> 故意浪费记忆体空间
	{
		int* ptr = new int[100000];
		cout << i << "\n";
		// delete [] ptr;  
	} 
	return 0;
}

如果你执行这段程序的话，因为 memory leak 会一直累积，所以如果你打开工作管理员看记忆体的空间就会不断地被占满。

Delete

它是一个 operator ，用来手动删除 dynamically allocated space 。

int* a = new int;
delete a; // release 4 bytes

int* b = new int[5];
delete b; // release only 4 bytes
					// Unpredictable results happen
delete [] b;  //这才是把全部删除

但是要注意的是，delete 不会对 pointer 做任何事，因此要养成一个好习惯，就是 delete 完，要把 pointer 宣告成 nullptr。

!写程序好习惯!

在不确定需要多少长度的时候 → 使用 dynamic allocation
当你写 new 的时候，要注意会不会发生 memory leak，如果有 → 要写 delete。
当你写 delete 的时候，一定要宣告 nullptr。

Two-dimensional dynamic arrays

在静态配置中，我们可以轻松的宣告一个二维的阵列

并且我们可以把她想成是 m x n = 有 m 个一维阵列，每个里面都有 n 个 elements

但在动态配置中，我们也做得到。

一样也可以把她想成有 m arrays，每个都有 n element

e.g., lower triangular matrix

我们只需要纪录一半的数据 →

#include<iostream>
using namespace std;

int main()
{
	int r = 3;
	int* array = new int* [r]; //array = 指向一个整数指标的指标 ; 後: 给我 3 个整数指标，
	for(int i = 0; i < r; i++) // 再把每一个指标都指向动态阵列 -> 搭拉
	{
		array[i] = new int[i + 1]; // 长度会 1->2->3->4->...
		for(int j = 0; j <= 1; j++)
			array[i][j] = j + 1; // 再 assign 进去
	}
	print(array, r) // 晚点说
	// delete? -> use loop
	return 0;
}

整个状态就会像是这样

跟静态配置不一样的地方在於，动态配置可以改变每一个项中指向的 array (後面的 n 个 element) 长度。

print():

void print (int* arr, int r)
{
	for (int i = 0; i < r; i++)
	{
		for(int j = 0;j <= i; j++)
			cout << arr[i][j] << " ";
		cout << "\n";
	}
}

其实就只是把 array 给印出来而已。

Arrays and pointer arithmetic

Pointer 其实就跟 array 是差不多的，他们都

储存第一个变数的地址
我们在传 array 的时候，就是在传递一个地址
array indexing operator[] indicates offsetting (????)

Pointer arithmetic

Instance:

int a = 11;
int* ptr = &a;
cout << ptr++ << "\n"; // 会指向下一个 variable (但你根本不知道是甚麽)
cout << ptr-- << "\n"; // 指向上一个

这个情况，你也不知道你 ++ - - 後会拿到甚麽东西。

Instance:

double a[3] = {10.5, 11.5, 12.5};
double* b = &a[0]; //-> 10.5
cout << *b << " " << b << "\n";  // 10.5
b = b + 2; // b++ & b++
cout << *b << " " << b << "\n";  //12.5
b--;
cout << *b << " " << b << "\n";  //11.5

所以这些 arithmetic 使用时机就是在，你知道顺序的东西里面 —> 也就是阵列啦!

要注意不能用两个 pointer 相加，但可以相减:

double a[3] = {10.5, 11.5, 12.5};
double* b = &a[0]; //-> 10.5
double* c = &a[2];
cout << c - b; // 会是 2

为什麽是 2 ，因为 c 还有 b 的位置上差了两格

Instance:

int y[3] = {1, 2, 3};
int* x = y;
for (int i = 0; i< 3; i++)
	cout << *(x + i) << " ";//1 2 3
cout << endl;	
for (int i = 0; i< 3; i++)
	cout << *(x++) << " ";//1 2 3
cout << endl;
for (int i = 0; i< 3; i++)
	cout << *(x + i) << " ";// unpredeictable
cout << endl;

结果会跑出: (在我的电脑上)

1 2 3
1 2 3 → 因为++之後，你已经不知道你的 x 指向哪?
0 3 3

在 array 中， [ ]的概念就像是 存取(指向) 第 n 个值，像是:

int x[3] = {1, 2, 3};
for (int i = 0; i < 3; i++)
	cout << x[i] << " "; // x[i] = *x(i + 1) 
for (int i = 0l i < 3; i++)
	cout << *(x + 1) << " "; // 1, 2, 3

使用 x[i] 其实跟＊(x + i) 是一模一样的，但是使用 x[i] 会比较直观好懂。

Instances

Instance:

incrementing array elements

#include<iostream>
using namespace std;

int main()
{
	int a[5] = {0};
	for(int i = 0; i < 5; i++)
		cin >> a[i];
	int* p = a;
    ///////////////////////
    for(int i = 0; i < 5; i++)
	{
		*p += 3;
		p++;
	}
    //////////////////////
	for(int i = 0; i< 5; i++)
		cout << a[i] << " ";
	return 0;
}

在这边，a 阵列每一项都会被 +3，做这件事的就是中间那一段。

Instance:

insertion sort 可见第 16 天的文章。

我们要排序一列数列

我们原来的策略是，左右各排一列数列，左边是已经排好顺序的(0 - n-2)，右边是还没排的(n - 1)。

简单说就是每一次要把(n - 1)插入到左边已排好的里面。

Pseudocode长这样:

insertionSort(a non-repetive array A, the array length n, an index cutoff < n)
// at any time, A_1~coutoff is sorted and A_(cutoff+1 ~ n) us unsorted
if A_cutoff+1 < A_1~coutoff
	let p be A[1]
else
	find p such that A_p-1 < A_cutoff+1 < A_p 
insert A_cutoff+1 to A_p and shift A_p~cutoff to A_p+1~coutoff+1
// 先存到 temp -> shift -> 再插入
if cutoff+1 < n
	insertionSort(A, n, cutoff + 1)

但如果今天我们想要先 sort 後面的A[1:n-1]，再把 A[0] 插进去，也是做得到。

Strategy: Given array, each time when we (recursively) invoke it, we pass a shorter array formed by elements from array[1] to array[n - 1], the second element to the last element.

implement:

#include<iostream>
using namespace std;

void insertionSort(int array[], const int n)
{
	if (n > 1)
	{
		insertionSort(array + 1, n - 1); //array+1 就是指向第二个element address 
		int num1 = array[0];
		int i = 1;
		for(; i < n; i++)
		{
			if(array[i] < num1)
				array[i - 1] = array[i];
			else
				break;
		}
		array[i - 1] = num1;
	}
}

Instance:

#include<iostream>
using namespace std;

int* firtNeg(int a[], const int n){
	for(int i = 0; i < n; i++){
		if (a[i] < 0)
			return &a[i];
	} // what if about a[i] > 0?
	return nullptr; // 当全部都大於 0
}
int main()
{
	int a[5] = {0};
	for(int i = 0; i < 5; i++)
		cin >> a[i];
	int* ptr = firstNeg(a, 5);
	if (ptr != nullptr)
		*ptr = -1 * *ptr;
	return 0; 
}

p - a 会得到甚麽?

a 就是储存第一个 element 的 address，p 是现在的 address，这样就可以找到那一个变数的 index 了。

我们在 firstNeg()里面，为什麽传入 const int n 却不传入 const int a[]呢?

主要是因为，你看看我们 main() 里面做了甚麽事情

我们先把 ptr 宣告成 firstNeg(a, 5)，但是在下一行又对 *ptr 做了其他的事情，在程序里面，因为 const 不能被更改，所以就会跑出错误