樣版基礎

  1. Template 的基本觀念
    1. 是 #define 的延伸, 但比 #define 安全, 不必擔心傳入有副作用的參數.
    2. 適用於演算法固定, 與資料型別無關的場合. function template 範例: swap, bsearch, sort, ... class template 範例 ("containers"): stack, queue, BST, heap, ...
    3. 缺點: 因為重複產生程式碼, 因此大幅度增加編譯時間及可執行檔的大小.
    4. 語法: 以保留字 "template" 開頭, 以角括弧表示參數列
  2. Function Template
    1. 例: 
                      template <class T>
                void swap(T & x, T & y)
                {
                    T temp;
                    temp = x;
                    x = y;
                    y = temp;
                }

    2. 之後即可直接使用: 
                      int a, b;
                char * p, * q;
                double x, y;
                ...
                swap<int>(a, b);
                swap<char *>(p, q);
                swap<double>(x, y);

      注意: swap 只是一個函數的樣版, 不是一個函數; 應該把函數樣版後面的 < ... > 視為完整函數名稱的一部分. (其實如果從函數的實際參數就可以判斷出 template 的參數, 那麼 template 的實際參數可以省略.)
    3. specialization: 一般化的 template 函數無法滿足特殊需要時, 可單獨定義特殊的函數, 將適時取代 template. 例如字串拷貝.
  3. Class Template: 請參考 heap3.cc
    1. 例: template <class T> class stack { ... };
    2. 使用方式: 
                      stack<int> a;
                stack<complex> b;
                stack<AV> c;

    3. 如果把 member function 的定義寫到 class 定義外, 則 T top() const { return data[1]; } 將變成 (深呼吸 ...): template <class T> T heap<T>::top() const { return s[top]; }
      分析: 樣版宣告 函數傳回值 類別的成員函數() ...
    4. template 可以複合使用, 例如將一個變數宣告成由 "名稱-屬性 對照表" 所構成的堆疊: stack<map<string,property>> symbol_table;
  4. 再談 Container
    1. 其實 Container 分為兩大類: 先前介紹的 vector, list, dequeue, heap 等等叫做 Sequence containers; 另一大類叫做 Associative containers: 例如字典 dictionary (或稱 map) 的觀念, 方便使用者以 key 查詢 value 的資料結構, 可以應用於 symbol table, database, ... 等等地方.
    2. 不論是那種 container, 都適合宣告成為樣版, 因為它們都是拿來裝其他資料結構用的. 在資料結構課程當中所學的大概都是 container.
  5. Associative Container
    1. 請參考 dictionary.cc 程式範例, 與 Standard Template Library 裡面的 map 使用範例. 編譯: g++ -Wall stl_test.cc。 一篇很棒的 STL 講義
    2. 最簡單的字典: 以正整數為 key 的字典即退化為一般的陣列.
    3. Dictionary/Map 提供的基本功能:
      1. 新增: 輸入 key, value. 應檢查 key 是否與既有資料重複.
      2. 刪除: 輸入 key. 應檢查是否有既有資料符合 key.
      3. 修改: 輸入 key. 應檢查是否有既有資料符合 key.
      4. 查詢: 輸入 key. 程式界面應考慮找不到的狀況.
    4. 實作方式: unsorted array, sorted array, unsorted linked list, sorted linked list, BST, Balanced BST, ...
      Q: 試比較各個功能 (operation) 在各種實作方式下所花的時間.
    5. 範例程式的 bug: 字串是否相等的比較不應該用 == 或 != 而應該用 strcmp. Q: 但是為什麼執行起來沒有問題呢?
    6. 作業:
      1. 在 dictionary.cc 中加入 copy constructor 與 assignment operator.
      2. 試以其他資料結構實作 dictionary.
      3. 增加 modify 功能.
      4. 完全修改界面, 使用 operator [] 把增、改、查 的功能合而為一. 新的界面要能滿足上述基本功能的需求. (原程式不行)
      5. 寫一個程式, 讀入姓名、學號、四項成績, 建立兩個 dictionaries, 一個可用以根據姓名 (char const *) 查詢整筆記錄; 另一個可用以根據學號 (char const *) 查詢整筆記錄. 注意 "個人資料" 本身就可以當做一個 class.
  6. 其他
    1. 注意: template 的宣告和定義都放在 .h 檔裡.
    2. template 的參數可以不只一個, 也可以不是 class. 例: template <class S, class T> void copy(S a[], T b[], int n) ... 例: template <class T, int n_ary> class Tree { ... };
    3. 如何理解 template 複雜的語法? 把 template 名稱連同 template 的實際參數視為一個完整單獨的單位 (即函數名稱或類別名稱), 例如: swap<int> 與 stack<int>
    4. 注意定義 template class, template function, template member 語法之不同: 前二者在 template < ... > 之後即已進入 template 的 scope, 所以類別或函數名稱後面可以不寫 < ... > (寫了也沒有錯); 但是定義 template member 時 compiler 無法自動判斷 template 的參數究竟是要給類別用, 還是要給成員用, 所以類別名稱必須完整寫出 (即必須加上 < ... >). 之後的部分已進入類別的勢力範圍, 故可把整個類別名稱省略掉.