# C++ (?) 常用工具與概念 --- ## 前情提要 ---- ### 指標 ---- ### recap: declaration and basic usage ```cpp= int n = 3; int *ptr = &n; // 宣告一個pointer，指向n cout << ptr << " " << *ptr << endl; // ptr為n的位址，*ptr 為 n 的值 *ptr = 5; ``` ---- ### 指標的運算 + 任意兩個 pointer 變數，可以相減。 + 相減的值是位址的差 ```cpp= #include <iostream> using namespace std; int main() { int a = 5; int b = 20; int *ptr1 = &a; int *ptr2 = &b; cout << ptr1-ptr2 << endl; } ``` ---- ### 陣列是指標 重要的是，陣列每一項都存在**連續的記憶體位址**。 ```cpp= int arr[5] = {6, 2, 4, 3, 5}; cout << arr << " " << *arr << endl; ```  arr, arr+1, ..., arr+4 都是指標，arr 指向陣列的首項。 ---- ### 問題: 會輸出什麼? ```cpp= #include <iostream> using namespace std; void increment(int n) { n++; } int main() { int x = 5; cout << x << endl; increment(x); cout << x << endl; } ``` 事實上，被當成參數的變數，會被函數複製一遍，已經不是原本的變數了。除非... ---- ### macro (巨集) ```cpp= #include <iostream> using namespace std; #define PI 3.14159 #define add(a, b) a+b int main() { cout << PI << endl; cout << add(71, 22) << endl; } ``` ---- ### 會輸出什麼? ```cpp= #include <iostream> using namespace std; #define add(a, b) a+b int main() { int n = add(4, 5)*add(6, 7); cout << n << endl; } ``` 答案是41，why? --- ## Function ---- 最大/最小值 ```cpp= int a = 5, b = 10, c = 15; cout << min(a, b) << endl; cout << max(b, c) << endl; ``` ---- 交換值 ```cpp= int a = 5, b = 10; cout << a << b << endl; swap(a, b); cout << a << b << endl; a ^= b ^= a ^= b; //使用xor交換兩數的神秘方式(?) ``` By the way, swap也可以用來交換 兩個相同長度的陣列 ---- 次方 ```cpp= #include <iostream> #include <cmath> // to use power using namespace std; int main() { double result = pow(5.55, 3.66); cout << result; } ``` By the way, 除非你要計算非整數次方，不然我們通常會自己寫快速冪。原本的複雜度是 $O(n)$ ---- 對數(其實沒有很常用) ```cpp= #include <cmath> //為了使用log ... int a = 15; cout << log(a) << endl; // 以e為底 cout << __lg(a) << endl; // 以2為底，然後取下高斯 ``` ---- 二分搜 ```cpp= #include <iostream> #include <algorithm> // to use lowerbound/upperbound using namespace std; int main() { int arr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; int n = *lower_bound(arr, arr+11, 10); //首個>=10的元素 cout << n << endl; n = *upper_bound(arr, arr+11, 11); //首個>11的元素 cout << n << endl; } ```  ---- 將某區間變成特定值 ```cpp= #include <iostream> #include <algorithm> using namespace std; int main() { int arr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; fill(arr+1, arr+5, -1); // 把 arr 的 [1, 5) 變成 -1 for(int i = 0; i < 11; i++) cout << arr[i] << " "; } ```  ---- Something else ```cpp= #include <iostream> #include <cmath> #include <algorithm> using namespace std; int main() { double a = -12.34; a = abs(a); // 絕對值 cout << a << endl; cout << sqrt(a) << endl; // 開根號 int b = 33, c = 12; int GCD = __gcd(b, c); // 最大公因數 cout << GCD << '\n'; } ``` --- ## 非演算法，但很重要的東西 ---- ### 給定一個陣列 arr ```cpp! int arr[10] = {8, 7, 6, 5, 1, 10, 11, 13, 27, 2}; ``` 如何求出 arr[l] 到 arr[r] 這個區間的和? 每次要求的時候再暴力算? ---- ### 前綴和 多維護一個陣列，其第i項代表arr中第0~i項的和。 ```cpp= #include <iostream> using namespace std; int main() { int arr[10] = {8, 7, 6, 5, 1, 10, 11, 13, 27, 2}; int prefix_sum[10] = {0}; prefix_sum[0] = arr[0]; for(int i = 1; i < 10; i++) { prefix_sum[i] = prefix_sum[i-1] + arr[i]; } cout << prefix_sum[9]-prefix_sum[5] << endl; // 如果我們要求出 [l, r] 區間的和 // 可以直接使用 prefix_sum[r]-prefix[l-1] } ``` 複雜度: $O(n)$ ---- ### 如何在陣列區間加值? 可不可以用 $O(1)$ 實現？ ---- ### 差分 (補充) ```cpp= #include <iostream> using namespace std; int main() { int n = 5; int a[n] = {1, 2, 3, 4, 5}; int d[n]; d[0] = a[0]; for(int i = 1; i < n; i++){ d[i] = a[i] - a[i-1]; } int l = 1, r = 3, x = 10; d[l] += x; // 使得從 l 之後，都會加 x d[r + 1] -= x; // 從 r + 1 之後，不應該繼續加 x，所以減回 x // 1 11 1 1 -9 a[0] = d[0]; for(int i = 1; i < n; i++){ a[i] = a[i-1] + d[i]; } for(int i = 0; i < n; i++){ cout << a[i] << ' '; } } ``` --- ## 衛生教育 ---- ### What is Coding Style? + 就是撰寫程式的風格，對於編寫易讀、易維護的代碼非常重要。 + 對於變數命名、縮排、空格都有規定 + [Google C++ Style Guide](https://google.github.io/styleguide/cppguide.html) ---- ### Camel Case v.s Snake Case ```cpp= int itemCount; // camelCase int item_count; // snake_case // 以下是不好看的變數名稱 char aLpHaBeT = 'C'; //?? double i, j, k; // a little bit meaningless ``` ---- ### Add space and indent properly ```cpp= int sum = a + b; // Good int sum=a+b; // Bad ``` 請務必統一縮排的空格數目 ```cpp= void printMessage() { cout << "Hello, world!" << std::endl; int x; x = pow(7, 6); cout << x << endl; } ``` ----  --- ## Bye!