owned this note   changed 3 years ago  
Linked with GitHub

進階STL：

priorty_queue set pair

2021/12/03 電算社第十堂社課

萬能標頭檔
















#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(由大排到小)

標頭檔

#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

數學上的 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)

pair

類似數對，但裡面可以存不是數字的東西
可以搭配其他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
}

pair x vector x algorithm

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";   
    }
}

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










#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";
}
Select a repo