泛型程式設計(Generic Programming)

元智大學 90-2

課程備忘錄 / 侯捷

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


課程教材:
1.《C++ Primer 3e》chap6,10,12,15,16, appnedix
2. 五篇文章 by 侯捷  見左視窗「STL系列文章」 2000/02~2000/06. 自行列印
3.《泛型程式設計與STL
4.《C++ 標準程式庫
5.《STL源碼剖析

1,2 為教材,3,4,5 為課外輔助參考書籍

註:單純以本課程主旨而言,4 為最佳教材。但估計許多同學還需補強 C++ template 語法基礎,故以 1+2為教材。


■第1週:02/27   缺書

1 課程介紹,遊戲規則,書籍評介,期末作業題目
2 GP (Generic Programming) and STL overview
★練習1:設定好你的編譯環境,建議使用 console mode.
★練習2:試用 C runtime library 的 qsort() 寫個程式
         感受一下 function pointer.
本週程式例:STL 的運用
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;

int main()
{
   vector<int>  vi;
   vi.push_back(23);
   vi.push_back(14);
   vi.push_back(39);
   vi.push_back(20);
   vi.push_back(9);
   vi.push_back(10);
   vi.push_back(36);

   for(int i=0;  i< vi.size(); ++i)
       cout << vi[i] << ' ';
   cout << endl;

   vector<int>::iterator  ite1 = vi.begin();
   vector<int>::iterator  ite2 = vi.end();
   sort(ite1,ite2);

   for(int i=0;  i< vi.size(); ++i)
       cout << vi[i] << ' ';
   cout << endl;

   sort(ite1,ite2, greater<int>());
   for(int i=0;  i< vi.size(); ++i)
       cout << vi[i] << ' ';
   cout << endl;
}
■第2週:03/06 書籍七折

請助教和同學提早15分鐘到達,領取書籍。同學請自備零錢,避免給助教太多困擾。980 * 0.7 = 686

Q : 同學提出一個問題,他將 qsort()放在某個class中,並於呼叫時指定某個member function做為qsort()的最後引數,結果編譯器報錯,要求該member function必須設定為static。同學不解。

A : 這是因為 qsort() 的最後參數為一個 function pointer,可視為一個 callback 函式。而 class member function會多出一個 this 指標做為隱藏參數,如此一來將與 qsort()的要求不符。改為 static member function 便可去除隱藏的 this 指標參數。我將於課中更詳細說明。

Q: 可否以優惠折扣購買其他參考書籍。

A: 可以。上課時登記,我把名單轉給出版社。折扣為 7.5 折。此為出版社對侯捷課程的特殊服務,其他讀者請勿來信要求代購。

 

GP vs. OO,見讀者來函與回應

本週仍著重在以實例方式,給同學一個 STL overview.

#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
class Dumy
{
friend ostream& operator<<(ostream& os, const Dumy& obj);
};
ostream& operator<<(ostream& os, const Dumy& obj)
{
   os << "this is a dumy object :)" << endl;
   return os;
}
template<typename T>
void print_elem(T i)
{
   cout << i << ' ';
}
int main()
{
   vector<int>  vi;
   vi.push_back(23);
   vi.push_back(14);
   vi.push_back(39);
   vi.push_back(20);
   vi.push_back(9);
   vi.push_back(10);
   vi.push_back(36);
   for(unsigned int i=0;  i< vi.size(); ++i)
       cout << vi[i] << ' ';
   cout << endl;
   vector<int>::iterator  ite1 = vi.begin();
   vector<int>::iterator  ite2 = vi.end();
   sort(ite1 , ite2);
   for(unsigned int i=0;  i< vi.size(); ++i)
       cout << vi[i] << ' ';
   cout << endl;
   sort(ite1 , ite2, greater<int>());
   for(unsigned int i=0;  i< vi.size(); ++i)
       cout << vi[i] << ' ';
   cout << endl;
   ostream_iterator<int> oite(cout, " ");
   copy(vi.begin(), vi.end(), oite);
   cout << endl;
   void (*funcptr)(int) = &print_elem;
   for_each(vi.begin(), vi.end(), funcptr);
   cout << endl;
   for_each(vi.begin(), vi.end(), print_elem<int>);  // VC6[o],CB5[o],GCC291[x]
   cout << endl;
   Dumy dumy;
   print_elem(dumy);  // argument deduction by compiler
}


