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做一層包裝。

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要刪除的值到最後，然後再刪除。

#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)

 #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

#include <stack>
// declare a stack
stack<T> s;
// 常用function
s.empty(); //測試堆疊是否為空。若為空回傳 true，反之 false。
s.size(); //回傳目前堆疊中有幾個元素。
s.push(); //在堆疊中加入一個元素。
s.pop(); //移除目前堆疊中最上層元素
s.top(); //取得目前堆疊中最上層元素

Queue

#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")

#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)

#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)

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。

#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。

#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敘述。

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。

m.refresh(n);

如果我們事先知道大小可以使用以下function直接保留bucket到n，避免超出threshold需要放大container。因為事先保留了n個bucket也可以避免hash collision。

m.reserve(n);

Sort

#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

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

// 找出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。例如

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

String/Character Manipulation

string 是一個保存 char 的序列容器，把字串的記憶體管理責任交由 string 負責而不是 programmer，減輕了 C 語言風格字串的麻煩。

• 提供了大量的字串操作函式。
• 可與 C 語言風格字串雙向轉換。

#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

//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來判斷最後取值是否成功

string s{"1 2 3"};
istringstream iss(s);
char c;
while(iss >> c) cout << c;

如果資料是混合型態

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++
• Bidirectional Iterators in C++

箭頭表示繼承，所以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(<=, >=) 2.Arithmetic Operators(+=, -=, +, -) 3.Use of offset dereference operator ([ ])

// 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**

數字表示

// 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

// 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。

#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

// 使用時間產生 random seed
srand(time(NULL));
// 產生random number
rand(); // 範圍在0 ~ RAND_MAX

Enum

// 宣告
enum state{
    stop = 0, // 給定一個整數，不然default從0開始
    right,
    left,
    down
};
// 使用enum
int st;
if(st == stop) {...}; // 把stop視為整數
state::stop           // 直接取用

排列組合

$$P_k^n=\frac{n!}{(n-k)!}$$

$$C_k^n={(}_k^n)=\frac{P_k^n}{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]中取二個