泛型程式設計(Generic Programming)

元智大學 92-2 課程備忘錄

侯捷

請注意:這裡只是備忘錄,不是完整教材或學習或討論的地方。

每周三 18:30~21:20
工程一館1102


課程教材(5 為教材,1,2,3,4,6,7,8 為輔助資料或書籍):

   1.《C++ Primer 3e》by Lippman & Lajoie. chap6,10,12,15,16, appnedix
   2.  "STL系列文章" by 侯捷,共五篇,見左視窗目錄大標題(白色)
   3.《泛型程式設計與STL》, "Generic Programming and the STL" by Matthew H. Austern.
   4.《C++ 標準程式庫》, "The C++ Standard Library", by Nicolai M. Josuttis.
* 5.《STL源碼剖析》by 侯捷
   6.《C++ Templates 全覽》, "C++ Tempaltes", by Vandevoorde & Josuttis.
   7.《C++ 設計新思維》, "Modern C++ Design" by Andrei Alexandrescu.
   8.《Effective STL》by Scott Meyers.


期末作業。各組任選一題。評分將視選題困難度而有所調整。
評分根據:選題困難度、程式可執行度、程式手法優劣、目標達成度、
                    上台演出情況、書面報告。
1.  改善 SGI STL memory pool 的效率。其優缺點可從「 2002/09 池內春秋
       memory pool 的設計哲學和無痛運用」一文中的執行步驟看出。繳交的作業必須也能   執行相同(或類似)的步驟,並以相同(或類似)的畫面顯示出你的改善效果。

2. 任選 deque, rb-tree, hashtable, sort, copy, next_permutation, prev_permutation ...等在複雜度上具有代表性的容器或演算法,以交談方式逐一獲得輸入數據,再以圖形方式展現其內容之逐一變化。(展現的螢幕圖形,應類似書中的圖)。

有同學詢問是否可使用 Java 完成繪圖部分,我的回答是你可以使用任何語言、任何工具來輔助繪圖,只要最終可形成一個獨立的可執行檔(.exe)。但若你選擇 C++ 以外的語言,如何讓你的繪圖組件和 C++ STL 溝通呢?畢竟你需要從 STL 取得每次交談式輸入數據後的容器或演算法的內容變化。

另有同學詢問可否使用 SGI (GNU C++) 以外的版本完成上述題目。我的回答是 OK。但是第一道題目中所說的 memory pool,只存在於 SGI(或其衍化)版本中。就我所知 STLPort  http://www.stlport.org/ 是一套以 SGI 版為基礎的高可攜性 STL,應該可以輕鬆移植到眾多主流編譯器上。