■第3週:03/13  
chap10 : function template

 

#include <iostream>
using std::cout;
using std::endl;
class Dumy
{
private:
  double d1, d2, d3, d4;
  static int i;
};
int Dumy::i = 5;  // initialization
void func(Dumy& a, Dumy& b)
{
   Dumy c;
   // a.xxxx
   // b.xxx
}
int main()
{
  int i = 3;
  int* pi =  &i;
  int& ri = i;
  double d = 3.5;
  double& rd = d;
  cout << i << endl;
  cout << pi << endl;
  cout << ri << endl;
  cout << sizeof(i) << endl;
  cout << sizeof(pi) << endl;
  cout << sizeof(ri) << endl;   // 4
  cout << sizeof(rd) << endl;   // 8
  Dumy d1;
  cout << sizeof(d1) << endl;   // 32
  func(d1, d1);                 // pass by reference
}

 

傳送日期: 2002年3月14日 AM 11:43
主旨: 元智GP 3-13上課問題

老師您好! 以下是一些問題要麻煩老師了

Q1: 通常Object在離開它的Scope時便會被destroy,那在Java這種(oo)語言中並不提
point及new/delete, 要如何控制Object的life time?

A1: 我後來自己找的答案不知正不正確,請老師指點.. 如果Object在它的Scope中有將
Referance傳遞出去就不會在離開它的Scope時被destroy

Q2: 課程中提及一個max的Specialization寫法如後
typedef const char *PCC
template<> PCC max<PCC>(PCC s1, PCC s2)
有沒有可能寫成
template<> PCC max<PCC>(PCC s1, PQ s2)?
那max後的角括號內要寫PCC或PQ?? (因為一般algorithms應會有許多不同Type的
Param)

A2: 先想一個比較具體的實例,再發問。也請自己上機試試。

Q3: 以Referance傳遞參數的好處應包含不會喚起copy construct所以比Pointer更有效率,這樣的講法不知對不對?

A3: 以pointer 傳遞引數,也不會喚起copy ctor。

Q4: 課堂上所提的Explicit Template Arguments似乎是用以解決不同型別參數所造成
的引數推導失敗這個問題, 對於老師所提的函式返回值型別不在引數型別推導範圍這個問題不知Explicit Template Arguments是
用在那?
另外即然函式返回值型別不在引數型別推導範圍可以Trait解決,那為何還需要
Explicit Template Arguments?

A4: explicit template arguments 用法見書上10.4節。至於 traits,工程比較大。


■第4週:03/20  
chap15 : operator overloading
#include <iostream>
#include <string>
using namespace std;
class INT
{
friend ostream& operator<<(ostream& os, const INT& i);
public:
  INT(int i)
    : m_i(i) // member initialization list
  { }
  INT& operator++()  // prefix, increment and then fetch
  {
     m_i++;
     return *this;
  }
  const INT operator++(int)  // postfix, fetch and then increment
  {
     INT temp = *this;
     ++(*this);              // invoke prefix form
     return temp;
  }
private:
  int m_i;
};
ostream& operator<<(ostream& os, const INT& i)
{
   os << '[' << i.m_i << ']';
   return os;
}
class JFunctor
{
public:
  void operator()(string s)
  {
     cout << s << endl;
  }
};
int main()
{
   {
   INT i(4);
   cout << i++;
   cout << ++i;
   // cout << i++++;
   cout << ++++i;
   }
   {
   int i(4);
   cout << i++;
   cout << ++i;
   // cout << i++++;
   cout << ++++i;
   }
   {
     JFunctor f;
     f("this is my functor");  // like a function call
     JFunctor()("this is my functor");
   }
}

