# C++
[TOC]
<!-- 工程師三大錯覺:
- 你會寫 C++
- 系統上線不會爆
- 交的到女朋友
筆者本人是一個不會寫 C++ 的資工學生，為什麼會說我**不會寫** C++ 呢?
因為我覺得:
- C++ 包山包海，根本學不完
目前會比較常用的語法幾乎都還停留在 C++ 11，至於 C++ 14, 17, 20... 我學不動了...
- 因為包山包海，所以複雜
C++ 一開始作為 C 語言的擴充版本，到後期已經衍伸出屬於自己的生態圈。基本上，C 與 C++ 現在根本不能算是同一類型的程式語言 (除非你寫 90 年代的 C++ 程式)。
談到這裡，你可能會想問我: 既然 C++ 這麼不親民，那你幹嘛還要學習 C++?
誕生在資訊世代的程式語言有這麼多，能夠受到多數開發者支持的主流程式語言一定都有其優點。對我來說，會讓我想學 C++ 的動機就是**刷題!**
因為 C++ 有著非常強大的函式庫與功能，像是:
- Standard Template Library (STL)
- Template
- Auto
- OOP Supported
這些已經造好的輪子 (資料結構與演算法) 用於刷題真是再適合不過了!
當大家還在用其他語言造輪子，C++ 使用者可以立即使用 STL 與它的函式成員解決程式題庫無理的要求，其便利性與效率都不是其他程式語言可以相比擬的。
因此，我決定認命學習 C++ 的必要部分，順便將它整理成筆記分享給深受同害的朋友們。 -->
### 主要參考文獻
- [Microsoft Docs ](https://docs.microsoft.com/zh-tw/cpp/cpp/?view=msvc-160)
- [AIdrifter CS 浮生筆錄](https://hackmd.io/ww2WwMVDRZWo9CMm2FgtYA?view)
- [Google C++ Style Guide 繁體中文版](http://www.slmt.tw/google-cpp-style-guide-zh-tw/index.html)
- [chenlen.com](https://chenlen.com/)
- [cplusplus.com](https://www.cplusplus.com/reference/)
- [山姆大叔談 C++：從歷史談起，再給個定義—Modern C++ 解惑系列文](https://ithelp.ithome.com.tw/users/20120425/ironman/2507)
- [比較安全的 C++ 虛擬函式寫法：C++11 override 與 final](https://kheresy.wordpress.com/2014/10/03/override-and-final-in-cpp-11/)
## 使用 VSCode 開發 C++
## Header files
本文介紹了設計 Header files 應該要注意的眉眉角角。
這些須注意事項主要是參考 Google C++ Style Guide 以及我個人開發系統程式的經驗。
### Self-contained Headers
所有標頭檔都應該符合 Self-contained。
也就是說，假設使用者要引入 A 標頭檔，無須引入 B, C, D 等 A 使用到的相依標頭檔。
因此，開發者在設計標頭檔時應自行插入該檔案所需要的所有標頭檔。
### The #define Guard
承接上面提到的 Self-contained Headers，我們可以思考一下:
假設我今天使用到了 A 和 B 標頭檔，但兩者都使用了 C 標頭檔，這樣會不會出現重複載入的問題呢?
### 標頭檔案的引入順序
## Scopping
### Namespace
## New features in C++ 11
ISO/IEC 14882 是 C++ 程式語言的標準，這類的規格書會規範程式語言的特性和語法，方便不同開發團隊實作適用 C++ 的編譯器專案。
至於 C++ 11 (ISO/IEC 14882:2011) 則是 ISO/IEC 14882 的第三個版本，前兩個版本分別是:
- ISO/IEC 14882:1998 (C++ 98)
- ISO/IEC 14882:2003 (C++ 03)
從時間線上可以觀察出 C++ 的第二版與第三版標準間隔了好一段時間，也因為這個緣故，C++ 11 更新了非常多個功能，所以又有人稱 C++ 11 與之後的版本是 Modern C++。
至於本文要介紹的功能則會以**筆者自己刷題要用的功能為主**，其他的功能就...再看看吧 XD
### Template
### Range based for-loop
C++ 11 提供了 Range based 的 For 迴圈，如果我們使用一般的迴圈尋訪一個陣列或是 STL Container，會需要這樣做:
```cpp
std::array<int, 4> arr{0, 4, 3, 2};
for (std::array<int, 4>::iterator it = arr.begin(); it != arr.end(); it++)
{
std::cout << *it << std::endl;
}
```
使用 Range based for-loop 以後，程式碼可以這樣寫:
```cpp
std::array<int, 4> arr{0, 4, 3, 2};
for (int it : arr)
{
std::cout << it << std::endl;
}
```
我們可以發現，上面的範例省去了很多的條件判斷式。不只如此，它還幫我們做了 Dereference 的操作，讓開發者可以少打很多程式碼 XD
不過到目前為止，都還沒有提到 STL，所以我們先用基礎型別來作範例吧!
遍歷陣列:
```cpp
int my_array[5] = {1, 2, 3, 4, 5};
for (int x : my_array)
{
std::cout << x << endl;
}
```
遍歷並修改陣列元素:
```cpp
int my_array[5] = {1, 2, 3, 4, 5};
// double the value of each element in my_array:
for (int x : my_array)
{
x *= 2;
}
```
如果將上面提供的範例執行，`my_array` 的元素並不會被加倍，如果要達到預期目標，我們需要將他的 Reference 傳入:
```cpp
int my_array[5] = {1, 2, 3, 4, 5};
// double the value of each element in my_array:
for (int &x : my_array)
{
x *= 2;
}
```
### Auto type
:::info
ref:
- [C++11 新特性之基本范围的 For 循环（range-based-for）](https://blog.csdn.net/hailong0715/article/details/54172848)
:::
## STL Container
### What's STL
標準模板庫 (Standard Template Library, STL)
### Example: Vector
> [圖片來源](https://mropengate.blogspot.com/2015/07/cc-vector-stl.html)
Vector 是強化版的 Array ，提供了更多靈活的成員函式， STL 的好處就是不用自己動手造輪子，就有一些增強型的資料結構可以使用。
Vector 有以下特性:
- 對末端元素進行 (新增/刪除) 操作的速度極快: O(1)
- 對前端元素進行 (新增/刪除) 操作的速度極慢: O(n)
- 查詢速度: O(n)
### 成員函式
- begin()
- end()
- size()
- max_size()
- empty()
- swap()
### 存取方式
```cpp=
vec[i];
vec.at(i) // 與 vec[i] 等效
vec.front() // return the first element in vector
vec.back() // return the last element in vector
```
### 新增與移除
```cpp=
vec.push_back(); // push
vec.pop_back(); // pop
vec.insert(); // 新增一或多個元素到 vector 的任意位置
vec.erase(); // 刪除 vector 中一或多個元素
vec.clear(); // clear all
```
### 取得長度
```cpp=
vec.empty(); // return true if vector is empty
vec.size();
vec.resize(); // re-size the length of vector
vec.capacity(); // 取得 vector 目前可容納的最大元素個數
vec.reverse(); // Reverses the order of the elements in the range [first,last).
```
### 使用範例
```cpp=
#include <vector>
using namespace std;
int main(){
vector<int>ivec;
for(int i = 0; i < 24; i++){
ivec.push_back(i);
}
}
```
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<string> vec;
vec.push_back("ss");
vec.pop_back();
vec.push_back("abc");
vec.push_back("dfg");
for (auto it = vec.begin(); it != vec.end(); it++){
cout << *it << endl;
}
return 0;
}
```
### What's Iterator?
```
想提問，iterator 跟指標有什麼不一樣?
```
簡單地講，指標基本上只是在記錄該變數（物件、資料...etc）在記憶體中的位址；iterator 比較抽象，它算是抽象過後的拜訪規則。
```c=
int a = 10;
int *b = &a;
```
而 iterator 比較像是「我要怎麼**依序**拿到這一串資料中的每個資料」，最簡單的例子是連續陣列 (array)，但這個很簡單，語法上你只要透過 index 就可以依序拿；但很多資料結構並不是用這麼簡單的方式來排列，iterator 就變成像是一個共通的語言，讓程式語法在依序拿資料時有個一樣的寫法。
```cpp
std::vector<int> a;
for (std::vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
```
## More STL Container
### 常見標頭檔
```c++=
#include <vector>
#include <deque>
#include <list>
#include <set> // set and multiset
#include <map> // map and multimap
#include <unordered_set> // unordered set/multiset
#include <unordered_map> // unordered map/multimap
#include <iterator>
#include <algorithm>
#include <numeric> // some numeric algorithm
#include <functional>
```
### dequeue
跟 vector 差不多，可是多了 `push_front()` 可以用：
```c++
deque<int> deq = { 4, 6, 7 };
deq.push_front(2); // deq: {2, 4, 6, 7}
deq.push_back(3); // deq: {2, 4, 6, 7, 3}
// Deque has similar interface with vector
cout << deq[1]; // 4
```
### list
STL 的 list 是 doubly linked-list：
:::info
Doubly linked-list 的特性如下：
1. 非連續的記憶體（可擴充性強）
2. 查找起來比 array 慢（拜非連續記憶體儲存所賜）
:::
```c++
list<int> mylist = {5, 2, 9 };
mylist.push_back(6); // mylist: { 5, 2, 9, 6}
mylist.push_front(4); // mylist: { 4, 5, 2, 9, 6}
list<int>::iterator itr = find(mylist.begin(), mylist.end(), 2); // itr -> 2
mylist.insert(itr, 8); // mylist: {4, 5, 8, 2, 9, 6}
// O(1), faster than vector/deque
itr++; // itr -> 9
mylist.erase(itr); // mylist: {4, 8, 5, 2, 6} O(1)
mylist1.splice(itr, mylist2, itr_a, itr_b ); // O(1)
```
### Set
> 接下來的 STL Container（包括 Set）都是屬於 Associated STL Container，也就是 key-value 對應關係的資料結構實作。
* Properties:
* 1. Fast search: O(log(n))
* 2. Traversing is slow (compared to vector & deque)
* 3. No random access, no [] operator.
```c++=
set<int> myset;
myset.insert(3); // myset: {3}
myset.insert(1); // myset: {1, 3}
myset.insert(7); // myset: {1, 3, 7}, O(log(n))
set<int>::iterator it;
it = myset.find(7); // O(log(n)), it points to 7
// Sequence containers don't even have find() member function
pair<set<int>::iterator, bool> ret;
ret = myset.insert(3); // no new element inserted
if (ret.second==false)
it=ret.first; // "it" now points to element 3
// 原本插入要log(n) 先用iterator先找到後 插入只要O(1)
// 當然iterator在找的時候也是花掉log(n)
myset.insert(it, 9); // myset: {1, 3, 7, 9} O(log(n)) => O(1)
// it points to 3
myset.erase(it); // myset: {1, 7, 9}
myset.erase(7); // myset: {1, 9}
// Note: none of the sequence containers provide this kind of erase.
```
### multiset
- multiset is a set that allows duplicated items
- set and multiset : value of the elements cannot be modified
- you may destory the data structure => matain failed ...
```c++=
// multiset is a set that allows duplicated items
multiset<int> myset;
// set/multiset: value of the elements cannot be modified
*it = 10; // *it is read-only
```
### map
- No duplicated key
```C++
map<char,int> mymap;
mymap.insert ( pair<char,int>('a',100) );
mymap.insert ( make_pair('z',200) );
map<char,int>::iterator it = mymap.begin();
mymap.insert(it, pair<char,int>('b',300)); // "it" is a hint
it = mymap.find('z'); // O(log(n))
// showing contents:
for ( it=mymap.begin() ; it != mymap.end(); it++ )
cout << (*it).first << " => " << (*it).second << endl;
```
### multimap
- multimap is a map that allows duplicated keys
- value can be modifed , but key can not be modified.
- because key is the index ...
```C++
// multimap is a map that allows duplicated keys
multimap<char,int> mymap;
// map/multimap:
// -- keys cannot be modified
// type of *it: pair<const char, int>
(*it).first = 'd'; // Error
```
### unordered_map
- 內部不會排序
- 使用 hashtable 實作
- 讀取效率為 `O(n)`，worst case 為 `O(1)`
```cpp=
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
unordered_map<string, int> umap;
int main()
{
umap.insert(pair<string, int>("s", 3000));
auto it = umap.begin();
umap.erase(it);
umap.insert(make_pair("ss", 56000));
cout << umap["ss"] << endl;
umap.erase("s");
for (auto it: umap) {
cout << it.first << it.second << endl;
}
return 0;
}
```
> https://shengyu7697.github.io/std-unordered_map/
## STL 常用函式
### std::sort
```cpp
#include <iostream>
#include <algorithm>
int main() {
int arr[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr, arr+10);
std::cout << "sort array by default (increasing):" << std::endl;
for (int i = 0; i < 10; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
```
搭配 C++ 11 特性與 STL 的 Vector 排序範例:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> vec{0, 4, 3, 2};
for (auto x : vec)
{
std::cout << x << std::endl;
}
std::sort(vec.begin(), vec.end());
for (auto x : vec)
{
std::cout << x << std::endl;
}
return 0;
}
```
### std::copy
```cpp
/* https://www.cplusplus.com/reference/algorithm/copy/ */
template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
while (first!=last) {
*result = *first;
++result; ++first;
}
return result;
}
```
- InputIterator first
要複製的容器的起始位址
- InputIterator last
要複製的容器的最後一個位址
- OutputIterator result
目標容器
```cpp
/* https://www.cplusplus.com/reference/algorithm/copy/ */
#include <iostream> // std::cout
#include <algorithm> // std::copy
#include <vector> // std::vector
int main () {
int myints[]={10,20,30,40,50,60,70};
std::vector<int> myvector (7);
std::copy ( myints, myints+7, myvector.begin() );
std::cout << "myvector contains:";
for (std::vector<int>::iterator it = myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
```
### size()
```cpp=
#include <iostream>
#include <vector>
using namespace std;
vector<int> vec;
cout << vec.size() << endl;
```
### empty()
```cpp=
if (vec.empty()) {
cout << "Not possible.\n" << endl;
}
```
### swap()
```cpp=
vector<int> vec2(vec); // Copy constructor, vec2: {4, 1, 8}
vec.clear(); // Remove all items in vec; vec.size() == 0
vec2.swap(vec); // vec2 becomes empty, and vec has 3 items.
```
## 左值與右值
### 如何分類
左值與右值的根本區別在於**是否允許取位址 `&` 運算子獲得對應的記憶體位址。**
- 左值
左值是對應到記憶體中有確定儲存位址的物件的表達式的值
- 右值
是所有非左值的表達式的值
```cpp=
int& foo1();
int foo2();
foo3();
int a,b[3];
a; //左值
b; //左值
b[0]; //左值
a+b[1]; //右值
foo1(); //左值
foo2(); //右值
foo3(); //右值
```
在 C++ 03 以前的標準定義了在表達式中左值到右值的三類隱式自動轉換:
- 左值轉為右值
如整數變數 `i` 在表達式 `i+3`
- 陣列名是常數左值
在表達式中轉化為陣列首元素的位址值
- 函式名是常數左值
在表達式中轉化為函式的位址值
https://cat.chriz.hk/2022/01/c-reference-collapsing-forwarding.html
## The rule of five
:::info
ref:
- [建構函式 (C++)](https://docs.microsoft.com/zh-tw/cpp/cpp/constructors-cpp?view=msvc-160)
- [C++11 明確地控制預設函式：delete 與 default](https://kheresy.wordpress.com/2014/10/09/c11-default-and-delete/)
- [C++中的左值、右值、參考與搬移語意
5月 02, 2017](http://changlt.blogspot.com/2017/05/c.html)
:::
- 解構子
- 複製建構子
- 設定運算子
- 移動建構子
- 移動指定運算子
### copy & move
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Box {
public:
Box() { std::cout << "default" << std::endl; }
Box(int width, int height, int length)
: m_width(width), m_height(height), m_length(length)
{
std::cout << "int,int,int" << std::endl;
}
Box(Box& other)
: m_width(other.m_width), m_height(other.m_height), m_length(other.m_length)
{
std::cout << "copy" << std::endl;
}
Box(Box&& other) : m_width(other.m_width), m_height(other.m_height), m_length(other.m_length)
{
m_contents = std::move(other.m_contents);
std::cout << "move" << std::endl;
}
int Volume() { return m_width * m_height * m_length; }
void Add_Item(string item) { m_contents.push_back(item); }
void Print_Contents()
{
for (const auto& item : m_contents)
{
cout << item << " ";
}
}
private:
int m_width{ 0 };
int m_height{ 0 };
int m_length{ 0 };
vector<string> m_contents;
};
Box get_Box()
{
Box b(5, 10, 18); // "int,int,int"
b.Add_Item("Toupee");
b.Add_Item("Megaphone");
b.Add_Item("Suit");
return b;
}
int main()
{
Box b; // "default"
Box b1(b); // "copy"
Box b2(get_Box()); // "move"
cout << "b2 contents: ";
b2.Print_Contents(); // Prove that we have all the values
char ch;
cin >> ch; // keep window open
return 0;
}
```
## What's Virtual function
### Virtual & override
- Parent 實作 Virtual Function，繼承的類別可以選擇採用或是複寫 (override)。
### Pure virtual fuction
- 完全不實作，留給繼承的類別實作。
## Smart pointer
在傳統的 C/C++ 程式中，使用動態分配記憶體需要留意已分配記憶體是否會在正確的時間點回收。
### Memory leak
如果在記憶體使用完畢後沒有將其釋放，而指向這塊記憶體的指標又被用於指向其他記憶體位址。這樣一來，程式便無法取得已分配的記憶體位址，無法得知位址也就代表我們沒有能力去回收這塊已分配的記憶體，這樣的情況便是 **Memory leak**。
### 回到正題: 學習使用 Smart pointer
Smart pointer 的出現幫助我們解決了這個叫人頭痛的困擾。
#### unique pointer
- 離開執行範圍會自動回收記憶體
- 有**所有權概念**，若要交由其他類別或是實體使用需進行**所有權轉移**。
```cpp=
/* https://ithelp.ithome.com.tw/articles/10213866 */
bool WorthBuying()
{
std::unique_ptr<TeaShopOwner> the_owner = std::make_unique<TeaShopOwner>();
if (the_owner->SupportCCP())
return false;
if (!the_owner->AdmitTaiwanAsACountry())
return false;
return true;
}
```
轉移擁有權有兩種方法:
- 方法一: 使用 `release()` 成員函式
```cpp=
/* https://ithelp.ithome.com.tw/articles/10214031 */
auto tea_owner = std::make_unique<TeaShopOwner>();
if (tea_owner->HitByCCPDirtyTrick()) {
TeaShopOwner* ccp = tea_owner.release();
delete cpp;
}
```
- [x] `tea_owner.release()` 呼叫的是 `std::unique_ptr` 的成員函式。
- [x] `tea_owner->HitByCCPDirtyTrick()` 會呼叫到 `TeaShopOwner` 的成員函式。
- 方法二: 使用 `std::move()`
```cpp=
auto tea_owner = std::make_unique<TeaShopOwner>();
if (tea_owner->HitByCCPDirtyTrick()) {
TransferOwner(std::move(tea_owner));
}
```
#### shared pointer
- 可以被多個實體持有
- 等到持有該 pointer 的所有物件都離開執行範圍才會回收記憶體。
```cpp=
std::shared_ptr<TeaShopOwner> owner = std::make_shared<TeaShopOwner>();
std::shared_ptr<TeaShopOwner> ccp_owner = owner;
try {
ccp_owner->SetOneCountryTwoSystem(true);
}
catch (const Never& e) {
}
```
> [more details...](https://ithelp.ithome.com.tw/articles/10214337)
## 讀取測資
- [[C++] 在 cin 後使用 getline() 會遇到的問題](https://aprilyang.home.blog/2020/04/10/getline-after-cin/)
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<int> num;
int main() {
int n,r,s;
cin>>n;
while (n‐‐) {
cin >> r;
num.clear();
for (int i=0;i<r;i++) {
cin>>s;
num.push_back(s);
}
// 剩下的留給你完成，提示：中位數。
cout<<endl;
}
return 0;
}
```
### long long
```cpp=
long long x = 123456789123456789LL;
int a = 123456789;
long long res = (long long)a * a;
```
## 習題
### [Leetcode #322 Coin Change](https://leetcode.com/problems/coin-change/)
```c++
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
vector <int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 0; i < dp.size(); i++) {
for (int coin: coins) {
/* 如果總額比硬幣的面額還大，那無解 */
if (coin > i) {
continue;
} else {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return (dp[amount] == amount + 1)?(-1):(dp[amount]);
}
};
```
### [918. Maximum Sum Circular Subarray](https://leetcode.com/problems/maximum-sum-circular-subarray/submissions/)
```c++
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int min_sum = INT_MAX;
int max_sum = INT_MIN;
int cur_min = 0;
int cur_max = 0;
int total_sum = 0;
for(int n: nums){
total_sum += n;
cur_max += n;
max_sum = max(cur_max, max_sum);
cur_max = max(cur_max, 0);
cur_min += n;
min_sum = min(cur_min, min_sum);
cur_min = min(cur_min, 0);
}
if (max_sum < 0)
return max_sum;
else
return max(max_sum, total_sum - min_sum);
}
};
```
### [f698: 後序運算式](https://zerojudge.tw/ShowProblem?problemid=f698&fbclid=IwAR2MuYASwew_UcoXuiasBwOjP1smJuPYkDn-4uUJyoUZfWeyT9PvN5gKF1g)
```
1 2 + 3 * (Ans = 9)
```
想法：
- 數字進來的話放 Stack
- 遇到運算子就 Pop 兩個數字
```c++
#include <stack>
#include <iostream>
#include <string>
using namespace std;
int main() {
stack <int> stk;
string input;
int a, b;
while (cin >> input) {
if (isdigit(input[0]) || (input.size() > 1)) {
stk.push(stoi(input));
} else {
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
switch (input[0]) {
case '*':
stk.push(a*b);
break;
case '/':
stk.push(b/a);
break;
case '+':
stk.push(a+b);
break;
case '-':
stk.push(b-a);
break;
}
}
}
cout << stk.top() << endl;
}
```
Sign in with Wallet
Connect another wallet