# C++學習筆記

## I/O

string str;
char c;

//輸入
cin >> str >> c;
//讀入一個字串加字元(會跳過空格與換行)
cin >> ws;
//只會讀掉一個換行或空白
getline(cin,str);  
//讀入一整行,會讀掉換行,但不會讀入字串裡
cin.get(c);  
//讀入一個字元放在c裡,也可不放變數就只會單純讀掉
cin.ignore();
//忽略一個字元  =cin.get()
cin.peek();  
//回傳輸入的第一個字元,但此字元並不會被讀掉,EOF回傳-1

//cin讀字元和cin.get()差別
char c;
cin >> c;  //不會讀換行和空白字元,會一直跳過直到是有效字元
cin.get(c);  //會讀所有字元,包括換行 空白

//輸出
cout << str << c;  //輸出字串加一個字元

//小數點輸出(自動四捨五入)
cout << setprecision(3) << 15.4677;  //輸出三位(含整數部分) ->15.5
cout << fixed << setprecision(3) << 15.4677;  //輸出到小數點後三位 ->15.468
cout << setw(4) << setfill('0') << 5 ;  //只會設定後面第一個數字
//=printf("%04d",5);  //未滿4位數字自動補0 => 005

//加速
cin.sync_with_stdio(0),cin.tie(0);

## STL函數庫

### 1. vector

#include <vector>

vector<int> vec; 
vector<int> vec{1,2,3}; //初始化為1,2,3
vector<int> vec(3,1);  //初始化為1,1,1
vector<int> vec(3);  //宣告3個int的空間並初始化為0
vec.push_back(value);  //從後面放入value
vec.pop_back();  //清除最後面的數
vec.size();  //得到目前長度
vec.at(索引號);  //取得某個位置的值
vec.insert(vec.begin(),0); //在vec.begin的位置放入0
vec.insert(vec.begin()+1,3,0); //在前面數來第二個位置插入3個0
vec.insert(vec.begin(),arr,arr+4);  //在前面插入arr[0]~arr[3]
vec.earse(vec.begin()); //移除第0個元素
vec.earse(vec.begin(),vec.begin()+5); //移除前5個元素

//宣告一個10x10的二維陣列並初始化為0
int size=10; 
//法一
vector<vector<int>> vec(size);
for(int i=0;i<size;i++){
    vec[i].resize(size); 
}  

//法二
vector<vector<int>> vec(size,vector<int>(size));

### 2. stack

#include <stack>

stack<int> s;
s.push(value); //從頂端放入value
s.pop();  //頂端移除一個值
s.top(); //回傳頂端元素的值
s.empty();  //檢查stack是否為空,是回傳1,否則回傳0

### 3. queue

(1)queue

#include <queue>

queue<int> q;
q.push(value); //從尾端放處value
q.pop(); //移除頭的值
q.front();  //回傳頭的值
q.back();  //得到尾巴的值
q.empty();  //檢查queue是否為空,是回傳1,否則回傳0

(2)priority queue

#include <queue>

priority_queue<int> maxq; //預設為最大堆
priority_queue<int,vector<int>,greater<int> > minq;  //最小堆宣告
priority_queue<int,vector<int>,less<int> > maxq;  //最大堆宣告

注意：priority queue使用struct的時候要注意bool operator的寫法

typedef struct node{
    int a,b,c;
    bool operator<(node x) const {
        return a>x.a;  //小到大
    }
}node;

priority_queue<node> q;

### 4. set

1. s.insert(value)返回的值是pair<iterator,bool>iterator代表插入的位置,bool代表插入是否成功,前者為pair.first,後者為pair.second
2. 注意:set不能直接修改裡面的值,這樣會破壞原有紅黑數的排序順序,改變元素值的方法是：先刪除舊元素，再插入新元素
3. multiset
用法跟set一樣,差別於multiset可以新增重複的元素,set不行
注意:multiset的insert的返回值和set的返回值不一樣,不可混用
4. unordered_set
快速查詢,無rb tree自動排序
5. unordered_multiset
跟unordered_set差別於unordered_multiset可新增重複元素

#include <set>

set<int> s;
s.insert(value); //在集合裡新增value
s.erase(value);  //在集合裡刪除value
s.count(value);  //檢查value有沒有在集合裡

auto it=s.insert(value);
if(it.second){
    cout << *it.first << endl; 
}

注意：如要使用struct建議用multiset，因為bool operator相等就會被判定為一樣的元素，即使其他值不一樣還是會被set吃掉。

typedef struct node{
    int a,b;

    bool const operator<(node other) const {
        return a>other.a;
    }
}node;

multiset<node> s;

### 5. map

1. 用法就像陣列一樣,一開始都會歸零,跟陣列不同的是key可直接使用,map[key]=value,如果key沒有對應到的值的話,value會是0,同時也就宣告了此pair,map可修改value,只要被宣告過,即使value修改為0,m.count[key]還是會回傳1
2. m.find(value)回傳值為一個iterator指向value所在的位置,找不則回傳m.end()
key=it->first , value=it->second
3. multimap
實現一對多映射,如要插入要用insert : mm.insert({key,value})
4. unordered_map
實作hash table,用法跟map一樣,只是速度比map快很多,但記憶體空間較為龐大
5. map會依照key的大小,預設為由小到大,如要由大到小排列要在參數後面加greater<key變數型態>

