- 比較下面兩行程式碼:
- (第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)結果相同,時間複雜度也一樣。