前面提到了函式的概念,相信大家已經都對函式有了基本的了解,也在上一章中詳細介紹了 sort 這個函式的用法。今天,將要介紹的是一些常用的 C++ 的內建函式。適當的使用內建函式,不僅可以減少出 bug 的機會,更可以增加程式的可讀性,並且通常具有良好的時間複雜度。因此,在了解背後原理的前提下,請多多利用內建函式。
這裡的函式,在第一眼時,可能不會覺得它很好用,或是不知會在什麼情況下用到。可以等一陣子以後,再回來看看有哪些常常需要的功能,其實是有內建函式的喔!
min/max
用法:min(a,b) 回傳 a, b 中較小者。若要傳入三個以上的值,則須用大括號包住。
範例:
1 2 3
| int a = 5, b = 10, c = 15; cout << min(a, b) << '\n'; cout << max({a, b, c}) << '\n';
|
注意事項:比較的值型態需相同,即使 long long 跟 int 也不能比,可以在 int 前加上 (long long) 或乘上 1LL 以強制轉型。
1 2 3 4 5 6
| long long a = 10; int b = 15;
cout << max(a, b) << '\n'; cout << max(a, (long long)b) << '\n'; cout << max(a, 1LL*b) << '\n';
|
abs
用法:abs(x) 回傳 x 的絕對值,型態與 x 相同。
範例:
1 2 3
| int a = 10; double b = -1.546; cout << abs(a) << abs(b) << '\n';
|
swap
用法:交換兩數。swap(a, b)後,a、b 互換,十分常用。
範例:
1 2 3
| int a = 3, b = 4; swap(a, b); cout << a << b << '\n';
|
注意事項:兩個長度相同的 array 也可以交換,但複雜度是 $O(N)$。
1 2 3 4 5 6
| int arr[] = {3,1,4,2};
int main(){ sort(arr, arr+4); for(int i=0;i<4;i++) cout << arr[i] << '\n'; }
|
sqrt
用法:sqrt(x) 得到 x 開根號後的值。型態與 x 相同,複雜度 $O(logx)$。
範例:
1 2 3
| int x = 5; double y = 45.1321; cout << sqrt(x) << " " << sqrt(y) << '\n';
|
pow
用法:pow(a,b)回傳 a 的 b 次方。複雜度根據底層結構不同,會有差異,暫時把它當成$O(1)$或$O(log)$等級的就好。但因為它是以浮點數進行運算,存在誤差,因此在整數世界不常使用。
範例:
1 2 3 4
| int x = 3, y = 5; double a = 1.256, b = 1234.456 cout << pow(x, y) << '\n'; cout << pow(a, b) << '\n';
|
注意事項:整數次方我們通常使用自己寫的快速冪技巧,不會使用pow函數。pow函數僅在小數次方使用。
__gcd
用法:__gcd(a, b)回傳 a 與 b 的最大公因數,複雜度 $O(log max(a, b))$。
範例:
1 2
| int x = 3, y = 5; cout << __gcd(x, y) << '\n';
|
__lg
用法:__lg(x) 回傳 x 以 2 為底的對數值取整,輸入必須是整數。複雜度$O(logx)$。
範例:
1 2
| int x = 50; cout << __lg(x) << '\n';
|
log
用法:log(x) 回傳 x 以 e 為底的對數值,是浮點數運算,複雜度$O(logx)$。
範例:
1 2
| double x = 50.456; cout << log(x) << '\n';
|
注意事項:
以 10 為底的 log 值可用 log10(x) 函數,其餘底則可使用對數基礎換底公式求得。
sort
用法:sort(a, b) 代表把從 a 位置(包含)到 b 位置(不含)之間的元素由小到大排序,詳細用法請見0-13。
範例:
1 2 3 4 5 6
| int arr[] = {3,1,4,2};
int main(){ sort(arr, arr+4); for(int i=0;i<4;i++) cout << arr[i] << '\n'; }
|
reverse
用法:reverse(a, b) 代表把從 a 位置(包含)到 b 位置(不含)之間的元素反轉,常用於字串。
範例:
1 2 3 4 5 6
| int arr[] = {3,1,4,2};
int main(){ reverse(arr+1, arr+4); for(int i=0;i<4;i++) cout << arr[i] << '\n'; }
|
min_element / max_element
用法:min_element(a, b) 回傳從 a 位置(包含)到 b 位置(不含)之間的最小值的指標,可用*加於其之前以得到值。
範例:
1 2 3 4 5 6
| int arr[] = {3,4,1,2};
int main(){ cout << *min_element(arr, arr+4) << '\n'; cout << min_element(arr, arr+4) - arr << '\n'; }
|
fill
用法:fill(a, b, c) 將 a 位置(包含)到 b 位置(不含)之間的所有元素全部變成 c。
範例:
1 2 3 4 5 6
| int arr[] = {3,4,1,2};
int main(){ fill(arr, arr+3, 321); for(int i=0;i<4;i++) cout << arr[i] << '\n'; }
|
lower_bound / upper_bound
用法:
lower_bound(a, b, c) 回傳在 a 位置(包含)到 b 位置(不含)之間第一個大於等於 c 的元素的位置。
upper_bound(a, b, c) 回傳在 a 位置(包含)到 b 位置(不含)之間第一個大於 c 的元素的位置。
需在由小到大排列好的陣列中才可使用。
若回傳的值是 b,代表沒有符合的元素。
同樣,可透過*取值。
範例:
1 2 3 4 5 6 7 8 9
| int arr[] = {3,5,1,2};
int main(){ sort(arr, arr+4); cout << *lower_bound(arr, arr+4, 3) << '\n'; cout << *lower_bound(arr, arr+4, 2) << '\n'; cout << *upper_bound(arr, arr+4, 3) << '\n'; cout << *lower_bound(arr, arr+4, 6) << '\n'; }
|
練習
TOJ 55
TOJ 47
##
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| #include<bits/stdc++.h> #define ll long long using namespace std; int n, m; int arr[1000005];
int main(){ ios::sync_with_stdio(0), cin.tie(0); cin >> n; for(int i=1;i<=n;i++) cin >> arr[i]; sort(arr+1, arr+1+n); cin >> m; for(int i=1,x;i<=m;i++){ cin >> x; cout << upper_bound(arr+1, arr+1+n, x) - lower_bound(arr+1, arr+1+n, x) << '\n'; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include<bits/stdc++.h> #define ll long long using namespace std; int n, m; int arr[1000005];
int main(){ ios::sync_with_stdio(0), cin.tie(0); cin >> n; for(int i=1;i<=n;i++) cin >> arr[i]; sort(arr+1, arr+1+n); cin >> m; for(int i=1,x;i<=m;i++){ cin >> x; int *big = lower_bound(arr+1, arr+1+n, x); int *small = big-1; if(*big == x) cout << x << '\n'; else{ if(small == arr) cout << "no "; else cout << *small << " "; if(big == arr+1+n) cout << "no\n"; else cout << *big << '\n'; } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include<bits/stdc++.h> #define ll long long using namespace std; int n, m; int arr[1000005];
int main(){ ios::sync_with_stdio(0), cin.tie(0); cin >> n; for(int i=1;i<=n;i++) cin >> arr[i]; sort(arr+1, arr+1+n); cin >> m; for(int i=1,x;i<=m;i++){ cin >> x; if(*lower_bound(arr+1, arr+1+n, x) == x) cout << x << '\n'; else{ if(x < arr[1]) cout << "no "; else cout << *(lower_bound(arr+1, arr+1+n, x)-1) << " "; if(x > arr[n]) cout << "no\n"; else cout << *(lower_bound(arr+1, arr+1+n, x)) << '\n'; } } }
|