// 本例模擬 STL 架構
#include <iostream>
using namespace std;
template<typename T>
struct JNode    // C++ struct 可取代 C++ class (預設屬性為 public)
{
  // something
  T m_data;
};
template<typename T>
class JList_Iterator
{
public:
  JList_Iterator& operator++()    // prefix
  {
     // do something...
     return *this;
  }
  const JList_Iterator operator++(int)   // postfix
  {
     JList_Iterator temp = *this;
     ++(*this);            // invoke prefix form
     return temp;
  }
  T& operator*() const    // dereference operator
  {
     return node->m_data;
  }
  T* operator->()         // member access operator
  {
     return &(this->operator*());
  }
private:
  JNode<T>* node;         // must have a native pointer
};
template<typename T>
class JList
{
public:
  typedef JList_Iterator<T> iterator;
  iterator begin()
  {
     iterator ite;
     // do something...
     return ite;
  }
private:
  // something
};
int main()
{
  JList<int> myList;
  // JList_Iterator<int> ite;
  JList<int>::iterator ite = myList.begin();
  ite++;
  ++ite;
  *ite;
}

 

■第5週:03/27 
1. 延續上一堂課的程式發展
2. chap12 : generic algorithm
// 以下 find1(), find2(), find3(), find() 示範函式的泛化過程
#include <iostream>
using namespace std;
// step1:
int* find1(int* arrayHead, int arraySize, int value)
{
   int i;
   for (i=0; i<arraySize; i++)
      if (arrayHead[i] == value)
          break;
   return &(arrayHead[i]);
}
// step2:
int* find2(int* begin, int* end, int value)
{
   while (begin != end && *begin != value)
      ++begin;
   return begin;
}
// step3:
template <typename T>
T* find3(T* begin, T* end, const T& value)
{
   while (begin != end && *begin != value)
      ++begin;
   return begin;
}
// final:
// 觀念突破:將 T* 視為一種 type,也就是 iterator
// 於是我們可以訂製自己的 iterator (behavior like a pointer)
template <typename Iterator, typename T>
Iterator find(Iterator begin, Iterator end, const T& value)
{
   while (begin != end && *begin != value)
      ++begin;
   return begin;
}
//---------------------------------------------------
// 模擬 STL 架構 (container, iterator)
// class JNode
// class JList
// class JList_Iterator
//---------------------------------------------------
template<typename T>
struct JNode    // C++ struct 可取代 C++ class (預設屬性為 public)
                // JNode 並不開放給 client,所以無損 encapsulation
{
  void* next;  // 亦可設為 JNode<T>*
  void* prev;
  T m_data;
};
//---------------------------------------------------
template<typename T>
class JList_Iterator
{
public:
  JList_Iterator& operator++()    // prefix
  {
     // do something...           // implementation detail
     return *this;
  }
  const JList_Iterator operator++(int)   // postfix
  {
     JList_Iterator temp = *this;
     ++(*this);            // invoke prefix form
     return temp;
  }
  T& operator*() const    // dereference operator
  {
     return node->m_data;
  }
  T* operator->() const // member access operator
  {
     return &(this->operator*());
  }
  bool operator==(const JList_Iterator<T>& x) const { return node == x.node; }
  bool operator!=(const JList_Iterator<T>& x) const { return node != x.node; }
  JList_Iterator(JNode<T>* x) : node(x) {}
  // one-argument non-explicit ctor. can be used as conversion function
private:
  JNode<T>* node;   // there is always a native (dumb) ptr in a smart ptr
};
//---------------------------------------------------
template<typename T>
class JList
{
public:
  typedef JList_Iterator<T> iterator;  // nested define
  // 以下,由於 node 指向尾節點的下一位置,因此 node 符合 STL 對 end() 的定義。
  iterator end()   { return node; }                      // invoke conversion func.
  iterator begin() { return (JNode<T>*)((*node).next); } // invoke conversion func.
  JList() { empty_initialize(); }  // 產生一個 empty list。
protected:
  // 環狀雙向串列,只維護一個節點指標,指向最後(尾)節點的下一位置。
  JNode<T>* node; // 永遠指向最後節點的下一節點。該節點無元素值,代表空節點。
                  // 其 next 節點永遠是頭節點。
  //以下用於初始化
  void empty_initialize() {
    node = get_node();  // 配置一個節點空間,令 data member node 指向它。
    node->next = node;  // 令 node 頭尾都指向自己,不設元素值。
    node->prev = node;
  }
  JNode<T>* get_node() { return new JNode<T>; }
  // STL use allocator and maybe implement memory pool.
};
//---------------------------------------------------
//
//---------------------------------------------------
int main()
{
   const int arraySize = 7;
   int ia[arraySize] = { 0,1,2,3,4,5,6 };
   int* end = ia + arraySize;
   // test find1()
   int* ip1 = find1(ia, sizeof(ia)/sizeof(int), 4);
   if (ip1 == end)
       cout << "not found" << endl;
   else
       cout << "found. " << *ip1 << endl;
   // test find2()
   int* ip2 = find2(ia, end, 9);
   if (ip2 == end)
       cout << "not found" << endl;
   else
       cout << "found. " << *ip2 << endl;
   // test find3()
   int* ip3 = find3(ia, end, 2);
   if (ip3 == end)
       cout << "not found" << endl;
   else
       cout << "found. " << *ip3 << endl;
   // test find(), final version.
   int* ip = find(ia, end, 5);
   if (ip == end)
       cout << "not found" << endl;
   else
       cout << "found. " << *ip << endl;
   // test Container and Iterator with find()
   JList<int> myList;
   // push_back or pust_front or insert some elements into myList
   // JList_Iterator<int> ite;
   JList<int>::iterator ite = myList.begin();
   ite++;
   ++ite;
   *ite;
   find(myList.begin(), myList.end(), 8);
   // 此例沒做任何事情,因為 myList 是個 empty list.
   // 本例只為突顯 interface 的設計。
   // 以上無論 find(), JNode, JList, JNode_Iterator,
   // 其介面皆符合 STL 規範,與 SGI STL 幾無二致
}


