完整的範例: heapsort

  1. Container 簡介 請參考 heap1.cc 範例程式並複習四個與 memory allocation 有關的特殊成員函數.
    1. 像 vector, list, double ended queue, ... 等等這類資料結構稱為 containers (容器?), 專門用來把很多 homogeneous (同質的) 小資料結構 (稱之為 element 元素) 收集在一起. 不同的 containers 用途在於提供給使用者不同的存取元素方法, 或針對不同的運算提升效率.
  2. heap 資料結構: 有興趣的讀者請詳閱資料結構書籍; 沒有興趣的讀者可以忽略成員函數實作 (演算法) 部分.
    1. heap 是一種 container, 方便使用者隨時加入新的元素, 及取出最小的元素. 適合用於處理 "排隊" 的場合, 但是其中參與排隊的元素未必是先到先贏, 而是根據它的 "優先順序" (priority) 來決定.
    2. 儲存規則: 把陣列當做 complete binary tree 來存放元素, 最小 (優先順序最高) 的元素放在第 1 格 (樹根), 左右兩棵子樹的元素都比樹根大, 但彼此之間沒有關係. 以下類推. 第 0 格不使用.
    3. 新增: 把新元素放在最後, 再往上浮; 刪除: 把樹根拔走, 最後一個元素移到樹根, 再往下沉.
    4. 可用來排序. 所產生的排序法叫做 heap sort, 排序時間保証在 O(n log(n)) 之內.
  3. Iterator 簡介 請參考 heap2.cc
    1. 動機: 像 vector, linked list, tree, ... 等等 containers, 使用者如何寫程式 "對裡面的每個 ... 的元素做 ... 動作" ? 必須要有一個機制可以讓使用者把 container 裡面的所有元素逐一取出來看, 可是又不應該讓使用者操心 container 實作的資料結構細節 (例如 tree 有 letf pointer, right pointer, 甚至 next pointer, parent pointer ...) 對於陣列而言是很簡單; 但是其他 containers 呢?
    2. 常用的 iterator 函數:
      1. CONTAINER::iterator CONTAINER::begin() const;
        指到某個 container 的 "第一個" 元素的 "指標"
      2. CONTAINER::iterator CONTAINER::end() const;
        指到某個 container 的 "比最後一個還要更後面" 元素的 "指標"
      3. CONTAINER::iterator CONTAINER::iterator::operator++();
        讓指到某個 container 的某個元素的 "指標" 指到下一個元素
      4. VALUE & CONTAINER::iterator::operator *();
        取得某個 "指標" 所指到的元素 (用以當做 l-value 或 r-value)
  4. Access Control 簡介 (參考 complex.cc)
    1. public: 區段為公開的界面, 裡面的成員可以供任何人使用; private: 區段為不公開的實作細節, 只有 implementor 知道, 也就是說, 只有該類別本身的成員函數的作者可以使用 private: 區段的成員.
    2. 注意: access control 的目的不在保密或防止惡意寫入 (不夠的!) 而在防止程式設計師的無心之失.
    3. 在一個類別 C 當中, 把一個不屬於 C 的函數 f 宣告成 friend, 可以讓 f 打破 access control, 使用到 C 的 private 區段部分的資料成員與成員函數.
    4. 在一個類別 C 當中, 把另外一個類別 F 宣告成 friend, 可以讓 F 的所有成員函數打破 access control, 使用到 C 的 private 區段部分的資料成員與成員函數.
    5. 朋友關係未必滿足對稱律 (即使 F 是 C 的朋友, C 也未必是 F 的朋友), 也未必滿足遞移律 (即使 A 是 B 的朋友, B 是 C 的朋友, A 也未必是 C 的朋友). 到底是誰對誰開誠布公? "我對朋友開誠布公".
  5. 類別中的類別 (nested class): 例如 "臺灣的國民黨", "xx 國的國民黨"... 連同外面的 scope 一起講才算是完整的類別名稱. 作業: 把 heap1.cc 所有的成員函數定義成 out-of-line functions.
  6. 作業: 試寫出 vector, list 與 dequeue (double-ended queue) 等三個 container 類別, 元素型別一律使用 double 就好. 要把 constructor, destructor, copy constructor, assignment operator 等實作出來. 要提供 iterator.