# C++語法, 筆記整理
[toc]
## 語法
### Vector
#### 特性
集合尾端增刪元素很快 : O(1)
集合中間增刪元素比較費時 : O(n)
#### Code Example

* vec.push_back() - 新增元素至 vector 的尾端，必要時會進行記憶體配置。
* vec.pop_back() - 刪除 vector 最尾端的元素。
* [vec.insert() - 插入一個或多個元素至 vector 內的任意位置。](https://vimsky.com/zh-tw/examples/usage/vector-insert-function-in-c-stl.html)
* vec.erase() - 刪除 vector 中一個或多個元素。
* vec.clear() - 清空所有元素。
* 初始化宣告`vector<int> v = {1, 2, 3}`
`vector<int> v(3, 1)\\v={1,1,1}`

參數: 
size - 多少個數字要被新增
value - 建一個充滿value的1D vector 
declare 1D vector

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> vect{ 10, 20, 30 }; 
    //vector大小
    cout<<"vect size:"<<vect.size()<<'\n';  
    for (int x : vect) 
        cout << x << " "; 
  
    return 0; 
}
 

declare 1D vector with initial size

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> vect(10); 
    //vector大小
    cout<<"vect size:"<<vect.size()<<'\n';  
    for (int x : vect) 
        cout << x << " "; 
  
    return 0; 
}
 

declare 2D vector

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<vector<int> > vect{ { 1, 2, 3 }, 
                               { 4, 5, 6 }, 
                               { 7, 8, 9 } }; 
  
    // Displaying the 2D vector 
    for (int i = 0; i < vect.size(); i++) { 
        for (int j = 0; j < vect[i].size(); j++) 
            cout << vect[i][j] << " "; 
        cout << endl; 
    } 
}

### Stack

// CPP program to illustrate
// Implementation of push() function

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	// Empty stack
	stack<int> mystack;
	mystack.push(0);
	mystack.push(1);
	mystack.push(2);
    
    // 获取并删除栈顶的元素
    int topValue = myStack.top(); // 获取栈顶元素的值
    myStack.pop(); // 删除栈顶元素
    
	// Printing content of stack
	while (!mystack.empty()) {
		cout << ' ' << mystack.top();
		mystack.pop();
	}
}

### Array

//define
int foo [5] = { 10,5,15,3,7};  
//intialize array to zero
int array[10] = {0};
//get array size
//total byte / first byte 
int n = sizeof(foo) / sizeof(foo[0]);

### Hashmap

#include <iostream> 
#include <unordered_map> 
using namespace std; 
  
int main() 
{ 
    unordered_map<string, int> umap; 
  
    // inserting values by using [] operator 
    umap["GeeksforGeeks"] = 10; 
    umap["Practice"] = 20; 
    umap["Contribute"] = 30; 
  
    // Traversing an unordered map 
    for (auto x : umap) 
      cout << x.first << " " << x.second << endl; 
  
} 

#### Hashmap erase

#include <iostream>
#include <unordered_map>

struct Node {
    int data;
};

int main() {
    std::unordered_map<int, Node*> dict;

    // 创建一些键值对并插入到unordered_map中
    Node* node1 = new Node{1};
    Node* node2 = new Node{2};
    Node* node3 = new Node{3};
    dict.insert({1, node1});
    dict.insert({2, node2});
    dict.insert({3, node3});

    // 删除指定键的元素
    int keyToRemove = 2;
    size_t numRemoved = dict.erase(keyToRemove);

    // 检查是否成功删除了元素
    if (numRemoved > 0) {
        std::cout << "元素删除成功。" << std::endl;
        // 可以在这里释放被删除节点的内存
    } else {
        std::cout << "未找到要删除的元素。" << std::endl;
    }

    return 0;
}

### Unorderset + vector
//功能與hashmap相同,加速查找

int main() {
    int n = 4;
    vector<vector<int>> roads{{0,1},{1,2},{2,3},{2,0}};
    vector<unordered_set<int>> graph(n);
        
    // Building the graph (adjacency list). 
    for (const auto& road: roads) {
        graph[road[0]].insert(road[1]);
        graph[road[1]].insert(road[0]);
    }
    for(int i=0;i<n;i++){
        cout<<i<<":"<<graph[i].size()<<endl;
    }
}

### Tree

#include <iostream>

using namespace std;
//定義樹的結構
//        root
//       /   \
//     left right
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int main()
{
    //產生一個node,並定義node數值
    TreeNode* root = new TreeNode(10);
    //產生一個node,並定義node數值
    TreeNode* rootleft = new TreeNode(5);
    //街上root左邊的node
    root->left = rootleft;
    //imshow
    cout<<root->val<<endl;
    //把root移到左方
    root = root->left;
    //imshow
    cout<<root->val<<endl;
    return 0;
}

### string

string s ="ABCD";
int len = s.length();

### pointer