■第6週:04/03  春假

 

■第7週:04/10 
// file : 42.cpp ([austern98])
// VC6 [x], BCB4 [o], G++ [o]  (VC6 not support partial specialization)
#include <iostream>
#include <cstddef>  // for ptrdiff_t
// 注意,不能開放 namespace std; 否則會和 std 的 iterator_trait 衝突
struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::iterator_category  iterator_category;
  typedef typename Iterator::value_type         value_type;
  typedef typename Iterator::difference_type    difference_type;
  typedef typename Iterator::pointer            pointer;
  typedef typename Iterator::reference          reference;
};
// partial specialization for regular pointers
template <class T>
struct iterator_traits<T*> {
  typedef random_access_iterator_tag  iterator_category;
  typedef T                           value_type;
  typedef ptrdiff_t                   difference_type;
  typedef T*                          pointer;
  typedef T&                          reference;
};
// partial specialization for regular const pointers
template <class T>
struct iterator_traits<const T*> {
  typedef random_access_iterator_tag  iterator_category;
  typedef T                           value_type;
  typedef ptrdiff_t                   difference_type;
  typedef const T*                    pointer;
  typedef const T&                    reference;
};
template <class Category,
          class Value,
          class Distance = ptrdiff_t,
          class Pointer = Value*,
          class Reference = Value&>
struct iterator {
  typedef Category  iterator_category;
  typedef Val'
;&+鞁"黲HE'
;&+鞁"黂ypedef Distance  iterator_distance;
  typedef Pointer   iterator_pointer;
  typedef Reference iterator_reference;
};
template <class InputIterator>
typename iterator_traits<InputIterator>::value_type
sum_nonempty(InputIterator first, InputIterator last)
{
  typename iterator_traits<InputIterator>::value_type  result = *first++;
  for (; first != last; ++first)
    result += *first;
  return result;
}
template< class InputIterator, class T >
typename iterator_traits<InputIterator>::difference_type
count( InputIterator first, InputIterator last, const T& x )
{
   typename iterator_traits<InputIterator>::difference_type n = 0;
   for ( ;  first != last; ++first)
     if (*first == x)
       ++n;
   return n;
}
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n, input_iterator_tag)
{
  for ( ; n > 0; --n, ++i );
}
template <class BidirectionalIterator, class Distance>
void advance(BidirectionalIterator& i, Distance n, forward_iterator_tag)
{
  advance(i, n, input_iterator_tag());
}
template <class RandomAccessIterator, class Distance>
void advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag)
{
  i += n;
}
template <class BidiectionalIterator, class Distance>
void advance(BidiectionalIterator& i, Distance n, bidirectional_iterator_tag)
{
  if (i >= 0)
      for ( ; n > 0; --n, ++i ) { }
  else
      for ( ; n < 0; ++n, --i ) { }
}
// top level
template <class Iterator, class Distance>
inline void advance(Iterator& i, Distance n)
{
  advance(i, n, iterator_traits<Iterator>::iterator_category());
}
template <class Category,
          class Value,
          class Distance = ptrdiff_t,
          class Pointer = Value*,
          class Reference = Value&>