#include <map>

map<string,int> m

//設定對應的值(3種寫法效果相同)
m["abcd"]=5;
m.insert({"abcd",5});
m.insert(pair<string,int> ("abcd",5));

m.count("abcd");  //檢查abcdu有沒有對應值,如果有回傳1,否則回傳0
m.erase("abcd");  //刪除key("abcd")和對應到的value(5)

//插入(兩種寫法效果相同)
m.insert({"abcd",5});
auto it=m.find("abcd");  //回傳"abcd"的iterator
auto key=it->first;  //abcd
auto value=it->second;  //5

auto it=m.insert(m.begin(),{"abcd",5});
//insert(iterator,pair)裡的iterator代表從哪裡開始search
auto key=it->first;  //abcd
auto value=it->second;  //5

//宣告排列由大到小的multimap
multimap<int,char,greater<int>> mm;  

### 6. deque(double-ended queue)

deque<int> d;

d.push_back(value);  //從後面放入
d.push_front(value);  //從前面放入
d.pop_back();  //清除後面
d.pop_front();  //清除前面

### 7. list
雙向連結串列

#include <list>

list<int> l;
l.push_front(value);  //從前面放入value
l.push_back(value);  //從後面放入value
l.pop_front();  //刪除前面
l.pop_back();  //刪除後面
l.erase(預刪除的位置);  //清除節點
l.insert(欲新增的位置);  //新增節點
l.clear();  //清空整個串列

## algorithm

### 反轉

vector<int> vec{1,2,3,4,5};
reverse(vec.begin(),vec.end());
//=>5,4,3,2,1

### 排序
如果排序元素小於16會用insert sort(元素保持stable)
超過16會用quick sort(元素不保持stable)
所以如果想要 當元素相同時但不變換原有位置,就要用stable_sort

int arr[100];
int size=10;
sort(arr,arr+size,greater<int>()); //遞減排序
sort(arr,arr+size,less<int>());  //遞增排序(預設)

vector<int> vec{5,9,4,8,7};
sort(vec.begin(),vec.end());
//=>4,5,7,8,9


//stable_sort用於當元素相同時不會改變原有的順序
bool cmp(double a,double b){
  return (int(a) < int(b));
}

vector<double> v1{1.9,1.5,1.2};
stable_sort(v1.begin(),v1.end(),cmp);  //1.9 1.5 1.2

//sort的compare function也可以寫在裡面
sort(a.begin(),a.end(),[&](int i,int j){
    return i>j;
});

### 自訂排序

vector<int> vec{5,9,3,4,5};

sort(vec.begin(),vec.end(),cmp);
//自訂遞減排序

bool cmp(int a,int b){
    if(a>b) return true;
    else return false;
    //回傳值代表判斷這樣順序對不對,如果回傳false才要改,回傳true代表這樣排序是對的就不用更改
}

## string

#include <string>

string str1;
string str2;
str1.empty(); //檢查str1是否為空,是回傳1,否則回傳0
str1.size();  //回傳str1的長度
str1.find("abc",3);  //從str1[3]開始找第一個"abc",回傳索引號,找不到則回傳-1
str1.insert(3,"def");  //在str[3]插入"def"
str1.assign(str2);  //複製str2到str1 == str1=str2
str1.assign(str2,3,5);  //從str2的第3個字元取出5個字元指定給str1
str1.append(str2,3,5);  //從str2的第3個字元取出5個字元加在str1後面
str1.assign(str2,3); //從str2的第3個字元指定整串字串到str1
str1.assign(10,'c');  //複製10個c到str1
str1=str2.substr(3,5);  //從str2的第3個位置取5個字元放到str1

## 動態配置

int *p = new int(10);  //配置一個int型別的空間並初始化為10
int *p = new int[100]{0};  //配置一個連續空間並初始化為0

//配置二維陣列
int **p = new int*[10];
for(int i=0;i<9;i++){
    p[i]=new int[10]{0};
}

//釋放二維陣列

for(int i=0;i<10;i++){
 delete [] p[i];
}
delete [] p;

## 鄰接串列

#include <vector>

vector<int> vector[10];  //宣告10個vector
vec[x].push_back(value);  //在vector[x]插入value

//一般遍歷
for(int i=0;i<vec[x].size();i++){
    cout << vec[x][i] << " ";
}

//用iterator遍歷
for(vector<int>::iterator i=vec[x].begin();i!=vec[x].end();i++){
    cout << *i << " ";
}

## 判斷alphabet(isalpha)

char c;
if(isalpha(c)==1024){
    //c is a alphabet
}
if(isalpha(c)==0){
    //c is not alphabet
}

## 轉換小寫(tolower)

char c;
c = tolower(c);

## 字串切割(stringstream)

