【筆記】std::find vs. std::set::find

  • 比較下面兩行程式碼:
    • (第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;
}
nt2-t1find()t3-t2set.find()
1040.4 10.10
1001681.7 140.14
10001082710.8 1440.14
1000095235495.2 17070.17
1000001084329141084.3 193540.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)結果相同,時間複雜度也一樣。

分享本文 Share with friends