class MyIter : public iterator<Category, Value, Distance, Pointer, Reference>
{
};
void main()
{
  int ia[5] = {0, 1, 2, 3, 4};
  int total = sum_nonempty(ia, ia+5);
  int c = count(ia, ia+5, 2);
  std::cout << total << std::endl;  // 10
  std::cout << c << std::endl;      // 1
  std::cout << *ia << std::endl;    // 0
  int* pi = &(ia[0]);
  advance(pi, 3);
  std::cout << *pi << std::endl;    // 3
  MyIter<random_access_iterator_tag, int> myiter;
}


■第8週:04/17  期中考。停課

 

■第9週:04/24  

從本週開始,每次上課請攜帶補充講義(5篇文章)

■第10週:05/01  

同學索求上課用到的 PowerPoint 圖檔。好的,就在這裡

 

目前分組名單:
注意,不允許四人以下。每組至少四人。未符規定者請重新分組。

組別 (1)
895645 黃新泳
895624 吳文彰
895626 劉宇智
895627 蔡錦明
895644 陳維錡
895660 黃勝建

組別 (2)
895606 林駿豪
895609 邱華成
895615 李健志
895636 闕乃賢
895658 林裕偉

組別 (3)
892245 林志偉
892216 陳炫廷
892205 林岱慶
892217 林金龍

組別 (4)
895608 蕭志堅
895628 郭先正
895649 謝長成
882301 林佳慧
882305 黃建銘
882339 張堯淙

組別 (5)
882209 賴俊升
882210 楊宗羲
882232 王昭雄
882238 何誌 (木堅) ←這是一個字
882245 林正甫
854136 江龍飛

組別 (6)
882221高林傳
882248張明偉
882307 何汶偉
882309 廖元宏
882310 郭炯彬
882316 李岳寅

組別 (7)
882342 羅彥麟
882315 廖伯璇
882351 謝履成
882359 劉致宣

組別 (8)
882303 陳家隆
882320 謝明治
882322 池柏諺
882335 蔡東泰
882338 楊朝景

組別 (9)
882205 謝松翰
882206 蔣宇程
882208 高裕麟
882246 邱清華
882308 白淳元
882321 陳建安

組別 (10)
資工3A 882240 陳薪圳
資工3A 882251 彭治弘
資工3B 882340 劉成韋
資工3B 882353 陳柏瑋
資工3A  882261  邱俊輝

組別 (11)
892251 許百寬
892261 蔡延忠
892266 謝曜任
892255 邱國鈞

組別 (12)
875123  黃雅楠
882358  林岳黌
875033  張元睿
881962  李璦蓉
874014  吳錫欽


組別 (13)
882343游訓傑
882344沈明峰
882345謝承恩
882346龐文欣
882354詹俊強

組別 (14)
882360 廖惟中
882336 林洋慶
882350 葉正德
874007 李森茂

組別 (15)
892226 陳習峰
892316 翁哲斌
892320 林仕軒
892324 梁皓雲
892339 張志賓
892345 蔡淮洋

組別 (16)
874054 呂友仁
882226 謝秉翰
882231 余鍵亨
882253 陳冠銘
882254 許家豪
882223 楊泓彬

組別 (17)
874015 程偉倫
874041 陳威任
874042 楊琳貴
874084 黃盈文

 

■第11週:05/08
allocator。教材:《STL源碼剖析》第2章 

 

■第12週:05/15
STL vector,list,deque內部資料結構與實作手法
教材:《STL源碼剖析》第4章
STL 的其他小玩意兒 (about adapters)
design patterns : 
(1) iterator。以 STL iterator為例。
(2) container adapter。以 STL stack, queue為例。 
(3) template method。這是 application framework 最基礎最根本
     的一種技法。

 

■第13週:05/22

1. 續講 template method...

2. red-black tree, set, map, multiset, multimap, hash table (part1)

