# C++ 筆記

- [C++ 短字串最佳化（Short String Optimization）](https://tigercosmos.xyz/post/2022/06/c++/sso/)
- C++ `#define` 和 `#include` 觀察

    假設有多個 xxx.h 和 xxx.cpp 檔案，include 的階層如下
    a -> b -> c
           -> d
      -> e -> f
           -> g
           
    若在 c.h, d.h, f.h, g.h 當中有衝突的 macro，e.g. '#define cout cout<<"C: "'
    則最後 apply 到各個 xxx.cpp 的 macro
    (1) parent 會影響到 child
        - b 的 macro 不會套用在 e.cpp 上
    (2) 根據 child include parent header 的順序，apply 最後一個
        - a.cpp 的結果，根據 include b.h 和 e.h 的順序
          及對應的 include c.h, d.h 和 f.h, g.h 順序決定

- 常見 C++ QA
- **(1) C++ 和 C 語言有什麼區別？**
- Object Oriented
- Template
- STL
- **(2) 物件導向 : 封裝、繼承、多型**
- 封裝
- 將細節隱藏，通過訪問修飾詞（public、private、protected）來實現
- (ef22) 透過封裝，為所有可能的不同實現方式提供彈性，使用者只需重新編譯
- 繼承
- 擴展類的功能
- base 類別的 private 成員不被繼承
- public 繼承 -> 保持 base 類別成員的 public 和 protected 關係
- protected 繼承 -> 繼承之後皆為 protected
- private 繼承 -> 繼承之後皆為 private
- 減少代碼重複，提高可維護性；但是過多的繼承可能導致類層次結構過於複雜
- 繼承應該符合 "is-a" 原則
- 多型
- 不同的物件對象，提供統一的介面，但有不同行為
- 動態多型 (Dynamic Binding 動態繫結)
- 虛擬函數、純虛函數
- Override 取代 base 的行為
- `base class 的指針或引用呼叫虛擬函數時，執行時期判斷要調用哪一個版本`
- 靜態多型
- Static polymorphism 當中有用到，`編譯時期判斷要調用哪一個版本`

            template<typename T> class Tool {
            public:
                void Plot() { static_cast<T*>(this)->PlotImpl(); }
                void PlotImpl() {puts("Default Tool plotting."); }
            private:    // 限定只有繼承的子類 T 可以使用這個 private constructor
                Tool() {}
                friend T;
            }

            template<typename T> void ToolHandler(Tool<T> &tool) {
                tool.Plot();
            }

- 多載和多型不同
- 函數重載（Function Overloading）: 同一個作用域中，多個同名函數，參數列表不同，呼叫時編譯會做 function match
- 運算符重載（Operator Overloading）: 定義自訂類別的運算子行為
- **(3) 動態多態性，虛擬函數**
- [C++中關於 virtual 的兩三事](https://medium.com/theskyisblue/c-%E4%B8%AD%E9%97%9C%E6%96%BC-virtual-%E7%9A%84%E5%85%A9%E4%B8%89%E4%BA%8B-1b4e2a2dc373)
- `base class 的指針或引用呼叫虛擬函數時，編譯器動態判斷，決定要調用哪一個版本`
- 虛擬函數
- 派生類型可以選擇是否重寫這個函數
- 如果沒有重寫，將調用 base class 中定義的版本
- 純虛函數
- 規範派生類型，必須實現這個函數

    class Animal {
    public:
        virtual void Cry(){ cout<<"Animal Cry"<<endl;   }
        // (1) 當沒有宣告 virtual 時，f() 函數會印 Animal Cry
        // (2) 若宣告 virtual，f() 函數會在 執行期 判斷指向的對象決定
    };

    class Dog: public Animal{
    public:
        void Cry(){ cout<<"Dog Cry"<<endl;  } // 若 base 有加 virtual，繼承後也會自動補上關鍵字 virtual
    };

    void f(Animal &ptr){
        ptr.Cry();
    }

- **(4) C++ 中的 static 關鍵字**
- global variable : 這個變數僅在當前檔案內可見
- global function : 這個函數僅在當前檔案內可見
- local variable : 在函式調用時只初始化一次，並保留其值
- member variable : 所有物件共用的，與類別相關聯而不是物件
- member function : 所有物件共用的，與類別相關聯而不是物件
- **(5) C++ 中的 STL**
- 標準模板庫（Standard Template Library）
- 提供了一系列常用的資料結構和算法，方便開發者快速開發高效、可靠的應用程序
- 容器（Containers）
- 循序容器（Sequential Containers）
- vector：動態陣列，支持隨機存取和動態大小調整。
- list：雙向鏈表，支持插入、刪除和遍歷。
- deque：雙端隊列，支持快速隨機存取和動態大小調整。
- 關聯式容器（Associative Containers） 對數級
- set/multiset：紅黑樹，自動排序，支持插入、刪除和查詢操作。
- map/multimap：紅黑樹，自動排序，支持鍵值對的插入、刪除和查詢操作。
- 容器配接器(container adapters) : 建立在其他容器之上的，以提供特定的行為
- stack：堆疊，LIFO 的資料結構，通常底層使用 vector 或 deque
- queue：隊列，FIFO 的資料結構，通常底層使用 deque 或 list
- priority_queue：優先隊列，根據優先級排序，通常底層使用 vector 或 deque
- 無序容器（Unordered Containers） : C++11 加入
- unordered_set/unordered_multiset ： 使用哈希表來實現
- unordered_map/unordered_multimap ： 使用哈希表來實現
- **(6) RAII（Resource Acquisition Is Initialization）**
- 一種管理資源的好方法，源於 C++
- 動態分配的記憶體、文件描述符、鎖
- 資源的申請和釋放應該與對象的生命週期綁定在一起，避免資源泄漏和多次釋放等問題

    void foo() {
        std::unique_ptr<int> ptr(new int(10));  // 分配動態記憶體
        // ...
    }  // 離開函數時，std::unique_ptr 會自動釋放記憶體

- **(7) C++ 中的智能指針 : shared_ptr / unique_ptr / weak_ptr**
- **(8) C++ 的模板（template）**
- 在不知道實際使用的資料型別或參數的情況下，編寫通用的程式碼，提高程式碼的重複利用性和可維護性
- 編譯器會根據實際使用的資料型別或參數進行實例化
- 類型模板 template class

        template<typename T>
        class Stack {
        private:
            std::vector<T> stack_;
        public:
            void push(const T& item) { stack_.push_back(item); }
            void pop() { stack_.pop_back(); }
            T& top() { return stack_.back(); }
            bool empty() const { return stack_.empty(); }
            size_t size() const { return stack_.size(); }
        };

- 函數模板 template function

        template<typename T>
        T max(T a, T b) {
            return a > b ? a : b;
        }

- **(9) C++ 的常量和引用**
- 字面值常量 : 特定字面值表示的常量，如 1、2、"hello" 等
- 符號常量 : 使用 const 關鍵字聲明，如 const int MAX_SIZE = 100
- 引用
- 一個已存在變量的別名
- 一種類型安全的指針，不需要使用 * 和 -> 運算符來訪問
- 引用的初始化只能在聲明時進行，不能再進行修改
- **(10) C++ 中的移動語意（move semantics）。**
- 通過將對象的所有權（ownership）從一個對象轉移到另一個對象，以提高程序的效率
- 通過使用右值引用（rvalue references）實現
- **(11) 修改 pointer 指向的用法**

    int B = 2;
    void f0(int *p){ p = &B; } // wrong
    void f1(int **p){ *p = &B; } // correct
    void f2(int *&p){ p = &B; } // correct
    
    int main(){
        int A = 1;
        int *ptrA = &A;

        // f0(ptrA);
        // f1(&ptrA);
        // f2(ptrA);
        printf("%d\n", *ptrA);
        return 0;
    }

- 解釋以下語法和關鍵字

    int *const ptr = # // 不可以指向不同位置，但可以改值
    int const *ptr2 = # // 指向 const int，不可以改值
    const int *ptr3 = # // 指向 const int，不可以改值
    
    int (*ptr)[10];  // 一個指標，指向 int [10] 的位置
    int *p[10];      // 十個指標，指向不同 int 的位置
    cout<<sizeof(*ptr)<<endl; // 10 乘以整數的大小
    cout<<sizeof(p)<<endl; // 10 乘以指標的大小
    
    struct : 包含一些成員，這些成員可以同時存在於內存中
    union : 包含一些成員，這些成員共享內存
    volatile : 告訴編譯器變量可能會被意想不到地改變，避免過度優化（尤其在嵌入式系統）
    
    Macro : 在預處理時單純的文字替換
    Inline function : 在 compile 階段取代
    

- 考題
- Hash table
- 事先預留空間，透過 hash function 把資料定址
- (1) [open addressing](http://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html)
- (2) [chaining](http://alrightchiu.github.io/SecondRound/hash-tablechaining.html)
- vector, array, list 差別
- vector : 動態數組，底層空間連續，支持隨機訪問和快速的尾部插入和刪除，可以重新分配空間
- array : 靜態數組，底層空間連續，元素個數在編譯時就已經確定了，元素個數變動時不方便，支持隨機訪問
- list : 雙向鏈表，底層使用指針，支持快速的插入和刪除操作，不支持隨機訪問
- strcat, strcpy
- [strcat](https://skylinelimit.blogspot.com/2018/02/c-5.html) : 複雜度為 $O(n+m)$ 而非 $O(m)$
- [strcpy](https://skylinelimit.blogspot.com/2018/02/c-2.html)