# C to C++
## I/O
```c++=
#include <iostream>
int main() {
// 停止 C++ 的輸入輸出 stream 與 C-style (fprintf) 同步，
// 可以加速輸入輸出，缺點是不可以混用兩者。
std::ios_base::sync_with_stdio(0);
// std::cin 是有 tie 著 std::cout：這會在每次輸入時 flush 輸出，造成效能負擔。
std::cin.tie(0);
}
```
不用像C那樣printf/scanf，直接cin/cout就好，注意方向不一樣還有cout不會幫你加空格
```c++=
int main(){
int c;
cin >> c; //讀一個整數c
double d;
cin >> d;
cout << c << ' ' << d << '\n';
}
```
## struct
可以告訴程式怎麼樣做兩個struct的比較/加減
```c++=
#include<bits/stdc++.h>
using namespace std;
struct axis
{
double x,y; //struct 裡面本來有的東西
bool operator < (const axis &b) const{ //比兩個向量的長度
return x*x+y*y<(b.x*b.x)+(b.y*b.y);
}
axis operator + (const axis &b) const{ //比兩個向量的長度
axis ret;
ret.x=x+b.x;
ret.y=y+b.y;
return ret;
}
};
int main(){
axis a={3.5,6.4}; //有點投機取巧的寫法，但很快
axis b={1.6,-2.9};
cout << (a<b) << '\n';
cout << (a+b).x << ' ' << (a+b).y << '\n';
}
```
## sort
不用像qsort那樣要寫兩行的compare function，直接比較就好。而且保證複雜度nlogn。也可以自訂義比較函數
```c++=
bool cmp(int a,int b){
return a>b;
}
int main(){
int a[5]={1,5,4,2,3};
sort(a,a+5);
sort(a,a+5,cmp)//由大到小
sort(a+1,a+4); //排a[1]~a[3]
}
```
對struct也可以寫函式好好排
```c++=
struct Point {
int x,y;
};
bool cmp(int a,int b){
if(a.x==b.x) return a.y<b.y;//x一樣就比y
return a.x<b.x;//否則比x
}
int main(){
Point a[5]; //這裡不用再寫struct Point
for(int i=0;i<5;i++) cin >> a[i].x >> a[i].y;
sort(a,a+5,cmp);//要把比較函式傳進去
for(int i=0;i<5;i++) cout << a[i].x << ' ' << a[i].y << "\n";
}
```
# STL
## pair
把兩個相同型態的變數綁在一起，用first和second表示。定義好的大小關係是先比第一個再比第二個。
```c++=
int main(){
pair<int,int> p1={3,5}; //第一種宣告方式
p2=make_pair(10,2); //第二種
cout << (p1<p2) << '\n';
cout << p1.first << ' ' << p1.second << '\n';
pair<int,double> p3={1,4.3};//也可以放不同型態
}//{1,4,3,5,2} => {(1,1),(4,2),(3,3),(5,4),(2,5)}
```
## vector
可變長的陣列，不用像C那樣malloc。
### 宣告
```c++=
int main(){
vector<int> v; //空的vector，要注意這時候不能戳v[0]之類的
vector<int> v(10); //像陣列的int v[10];
vector<int> v(10,1); //宣告長度為10的陣列，並把值都初始化成1
//vector<int> v[10];這個寫法不是宣告一個長度為10的vector，是宣告10個空的vector
}
```
### 插入(push_back)
```c++=
int main(){
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(2);
cout << v.size() << '\n'; //輸出vector的大小
cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';
}
```
### 刪除(pop_back)
```c++=
int main(){
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(2);
v.pop_back(); //括號不需要傳東西進去
cout << v.size() << '\n'; //輸出vector的大小
cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';
}
```
### 輸出vector裡面的東西
```c++=
int main(){
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(2);
cout << v.size() << '\n'; //輸出vector的大小
for(int i=0;i<v.size();i++) cout << v[i] << ' ';//第一種
cout << '\n';
for(int i:v) cout << i << '\n';//第二種
}
```
### 其他常用的寫法
```c++=
int main(){
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(2);
cout << v.size() << '\n'; //輸出vector的大小
cout << v.back() << '\n'; //輸出vector的最後一個東西
cout << v.empty() << '\n'; //vector是不是空的
sort(v.begin(),v.end()); //排序vector裡面的東西
reverse(v.begin(),v.end()); //反轉vector
}
```
在存樹或圖的時候常用(adjacancy list)，因為不確定一個點會有幾個child，開vector可以避免開出int a[N][N]大小的陣列。
```c++=
vector<int> v[10];
int main(){
for(int i=0;i<m;i++){
int c,d;
cin >> c >> d;
v[c].push_back(d); //d在c的adjacancy list裡面
v[d].push_back(c); //c在d的adjacancy list裡面
}
}
```
好用的連結：https://cplusplus.com/reference/vector/vector/
## string
在C裡面string本身就是一個字元vector，所以使用方式完全跟vector一樣。也可以像讀%s一樣直接cin字串。比較特別的是可以用s.size()在O(1)的時間知道字串長，不用使用笨笨O(N)的strlen。還有字串可以用>,<, ==直接比較，不需要使用strcmp。也可以直接使用字串加法
```c++=
string s1="abbbb";
string s2="ccc";
cout << s1==s2 << '\n';
cout << s1+s2 << '\n';
cout << s1.size() << '\n';
s1.pop_back();//刪除最後一個字元
s1.push_back('a');//加入a
```
## queue
只有push跟pop，push就是從後面塞東西，pop就是從前面拿東西。沒辦法像vector一樣看queue裡面的第幾個。
```c++=
int main(){
queue<int> q;
q.push(3);
q.push(5);
cout << q.front() << '\n'; //q的前面(第一個要被pop的東西)
q.pop();//只會把最前面的東西pop掉，不會回傳被pop的值
//注意在用q.front(),q.pop()之前要先檢查q是不是empty
cout << q.front() << '\n';
cout << q.empty() << '\n'; //q是不是空的
cout << q.size() << '\n'; //q的大小
}
```
[queue練習](https://neoj.sprout.tw/problem/37/)
[BFS練習](https://zerojudge.tw/ShowProblem?problemid=a982)
## stack
一樣只有push跟pop，都是從stack上面放/拿走東西。注意stack的最上面不是叫front而是top
```c++=
int main(){
stack<int> st;
st.push(3);
st.push(5);
cout << st.top() << '\n'; //st的上面(第一個要被pop的東西)
st.pop(); //只會把最上面的東西pop掉，不會回傳被pop的值
//注意在用st.top(),st.pop()之前要先檢查st是不是empty
cout << st.front() << '\n';
cout << st.empty() << '\n'; //st是不是空的
cout << st.size() << '\n'; //st的大小
}
```
[stack練習1](https://neoj.sprout.tw/problem/36/)
[stack練習2](https://zerojudge.tw/ShowProblem?problemid=c123)
[stack練習3](https://zerojudge.tw/ShowProblem?problemid=b304)
## priority_queue
可以想像成heap，push就是把東西丟進heap，pop會把最大的東西pop出來。
### 宣告方式
```c++=
int main(){
priority_queue<int> pq; //max-heap 最上面最大
priority_queue<int, vector<int>, greater<int> > pq2;//min heap 最上面最小
priority_queue<struct, vector<struct>, cmp> //可以自訂比較函數
}
```
### push/pop
```c++=
int main(){
priority_queue<int> pq;
pq.push(1);
pq.push(3);
pq.push(2);
cout << pq.top() << '\n';//在這裡也是top
pq.pop();//只會把最上面的東西pop掉，不會回傳被pop的值
//注意在用pq.top(),pq.pop()之前要先檢查pq是不是empty
cout << pq.empty() << '\n'; //pq是不是空的
cout << pq.size() << '\n'; //pq的大小
}
```
[Priority queue練習1](https://neoj.sprout.tw/problem/59/)
[Priority queue練習2](https://zerojudge.tw/ShowProblem?problemid=b151)
## iterator
在進入set跟map之前要先提一個在STL裡面用法跟指標有點像的工具：iterator。因為STL有自己的實作方式，不像陣列是連續的一塊記憶體，因此需要使用比較特別的指標(iterator)才能做到一些原本陣列才能做到的事情
### 宣告
```c++=
vector<int>::iterator iter=v.begin();
set<double>::iterator iter;
```
### 常見用法
其中v.begin()指的是vector的頭，v.end()指的是vector的尾。++ 代表的是找vector的下一個元素，就像指標的++那樣。
這裡要注意的是v.begin代表的是vector的第一個element(v[0])，但v.end()代表的是vector最後一個element的後一個(v[n]，裡面沒有值)。有點像sort的時候傳的是a和a+n那樣。如果要取到最後一個值可以用v.end()再- -
```c++=
for(vector<int>::iterator iter = v.begin(); iter != v.end(); ++iter){
cout << *iter << endl;
}//輸出陣列所有元素
vector<int> :: iterator it = v.end();
cout << *prev(it) << '\n'; //vector的最後一個寫法1
it--;
cout << *it << '\n'; //vector的最後一個寫法2
```
另外還有rbegin和rend，但其實他們可以做到的事begin跟end都做得到，這裡就先不提。
### auto
C++ 11才有的功能，對於有被初始化的變數可以自動判斷他的型別，譬如說上面那個iterator看起來一長串很麻煩，改成這樣也可以：
```c++=
for(auto iter = v.begin(); iter != v.end(); ++iter){
cout << *iter << endl;
}
auto it = v.end();
it--;
cout << *it << '\n'; //輸出vector的最後一個
```
## set
就像一個集合那樣，可以insert(把東西加進集合裡面)、erase(把東西移出集合)、find(檢查集合裡面有沒有某個東西)，複雜度都是 $O(\log N)$
```c++=
set<int> s;
s.insert(3);
s.insert(2);
s.insert(4);
s.insert(3);//重複insert不會多一個
s.erase(3);
s.erase(s.begin()); //也可以傳入想刪除的iterator，例如這樣是刪掉最小的數
for(auto o:s) cout << *o << ' ';
```
find比較特別，如果有找到會回傳一個iterator指向找到的element，沒有則會回傳s.end()。但find沒辦法知道找到的element是第幾大，這個在lower_bound那段會詳加說明。
```c++=
set<int> s;
s.insert(3);
s.insert(2);
s.insert(4);
auto it = s.find(3);
if(it == s.end()) cout << "Not Found\n";
else cout << *it;
```
## multiset
前述set的multi版本，也就是集合裡面可以有多個重複的element。需要注意的是erase(3)在multiset有多個3時會**全部刪掉**，如果只需要erase一個的話可以：
```c++=
multiset<int> s;
for(int i=0;i<5;i++) s.insert(3);
s.erase(s.find(3));
for(int i:s) cout << i << ' ';//輸出四個3
```
1=>1
5=>6
"abcde"=>1
## map
map裡面存的是很多對key跟value的對應。實際使用起來感覺會跟陣列很像，但map比較強大的點在於陣列的index只能是非負整數，而且如果你要戳a[N]就要開N的記憶體，map用$O(\log N)$的複雜度解決這些問題。
```c++=
map<int,int> m;
m[3]=1; //map可能有insert，但這樣寫方便多了
m[-1]=2;
m[1000000000]=9;//這樣也只會佔到O(1)記憶體
m.erase(-1); //把m[-1]設成0不會從map裡面消失，這樣才會
map<string,int> m2;
m2["cat"]=1; //有點像hash的感覺
//但需要注意的是如果放了很多長字串進去map記憶體還是O(字串長)
```
## 遍歷
map裡面存的是pair，在遍歷上會比vector跟set麻煩一點，但概念是一樣的
```c++=
map<int,int> m;
m[1]=2;
m[-1]=5;
m[9]=3;
for(pair<int,int> i:m)cout<<i.first<<':'<<i.second<<'\n';
for(auto i:m)cout<<i.first<<':'<<i.second<<'\n';
```
map可以很方便的實現類似counting sort的演算法，惟map常數較大(同樣時間複雜度比較容易TLE)，如果用陣列可以過的題目就不要開map
## lower_bound
lower_bound是幫助我們在前述STL裡面$O(\log N)$二分搜的工具，可以幫我們找到指向不小於給定值val最小數的iterator(如果所有數都比val小則回傳v.end())。需要特別注意的是**vector和set/map的lower_bound寫法不可混用**，編譯不會跳錯但會造成複雜度退化成$O(N)$，是很多人常常踩到的bug
### vector
因為vector裡面有第k個element的概念，所以除了可以知道值以外還可以知道他是第幾小的element。前提是vector裡面的東西必須要由小到大排好
```c++=
vector<int> v={1,3,6,9,8};
sort(v.begin(),v.end()); //排好變{1,3,6,8,9}
auto it = lower_bound(v.begin(), v.end(), 5);//不小於5最小=6
cout << *it <<'\n';
cout << it - v.begin() <<'\n'; //像指標加減法那樣知道他是第幾個
it = lower_bound(v.begin(), v.end(), 10);//這樣會回傳v.end()
cout << *it <<'\n';
cout << it - v.begin() <<'\n';
```
### set/map
set跟map沒有第k個element的概念，只能經由++(next)或- -(prev)知道他的前一個或後一個。寫法也不太一樣：
```c++=
set<int> s={1,3,6,8,9};
auto it = s.lower_bound(6);//不小於6最小=6
cout << *it <<'\n';
cout<< *prev(it) <<'\n'; //小於5的最大整數=3
```
```c++=
map<int,int> m;
m[1]=9;m[-2]=5;m[3]=-7;m[6]=8;
auto it = m.lower_bound(2);//對key找，大於等於2最小的數是3
cout << (*it).first << ' ' << (*it).second <<'\n';//先取值才能取first/second
cout << (*prev(it)).first << ' ' << (*prev(it)).second <<'\n';//比2小最大
```
### upper_bound
原本是**不小於**給定值val，upper_bound是**大於**給定值val。基本上就是大於等於和大於的差別。舉個例子：
```c++=
set<int> s={1,3,6,8,9};
auto it = s.lower_bound(6);//不小於6最小=6
cout << *it <<'\n';
it = s.upper_bound(6); //大於6最小=8
cout << *it <<'\n';
```
## Reference 參照
```c++
// 不用再傳 pointer 了！
void swap(int& a, int& b) {
int t = a;
a = b;
b = t;
}
int main() {
int a = 3, b = 5;
swap(a, b);
cout << a << ' ' << b << '\n'; // 5 3
int c = 1;
int &d = c;
d = 5;
cout << c << '\n'; // 5
}
```
對一個函數傳入大小為 $N$ 的 `vector` 是 $O(N)$ 的。可以用參照來解決 copy 一遍的問題：
```c++
void print(vector<int>& a) {
// O(1) function call!
}
```
## Range For
黑魔法。可以這樣對 `vector` 做事：
```cpp=
int main() {
vector<int> a(5);
for (int& i: a) cin >> i; //記得參照，不然輸不進去！
for (int i: a) cout << i << '\n';
}
```
搭配 `auto` 更顯強大：
```cpp=
int main() {
vector<pair<int, int>> pairs(5);
for (auto& [u, v]: pairs) cin >> u >> v;
for (auto [u, v]: pairs) cout << u << ' ' << v << '\n';
// 不用再 pairs[i].first 了！
}
```
Sign in with Wallet
Connect another wallet