from 彭治弘 s882251
老師您好
關於上一次泛型上課的時候曾經有同學向老師反應說
findfirstfile/findnextfile使用的時候會發生錯誤
學生今晚花一點時間測試發現
若是只要單純的計算某一個目錄下有幾個檔案等
像是老師上一次demo給我們看的時候那樣
那麼使用該函式在vc bcb等都不會有問題
只是在98 2000上跑出來的結果會不一樣
也就是說98跑出來的東西會跟vc所compile出來的東西一樣
但若是使用BCB編譯的話
跑出來的東西會有一點點錯誤 但是只要稍稍加一些檢查
在兩個版本的編譯器中編譯跑出來的結果應該不會錯
但唯一的例外是
如果要達成某些特殊的功能時 使用BCB所編譯出來的程式再執行時
會跟作業系統independent 也就是我們使用左鍵框起來點內容時
跑出來的檔案大小以及數量會跟程式跑出來的東西不一樣
不過那要看程式寫到哪一個階段
如果用到了某些技巧 而又希望能做出跟系統一樣的行為時 一定要用vc
用bcb一定出錯
以上是學生在自己的電腦上測試所發現的行為
編譯環境 98 vc bcb, 2000 vc

謝謝彭治弘同學和大家分享心得

 

傳送日期: 2002年5月9日 PM 01:57
主旨: 上課的問題

老師您好 , 我是□□□ , 感謝老師這些日子來的指導

昨天下課前請教老師的問題描述如下:
以源碼剖析第69頁圖2-7為例 ,若向系統要32bytes的空間 , 而32bytes預留的20個己用完 , 且memory pool又己用盡 , 此時勢必需再配置heap空間 , 如此週而復始的malloc動作中 , 每塊記憶體應各自有自己的cookie以便未來釋放之用 , 在第二級配置器中以free-list將前述各塊記憶體串在一起 , 不知後來的釋放動作是如何進行的呢?

學生回去參考SGI source 還是沒有頭緒 , 在第二級配置器中似乎沒看到free( )的蹤影 , 書上提到deallocate 若大於__MAX_BYTES 則呼叫malloc_alloc::deallocate 釋放 , 反之僅將其收回free-list中 , 不知是在何時釋放 ....


傳送日期: 2002年5月12日 AM 11:03
主旨: 我知道答案了

老師您好 , 我是□□□

日前請教您的問題 ~在SGI allocator 第二級配置器中 , 記憶體釋放是如何進行的?

答案就是在Effective C++的條款10中 (p44 倒數第3行起)

最近才開始看老師所介紹的三本C++小書 , 過程實在是太棒了 , 要不是這次有幸旁聽老師的GP , 在看這幾本書可能不會有那麼深刻的體驗 .
透過C++ Primer及STL課程 , 感覺對OO與GP的精神愈來愈能掌握 , 這陣子在工作及一些書籍的閱讀中也都有所驗證 , 再次謝謝老師 , 如果能在程式設計這條路上有所成就 , 端賴老師的諄諄教誨 .

Ps : Effective C++條款7 (p31 倒數第8行)所提的混合風格 , 這個例子實在是太棒了 , 要不是這次上課了解到template , 一定會看不懂 .

 

 

傳送日期: 2002527 PM 05:37
主旨: 侯老師您好

我是今年將畢業的 大六 ( :P ) 學生 因為不想當兵 先選擇上班
由於剛開學時慕名跑去加入了老師的課
但期中完後公司這邊較忙所以也少去了
其中後也沒空去退選 又沒有認識的同學在班上
所以對進況不甚了解
想請問一下老師期末的作業定了ㄇ??

畢業生何時之前要繳交呢?
p.s)只是怕成績單太難看的學生留 && 能否以email方式繳交呢 thx

感恩 :P

●侯捷回覆: ref http://www.jjhou.com/course-generic-yzu-902.htm
如果你沒有交作業,沒有上台報告,你一定會被當,而且最多 20 分。
20 分是平時成績。從這封信看,顯然你平時沒來上課,如果你讓我知道你是誰,那麼你的平時成績只能得 10 分。
這可能就是你的期末總成績。

我曾經給過期末總成績17分。所以給10分不會讓我手軟。你會得到怎樣的成績,就看自己的表現。如果作業交得出來,上台表達也不錯(證明你不是抄來的),不上課當然無所謂,還是可以得到不錯的成績(因為你已達到這門課的訓練目標)。

 

 

