泛型程式設計(Generic Programming)

元智大學 91-2

課程備忘錄 / 侯捷

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

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


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

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


期末作業。各組任選一題。評分將視選題困難度而有所調整。
評分根據:選題困難度、程式可執行度、程式手法優劣、目標達成度、
                    上台演出情況、書面報告。

1.  移植 SGI STL's allocator 到 VC & CB。
     提示:仔細研讀《STL源碼剖析》第二章 p43~p70 和 池內春秋
     目標:移植到 VC, BCB
2.  改善 SGI STL's allocator。
     提示:仔細研讀《STL源碼剖析》第二章 p43~p70 和 池內春秋
     改善:將記憶體運用率提至最高,減少所有可能閒置。課內詳述。
3.  追蹤並報告 Doug Lea 的 malloc algorithm。
     提示:http://gee.cs.oswego.edu/dl/
     注意:不必寫程式,但選此題者需有良好的書面報告撰寫能力,
                 與大程式追蹤能力,才可能獲得好成績。
4.  為 STL containers 添加 serialization 功能。
     提示:難度極大。我只要求給出簡易模型。例如只針對 list 構想。課內詳述。


■第1週:02/26  

1 課程介紹,遊戲規則,書籍評介,期末作業題目(未定),助教協助購書
2 GP (Generic Programming) and STL overview
■第2週:03/05
《STL源碼剖析》書到。眳p予 7 折優惠。   
三種編譯器之 command line 環境設定 batch file
★vc6
@echo off
rem environment setting for <Polymorphism in C++>
rem
rem C:\MSDEV\VB98 for MSPDB60.DLL.
rem (also in C:\msdev\vb98
set PATH=C:\MSDEV\VC98\BIN;C:\MSDEV\common\MSDev98\Bin;D:\Utility
set INCLUDE=C:\MSDEV\VC98\INCLUDE;C:\MSDEV\VC98\MFC\INCLUDE
set LIB=C:\MSDEV\VC98\LIB;C:\MSDEV\VC98\MFC\LIB
cls
set
★cb6
@echo off
rem environment setting for <BCB 6.0>
rem
set PATH=C:\borland\CBuilder6\BIN;C:\WINDOWS;C:\WINDOWS\COMMAND;d:\UTILITY
set INCLUDE=C:\borland\CBuilder6\INCLUDE
set LIB=C:\borland\CBuilder6\LIB
cls
set
★gcc
@echo off
rem environment setting for <GNU C++ 3.2, MinGW>
rem
set PATH=c:\mingw\BIN;C:\WINDOWS;C:\WINDOWS\COMMAND;d:\UTILITY
set INCLUDE=
set LIB=
cls
set
1. STL 運用實例(六大組件都用過) 實例
2. C++ Templates 
★練習1:設定好你的編譯環境,建議使用 console mode.
★練習2:試用 C runtime library 的 qsort() 寫個程式
         感受一下 function pointer.(參考《STL源碼剖析》p40)
課後學生來信詢問(下次上課答覆)
■第3週:03/12
繼續練習使用 STL 實例
各種 STL containers 和 STL algorithms(以及其他組件)的運用,是很有趣的。
同學應該自己動手試試。
■第4週:03/19
練習 C++ template 技術。實例
課後學生來信詢問(下次上課答覆)

 

yz912-allocator.h
yz912-list.h
yz912-algorithm.h
yz912-functional.h
yz912-iterator.h
yz912-main.cpp
■第5週:03/26
本週開始,一方面認識六大組件,一方面由老師示範寫一個 STL lite(是個
不小的工程) 。主要只寫出 interface,不涉太多 implementation。
首先,寫一個陽春型的 allocator。
■第6週:04/02(春假
■第7週:04/09
仔細研究 SGI STL allocator 的優缺點
■第8週:04/16(期中考。本課程無期中考
■第9週:04/23
接合 YZ::allocator 與 YZ::list
o.寫出第一級 alloc (TASS,p57)
o.寫出 simple_alloc (TASS,p54)
o.測試 simple_alloc
o.寫出 __list_node 和 __list_iterator (TASS, p129,p130)
o.寫出 list 的數項操作函數 (TASS,p131~p137)
o.寫出全域函式 constuct(),destroy() (TASS,p50~52)
o.寫出全域函式 distance() (TASS,p99)
o.寫出全域函式 for_each(),find() (TASS,p344~349)
o.測試 list

■第10週:04/30
o.為什麼 SGI memory pool 有能力測知被歸還的 block(由某個指標指出)的大小?
   靠的是 simple_alloc(TASS,p54)中由編譯器推導出來的 T。 
o.第四章 vector, list, deque 結構與特性。
■第11週:05/07
o.補充 copy ctor, op=, dtor 之於 class with pointer members 的重要性
  示範:yz912-string.cpp
o.補充 std::string(sizeof,reference counting,Copy-On-Write)
o. specialization of class template 
o. partial specialization of class template
o. iterator and traits mechanism(TASS, ch3)
同學詢問「一堆資料,先根據某值排序,再根據某值排序」該怎麼寫。
請參考這裡 QA28-2.cpp
課後學生來信詢問(關於 operator< for pair)(下次上課答覆
■第12週:05/14
o. 公佈期末作業分組及評量細節
o. 再度補充 std::string(sizeof, reference counting, Copy-On-Write, proxy)
o. 繼續講解 iterator and traits mechanism(TASS, ch3)
o. 修改 yz912-list.h,為 list 加上 iterator_category;
o. 修改 yz912-iterator.h,添加 iterator_traits<>。
o. 修改 yz912-iterator.h,使 distance()做到最佳效率。
o. 修改 yz912-iterator.h,添加 advance()。
o. hash table 概念
同學詢問了一個關於 traits 的問題:
是否可以拿 TASS p86 的 MyIter,針對 native pointer 做偏特化設計,
依此類推,是否可以對所有 STL container iterator 做
「針對 native pointer 的偏特化設計」,
如此一來就不需要 iterator traits 機制了。因為畢竟像
   iterator_traits<Iterator>::value_type 
這樣的述句,對許多人還是存在理解上的困難。
由此推想,是否 STL 是在做出上述的動作(設計)之後,發現可以往上
提取一層抽象性,所以才發展出 iterator traits 機制?
●侯捷回覆:
TASS p86 的 MyIter,乃至於任何 STL container iterators,都不能
針對 native pointer 做偏特化設計。因為它們是 something like pointer,
它們所接受的 template type parameter T,是元素型別,
不該對 native pointer 做偏特化設計(牛頭不對馬嘴)。
只有更上層的 class template,才能(才適合)對 iterator 做出
「針對 native pointer 的偏特化設計」。也就是說,
只有更上層的 class template,
才能利用 C++ 語言的 template partial specialization 特性,
區分出它所收到的東西(型別)是個 native pointer 還是個 iterator class. 
以上所謂「更上層」意思是「凌駕於 native pointer 和 iterator class 之上」,
這個更上層的東西就是 iterator_traits<I>。 
■第13週:05/21
o. hash table 技術細節
o. hash table 的運用
o. map 的運用
■第14週:05/28
o. STL functors (function objects)
o. STL adatpers
o. 修改 yz912-functional.h,
   添加 15 個 functors 和 2 個 functor adapters。
o. 修改 yz912-algorithm.h,添加 count_if()
o. 修改 yz912-main.h,添加測試    
   YZ::count_if(myList.begin(), myList.end(), 
                YZ::not1(YZ::bind2nd(YZ::less<int>(),30)));
o. 探討istream_iterator, ostream_iterator
■第15週:06/4(端午節放假
■第16週:06/11(本學期最後一次上課。繳交期末作業
o. 在 STL 中可看到的 design patterns
o. Adapter
o. Command
o. Proxy
o. Reference Counting
o. Smart Pointer
■第17週:06/18(期末考。本課程無期末考