泛型程式设计（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源码剖析》书到。  峰予 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（期末考。本课程无期末考）