傳送日期: 2002年5月27日 PM 08:22
主旨: 上霸王課,謝謝侯老師!!

侯老師你好:

我去年於資工所畢業(算是半路出家,大學學的是電機。)目前於桃園工作(Embedded System 軟體設計),在研究所時就久仰你的大名,某日工作時突然想到您不是在元智教書,名師的課不能不上,又是免費的,所以魯莽的闖入上課,未曾知會老師一聲,十分抱歉。

到目前為只上了大約半學期的課(我從第九週才去上課),讓我收獲不少。上你的課之前有先看了一點 STL 的書,但是自己讀是十分苦的,又不容易理解,也沒體會到多少 STL 的精神,但上了老師你的課三、四週之後,終能體會到 STL 的「神奇」。雖然我有學 C++,但還不知道能夠這樣用 C++,STL 稱為神奇也不為過吧!!之前工作上只是使用 STL,從不會想看 STL source code,因此對它總是半清不楚,但現在從老師那偷得(未付錢就學得)STL的知識後,若有問題也「敢」看 STL 的 SOURCE CODE ,自己找出問題,觀念上清淅了許多。

這二週老師有提到 Design Patters 的書,而我也正在讀此書,不過和 C++ Primer 比起來,Design Patters 就難以下嚥,也許是我程度不夠。不過我發現書的翻譯風格也有差別,因為這二週老師說到 iterator,adaptor,template method,就文字上的翻譯來說,老師你翻譯教人一看便明白。另外,Design Patters 的範例不完整,讓人有管中窺豹之感,不知老師有沒有興趣寫一本 Design Patters 的書,以完整 C++ 的範例貫穿全書,讓我們這群人能夠滿足。

老師您是十分溫和的人,由其是老師譯/著作非常多,但從不以非正常手段要求學生買你的書,反而將學生可能會參考到的資料放在網站上,供學生自行下載。元智有您這樣的老師,真是學生之福。

學生上霸王課無以回報,便以此封信表感謝之意,望老師您別見怪。祝 身體健康、萬事如意

●侯捷回覆:我哪裡會見怪,我很開心。歡迎大家來聽課,所以我才會刻意把課開在晚上。

擁有很多編程實務經驗,才能看懂《Design Patterns》一書。如果有一個(或一些)好例子,的確可以節省大家不少時間。你可以上網搜尋《Design Patterns》的讀書會,上面應該有許多實例。已經不少人建議我寫本《Design Patterns by Example》之類的書,但是我的時間…呃…well…I dont know…。《Design Patterns》中譯本(葉秉哲譯, 培生)其實譯得相當不錯,難讀是因為它本身的層次高。你在課堂上一聽就明白是因為 (1) 我選了最簡單的patterns來講,做個入門 (2) 課堂上有3D講解,當然好過 2D紙頁 :)

在我的新作《多型與虛擬 2e》第七章中,以MFC(Lite)為例,講了十來個Design Patterns,呈現它們在 MFC(Lite)中的實現情形。此書尚未出版,且第七章不在免費公開之列。MFCLite是我模擬的一個 mini application framework(以MFC為模仿對象),可在侯捷網站上下載(「先睹為快」欄)。該章達240頁,講述對的對象MFCLite則達4000~5000行之多,而且十分複雜(畢竟是 application framework),所以閱讀它仍然需要相當高的門檻。不過,讀懂它可以讓人在OO有相當層次的徹悟 — 這是完成它之後我的切身感受(不是說它師法的MFC有多好,而是因為這麼一個活生生的例子,又「只有」四五千行)。

傳送日期: 2002年5月28日 PM 06:19
主旨: 老師您好 關於泛型

老師您好
關於之前我有寄一封信給老師您
告訴您說BCB在compile含有findfirstfile findnextfile等函式的時候會有問題
當時學生跟您說可能和作業系統有點independent

現在我將我們這組測試的報告以及發現的心得撰寫如下
並在附件中將我們這組的程式碼附上

以便老師您可以隨時debug


