## 定義
所謂的 STL 就是 Standard Template Library，裡面有很多好用的資料結構與函數
比如之後會單獨拉出來的 stack 和 queue，還有下面會介紹的 vector 等等
這些資料結構都會介紹初始化方式、常用函式、資料結構的特色等等
因為我們都用 `#include<bits/stdc++.h>`，所以不需要再特別載入標頭檔
## vector(向量)
vector 可以簡單理解成可以在尾端動態增加/刪減元素的 array，先介紹初始化的方式

#include<bits/stdc++.h>
using namespace std ;

int main() {
    vector<int> v1 ; // v1 = {} size = 0
    vector<int> v2(3) ; // v2 = {x, x, x}, size = 3
    vector<int> v3(2, 1) ; // v3 = {1, 1} size = 2
    vector<int> v4 = {1, 2, 3, 4} ; // v4 = {1, 2, 3, 4} size = 4
    
    return 0 ;
}

還有很多種初始化的方式，但基本上只要記住這些就可以了

---
iterator 是一種抽象指標，可以用來存取 STL 資料結構的元素，以下是搭配 vector 的範例

#include<bits/stdc++.h>
using namespace std ;

int main() {
    vector<int> v = {1, 2, 3, 4, 5} ;
    
    auto it = v.begin() ; // vector<int>::iterator it ;
    for (;it!=v.end();it++)
        cout << *it << ' ' ;
    // next(it) -> it+1, prev(it) -> it-1
    
    it = find(v.begin(), v.end(), 2) ;
    int position = it - a.begin() ;
    if (it == v.end()) // not exist
        cout << "2 isn't in v\n" ;    
    else
        cout << "The position of 2 in v is " << position << '\n' ;
    
    v.insert(v.begin()+1, 6) ; // 1 6 2 3 4 5
    vector<int> v1 = {9, 10} ;
    v.insert(v.end(), v1.begin(), v1.end()) ;
    
    v.erase(v.begin()+2) // erase v[2] ;
    v.erase(v.begin()+1, v.begin()+3) ; // erase v[1]~v[3] ;
    
    return 0 ;
}

以上的 `v.begin()` 就是 v 的第一個元素地址，`v.end()` 是"最後一個元素"往後一個的地址
但 insert 和 erase 功能不太常用，只是做為 iterator 的範例

接著就是大小、遍歷、排序、翻轉等等操作的實現

#include<bits/stdc++.h>
using namespace std ;

int main() {
    vector<int> v1 ; // v1 = {}, size = 0
//    vector<int> v2(3) ; // v2 = {x, x, x}, size = 3
//    vector<int> v3(2, 1) ; // v3 = {1, 1}, size = 2
    vector<int> v4 = {4, 3, 2, 1} ; // v4 = {4, 3, 2, 1}, size = 4
    
    v1.push_back(-1) ; // v1 = {-1} size = 1
    cout << v1[0] << ' ' << v1.size() << '\n' ; // -1 1
    v1.clear() ; // v1 = {}, size = 0
    
    int len = v4.size() ;
    for (int i=0;i<len;i++) // 照順序輸出
        cout << v4[i] << ' ' ;
    cout << '\n' ;
    
    for (auto it=v4.begin();it!=v4.end();it++) // 照順序輸出
        cout << *it << ' ' ;
    cout << '\n' ;
    
    sort(v4.begin(), v4.end()) ; // 排序
    for (int i=0;i<len;i++)
        cout << v4[i] << ' ' ;
    cout << '\n' ;
    
    reverse(v4.begin(), v4.end()) ; // 翻轉
    for (int i=0;i<len;i++)
        cout << v4[i] << ' ' ;
    cout << '\n' ;
    
    v4.clear() ;
    return 0 ;
}

## pair / tuple
先聲明 tuple 不是 STL 的一部分，但因為在使用上可以當作 pair 的延伸，所以在這邊一起講
pair 可以同時儲存兩個不同 type 的元素，tuple 可以儲存多個不同 type 的元素
而且它們兩個都可以被比較，兩個結構的比較方式是先比較第 $0$ 項，再比較第 $1$ 項，以此類推

#include<bits/stdc++.h>
using namespace std ;
#define FF first
#define SS second

