前面提到了函式的概念，相信大家已經都對函式有了基本的了解，也在上一章中詳細介紹了 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';
}
}
}
|