# 進階STL： # priorty_queue set pair ### 2021/12/03 電算社第十堂社課 --- ### 萬能標頭檔 ---- ```cpp= #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 --- ## priority_queue ---- 會依照大小順序排列的queue(由大排到小) ---- 標頭檔 ```cpp= #include<queue> ``` ---- 宣告 ```cpp= priority_queue<type> pq; ``` ---- 功能 * pq.push() * pq.pop() * pq.top() * pq.empty() * pq.size() ---- ```cpp= #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（由小到大） ```cpp= priority_queue<int , vector<int> , greater<int> > pq; pq.push(6); pq.push(4); cout << pq.top(); ``` --- ## set ---- 數學上的 set： 一堆東西，不重複、沒有順序  C++ 裡的 set：會自己排序好 ---- 標頭檔 ```cpp= #include<set> ``` ---- ```cpp= #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) --- ## pair ---- 類似數對，但裡面可以存不是數字的東西 可以搭配其他STL使用(如vector) ---- 標頭檔 ```cpp= #include <tuple> ``` ---- 宣告 ```cpp= pair<type1 , type2> p; ``` ---- 初始化 ```cpp= pair<int, int> p = make_pair(8, 7); // p = (8, 7) ``` ```cpp= pair<int, int> p = {8, 7}; // p = (8, 7) ``` ---- 功能 `p.first` `p.second` ---- ```cpp= #include <iostream> #include <tuple> using namespace std; int main(){ pair<int, int> p = {1, 2}; cout << p.first << ' ' << p.second; // 1 2 } ``` ---- 多層pair ---- ```cpp= pair<type1, pair<type2, type3> > p; ``` ---- ```cpp= #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 } ``` --- ### pair x vector x algorithm ---- ```cpp= vector< pair<int, int> > vp; ``` ---- ```cpp= #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"; } } ``` --- ### OJ練習 考完期中考了:D 在考完當天，1892班只出了數學一科的成績， 好勝的同學們想要排出誰的分數高，誰的分數低！ 因次，他們決定使用c++ sort的方式進行。 他們想要製作出一張表，裡面記錄這20位同學，的座號和分數， 並且按照**成績由小到大**排序。 ---- 輸入說明：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 ---- ```cpp= #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"; } ``` ----