STL 容器

STL 的宣告方式都是 資料結構 <資料型態> 名字！
資料型態都可以自己替換

vector

動態長度的陣列! 可以配合 range-based for loop 使用。
雖然是動態長度，但不代表可以隨便戳大小以外的 index 喔！
動態長度只是代表你可以 push_back, pop_back 改變陣列大小而已

複雜度：

插入: O(n)
刪除: O(n)
搜尋: O(n)

vector <int> a(100, 3); // 長度為 100，初始值都為 3 的 vector
vector <vector<int> > b(3, vector <int> (2, -1)); // 3 * 2 ，初始 -1 的二維 vector 

for(int x : a) cout << x << ' '; // 印出裡面所有東西
sort(a.begin(), a.end()); // 排序

a[2] = 1;
a.push_back(2); // 最後面加上一個 2 (所以是第101個元素)
a.pop_back();  // 移除最後一個元素
int n = a.size(); // 長度

map

map 可以用來將一個 key map 到一個 value
key 可以是 int 以外的資料型態！　
要遍歷一次 map 的話需要用到 map 自己的 iterator，打出來很長
for (map <string,int>::iterator it = mp.begin();it != mp.end();it++)
我們下面直接用 auto 配上 range-based for loop 就能很輕鬆的跑過去!

複雜度：

插入: O(logn)
刪除: O(logn)
搜尋: O(logn)

map <string,int> mp; // key: string, value: int

mp["Hi"] = 2;
mp.erase("Hi"); // 刪除

for(auto it : mp){ // 迴圈跑過 map 裡面的值
    cout << it.first << ' ' << it.second << '\n';
    // .first 是 key, .second 是 value
}

if(mp["123"]) cout << "YES"; 
else cout << "NO";
// 輸出 NO

auto it = mp.lower_bound("Hi"); // 是找 key，不是 index! 沒找到會回傳 mp.end()
mp.erase(it); 

set / multiset

會幫你把裡面的東西排序好。每個操作都是 O(logn)的時間。
set 不能有重複的元素，multiset 可以。
如果你在 set 加入兩個一樣的元素，程式不會報錯，就只是裡面只會有一個。
而跟 map 一樣，要取用 set 裡面的東西需要用到他的 iterator，
要取得 iterator 的值就要加一個 * (例如下面的 s.begin(), s.end())

複雜度：

插入: O(logn)
刪除: O(logn)
搜尋: O(logn)

以下示範 set ，multiset 的用法也都一樣

set <int> s;
multiset <int> ms; 

s.insert(2); // 插入 2
s.insert(3); // 插入 3
s.erase(2); // 刪除 2

cout << *s.begin(); // 輸出 set 的最前面 （最小）因為裡面是排序好的
cout << *(--s.end()); // 輸出最大 要-1 因為 s.end() 不存在，是前一個才是最後一個

auto it = s.lower_bound(2); // 第一個比 2 大的元素 沒找到會回傳 s.end()
cout << *it;
s.erase(it); 

auto it = s.find(2); // 沒找到會回傳 s.end()
cout << *it;

要注意的是 multiset 用 erase 一個值的會把裡面所有的那個值都刪除掉
要只刪除一個的話要用刪 iterator 的方式

multiset <int> ms;
ms.insert(2);
ms.insert(2);
ms.insert(2);

ms.erase(ms.find(2)); // 刪除一個
ms.erase(2); // 刪除全部的 2

queue

一個先進先出 (First in First Out) 的資料結構，很像是一個排隊的結構，先進去的人會先出來。
每次只能取得最前面的元素！不能修改！

複雜度:

插入: O(1)
刪除: O(1)
搜尋: O(n)

queue <int> q; // 宣告裡面存 int 的 queue
queue <pair<int,int> > q2; // 宣告裡面存 pair 的 queue

q.pop(); //移除最前面的元素
q.push(2); // 在最後面加入一個元素
int n = q.size(); // 長度
int f = q.front(); // 隊列最前面的元素

priority_queue

跟 queue 不一樣! 每次可以取得最大值! 也可以自己定義甚麼排序的定義，可以自己寫 overload operator

複雜度:

插入: O(logn)
刪除: O(logn)
搜尋: O(nlogn)

priority_queue <int> pq; // 從大排到小
priority_queue <int, vector<int>, greater<int> > pq2; // 最小值優先的 priority_queue (pq)
int n = pq.size(); // 大小

while(!pq.empty()) { // 當 pq 不是空的
    int x = pq.top(); // pq 的最大值
    pq.pop(); // 移除最大值
    x--;
    if(x) pq.push(x); // 加入 x
}

struct point{
    int x, y;
};

struct cmp {
    bool operator(point a, point b){
        return a.x < b.y;
    }
    // 這個 function 一定要叫做 opeartor 喔
}

int main(){
    priority_queue <point, vector<point>, cmp> pq;
}

要注意的是 priority_queue 判定誰比較優先是判斷 !cmp，所以排序的方法要反過來。
例如你想要最大的優先的話，就應該定義 cmp 是小的優先。