#include <sstream>

string input;
stringstream str(input);  //初始化為input
string output;
while(str >> output){  //一直讀,直到沒有
    
}
//清空
str.str("");  //清空字串
str.clear();  //清空EOF

//以逗號分割
string s="abc,123,cd456";
stringstream ss(s);

string tmp;
while(getline(ss,tmp,',')){
    cout << tmp << '\n';
}
/*
OUTPUT:
abc
123
cd456
*/

## 二分搜(lower_bound)

int findvalue;
int arr[100];
int size;
int index=lower_bound(arr,arr+size,findvalue)-arr;  
//回傳大於或等於findvalue的最小值的位置,減掉begin的位置就是索引號
int index=upper_bound(arr,arr+size,findvalue)-arr; 
//回傳大於findvalue的最小值的位置,減掉begin的位置就是索引號

//如果是搜pair要寫正式寫法:make_pair不能用{}
auro it=lower_bound(all(x),make_pair(a,b));

## 累積函數(accumulate)

vector<int> vec{1,2,3,4,5};
int add=accumulate(vec.begin(),vec.end(),0);
// 0為初始值的相加函數  =15
int mul=accumulate(vec.begin(),vec.end(),1,multiplies<int>());
// 1為初始值的相乘函數  =120

## iterator

vector<int>::iterator it;
//=auto it;

//用iterator遍歷
vector<int> vec{1,2,3};
for(auto it=vec.begin();it!=vec.end();it++){
    cout << *it << " ";
}

auto pre=prev(it);  //pre=it的前一個
auto nex=next(it);  //nex=it的後一個

## pair

就相當於一個struct,只是限定兩個元素,用'.'存取,第一個值是first,第二個值是second

#define pii pair<int,int>

vector<pii> a;  //宣告一個pair<int,int>型別的vector
a.push_back(make_pair(5,10));  //放入5跟10
//= a.push_back({5,10});  //結果一樣

pair<int,string> b;
b={3,"three"};
//= b=make_pair(3,"three");

cout << b.first << ' ' << b.second << '\n';  //分別存取pair裡面的兩個值
//output:3 three

## tuple
相當於一個struct,可自訂struct裡的型別和數量

tuple<int,string> t={10,"abc"};
//宣告一個tuple

//存取元素:get<index>變數名稱  
//注意:index不可為變數
get<0>(t)=9;
cout << get<0>(t) << ' ' << get<1>(t);  //9 abc
//印出第index個的元素

//set會依照tuple裡元素的順序排列,從第一個開始,如果一樣就判斷第二個
set<tuple<int,int,int>> s;
s.insert({1,2,9});
s.insert({9,7,3});
s.insert({1,2,3});
s.insert({5,2,0});

//c++17以上可以寫auto& [a,b,c]來替代get<index>(v[i])
for(auto& [a,b,c]:s){
    cout << a << ' ' << b << ' ' << c << '\n';
}
/*
1 2 3
1 2 9
5 2 0
9 7 3
*/

上面宣告的tuple就相當於以下struct,只是存取時的元素名稱不一樣

struct node{
    int a;
    string b;
};

node t={10,"abc"};
cout << t.a << ' ' << t.b;  //10 abc

## Bitset

以bit為單位的集合,用法與二進制int一樣

可印出數字二進制

#define MAXN 7

bitset<MAXN> b;  //初始化:0000000
b[3]=1;  //0001000
b.reset();  //0000000

//二進制
int a=7;
bitset<32> b(a);
cout << b ;  //00000000000000000000000000000111

## 排列組合next_permutation
要列出一組數字的排列組合要先把該組數字排序,再利用nexe_permutation函數來取得下一個排列組合,如果該組排列組合已經是最大的了,會依照升序排列,並回傳false,否則回傳true

vector<int> a{1,2,3};

do{
    for(auto i:a) cout << i << ' ';
    cout << '\n';
}while(next_permutation(a.begin(),a.end()));

cout << '\n';
for(auto i:a) cout << i << ' ';

output:

1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

1 2 3

## fill
memset 只能初始成0跟-1,當要初始成其他值時,就可用fill
fill顧名思義就是填滿,填滿特定的值,參數如下

fill(左邊界,右邊界,要初始的值)

vector<int> a(10);
fill(a.begin(),a.end(),-2); //-2 -2 -2 -2 -2 -2 -2 -2 -2 -2


int b[5];
fill(b,b+5,100);  //100 100 100 100 100

## Binary Search
內建二分搜找元素,如果有找到回傳1,否則回傳0

vector<int> a{1,2,3,4,5};
cout << binary_search(a.begin().a.end(),3) << '\n';  //1
cout << binary_search(a.begin().a.end(),10) << '\n';  //0
	

## 隨機生成大數
範圍:long long

mt19937_64 mrand(time(0));
int num = mrand();

## iota
填充1~n到陣列裡

vector<int> a(10);
iota(all(a), 1);    //從1開始
for (auto i : a) cout << i << ' ';  // 1 2 3 4 5 6 7 8 9 10