---
# System prepended metadata

title: C++筆記
tags: [programing note]

---

###### tags: `programing note`
# C++筆記
## 先備知識
### 時間複雜度
* 根據定義，不計算常數倍數，所以我們只說 O(n)而不會說 O(3n)或 O(5n)。因為常數倍數不計，所以 log(n)不必指明底是 2 或 10。

* 兩個函數相加的 Big-O 等於比較大的函數。也就是說，若當 n 足夠大的時候，f(n)>g(n)，則 O(f(n)+g(n)) = O(f(n))。

* 如果某一段程式的複雜度是 O(f(n))而這段程式執行了 g(n)次，則複雜度為
O(f(n)*g(n))。

* 當要估算複雜度時，建議可以一秒 106~107的指令數量來估計，所以，假設執行一筆測資的時限為1 秒，我們可以得到下面常見的複雜度推估：

| n    | 超過 1 萬 | 數千 | 數百 | 20~25 | 10    |
| ---- | --------- | ---- | ---- | ----- | --- |
|複雜度 |O(n) or O(nlog(n))|O(n^2)| O(n^3) |O(2n) |O(n!)|


## 初始定義
### 函式庫
<bit/stdc++.h>
<math.h>
<string.h>
### 使用命名空間
using namespace std; 
//namespace為命名空間，預設的
//所以可以建立自己的命名空間
### 優化程式速度
```
#pragma GCC optimize("O0")//不優化(預設)
#pragma GCC optimize("O1")//優化一點
#pragma GCC optimize("O2")//優化更多
#pragma GCC optimize("O3")//O2優化再加上inline函式優化
#pragma GCC optimize("Os")//針對程式大小進行優化(程式最小)
#pragma GCC optimize("Ofast")//O3加上一些快速但不安全的數學運算
```
引用資料：[HOW TO OPTIMIZE YOUR CODE IN C++](https://horikitacoding.blogspot.com/2019/07/how-to-optimize-your-code-in-c.html)
## 輸入輸出

//想輸入輸出
```
cout << "hello, world" << endl;   //cout輸出    //endl換行
cin>> name1>> name2;    	  //cin輸入     //第二個>>為,的意思
```
### 限定位數
#### printf()
output 幾位(int): ex兩位, printf("%02d")
幾位(float): ex兩位, printf("%0.2f", 0.222)

#### cout<<
cout << fixed << setprecision(10) << 1.0*a/b << '\n';
fixed表示的，是小數點以下的意思，因此，若沒有fixed，setprecision(10)代表的，其實是總共輸出十位數字
設定一次輸出位數後，下一次便不需要重新設定
如果想要重新設定，可以使用「cout.unsetf( ios::fixed );」關閉fixed，範例如下
```
cout << fixed  <<  setprecision(3) << 3.1234  <<  endl;
cout.unsetf( ios::fixed );
cout << x << endl;
```
### 優化
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(false);
## bitset
bitset 表示一個固定大小的 N 位序列
#include <bitset>
bitset<32> bs1(toBinary(number));	//<位數>	//bs1第一個	//toBinary()為一個Function(可以省略)
## 動態陣列
### set
```
set<變數類型> 變數名稱(myset) = {}   //也可以=myset(array, array+n)		
會將數值由小排到大, 並去掉重複的
myset.insert(value)插入數值(不可以重複,只會紀錄不一樣的)
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); it++) {
    std::cout << *it << " ";
}
    
//輸出set內的值//由小到大
for (std::set<int>::iterator it = myset.rbegin(); it != myset.rend(); it++) {
    std::cout << *it << " ";
}

set<int>::iterator it = myset.find(value);
//find special value
    
myset.erase(2);//delect某個元素
myset.count(value)//判斷是否有該元素
myset.empty()//判斷set內是否有東西
myset.size()
```
    set 容器裡面元素的值是不可修改的

#### 補述:
    multiset(寫法像set)只是可以重複元素
	map(寫法像set+pair)有兩個欄位//first&second
### vector
vector<type> name 	//////name.?

?:
```
push_back：把元素加到尾巴，必要時會進行記憶體配置
pop_back：移除尾巴的元素
insert：插入元素
erase：移除某個位置元素, 也可以移除某一段範圍的元素
clear：清空容器裡所有元素
size：回傳目前長度
empty：回傳是否為空
[i]：隨機存取索引值為i的元素，跟陣列一樣索引值從 0 開始
at(i)：隨機存取索引值為i的元素，跟上面 operator[] 差異是 at(i) 會作邊界檢查，存取越界會拋出一個例外
reserve()：預先配置大小		//假設我想要預先配置好 5 個大小的話可以這樣寫 vector.reserve(5)//不指定元素
resize() : 預先配置大小		//可以指定元素(不指定的話都是0),ex. resize(5, 10);//長度5元素指定為10
capacity() : 容量(記憶體長度)//非實際長度
shrink_to_fit() : 釋放（free）那些尚未使用的空間
```

***
如果是指定複製傳統陣列的範圍的話，可以這樣寫，
int n[5] = {1, 2, 3, 4, 5};
vector<int> v(n+2, n+4); 	// {3, 4}

## 搜尋法
    
### 二分搜
```
binary_search()  :  return boolean是否有收尋到
lower_bound()    :  return value // value>=目標
upper_bound()    :  return value // value>目標
```
### 山峰::三分搜
其一:山峰::三分搜
三分搜是將區間三等分，如果 1/3 的位置大於 2/3 的位置，可以丟掉左 邊的 1/3；反之，如果 2/3 的位置較大，則可以丟棄右邊 1/3 的區間。如此每次可以 將區間長度減少 1/3，在 O(log(n))次比較可以找到最低點
### 山谷::差分二分搜
只要以二分搜找到差分序列第一個大於等於 0 的位置就是 f 的最小值
    
## 佇列queue
佇列//出入口不同，一進一出
```
queue<int> Q; 
Q.push(t)放入數值
Q.empty()檢查數值
Q.pop()刪除數值
Q.front()前端值
Q.back()後端值
```
    
## 堆疊stack
堆疊//出入口相同
```
stack<int> S;
S.push(t)放入數值
S.empty()檢查數值
S.top()top值
S.pop()刪除top數值
```
    
## 雙向佇列deque
雙向佇列//兩個出入口
```
deque<int> D;
D.push_front/back放入前/後端
D.empty()檢查數值
D.pop_front/back()刪除前/後端
D.front()前端值
D.back()後端值
```
## 字元或字串
### 字串宣告
1.     string str("txt");
       string str = "txt";
2.     string str1 = "test";
       string str2(str1);
3.     string str(7,'*');
運用第三個宣告方式，可以一次打印指定數量字元
### 字串長度呼叫
`int length = k.size();`
### 轉換字元或字串
字串一定要用 string 變數名稱 不可以用char a[n]來替換
`int x = stoi(放入字串)	//將字串轉換成數字`
### 判斷字元或字串
判斷字元或字串  //括號中放要判斷的東西
```
isalnum()	如果是字母或數字，返回true
isalpha()	如果是字母，返回true
isdigit()	如果是數字，返回true
islower()	如果是小寫字母，返回true
ispunct()	如果是標點符號，返回true
isspace()	如果是空白字符，包括空格、進紙、換行符、回車、製表符等，返回true
isupper()	如果是大寫字符，返回true
tolower()	如果是大寫字符，返回其小寫
toupper()	如果是小寫字符，返回其大寫
isxdigit()	如果是16進制數，返回true，如0-9、a-f、A-F
iscntrl()	如果是控制字符，返回true
isgraph()	如果是除空格以外的打印字符，返回true
isprint()	如果是打印字符，返回true
```

## struct 結構體
適合建構多維陣列
ex. 三維陣列
```
struct point{
    int x, y, z;
};
```
此結構體的point代表的是你自己建構的一種資料型態
建立point這種變數的方法
```
point p;
```
p為變數名稱

## 串列鏈結(Linked list)
* 串列是一個很重要的資料結構，顧名思義，他是將資料以鏈結的方式串成一列。他最重要的運用場合是當資料無法依序儲存在連續空間的時候

* 雙向的串列我們會儲存每一個資料的前一筆與下一筆鏈結，單向的只存下一筆
    
* 在陣列中構造所需的鏈結串列，用陣列的索引(index)
    * 左邊的 next 改成 i 的 next，把右邊的 pre 改成 i 的 pre，這樣在串列中沿著鏈結追蹤時就再也找不到 i 了，也就相當於從串列中移除了
    
## 貪心演算法
    
## 其他
變換變數類型==> (類型)value
絕對值=> abs(value)   //#include <math.h>
陣列宣告數值	int number[10] = {0};

## 參考資料
[從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/) 
[大數運算](https://hackmd.io/@CLKO/r1KtmuMdf?type=view)