- 比較下面兩行程式碼：
- (第16行)：find(st.begin(), st.end(), i);
- (第20行)：st.find(i);
- std::find
- function in <algorithm>，執行一次find平均花費的時間，隨著n變大(linear search)，增加的很快，複雜度 O(n)。(未排序的資料結構，如vector，只能用這個。)
- std::set::find
- set的member function，使用binary search，複雜度 O(log(n))，速度快上許多。
- 【練習】LeetCode 1296. Divide Array in Sets of K Consecutive Numbers
- 使用multiset，用std::find會TLE，改用std::set::find可以AC。
Simulation code (credit: Amy Chou)
#include <iostream>
#include <ctime>
#include <cmath>
#include <set>
using namespace std;
int main() {
int n;
for (n=10; n<=100000; n*=10){
set<int> st;
for (int i=0; i<n; i++) st.insert(i);
clock_t t1, t2, t3;
t1 = clock();
for (int i=0; i<n; i++){
auto it = find(st.begin(), st.end(), i);
}
t2 = clock();
for (int i=0; i<n; i++){
auto it = st.find(i);
}
t3 = clock();
cout << "n = " << n << endl;
cout << (t2 - t1) / (t3 - t2) << endl;
}
return 0;
}
| n | t2-t1 | find() | t3-t2 | set.find() |
| 10 | 4 | 0.4 | 1 | 0.10 |
| 100 | 168 | 1.7 | 14 | 0.14 |
| 1000 | 10827 | 10.8 | 144 | 0.14 |
| 10000 | 952354 | 95.2 | 1707 | 0.17 |
| 100000 | 108432914 | 1084.3 | 19354 | 0.19 |
從multiset移除一個元素
- multiset允許重複元素存在
- 宣告 multiset<int> st
- (1) st.erase(val)：會把所有的val (一或多個)同時移除。
- (2) st.erase(st.lower_bound(val))：只移除一個val。
- (3) st.erase(st.find(val))：只移除一個val，與做法(2)結果相同，時間複雜度也一樣。