Intersection of two integer arrays

學習筆記 of Competitive Programming's Handbook by Antti Laaksonen (4.6)

求兩個整數陣列v1, v2 的交集，有三種方式可以實現：
1. 將其中一個陣列設成set，再比較另一個陣列的所有元素 （ O(nlogn) ）
2. 將其中一個陣列設成unordered_set，再比較另一個陣列的所有元素（ O(n) ）
3. 兩個陣列都做sorting，再一一比較各個元素（ O(nlogn) ）
    (p.s. sorting: O(nlogn)，其他: O(n))

set 與 unordered_set的差別在於，set奠基於平衡二元樹，unordered_set奠基於雜湊法，前者可保有順序與一些獨有函數功能，而後者效率較好

特別的是，單看複雜度，第二個方法是最快的，然而，實際操作卻發現複雜度為O(nlogn)的第三個方法才是最省時的！（三比二快了兩倍）
更好玩的是，雖然一和三都是O(nlogn)，三卻比一快了近十倍！
理由在於，雖然第三個方法是 O(nlogn)，卻只要在開始時做一次sorting，其他動作便都是線性的了
而第一個方法則因為要在整個程序中維持複雜的平衡二元樹的結構，需花費較多時間

以下以C++實作三種方法m1, m2, m3：
（p.s. 新學到的好用關鍵字：auto，用來迭代set或vector等結構很方便）
（關於auto可參考這篇好文章：C++ 程式語言 auto 自動變數類型語法教學與範例）

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
using namespace std;

set<int> v3; //intersection

void m1(vector<int> &v1, vector<int> &v2){
    set<int> s;
    for (auto it : v1) s.insert(it);
    
    for (auto it : v2)
        if (s.count(it)) v3.insert(it);
}

void m2(vector<int> &v1, vector<int> &v2){
    unordered_set<int> s;
    for (auto it : v1) s.insert(it);
    
    for (auto it : v2)
        if (s.count(it)) v3.insert(it);
}

void m3(vector<int> &v1, vector<int> &v2){
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    
    for (auto it1 = v1.begin(), it2 = v2.begin();
         it1 != v1.end() && it2 != v2.end(); it1++) {
        while (*it1 > *it2) it2++;
        if (*it1 == *it2) {
            v3.insert(*it1);
            it2++;
        }
    }
}

void print_v3(){
    for (auto it : v3) cout << it << " ";
    cout << endl;
}

int main(int argc, const char * argv[]) {
    vector<int> A = {4,2,5,9,7}, B = {5,2,3,9};
    m1(A, B);
    print_v3(); v3.clear();
    m2(A, B);
    print_v3(); v3.clear();
    m3(A, B);
    print_v3();
    return 0;
}