int main() {

    pair<int, int> Pii = {1, 2} ; // 初始化
    pair<int, string> Pii2 = make_pair(3, "abcd") ;

    cout << Pii.FF << ' ' << Pii.SS << '\n' ;
    cout << Pii2.FF << ' ' << Pii2.SS << '\n' ;

    tuple<int, int, int> T1(1, 2, 3) ; // 初始化
    tuple<char, char, int, int> T2 = make_tuple('a', 'b', 8, 9) ;

    cout << get<1>(T1) << '\n' ; // 取出第 1 項 (index 0 ~ n-1)

    char c1, c2 ;
    int n1, n2 ;
    tie(c1, c2, n1, n2) = T2 ; // 將 c1, c2, n1, n2 設為 T2 裡的元素
    cout << c1 << ' ' << c2 << ' ' << n1 << ' ' << n2 ;

    return 0 ;
}

由於這種可以被比較的方式，sort 也可以用在這兩個結構上面
當然在多個不同情況下，struct

## set (集合) / unorded_set
所謂的集合就是數學意義上的集合，裡面的元素不會重複，不過這裡的 set 會自動排序

#include<bits/stdc++.h>
using namespace std ;

int main() {
    set<int> st ; // 初始化
    st.insert(1) ;
    st.insert(2) ;
    st.insert(3) ;
    st.insert(3) ;

    for (int num: st) // 遍歷輸出
        cout << num << ' ' ;
    cout << '\n' ;

    if (st.find(1) != st.end()) // 查找元素方式
        cout << "Can find 1 in st\n" ;
    st.erase(2) ;

    for (int num: st) // 遍歷輸出
        cout << num << ' ' ;
    cout << '\n' ;
    for (auto it=st.begin();it!=st.end();it++) // 遍歷輸出
        cout << *it << ' ' ;
    cout << '\n' ;
    
    // 基本上 unorded_set 跟 set 用法一樣
    // 但順序是打亂的，不會照值大小排序

    return 0 ;
}

## priority_queue (優先 queue)
(建議先看過 queue 和樹論中的 heap 再來讀)
是一種特殊的 Queue，其中的每個元素都有一個優先權，取出時會選擇優先權最高的那個元素
實作方法最常用的是 Heap，在樹論有介紹過，當時只有最大最小值，這裡可以調整
enqueue、dequeue 的時間複雜度都是 $O(log\ n)$

#include<bits/stdc++.h>
using namespace std ;

struct cmp { // 比較
    bool operator()(const int &a, const int &b) const {
        return a > b ;
    }
};

int main() {
    priority_queue<int> pq1 ; // 大到小 top 為最大
    priority_queue<int, vector<int>, greater<int>> pq2 ; // 小到大 top 為最小
    priority_queue<int, vector<int>, cmp> pq3 ; // 小到大 top 為最小

    pq1.push(1) ;
    pq1.push(2) ;
    cout << pq1.top() << '\n' ;

    pq3.push(5) ;
    pq3.push(6) ;
    cout << pq3.top() << '\n' ;

    while (!pq1.empty()) { // or while(pq1.size())
        cout << pq1.top() << ' ' ;
        pq1.pop() ;
    }
    cout << '\n' ;

    while (!pq3.empty()) {
        cout << pq3.top() << ' ' ;
        pq3.pop() ;
    }
    cout << '\n' ;

    return 0 ;
}

由於用法比較特別，目前只要記起來就好，如果要更多原理可以去看 C++ 的 STL document
## map / unorded_map
所謂的 map 具有 key : value，就跟數學中的 function 的概念一樣，f(key) = value
在 map 當中會以 pair 的形式去儲存 (key, value)，且 key 會由小到大排序

#include<bits/stdc++.h>
using namespace std ;

int main() {
    map<int, int> mp1 ; // 初始化
    map<char, int> mp2 ;
    mp1[2] = 7 ;
    mp1[1] = 8 ;
    mp2['a'] = 5 ;
    mp2['b'] =  10 ;

    for (auto it=mp1.begin();it!=mp1.end();it++) // 遍歷 mp1
        cout << it->first << ' ' << it->second << '\n' ;

    if (mp2.find('c') != mp2.end()) // 找 mp2 裡有沒有 c
        cout << "c is a key in mp2.\n" ;
    else
        cout << "c isn't a key in mp2.\n" ;

    mp2.erase('b') ; // 刪除 mp2 裡面的 key: b
    for (auto it=mp2.begin();it!=mp2.end();it++) // 遍歷 mp2
        cout << it->first << ' ' << it->second << '\n' ;


    // unorded_map 跟 map 用法不太一樣
    unordered_map<int, int> mp3 ; // 初始化
    unordered_map<char, int> mp4 = {{'a', 6}, {'b', 12}} ;
    mp3.insert({2, 9}) ;
    mp3.insert({3, 10}) ;

    for (auto it=mp4.begin();it!=mp4.end();it++) // 遍歷 mp4
        cout << it->first << ' ' << it->second << '\n' ;
    // 其餘其餘功能一樣就不展示
    return 0 ;
}