#include <bits/stdc++.h>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
// and more

• 引入大部分的常用標頭檔
• 部分比賽和 Online Judge 不支援這個標頭檔，測機務必先測試可否使用
• 占用較大的記憶體空間，限制較緊時應避免使用此標頭檔

循序存取 (Sequential Access)
V.S.
隨機存取 (Random Access)

• 此隨機非彼隨機
• 在一條東西上移動時，花費的時間不隨距離增長
• 瞬間移動
• Youtube vs. CD player
• 可隨機存取：陣列、vector、deque
• 不可隨機存取：set、map、stack、priority_queue

會依照大小順序排列的queue(由大排到小)

標頭檔

#include<queue>

宣告

priority_queue<type> pq;

功能

• pq.push()
• pq.pop()
• pq.top()
• pq.empty()
• pq.size()

#include <iostream>
#include <queue>
using namespace std;
int main(){
    priority_queue<int> pq;
    pq.push(2); //前[2]後
    pq.push(1); //前[2, 1]後
    pq.push(3); //前[3, 2, 1]後
    pq.pop(); //前[2, 1]後
    cout << pq.top(); // 2
    cout << pq.empty(); // 0
    cout << pq.size(); // 2
}

greater（由小到大）

priority_queue<int , vector<int> , greater<int> > pq;
pq.push(6);
pq.push(4);
cout << pq.top();

數學上的 set：
一堆東西，不重複、沒有順序

C++ 裡的 set：會自己排序好

標頭檔

#include<set>

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    set<int> s;
    s.insert(4); // s = {4}
    s.insert(5); // s = {4, 5}
    s.insert(3); // s = {3, 4, 5}
    s.erase(4);  // s = {3, 5}
    
    cout << s.size() << '\n';   // -> 2
    cout << s.empty() << '\n';  // -> 0 (false)
    
    // 檢查set裡面有沒有某個值
    cout << s.count(4) << '\n'; // -> 0
    cout << s.count(3) << '\n'; // -> 1
    s.clear();      // s = {}
    cout << s.empty() << '\n';  // -> 1 (true)  
}

• s.empty()
• s.size()
• s.clear()
• s.insert(a)
• s.erase(a)

• s.begin()
• s.end()
• s.count(a)
• s.lower_bound(a)
• s.upper_bound(a)

類似數對，但裡面可以存不是數字的東西
可以搭配其他STL使用(如vector)

標頭檔

#include <tuple>

宣告

pair<type1 , type2> p;

初始化

pair<int, int> p = make_pair(8, 7);
// p = (8, 7)

pair<int, int> p = {8, 7};
// p = (8, 7)

功能
p.first
p.second

#include <iostream>
#include <tuple>
using namespace std;
int main(){
    pair<int, int> p = {1, 2};
    cout << p.first << ' ' << p.second; // 1 2
}
 

多層pair

pair<type1, pair<type2, type3> > p;

#include <iostream>
#include <tuple>
using namespace std;
int main(){
    pair<int, pair<int, int> > p = {1, {2, 3}};
    /*
    p.first = 1
    p.second.frist = 2
    p.second.second = 3
    */
    cout << p.first << ' ' << p.second.first << ' ' << p.second.second; // 1 2 3
}

vector< pair<int, int> > vp;

#include<bits/stdc++.h>
using namespace std;
 
vector< pair<int,int> > v(5);
 
int main()
{
    v[0].first = 1;    v[0].second = 2;
    v[1] = make_pair(1,5);
    v[2] = make_pair(3,4);
    v[3] = make_pair(3,6);
    v[4] = make_pair(5,4);
    
    sort(v.begin() , v.end());
    
    for(int i=0 ; i<5 ; i++)
    {
        cout << v[i].first << " " << v[i].second << "\n";   
    }
}

輸入說明：20位同學的座號（左）以及數學成績（右）
輸出說明：排列完的座號以及成績

1 45
2 54
3 54
4 23
5 86
6 24
7 77
8 96
9 56
10 76
11 86
12 45
13 87
14 45
15 87
16 8
17 57
18 98
19 100
20 34

我是防雷頁:D

#include<bits/stdc++.h>
using namespace std;
vector< pair<int,int> > v(1e5); // 10^5
int main()
{
    for(int i=0 ; i<20 ; i++)    cin >> v[i].second >> v[i].first;   
    sort(v.begin() , v.begin()+20);
    for(int i=0 ; i<20 ; i++)    cout << v[i].second << " " << v[i].first << "\n";
}