pointer 是一種變數，而且就跟 array variable 一樣，他也是用來儲存記憶體位置的一個變數。
type pointed* pointer name;
type pointed *pointer name
兩種差別是 * 黏在誰的身上。
Instance:
int *ptrInt;
double* ptrDou;
Pointer 可以 point 到任何一種 type 上，但是要記得，同一種 type 只能 point 到那一種 type 的變數上。
在 32 bit 中， 一個 pointer 是 4 bytes，
在 64 bit 中， 一個 pointer 是 8 bytes。
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
分為兩種:
&: The address-of operator, returns a variable's address.
*: The dereference operator, returns the pointed variable (return 他的值).
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 的地方。
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 的時候，& 不等於 平常用的 &
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 解決這種問題。
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 裡面 變數會消失但是你之後還想要繼續使用這個變數的時候。)
那如果改成 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?
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。
為什麼要有指標的理由!
在以前，我們在宣告一個 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;
}
但是 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 會一直累積，所以如果你打開工作管理員看記憶體的空間就會不斷地被占滿。
它是一個 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。
!寫程式好習慣!
在靜態配置中，我們可以輕鬆的宣告一個二維的陣列
但在動態配置中，我們 也做得到。
一樣也可以把她想成有 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 給印出來而已。
Pointer 其實就跟 array 是差不多的，他們都
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 31 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] 會比較直觀好懂。
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] 插進去，也是做得到。
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 不能被更改，所以就會跑出 錯誤
When should we use pointers?
最近被程式搞的內心頗憔悴:
希望我 26 歲的時候不會變成 Dave。
iThome鐵人賽
看影片追技術