(1)兩個版本在純檔案版的程式中是沒有任何錯誤的 vc and bcb是相同的
(2)當我們想要寫一個讀取子目錄的檔案以及資料夾的功能較強的版本時
發現vc所編譯出來的執行檔跑出來的結果和我們按右鍵看到的內容是一樣的
在98 and 2000底下都沒有錯誤
(3)但是bcb所產生的檔案目錄版的執行檔會跑出令我們意外的結果
(4)同組的同學在測試的時候,平台是2000 and XP,編譯環境都在vc,發現都無錯誤
(5)所以我們歸納出應該是bcb和系統的哪一部份不相容(有關資料夾的部分就是目錄)
(6)或是直接說我們設計的那個演算法和vc的構思相同,但可能bcb不support

老師您可以直接在附加檔案中編譯執行並看看結果
因為每個人的電腦環境不一樣
恐怕在老師您的電腦上可能會跑出錯誤的答案
不過我們這組已經測試過三到四台的電腦了 發現沒問題
唯恐在下星期的demo出槌
所以我們還會繼續測試,不過bcb一定會有錯就是了,
雖然他所列的檔案數量以及資料夾數量是正確的

還有就是老師您一直跟我們說盡量在命令列模式下編譯
但是這次學生寄給老師您的卻是整合環境的
學生在此項老師說聲抱歉
因為我們還是蠻喜歡click的
所以請老師原諒我們吧

●侯捷回覆:命令列只是一個建議。我給學生很大的彈性空間 :) 我說過各位甚至可以自己想題目 :)

 

■第14週:05/29
1.hash table(part2)
2.heap, heap algorithms. QuickSort, priority-queue. 

3. function adapter

以下摘錄自 SGI STL header "stl_functiona.h" (included by header "functional")

// C++ Standard 規定,每一個 Adaptable Unary Function 都必須繼承此類別
template <class Arg, class Result>
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
};
// C++ Standard 規定,每一個 Adaptable Binary Function 都必須繼承此類別
template <class Arg1, class Arg2, class Result>
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};      
// 已知兩個 Adaptable Unary Functions f,g,以下配接器用來產生一個 h,
// 使 h(x) = f(g(x))
template <class Operation1, class Operation2>
class unary_compose
  : public unary_function<typename Operation2::argument_type,
                               typename Operation1::result_type> {
protected:
  Operation1 op1;
  Operation2 op2;
public:
  unary_compose(const Operation1& x, const Operation2& y) : op1(x), op2(y) {}
  typename Operation1::result_type
  operator()(const typename Operation2::argument_type& x) const {
    return op1(op2(x));
  }
};
// 輔助函式,讓我們得以方便使用 unary_compose<Op1,Op2>
template <class Operation1, class Operation2>
inline unary_compose<Operation1, Operation2> 
compose1(const Operation1& op1, const Operation2& op2) {
  return unary_compose<Operation1, Operation2>(op1, op2);
}
// 已知一個 Adaptable Binary Function f 和兩個Adaptable Unary Functions g1,g2,
// 以下配接器用來產生一個 h,使 h(x) = f(g1(x),g2(x))
template <class Operation1, class Operation2, class Operation3>
class binary_compose
  : public unary_function<typename Operation2::argument_type,
                               typename Operation1::result_type> {
protected:
  Operation1 op1;
  Operation2 op2;
  Operation3 op3;
public:
  binary_compose(const Operation1& x, const Operation2& y, 
                    const Operation3& z) : op1(x), op2(y), op3(z) { }
  typename Operation1::result_type
  operator()(const typename Operation2::argument_type& x) const {
    return op1(op2(x), op3(x));
  }
};
// 輔助函式,讓我們得以方便使用 binary_compose<Op1,Op2,Op3>
template <class Operation1, class Operation2, class Operation3>
inline binary_compose<Operation1, Operation2, Operation3> 
compose2(const Operation1& op1, const Operation2& op2, const Operation3& op3) {
  return binary_compose<Operation1, Operation2, Operation3>(op1, op2, op3);
}

 

■第15週: 06/05 本課程期末作業 分組報告。

注意事項:(1) 繳交書面報告一份,程式(含源碼及可執行檔)磁片一份。
                    (2) 自行推派主講同學上台報告。不限一位,可分工。
                    (3) 演練執行你的程式。

本週由 9~17組同學繳交作業並上台報告。

 

■第16週:06/12  本課程期末作業 分組報告(續上週)。

本週由 1~8組同學繳交作業並上台報告。

 

■第17週:06/19 期末考週。停課。本學期課程結束。