■第1週:02/18(第一次上課
1 課程介紹,遊戲規則,書籍評介,期末作業題目(未定),助教協助購書
2 GP (Generic Programming) and STL overview
// 程式一
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int intcmp(const void* a1, const void* b1)
{
  const int* a = (const int*)a1;
  const int* b = (const int*)b1;

  if (*a < *b)  return -1;
  if (*a == *b) return 0;
  if (*a > *b)  return 1;
}

void main()
{
  int ilist[5]={8,20,7,98,105};
  int  i, ret, key=7;

    printf("%d \n", sizeof(ilist[0]));    // 4
    qsort(&ilist, 5, sizeof(ilist[0]), intcmp);
    for (i=0; i<5; i++)
         printf("%d \n", ilist[i]);
    if (0==bsearch(&key, &ilist, 5, sizeof(ilist[0]), intcmp))
        printf("not found\n");
    else
        printf("find\n");
}

// 程式二
// headers 應採用新的規格
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

// 一個用以列印的 functor

template<typename T>
class printElem
{
public:
   void operator()(const T& i)
   {  cout << i << ' ';  }
};

int main()
{
  int ia[10] = {2,6,9,14,49,70,38,90,71,28};

  // 使用 vector
  vector<int>  vi(&ia[0], &ia[10]);
  vi.push_back(38);

  cout << vi.size() << endl;      // 11
  cout << vi.capacity() << endl;  // 20(每次成長兩倍)
  for(int i=0; i<vi.size(); ++i)
      cout << vi[i] << ' ';

  // 使用 iterators
  vector<int>::iterator  ite1 = find(vi.begin(), vi.end(), 49);
  vector<int>::iterator  ite2 = find(vi.begin(), vi.end(), 90);

  cout << *ite1 << endl;  // 49
  cout << *ite2 << endl;  // 90

  cout << "jjhou" << int(5) << endl; // 暫時物件

  sort(vi.begin(), vi.end());

  for_each(vi.begin(), vi.end(), printElem<int>());
}
■第2週:02/25
《STL源碼剖析》書到。眳p予 7 折優惠。   
Console 模式中使用C/C++ 編譯器
繼續練習 STL 實例
各種 STL containers 和 STL algorithms(以及其他組件)的運用,是很有趣的。
同學應該自己動手試試。

這裡附上一個 .ppt,對本次課中許多同學所疑惑的 functor和 for_each() 或許有幫助。

同學發問 :

Dear teacher:
老師,我想把有關for each第三個參數的問題再延伸一下,雖然老師您今天說使用functor比function pointer的overhead稍稍大了一點,那為什麼我們不大量改用fuction pointer,而仍舊使用functor為主(我記得老師今天說過,在STL裡面常使用functor),fuctor是有存在什麼過人的優點,讓我們非使用fuctor不可呢?還麻煩老師在下週上課時,能為我解答一二。


Sent: Thursday, February 26, 2004 6:35 PM
Subject: 侯老師您好
最近玩了一下STL,
發現algorithm當中,
random_shuffle很奇怪耶,
寫好的程式,
若每次的array初值都是一樣,
經過它的亂序排列,
每次執行程式的結果,結果都一樣?

int main(int argc, char* argv[])
{
cout << "Please Input Range Number N(i.e.,1~N):";
int N;
cin >> N;
cout << endl;

vector<int> NUMBER(N);
cout << "Original Order:" <<endl;
for(int i=0;i<N;i++)
{
NUMBER[i]=i+1;
cout << NUMBER[i] << ",";
}

random_shuffle(NUMBER.begin(),NUMBER.end());

cout << endl << "After Shuffle Order:" << endl;
for(int i=0;i<N;i++)
{
cout << NUMBER[i] << ",";
}
}


Sent: Thursday, February 26, 2004 1:06 PM
Subject: about function pointer...please.
侯老師 您好 :
有個 function pointer 的問題想請教您.
我的目的是要用一個函式指標陣列去索引到各個函式, 各函式的參數型別及數量都不盡相同, 我試了簡略符號 (Ellipses) ,可是這樣宣告的話 ,編譯時就有錯. (我的編譯器是 Borland C++ Builder 4.0 ) 您可以撥冗幫我看看嗎 ? 謝謝.
程式碼如後,錯誤訊息如附件.
祝教安

#pragma hdrstop
#include <condefs.h>
#include <stdlib.h>
int f1(int);
int f2(int,int);
int f3(int,int,char);
//---------------------------------------------------------------------------
#pragma argsused
int main(int argc, char* argv[])
{
int (*ftn[3])(int,...)={f1,f2,f3};
return 0;
}

int f1(int i)
{
return i;
}

int f2(int i,int j)
{
return i+j;
}

int f3(int i,int j,char *a)
{
int ia=atoi(a);
return i*j*ia;
}

 

■第3週:03/03
書續到。眳p予 7 折優惠。   
繼續練習 STL 實例
本周複習 Class Templates

這個  .ppt 是本課程講義

Q1:
const Complex operator+(const Complex& x) {
    return Complex<T>(*this) += x;          //是什麼意思
}
A1: 以 *this 為初值產生一個暫時物件,將該暫時物件加上 x,傳回。

Q2: for_each() 的參數為什麼採用pass by value?
A2: 我認為 STL 設計者的一個可能想法是:傳入的 first iterator 在 for_each() 中有所改動,因此不希望影響呼叫端。傳入的 functor也可能有所改動(因為其 operator()被呼叫後難保不會改變其state),不希望影響呼叫端。至於 last,的確不會被改動。

Q3: binary_search() 為什麼可以接受 forward_iterator?
A3: 從《STL源碼剖析》p379 -->p375可知,binary_search() 使用 lower_bound(),後者有兩個版本,一是 forword iterator版本,較慢。一是random access iterator 版本,較快。編譯器會根據程式實際所給的 iterator type 決定呼叫哪一個版本。

Q4:
const C obj1;
C obj2;
C obj3 = obj1 + obj2; 是否需要一個 member function operator+ const { ... } ?
A4: 是的。如果只有 member function operator+ { ...},編譯不過。

Q5: 請再次解釋 overloading

■第4週:03/10
本周複習 Function Templates
本周複習 Operator overloading
.ppt 本課程講義
另例
■第5週:03/17
.ppt 本課程講義
本周複習 
static members, 
new expression and operator new, 
delete expression and operator delete, 
array new, 
memory pool concept
本周主題:STL Allocator
更多資訊 2002/09 池內春秋
■第6週:03/24
.ppt 本課程講義
本周主題:STL Allocator
■第7週:03/31
.ppt 本課程講義
本周主題:Iterator  Tratis
■第8週:04/07
.ppt 本課程講義
本周主題:
(1) Type  Tratis
(2) STL Lite
yz-allocator.h
yz-list.h
yz-algorithm.h
yz-functional.h
yz-iterator.h
yz-main.cpp
同學很用心地回去查了字典,給了我一封信如下。我很開心同學的態度。
昨天提到了尸位素餐這個成語,所以我回家後便查了一下典故,希望能跟老師分享。

屍音史,是古代祭禮中的一個代表神像端坐看而不須要做任何動作的人。
“書經”有句道:“太康尸位””尸位就是源出於此,用來比喻一個有職位而
沒有工作做的人,正如祭禮中的屍,只坐在位上,不必做任何動作一樣。
“素餐”也是出於詩經:“彼君子兮,不素餐兮。”後人於是用“素餐”來比喻
無功食祿的人。把“尸位”和“素餐”兩者連合成為一句成語,應該說是
出於“漢書”,因為該書的“朱雲傳”裹:“今朝廷大臣,上不能匡主,
下亡以益民,皆尸位素餐。”整句成語的意思,也是和上述的尸位和素餐相同。
這樣說,我們要研究成語的出處,對這句成語分合的出處,也應該詳細知道。

一般機關、社團、商店的冗員,憑看人事或其他特殊的關係,只知道每月按期
領取薪金,每日吃喝閒坐,而不做任何工作,這種人都可以說是“尸位素餐”。
此外,一般工作能力很差的人,雖然已經盡了自己的能力服務,但事情總是做不好,
毫無成積可言,這種人能夠保持職位,不是靠自己的本領,而是藉著特殊關係,
因此也可以說“尸位素餐”。
■第9週:04/14(期中考週。停課一次。本課程無期中考
■第10週:04/21
vector, list, deque
■第11週:04/28
set, map, hashtable
.ppt 本課程講義
■第12週:05/05
hashtable, iostream iterator
.ppt 本課程講義
分組名單
第 1 組
901436 簡汶翰
901315 陳志仁
902205 梁宏達
902229 李宗益
902253 廖世傑
902254 吳俊緯
第 2 組
902220 張皓傑
902255 田益維
902236 張耀宗
902249 董錦宜
902201 陳樹松
第 3 組
882356 李建輝
892632 方鶴
912323 蔡勛任
912332 簡廷因
912343 張恆瑞
912356 吳梵誠
第 4 組
902315 劉致光
902323 蔡佩辰
902331 陳重民
902332 古鎮宇
902335 王仁暉
902359 陳勁凡
第 5 組
902209 徐士卜
902208 陳宗邦
902207 陳伯符
902219 洪聖哲
902231 黃威晟
902240 林益平
第 6 組
902228 楊貴麟
902334 王珮蓁
902342 劉芳伶
902349 徐悅芝
902350 林彥伯
902351 李素玫
第 7 組
902260 麥雲峰
902310 朱國宏
902317 魏宇澤
902340 李昌達
902360 何家豪
第 8 組
902257 薛博元
902234 彭玉池
902237 董信宗
902222 姜兆剛
902244 何沛宇
902233 于世慶
第 9 組(名單重複,取消)
902248 凌鈺城
902251 周彥如
902259 鄭孟璿
902349 徐悅芝
第 10 組
892212 劉祐妏
892229 陳奕超
892233 江政哲
892234 林采盈
892359 梁維修 
第 11 組
882348 陳坤琦      
882324 葉天翔       
892314 楊旻樺       
892350 王順英       
892340 羅邦翔 
912340 鄭傑仁
第 12 組
902241 蔡  芸
902248 凌鈺城
902251 周彥如
902259 鄭孟璿
第 13 組
912327 洪鵬傑
912309 陳彥如
912349 張家豪
第 14 組
902336 方稟淳
902305 藍偉銘
902328 李昉昇
902320 鍾承佑
■第13週:05/12
iostream iterator, adapter
■第14週:05/19
memory allocation and design patterns in std::String
.ppt 本課程講義
■第15週:05/26
memory allocation and design patterns in std::String
----- Original Message -----
Subject: 來自一個旁聽者的感謝
> 老師:
>
> 您好。我是一個憧憬著嚴謹的邏輯世界,卻始終未能在編
> 程領域登堂入室的人。這學期因緣具足,來上了您在元智
> 大學開的 STL與泛型程式設計課。感謝老師在眾多修課學
> 生之外,慷慨地接受外來的旁聽者。課上到後來,我習慣
> 了坐在最前面,一方面看投影畫面較輕鬆,一方面也容易
> 向老師請益。只是常常發問,影響了老師上課的進度,也
> 有損其他正式修課同學的權益,實在不好意思,只好在此
> 向老師以及同學們表示歉意。
>
> 如果沒有老師的引領,我大概只是安於做一個 STL的使用
> 者,永遠不會去接觸它的源碼,一窺其設計的奧祕。然而,
> 來聽老師的課,除了技術的提昇,更大的啟示來自於親炙
> 老師,從您身上感受到的做人與求學的態度。原來,即使
> 活在這麼一個浮薄的時代,一個人仍然可以勤勉懇切,一
> 磚一瓦的搭建起學問的殿堂,踏踏實實地走出自己人生的
> 康莊大道。
>
> 我所學到的一些技術也許有過時的一天,但是我誠願將這
> 種老實做人的精神永遠放在心上。
>
> 謹向老師深深一鞠躬。
>
> 學生 □□□ 敬上
Hi, □□ :

課程中我便注意到您,總是坐在第一排或第二排,神態認真專注。

在這麼些年的課程當中,旁聽的同學帶給我最大的欣慰。因為你們
總是那麼專注、珍惜、用功。

雖然你們覺得是我給了你們 something,是我幫助了你們。但我要說,
在授課過程中,這樣(專注、珍惜、用功)的學生對我也是非常重要,
意義非凡。

謝謝你們。

我個人談不上在「學問的殿堂」上有什麼成績。「勤勉懇切踏踏實實」倒的確是
真實的寫照。如果在這個形象上我對同學帶來了某種正面的影響,我非常開心 :)

> 只是常常發問,影響了老師上課的進度,也有損其他正式修課
同學的權益,實在不好意思,只好在此向老師以及同學們表示歉意。

我的課程永遠歡迎發問。這會使上課氣氛活潑,帶動其他同學的勇氣。
發問對課程的良性發展有幫助 :) 你有功於本課程 :)

-- jjhou

■第16週:06/02(繳交期末作業並上台報告
■第17週:06/09(繳交期末作業並上台報告
■第18週:06/16(期末考週。本課程無期末考