泛型程式設計(Generic Programming)

元智大學 93-2 課程備忘錄 (3學分)

侯捷

請注意:此為備忘錄,不是呈現完整教材或學習討論的地方。

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

課程投影片( 2005/05/18更新)

06/08, 06/15 分組口試。報告文件和程式碼請於上台前一天 email 送達。
口試時每組請帶隨身碟,使用教室現成之電腦+投影設備


教材(5 為教材,1,2,3,4,6,7,8,9 為相關資料或書籍):

   1.《C++ Primer 3e》by Lippman & Lajoie. chap6,10,12,15,16, appendix
   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.
   9.《C++ Template Metaprogramming》by David Abrahams, Aleksey Gurtovoy.

成績評量:

平時成績佔 20%,期末作業佔 80%。期末作業需上台簡報並接受口試,未及時繳交或未到場者 0 分(不接受補繳)。過去有多位同學因疏忽或不在乎而得到 0 分,甚且(大四同學)導致無法畢業。慎之哉慎之哉。

期末作業:

4~6人一組,期末口試時交出程式碼+書面報告(均以email方式提交,於口試前一天傳送),並推派代表上台以投影片進行簡報。文件+簡報佔很重的評分比例。要的不只是各位能夠把程式寫出來,還要能夠流暢地讓別人知道你的想法(以書面方式,以口頭方式...)。

以下二題都要完成:
■1. 寫個程式練習運用 STL hashtable 的各種動作。元素為 pairs,其中 key 是個 std::string,value 是個 int。可參考《STL源碼剖析》5.7.6節。

※提示1:由於 key 是個 std::string,所以必須為 STL加上 std::string's hash function。可參考《STL源碼剖析》5.7.7節。這也就是讓同學解決書中 p.269 最下的問題。

※提示2:std::string's member function c_str() 會以 char* 形式傳回 string 內含字串。

※提示3:hashtable 無 default ctor。也就是說必須在宣告 hashtable object 的同時給出某些 arguments。可參考《STL源碼剖析》5.7.6節。

※提示4:hashtable 需要的 template arguments 很多。如果不知如何寫出它們,可先在程式中宣告一個 hash_map object(參考 p.278),並觀察 hash_map 源碼,看看後者如何宣告其底部的 hashtable(p.276)。然後依樣畫葫蘆可也。

教學 memo:檢視不同版本之 STL hashtable source。


■2. 寫個程式,以 iterator 巡訪磁碟檔案,使能滿足以下 main() 函式:

int main()
{
  // count of file entries in the directory
  cout << "Total count: "
          << count_if( file_iterator(), file_iterator(0), always_true<file_iterator::value_type>() )
          << endl;

  // for_each() to display all entries
  for_each( file_iterator() , file_iterator(0) , display_file_entry() );

  // accumulate() to add up the size of all file entries
  cout << "Total: "
          << accumulate( file_iterator() , file_iterator(0), 0 , file_size() )
          << " bytes." << endl;

  return 0;
}

※提示1:參考 "C++ and STL: Take Advantage of STL Algorithms by Implementing a Custom Iterator" by Samir Bajaj(http://msdn.microsoft.com/msdnmag/issues/01/04/STL/default.aspx)。為恐 Internet 網頁佚失,故為上述網頁做了一個備份

※提示2:參考 std::istream_iterator 和 std::ostream_iterator 源碼。

※提示3:參考 Win32 APIs : FindFirstFile(), FindNextFile(),  WIN32_FIND_DATA

 

周次 日期 時數 內容 備註
1 02/23 1 課程介紹,遊戲規則,書籍評介,期末作業題目 購書
1 02/23 2 示範數個 STL applications  
2 03/02 3 C++ Class Templates & Function Templates

(複習 pass/return by value, member initialization list)

書到
3 03/09 3 C++ Operator Overloading

(複習constness, inline)

 
4,5 03/16
03/23
4 STL-Lite (.zip)  
5 03/23 2 STL Allocators  
6,7 03/30
04/06
6 STL Containers (Vector, List, Deque, HashTable, Map)  
8 04/13 1 STL Algorithms  
9 04/20   期中考,停課  
8,10 04/13
04/27
4 STL Iterators & Iterator Traits  
10 04/27 1 STL Functors  
11 05/04 3 STL Adapters (Iterator Adapters, Function Adapters)  
12 05/11 3 Patterns in STL (Reference Counting in std::string)  
13 05/18 3 Patterns in STL (Proxy, Adapter, Iterator…)  
14 05/25 3 Generics in Java (ref. JavaTwo 2004) .ppt
15 06/01 3 Command, Iterator in Java  
16 06/08 3 期末作業,分組報告與口試 每組 20min.
17 06/15 3 期末作業,分組報告與口試 每組 20min.
18 06/22 3 期末考,停課  

 

分組名單。(簡報+口試時,逆序進行。亦即第1組最後一個上場)

第1組:
902206 陳君豪
902210 黃逸華
902215 林宗翰
902217 林貞喬
902224 王妍榮
902239 陳大鵬

第2組:
902353 葉柏均
912307 許志揚
912353 林易達
912360 巫青樺
912325 鐘健毓
912350
王呈佑

第3組:
902306 盧風其
902316 林俊雄
902318 蕭以潔
902333 張乃中
902339 戴才淵
902354 梁秉洋

第4組:
922211 劉雨芊
922303 周君樺
922321 林東潁
922328 張慈殷
922330 黃昱琦
922338 曾子安

第5組:(破例 7 人)
912212 馮彥儒
912256 廖勇盛
912220 黃泰一
912241 周雨霆
912244 何周達
912245 黃彥彰
912229 蔡弘道    

第6組:
912222 蔡松達
912223 申慶堯
912233 姜國程
912236 林敬航
912255 郭柏鋒
912260 蔡承勳

第7組:(破例 7 人)
912305 呂安勝
912319 陳俊瑋
912348 簡健宇
912363 邱一航
922264 蔡昌富
912228 王上維     
912215 周柏因     

第8組:
912338 蔡景翔
912326 許宏國
912335 逄皓宇
922254 王維成
901034 廖名寬

第9組:
912312 朱柏衡
912334 王?霖
912346 徐榮彬
912351 洪崇紳

第10組:
911320 吳政霖
912211 蕭建文
912217 吳宜穎
912231 陳俊竹
912232 黃健智
912248 黃俊豪

第11組:(破例 7 人)
922216 吳顯如
922225 盧育龍
922208 黃志睿
922228 江元浩
922251 蔡明釗
912548 武芝羽
922244 吳靜宜

第12組:
912207 許梓亭
912210 朱詩敏
912250 吳秉蓉
912324 張彥倫

-- the end