### C++ Container
ref : https://srhuang.github.io/c++/2019/11/15/cplusplus-004.html
| Name | Brief | Iterators | Capacity | Element Access | Modifiers | Others |
| ------------ | ------------------------ | ---------- | --------------------- | --------------------------- | ------------------------------------------------------------- | ------------- |
| array | Static contiguous array | begin, end | size, empty | operator[], at, front, back | swap | |
| vector | Dynamic contiguous array | begin, end | size, empty, capacity | operator[], at, front, back | push_back, pop_back, insert, erase, swap, clear | |
| deque | Double-ended queue | begin, end | size, empty | operator[], at, front, back | push_back, pop_back, insert, erase, swap, clear | |
| list | ==Doubly-linked list== | begin, end | size, empty | front, back | push_back, pop_back, insert, erase, swap, clear | sort, reverse |
| forward_list | ==Singly-linked list== | begin, end | empty | front | push_front, pop_front, insert_after, erase_after, swap, clear | sort, reverse |
### C++ Data Type, Size, Range
==針對x86_64系統。==
char : 1 bytes
short : 2 bytes
int : 4 bytes
long : 8 bytes
| Type | Size | Range |
| -------- | -------- | -------- |
|char |1byte| -127 to 127
|unsigned char |1byte| 0 to 255
signed char |1byte| -127 to 127
short int |2bytes| -32,768 to 32,767
unsigned short int |2bytes| 0 to 65,535
signed short int |2bytes| -32,768 to 32,767
int |4bytes| -2,147,483,648 to 2,147,483,647
unsigned int |4bytes| 0 to 4294967295
signed int |4bytes| -2,147,483,648 to 2,147,483,647
long |8bytes| -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
long int |8bytes| same as long
signed long int |8bytes| same as long int
unsigned long int |8bytes| 0 to 18,446,744,073,709,551,615
long long int |8bytes| -(2^63) to (2^63)-1
unsigned long long int |8bytes| 0 to 18,446,744,073,709,551,615
float |4bytes|
double |8bytes|
long double |12bytes|
wchar_t |2 or 4 bytes| 1 wide character
### Array
std::array這個container把fixed sized array做一層包裝。
```cpp=
array<T, N> arr; // T為型態,N為長度
// 常用function
arr.empty();
arr.size();
arr.at();
arr.front(); // 第一個element, arr.at(0), arr[0]
arr.back(); // 最後一個element, arr.at(N - 1), arr[N-1]
arr.fill(); //把arr全部填入同一個值
arr.swap(); //和另一個array交換。
// Traversal
for(int i = 0; i < arr.size(); ++i)
cout << arr[i] << endl;
for(const auto& i : arr)
cout << i << endl;
for(auto it = arr.begin(); it != arr.end(); ++it)
cout << *it << endl;
````
### Vector
+ 支援隨機存取
+ 集合尾端增刪元素很快 : O(1)
+ 集合中間增刪元素比較費時 : O(n),所以允許的話,可以先swap要刪除的值到最後,然後再刪除。
```cpp=
#include <vector>
//declare a vector
vector<T> v;
vector<T> v(n); // 定義n的長度
vector<T> sub(v.begin(), v.begin() + 5); // subvector
vector<T> v(s.begin(), s.end()); // import data from set
vector<vecotr<T>> v_2d; // 2維vector
vector<vector<T>> v_2d1(n, vector<T>(m)); //
// 常用function
v.empty();
v.size();
v.front();
v.back();
v.push_back(); // 將obj推到vector的最後端。
v.emplace_back(); // 將obj推到vector的最後端。
// 如果用這個construct obj則可以減少copy或是move
v.pop_back(); // 如果要同時操作front, back則用deque
v.insert(); // 插入到指定位置
v.insert(v.begin(), target) // 加入target到最前面
v.insert(v.begin() + n, target) // 加入taret到任意位置, n <= v.size()
v.erase(); // 移除某個指定位置element
// 另一種比較有效率的刪除方法,
// 但是順序會變,只能用在不在乎順序的情況
swap(v[n], v.back()); // 交換n和最後一個位置
v.pop_back(); // back()會在原本n的位置
v.clear(); // 清除全部element
v.count(v.begin(), v.end(), val); // 計算範圍內val出現的次數
auto it = find(v.begin(), v.end(), val); // 尋找第一個val出現的位置。
v.reverse(first, last); // 反轉vector從first到last
// insert vector v2 to the end of vector v1
v1.insert(v1.end(), v2.begin(), v2.end());
// 調整vector大小
v.resize(n, vector<int>(m, -1)); // v成為nxm大小,預設值都為-1
// Traversal
for(int i = 0; i < v.size(); ++i) {
cout << v[i] << endl;
}
for(const auto& i : v) {
cout << i << endl;
}
for(auto it = v.begin(); it != v.end(); ++it) {
cout << *it << endl;
}
// accumulate
accumulate(v.begin(), v.end(), bias); // 同常bias = 0
accumulate(v.begin(), v.end(), 0l); // 避免overflow,可以使用long來相加。
// 使用lambda,當val為偶數才相加
accumulate(begin(v), end(v), bias, [](int& sum, int val){
return sum + (val % 2 == 0 ? val : 0);
});
// fill the increase value
// 從begin()開始到end(),填充val,且下一個是val++,以此類推。
// v[0] = val, v[1] = val + 1, v[2] = val + 2,...
// 必須include <numeric>
iota(v.begin(), v.end(), val);
```
### List
+ 使用double linked-list 實現,所以移動刪除都是O(1)
```cpp=
#include <list>
// delcar
list<int> l;
// 常用function
l.empty();
l.size();
l.push_back();
l.pop_back();
l.push_front();
l.pop_front();
//將一個list中的值移到另一個list中
l.splice(iterator pos, list& x); // 把x所有的element接到l中pos的位置。
l.splice (iterator pos, list& x, iterator i); // 把i單一個element從x中搬移到l中pos的位置。
l.splice (iterator pos, list& x, iterator first, iterator last); // 把x中從first到last的element搬到l中pos的位置。
```
### Stack
```cpp=
#include <stack>
// declare a stack
stack<T> s;
// 常用function
s.empty(); //測試堆疊是否為空。若為空回傳 true,反之 false。
s.size(); //回傳目前堆疊中有幾個元素。
s.push(); //在堆疊中加入一個元素。
s.pop(); //移除目前堆疊中最上層元素
s.top(); //取得目前堆疊中最上層元素
```
### Queue
```cpp=
#include <queue>
// declare a queue
queue<T> q;
// 常用function
q.empty(); //測試佇列是否為空。若為空回傳 true,反之 false。
q.size(); //回傳目前佇列中有幾個元素。
q.push(); //在佇列中加入一個元素。
q.pop(); //移除目前佇列中最前端元素 (即最早進入佇列的元素)。
q.front(); //取得目前佇列中最前端元素的 reference
```
### Deque (Double-Ended Queue,唸作 "deck")
```cpp=
#include <deque>
// declare a deque
deque<T> dq;
deque<T> dq(v.begin(), v.end()); // 把vector放入deque
// 常用function
dq.empty(); //測試 deque 是否為空。若為空回傳 true,反之 false。
dq.size(); //查詢目前 deque 中有幾個元素。
dq.push_front(); //在 deque 的前端加入一個元素。
dq.push_back(); //在 deque 的後端加入一個元素。
dq.pop_front(); //移除目前 deque 中最前端元素。
dq.pop_back(); //移除目前 deque 中最後端元素。
dq.front(); //取得目前 deque 中最前端元素的 reference。
dq.back(); //取得目前 deque 中最後端元素的 reference。
// 自訂compare function
// 和 sort相反,下面是min-heap
auto cmp = [](int& a, int& b) {
return a > b;
}
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
```
### PriorityQueue(Binary Heap)
```cpp=
#include <queue>
// declare a priorityqueue
priority_queue<T> pq; // 預設為最大在上面
priority_queue<T, vector<T>, greater<T> > pq; //改成由小排到大
// 自己定義compare function
// 從小排到大,與sort的cmp相反
auto cmp = [](int& a, int& b) {
return a > b;
};
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
// 常用function
pq.empty(); //測試優先佇列是否為空。若為空回傳 true,反之 false。
pq.size(); //回傳目前優先佇列中有幾個元素。
pq.push(); //在優先佇列中加入一個元素。
pq.pop(); //移除目前優先佇列中優先順序最高的元素。
pq.top(); //取得目前優先佇列中優先順序最高元素的 constant reference。
```
#### make_heap
因為使用priority_queue會有額外的空間,其實,vector就可以當成heap使用。這樣空間成本就會變成==O(1)==
```cpp=
vector<int> nums{1, 3, 5, 2, 4, 6};
make_heap(nums.begin(), nums.end()); // 預設是max-heap
make_heap(nums.begin(), nums.end(), less<int>()); // max-heap
make_heap(nums.begin(), nums.end(), greater<int>()); // min-heap
// pop,因為pop_heap只是把element往最後移動,
// 所以還要pop_back()
pop_heap(nums.begin(), nums.end()); // for max-heap
pop_heap(nums.begin(), nums.end(), greater<int>()); // for min-heap
nums.pop_back();
// push, 需要先把element放到最後
nums.push_back(val);
push_heap(nums.begin(), nums.end()); // for max-heap
push_heap(nums.begin(), nums.end(), greater<int>()); // for min-heap
// sort_heap
sort_heap(nums.begin(), nums.end()); // 升序排序
sort_heap(nums.begin(), nums.end(), greater<int>()); // 降序排序
```
### Set/MultiSet
預設set會從小到大排序。
set容器裡面的元素是唯一的,具有不重複的特性
multiset可以允許元素重複。
unordered_set 不排序的set。
unordered_multiset 不排序的multiset。
```cpp=
#include <set>
// declare a set
set<T> s;
set<T> s{1, 2, 3, 4, 5}; // with initial value
set<T> s(vector<T>); // 可以輸入vector
set<T> s(vector.begin(), vector.end()); // import data from vector,方便查找資料
set<T,greater<T>> s2; // 從大排到小
multiset<T> st;
// 常用function
s.empty();
s.size();
s.insert();
auto it = s.insert(val); // 可以取得insert之後的位置
s.erase(); // 可以傳入key或是iterator, 如果傳入為key會刪除重複的key
//所以必須先使用find找出value的iterator,這樣才可以確保只刪除一個
s.erase(s.find(value));
s.clear();
s.count(); // 看看elemet有幾個,因為set只容許一個,所以等於是判斷有無。multiset會回傳個數。
s.find(); // 回傳iterator,所以還要判斷使否是s.end();
// convert set to vector
vector<T> v(s.begin(), s.end());
// Traversal
for(const auto& item : s) { //宣告成const前提是不會在function內修改item的值。
cout << item << endl;
}
for(auto it = s.begin(); it != s.end(); ++it){
cout << *it << endl;
}
for (auto it = s.rbegin(); it != s.rend(); ++it) {
cout << *it << endl;
}
// 取第一個和最後一個element
cout << *s.begin() << endl; // 取第一個element的值
cout << *s.rbegin() << endl; // 取最後一個element的值,不可以直接使用end()
cout << *(--s.end()) << end; // 必須使用end()的前一個
```
### Map/MultiMap
Map 的 key-value 對應主要用於資料一對一映射 (one-to-one) 的情況。
+ 第一個稱為關鍵字 (key),每個關鍵字只能在 map 中出現一次。
+ 第二個稱為該關鍵字的值 (value)。
+ 預設也是從小到大排序
multimap 允許多個相同的key-value pair。
unordered_map 不排序的map。
unordered_multimap 不排序的multimap。
```cpp=
#include <map>
//declare a map
map<T, U> m;
map<T, U, greater<T>> m; // 從大排到小
// 常用function
m.empt();
m.size();
m.insert();
m.erase(); // 刪除element
m.clear(); // 清空所有的element
m.count(); // 回傳有幾個element
m.find(); // 回傳iterator
m.swap(x); // 把m和x的資料交換,m和x必須一樣的type
// Traversal by reference
for (const auto& item : m) {
cout << item.first << ":" << item.second << endl;
}
// Traversal by reference with name
for(const auto& [key, value] : m) {
cout << key << ":" << value << endl;
}
// Traversal by iterator
for (auto it = m.begin(); it != m.end(); ++it) {
cout << it->first << ":" << it->second << endl;
// 使用prev()取得iterator的前一個
cout << prev(it)->first << ":" << prev(it)->second << endl;
}
// 取第一個和最後一個element
cout << m.begin()->first << endl; // 取第一個element的值
cout << m.rbegin()->first << endl; // 取最後一個element的值,不可以直接使用end()
cout << (--m.end())->first << end; // 必須使用end()的前一個
```
使用unordered_map的時候,根據key產生出來的hash來查找value。既然是hash就會有碰撞問題。根據[unordered_map reserve() in C++ STL](https://www.geeksforgeeks.org/unordered_map-reserve-in-c-stl/)敘述。
>As we know a Bucket is a slot in the container’s internal hash table to which all the element are assigned based on the hash value of their key . Buckets are numbered from 0 to bucket_count.
如果增加的數目超出bucket_count,map就會自動變大bucket_slot,並且重新計算所有item的hash。
>When the Load Factor(load_factor) reaches a certain threshold, the container increases the number of buckets and rehashes the map.
使用以下的程式碼,就是放大bucket到n,並且重新計算hash table。
```cpp
m.refresh(n);
```
如果我們事先知道大小可以使用以下function直接保留bucket到n,避免超出threshold需要放大container。因為事先保留了n個bucket也==可以避免hash collision==。
```cpp
m.reserve(n);
```
### Sort
```cpp=
#include <algorithm>
// 對vector<T> v進行排序,預設是從小到大
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<T>()); //從大到小排序
sort(v.rbegin(), v.rend()); // 也是從大排到小,
// 因為給了存放位置是從後面開始
// 所以把最小值依序排在最後面
// call by value
sort(v.begin(), v.end(), [](int a, int b){
return a < b; // 從小到大排序
});
// call by reference
sort(v.begin(), v.end(), [](int& a, int& b) {
return a < b;
});
// sort vector<vector<int>>
vector<vector<int>> nums;
sort(nums.begin(), nums.end()); // nums[0] 小的在前面,nums[0]一樣則是nums[1]小的在前面。
// 如果針對多維資料做排序
vetor<vector<int>> nums = {{1, 5}, {3, 2}, {2, 2}, {1, 2},{4, 1}};
sort(nums.begin(), nums.end(), [](vector<int>& a, vector<int>& b){
return a[1] < b[1]; // 只針對第二個element排序
});
// 結果為
// {{4, 1}, {3, 2}, {2, 2}, {1, 2}, {1, 5}}
// 其中第二個element一樣的話,會照在nums出現的順序。
```
### Lambda
![](https://docs.microsoft.com/en-us/cpp/cpp/media/lambdaexpsyntax.png?view=msvc-170)
1. capture clause (Also known as the lambda-introducer in the C++ specification.)
+ [&] 表示code裡面使用到的外部變數會用call by reference的方式。
+ [=] 表示code裡面使用到的外部變數會用call by value的方式。
+ [] 表示 Lambda 運算式主體不存取封閉範圍中的任何變數。
+ [x, &y]:x 變數使用傳值、y 變數使用傳參考。
+ [=, &y]:除了 y 變數使用傳參考之外,其餘的變數皆使用傳值的方式。
+ [&, x]:除了 x 變數使用傳值之外,其餘的變數皆使用傳參考的方式。
2. parameter list Optional. (Also known as the lambda declarator)
3. mutable specification Optional.
4. exception-specification Optional.
5. trailing-return-type Optional.
6. lambda body.
### Binary Search
```cpp=
// 找出vector中「大於或等於」val的「最小值」的位置
// 所以 *it有可能等於 val
auto it = lower_bound(v.begin(), v.end(), val);
cout << it - v.begin() << endl; // 印出it所在的index
// 找出vector中「大於」val的「最小值」的位置
// *it 一定不等於val
auto it = upper_bound(v.begin(), v.end(), val);
cout << it - v.begin() << endl; // // 印出it所在的index
```
也可以找非1D vector。例如
```cpp=
vector<vector<int>> nums{{0,0,1},{0,2,2},{1,3,2}};
vector<int> pattern{0, 2, 1};
auto it = lower_bound(begin(nums), end(nums), pattern);
cout << it - nums.begin() << endl;
// 1
```
![binary_search](https://bajamircea.github.io/assets/2018-08-09-lower-bound/01-lower_bound.png)
### String/Character Manipulation
string 是一個保存 char 的序列容器,把字串的記憶體管理責任交由 string 負責而不是 programmer,減輕了 C 語言風格字串的麻煩。
+ 提供了大量的字串操作函式。
+ 可與 C 語言風格字串雙向轉換。
```cpp=
#include <string>
//declare a string
string s1;
string s2{"hello"}; // 給予預設值
// index
for(int i = 0; i < s2.lenth(); ++i)
cout << s2[i] << endl; // h(0), e(1), l(2), l(3), o(4), 從左到右
// 重複char n次
string s(n, c);
// 常用function
s1.clear();
s1.empty();
s1.size();
s1.length();
s1.count(s1.begin(), s1.end(), char); // 計算範圍內char出現的次數
// 意思是"until the end of the string"
string::npos;
// 第一個出現某個char的位置。
s1.find(c);
// 最後一個出現某個char的位置。
s1.rfind(c);
// 找出substring
string sub = "ll";
// size_t find(string& str, int pos = 0);
size_t pos = s1.find(sub);
// npos : until the end of the string
if(pos == string::npos) { // 如果沒找到
}
// 字串反轉
reverse(s.begin(), s.end()); // 沒return,原本的string會反轉
string(s.rbegin(), s.rend()); // 使用iterator來反轉,產生一個新的字串
s1.push_back(); // 新增一個char到最後
s2.pop_back(); // 移除最後的char
string s = s1 + s2; // 字串串接
char c = s2[1]; // 取idx = 1的character,第二個位置。 c = 'e'
string sub = s2.substr(pos, len); //從pos開始取len長度
string sub2 = s2.substr(pos); // 從pos開始到最後
// 移除string中某個char
str.erase(remove(str.begin(), str.end(), '.'), str.end());
// 計算某個char出現的次數
count(str.begin(), str.end(), '.');
// 刪除某一個char或是某個範圍的chars
// 因為string 為immutable,所以移除char等於建立一個新的string
// time complexity : O(N)
str.erase(str.begin() + offset); // 移除begin開始第offset個char
str.erase(str.begin(), str.begin() + 3); // 移除前3個char
// 判斷函式
isalpha(c); // 是否為字母 'a'~'z' 'A'~'Z'
isdigit(c); // 是否為數字 '0'~'9'
isalnum(c); // 是否為字母和數字
islower(c); // 是否為小寫 'a' ~ 'z'
isupper(c); // 是否為大寫 'A' ~ 'Z'
isspace(c); // 是否為space
// 轉換成upper or lower case
toupper(c);
tolower(c);
// convert string to integer
stoi(str);
// convert integer to strng
to_string(val);
```
### StringStream
istringstream : input string stream。
ostringstream : output string stream。
stringstream : 可以使用在input/output。
ref : [Processing strings using std::istringstream](https://www.geeksforgeeks.org/processing-strings-using-stdistringstream/)
```c=
//stringstream
string str= "Welcome to coding with art";
// declare stringstream
stringstream ss(str);
string word;
// default seperator is space
while(ss >> word)
cout << word << endl;
// 使用getline換seperator
while(getline(ss, word, ',')) // from, to, delim
cout << word << endl;
// 兩個方法如果取到最後再取,都只會return最後一個string
// 清除stringstream,在輸入新的string
ss.str(""); // erase the buffer
ss.clear(); // reset error flags
ss << str;
// 把string丟進oss,最後使用str()輸出
oss << "123,";
oss << "456";
cout << oss.str() << endl;
// 用iss來parse string,和stringstream類似。
// 預設是使用space來當分隔。
istringstream iss(data);
string cur;
iss >> cur;
// 不管是 ss, iss, 或是oss都是在前面
```
可以用iss來判斷最後取值是否成功
```cpp=
string s{"1 2 3"};
istringstream iss(s);
char c;
while(iss >> c) cout << c;
```
如果資料是混合型態
```cpp=
string str("1, 2, 3");
istringstream iss(str);
int n;
char c;
while(iss >> n >> c) {
cout << n << endl;
}
```
### Iterator
+ [Random Access Iterators in C++](https://www.geeksforgeeks.org/random-access-iterators-in-cpp/)
+ [Bidirectional Iterators in C++](https://www.geeksforgeeks.org/bidirectional-iterators-in-cpp/)
![](https://media.geeksforgeeks.org/wp-content/uploads/iterators.png)
箭頭表示繼承,所以Random Access Iterator可以是bidirectional,也可以是Forward Iterator或是Input Iterator。
| Type of Iterator | Container |
| -------- | -------- |
| Random Access | vector, deque |
| bidirectional | list, map, multimap, set, multiset|
| Type of Iterator | Limitations |
| ------------- | ---------------------------------------------------------------------------------------------------------------------- |
| bidirectional | 1.Relational Operators(<=, >=)</br>2.Arithmetic Operators(+=, -=, +, -)</br>3.Use of offset dereference operator ([ ]) |
```cpp
// iterator可以用在set, map或是vector
distance(n.begin(), n.end()); // 計算兩個iterator的距離,第一個參數一定要比第二個還前面,不然會出現負數
prev(it); // 前一個, it不會移動,只會output前一個iterator
prev(it, 2); // 前兩個
next(it); // 後一個,it不會移動,只會output後一個iterator
next(it, 3) // 後三個
advance(it, 3); // 往前進3個,it會被改變。
begin(); // 第一個
end(); // **最後一個的後面, 不是最後一個element**
```
### 數字表示
```cpp
// Prefix
nums = 0x1a; // 16進位使用0x
nums = 030; // 8進位使用0
nums = 0b11000000; // 2進位使用0b
// Postfix or suffix
long num1 = 999L; // L 表示long
unsigned long num1 = 999UL; // U 表示unsigned, UL : unsigned long
float num1 = 999.02F; // F : float
double num1 = 999.02L; // L : long double
//科學記號表示法:數值後面接E或e再接10的乘方
314.159 = 3.14159E2
float floatValue1 = 3.14e2
float floatValue2 = 3.14e+2
```
### Bit Manipulation
```cpp
// bitset
std::bitset<8> bits{0b0000'1010}; // 宣告一個長度為8bits的變數
bits.set(2); // set bit2 to 1, 0b0000'1110
bits.reset(3); // set bit3 to 0, 0b0000'0110
bits.flip(4); // flip bit4(0->1, 1->0), 0b0001'0110
bits.test(4); // return bit4's status
bits.count(); // 回傳set bits個數,和__builtin_popcount(bits) 一樣。
bits.any(); // 任一個bit是set bit。
bits.all(); // 所有bit都是set bit。
bits.none(); // 沒有bit是set bit
// gcc build in function, 以下是int版本
__builtin_clz(0b0000'1100); // 回傳leading 0 有幾個 (28)
__builtin_ctz(0b0000'1100); // 回傳Tailing 0有幾個(2)
__builtin_ffs(0b0000'1100); // 回傳右起第一個1的位置。
__builtin_popcount(0b0000'1100); // 回傳1的個數
```
### Algorithm
再c++中有STL algorithm裡面有很多好用的function。
```cpp
#include <algorithm>
sort(vec.begin(), vec.end()); // 傳入前後的iterator,就可以幫你排序
is_sorted(vec.begin(), vec.end()); // 判斷使否為遞增序列
// 把某個範圍的__容器__內填入固定的值
// 前兩個argumnet為開始和結束的iterator
/// 在s1的string中從pos~pos+sz都填上c
fill(s1.begin() + pos, s1.begin() + pos + sz, c);
// 計算val或是char出現的次數
int cnt = count(v.begin(), v.end(), val);
// 使用count_if + lambda,如果條件成立才數
int cnt = count_if(v.begin(), v.end(), [&](int& a){
return a > b;
});
// 找出最大最小值
cout << *min_element(v.begin(), v.end()) << endl; // 輸出為iterator,取值必須使用*
cout << *max_element(v.begin(), v.end()) << endl;
// 同時找出最大最小值
auto [p_min, p_max] = minmax_element(v.begin(), v.end());
// 從幾個數中找出最大最小值
// 從兩個數找出最大最小值
min(val1, val2);
max(val1, val2);
// 從多個數中找出最大最小值
min({val1, val2, val3, ...});
max({val1, val2, val3, ...});
// 計算prefix sum
// 開始iteraotr, 結尾iterator, 存入開始iterator
partial_sum(v.begin(), v.end(), v.begin());
```
### Random
```cpp=
// 使用時間產生 random seed
srand(time(NULL));
// 產生random number
rand(); // 範圍在0 ~ RAND_MAX
```
### Enum
```cpp=
// 宣告
enum state{
stop = 0, // 給定一個整數,不然default從0開始
right,
left,
down
};
// 使用enum
int st;
if(st == stop) {...}; // 把stop視為整數
state::stop // 直接取用
```
### 排列組合
$$
P^n_k = \frac{n!}{(n - k)!}
$$
$$
C^n_k = (^n_k) = \frac{P^n_k}{k!} = \frac{n!}{k!(n-k)!}
$$
c++中沒內建計算排列組合的函式,但是簡單的排列組合,可用以下來計算。
```
m[n] * (m[n] - 1) * (m[n] - 2) / 6; // 從m[n]中取三個
m[n] * (m[n] - 1) / 2; // 從m[n]中取二個
```