int b = 2;
//從這個地址中取出變數b的值
//&是取出地址,*是取出地址裡面的值
//*&b == b
printf("變數 b 的值：%d\n", b);
printf("變數 b 的值：%d\n", *&b);


//指標宣告方式 指標指向b的位置
int* pointer = &b


int a; // 一個整型數
int *a; // 一個指向整數的指標
int **a; // 一個指向指標的指標，它指向的指標是指向一個整型數
int a[10]; // 一個有10個整數型的陣列
int *a[10]; // 一個有10個指標的陣列，該指標是指向一個整數型的
int (*a)[10]; // 一個指向有10個整數型陣列的指標
int (*a)(int); // 一個指向函數的指標，該函數有一個整數型參數並返回一個整數
int (*a[10])(int); // 一個有10個指標的陣列，該指標指向一個函數，該函數有一個整數型參數並返回一個整數

## ostringstream istringstream

//ostringstream用法
ostringstream out;
out << "123 "
out << "456 "
cout << out.str(); // "123 456 "

//istringstream用法
string data =  "123 456 ";
istringstream in(data);
string value = "";
in >> value;
cout <<value; // "123"
in >> value;
cout <<value; // "456"

## function
### Selection sort

void selectionSort(vector<int>& a,vector<int>& idx, int n) {
   
   int i, j, min, temp,tmp_idx;
   for (i = 0; i < n - 1; i++) {
      min = i;
      for (j = i + 1; j < n; j++)
         if (a[j] < a[min] || (a[j]==a[min] && idx[j]>idx[min]))
            min = j;
         temp = a[i];
         a[i] = a[min];
         a[min] = temp;
         tmp_idx = idx[i];
         idx[i] = idx[min];
         idx[min] = tmp_idx;
   }
}

### 判斷奇數(AND應用)

    int num=10;
    if num & 1 ? cout<<"奇數": cout<<"偶數";

### 找出數列中的唯一數字(XOR應用)
預設數列內僅有一個數字出現一次,其他都是重複兩次

#include <iostream> 
#include <vector>
using namespace std; 
  
int main() 
{ 
    vector<int> nums{4,1,2,1,2};
    for(int i=1;i<nums.size();i++){
        nums[0] ^= nums[i];
    }
    cout<<nums[0];
} 

### swap(XOR應用)

void swap(int & a,int & b){
    a^=b;
    b^=a;
    a^=b;
}

# C與C++差異與其他語言差異
## C & C++ 與其他新一代語言
* (a)C & C++:
* 透過編譯器和連結器，直接產生原生的機器碼
* (b)新一代的程式語言(Java, C#):
* 透過翻譯轉成 bytecode，然後再由虛擬機器（Virtual Machine）來執行
* 優缺點
* (b)的優點:技術先進,移植性
* 可能的缺點:效率(平台差異)
* 本質上技術相同,C++ Complier可想成虛擬機器
* 虛擬機器的設定標準
* (a)是共同制定的標準
* (b)架構則是 Sun 或 MS 所制定的
* 框架差異
* 只學C/C++不能解決應用問題,因為它只有基本I/O,至少要學會一種GUI框架,或是database框架
* JAVA/C# 函式庫已包含在框架內
* 型別
* (a) 語言都是採用傳統的靜態型別系統
* 不強制改變使用者自訂型別（UDT: User-defined Type）的記憶體佈局
* 允許在 stack 中配置 UDT 變量（也就是「物件」，但由於在 C 語言中，沒有真正物件導向的觀念，因此以「變量」來指稱）
* 你無法在編譯期產生變量，也不可能在執行期產生新的「型別」
* 使得執行期的效率高
* 零成本」原則：「使用者不該為他沒有用到的功能，付出執行期的效率代價」
* (b) 單根繼承的泛化型別系統
* 型別本身也可以當作變量

* 哲學觀點
* (a)把你當大人,給予最高彈性
* (a)不強迫限制或規範
* (a)不內建垃圾回收器（GC: Garbage Collection）
## C與C++差異
* C 語言是 C++ 的一個子集
* C++改進
* 引入 bool 型別
* 鼓勵以 0 而非自行定義的 NULL 巨集等代表空指標。
* 引入 const，讓「常數性」成為與型別不可分割的一部份，除了提升安全，讓編譯器承擔檢核的責任之外，也有助於代碼的優化。
* 引入 const, inline 等用法，減少非必要巨集的使用。（因為展開　巨集是預處理器的動作，沒有通過編譯器，也就沒有型別安全可言）。
* 引入 reference 機制，簡化指標的語法，並有效減少指標（尤其是　兩層以上的複雜指標）的使用。

ref:https://www.ptt.cc/man/C_and_CPP/DB9B/D3B0/M.1475403294.A.F90.html

## bitwise operation

找出Int 第n個bit值

int find_bit_val(int num, int bits)
{
    int res = (num & (int)pow(2, bits))>>bits;
}