owned this note
owned this note
Published
Linked with GitHub
---
tags: 2021CRC
title: 進階STL：priorty_queue set pair
slideOptions:
transition: slide
theme:
---
# 進階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";
}
```
----
Google Drive
Gist
Clipboard
Sign in with Wallet
