泛型程式設計(Generic Programming)

元智大學 89-2

課程備忘錄 / 侯捷



■第1週:03/01 缺書

介紹課程,遊戲規則,書籍評介,期末作業題目
GP (Generic Programming) and STL overview
★練習1:設定好你的編譯環境,建議使用 console mode.
★練習2:試用 C runtime library 的 qsort() 寫個程式
         感受一下 function pointer.
■第2週:03/08  書到 七折([Austern98], [Lippman98])
STL components review
●程式例1 試用 STL 的容器和演算法
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<functional>
using namespace std;
void print(int i)
{
   cout << i << ' ';
}
int  main()
{
   {
   int i;
   int ia[10]={12,14,54,6,3,66,45,90,10,20};
   vector<int> iv(ia, ia+10);
   for_each(iv.begin(), iv.end(), print);
   cout << endl;
   sort(iv.begin(), iv.end());
   for_each(iv.begin(), iv.end(), print);
   cout << endl;
   set<int> is;
   is.insert(4);
   is.insert(3);
   is.insert(7);
   is.insert(0);
   is.insert(2);
   for_each(is.begin(), is.end(), print);
   cout << endl;
   }
   {
   int i;
   int ia[10]={12,14,54,6,3,66,45,90,10,20};
   vector<int> iv(ia, ia+10);
   for_each(iv.begin(), iv.end(), print);
   cout << endl;
   sort(iv.begin(), iv.end(), greater<int>() );
   for_each(iv.begin(), iv.end(), print);
   cout << endl;
   }
}
●程式例2 試用各種 STL components
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
  int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };
  vector<int, allocator<int> > vec( ia, ia+6 );
  cout << count_if(vec.begin(), vec.end(),
                   not1(bind2nd(less_equal<int>(), 40)));
  return 0;
}
// result : 4


■第3週:03/15
find() 泛型化,
運算子多載化 operator overloading.
●程式例1  find() 泛型化的最後結果
#include <iostream>
#include <list>
using namespace std;
template <typename I, typename T>
I find(I begin, I end, const t& value)
{
  // cout << "jjhou" << endl;
  while (begin != end && *begin != value)
     ++begin;
  return begin;
}
int main()
{
  int ia[5] = { 0,1,2,3,4};
  int* pi = find(ia, ia+5, 2);
  cout << *pi << endl;       // 2
  double da[5] = { 0,1,2,3,4};
  double* pd = find(da, da+5, 2.0);
  cout << *pd << endl;       // 2
  list<int> mylist(ia, ia+5);
  list<int>::iterator ite;
  ite = find(mylist.begin(), mylist.end(), 4);
  cout << *ite << endl;      // 4
}
★教訓:如果 find() 介面如下
template <typename I, typename T>
I find(I begin, I end, T value)    // 注意最後一個參數的型式
而非:
template <typename I, typename T>
I find(I begin, I end, const T& value)
會得到以下的可怕錯誤:
Borland C++ 5.4 for Win32 Copyright (c) 1993, 1999 Inprise Corporation
..\T1.CPP:
Error E2015 ..\T1.CPP 19: Ambiguity between
  'std::find<int *,int>(int *,int *,const int &)' and
  'find<int *,int>(int *,int *,int)' in function main()
Error E2015 ..\T1.CPP 24: Ambiguity between
  'std::find<double *,double>(double *,double *,const double &)' and
  'find<double *,double>(double *,double *,double)' in function main()
Error E2015 ..\T1.CPP 30: Ambiguity between
  'std::find<std::list<int,std::allocator<int> >::iterator,int>
    (std::list<int,std::allocator<int> >::iterator,
     std::list<int,std::allocator<int> >::iterator,const int &)' and
  'find<std::list<int,std::allocator<int> >::iterator,int>
    (std::list<int,std::allocator<int> >::iterator,
     std::list<int,std::allocator<int> >::iterator,int)' in function main()
原因是
template <typename I, typename T>
I find(I begin, I end, T value)
template <typename I, typename T>
I std::find(I begin, I end, const T& value)
形成模稜兩可。見 C++ Primer, p521.
★練習:找出你的編譯器的 algorithm 相關檔案,
  看看 STL find() 如何定義。
★仔細思考演算法泛型化過程中的思維模式,以及課中所給的幾個良好編程風格,
如 pass by reference, 如 const 的運用
★學生來信問:
在聽了您上的課後,覺得STL真是沒話說。
不過,有些問題請教。
在intel系列的電腦,在記憶體的位置的位元組是倒過來放的(好像是Byte-reverse sequence吧)。
用久了之後,好像也不覺得有什麼差別。(底下為測試程式)
但這學期,修了PDA的Palm OS程式設計的專題,發現,在PDA上,記憶體的位置是沒有倒過來放的。
這樣一來,在從電腦傳輸至PDA時、在PDA上執行時,都要多花轉換位元組的時間。
PDA不是比較晚出來嗎(照理說,較新的較好不是嗎)?為什麼會採這種放法呢?
是不是這樣有什麼我所看不到的益處?
還有,底下這段程式,在BCB5.0下是沒問題的。
但是在gcc(linux、breebsd)下,卻有錯誤,也不像是不支援...
不知道是什麼緣故。希望候sir不吝賜教
以下為gcc下的錯誤顯示。
[root@linux realDK]# g++ test.cpp
test.cpp: In function `void print(T &)':
test.cpp:37: parse error before `;'
test.cpp: In function `void print<vector<char,__default_alloc_template<true,0> >
>(class vector<char,__default_alloc_template<true,0> > &)':
test.cpp:28:   instantiated from here
test.cpp:38: `i' undeclared (first use this function)
test.cpp:38: (Each undeclared identifier is reported only once
test.cpp:38: for each function it appears in.)
test.cpp:38: confused by earlier errors, bailing out
#pragma hdrstop
#include <iostream>
#include  <vector>
#include <cstdio>
using namespace std;
template <typename T>
void print(T &pricon);
static void convert (unsigned long d)
{
unsigned char *p;
unsigned char b1,b2,b3,b4;
        vector<char> s1;
p=(unsigned char *)(&d);
b1=*p;
p++;
b2=*p;
p++;
b3=*p;
p++;
b4=*p;
        s1.push_back(b1);
        s1.push_back(b2);
        s1.push_back(b3);
        s1.push_back(b4);
        print(s1);
}
template <typename T>
void print(T &pri_con)
{
        if (pri_con.empty())
        cout<<"container is empty!\n";
        else{
                T::iterator i;
                for (i=pri_con.begin();i!=pri_con.end();i++){
                printf("%x",*i); //cout<<(int)*i<<"  ";
                }
        }
}
int main(int argc, char* argv[])
{
        int it=0x12345678;
        printf("before convert:%x",it);//cout<<"before convert:";
        cout<<endl<<"after convert:";
    convert(0x12345678);
}
//---------------------------------------------------------------------------
侯捷回覆:
記憶體位元組的排列方式有 big-endian(正放)和 little-endian(倒放)兩種,
無關好壞。
你這程式的模式切割很不理想,UI介面部份和核心運算部份一定要切割乾淨。
修改如下。課堂上解說。
#pragma hdrstop        // for what ?
#include <iostream>
#include <vector>
#include <algorithm>   // for_each()
using namespace std;
void convert (const unsigned long& d, vector<char>& v)
{
  unsigned char* p = (unsigned char*)(&d);
  v.push_back(*(p++));
  v.push_back(*(p++));
  v.push_back(*(p++));
  v.push_back(*(p++));
}
void print(const char& elem)
{
   cout << hex << (int)elem << dec;
}
int main(int argc, char* argv[])
{
    int it=0x12345678;
    cout << "before convert: " << hex << it << dec;
    vector<char> v;
    convert(it, v);
    cout << endl << "after convert:";
    for_each(v.begin(), v.end(), print);
}
//-- the end

■第4週:03/22
運算子多載化 operator overloading.

C++ Primer 3/e, chap15.
ref. [EC] item11,15,16,17
ref. [MEC] item6,7
ref. STL <memory> class auto_ptr;

課堂示範: operator++, operator++(int), operator<< .

思考:prefix 和 postfix 的效率比較
●程式例1
#include <iostream>
using namespace std;
class INT
{
friend ostream& operator<<(ostream& os, const INT& i);
public:
  INT(int i) : m_i(i) { };
  // prefix : increment and then fetch
  INT& operator++()
  {
    ++(this->m_i);
    return *this;
  }
  // postfix : fetch and then increment
  const INT operator++(int)
  {
    INT temp = *this;
    ++(*this);
    return temp;
  }
private:
  int m_i;
};
ostream& operator<<(ostream& os, const INT& i)
{
  os << '[' << i.m_i << ']';
  return os;
}
int main()
{
  INT I(5);
  cout << I++;  // [5]
  cout << ++I;  // [7]
}


★練習:operator--, operator--(int),寫不下去就看上述範例,再繼續寫。
動手寫一遍比沒動手的學習效果好許多。打鐵要趁熱。
★練習:找出 STL 中的 auto_ptr,看看其中的 operator*(), operator->()
找出STL中的 for_each()演算法,看看其中如何運用 opeartor().

 

 

■第5週:03/29
運算子多載化 operator overloading.
仿函式 functor
function template

C++ Primer 3/e, chap15.
ref. [EC] item11,15,16,17
ref. [MEC] item6,7
ref. STL <memory> class auto_ptr;

課堂示範: operator(), operator=, operator*, operator->.

思考:cout << i++ << i--;
提示:function parameters 的 evaluation 次序

 

同學提問:延續第3週的 ambiguous 問題。以下是我的測試與回答。
#include <iostream>
#include <list>
using namespace std;
/*
以下如果寫的是:
I find(I begin, I end, T value)   // (1)
GCC2.9[o], VC6[o], cb4[x]
CB4 會給錯誤訊息:ambiguity between std::find and find
但我並沒有 #include <algorithm> 為何會決議至 std::find 呢?
猜測:可能 BCB4 某處有 std::find 的宣告,並且被本程式含入。
以下如果寫的是:
I find(I begin, I end, const T value)  // (2)
GCC2.9[o], VC6[o], cb4[x]
CB4 會給錯誤訊息:ambiguity between std::find and find
但我並沒有 #include <algorithm> 為何會決議至 std::find 呢?
猜測:可能 BCB4 某處有 std::find 的宣告,並且被本程式含入。
以下如果寫的是:
I find(I begin, I end, T& value)      // (3)
GCC2.9[w], VC6[o], cb4[o]
GCC2.9 會給警告訊息:
  initialization of non-const reference `int &' from rvalue `int'
在 GCC2.9 中:
(1)(4) 可共存。決議結果為 (4).
(2)(4) 可共存,決議結果為 (4).
(3)(4) 可共存,不再有警告,因為決議結果為 (4).
(2)(3)(4) 可共存,決議結果為 (4).
(1)(3)(4) 不可共存, redefined!
(1)(2)(3)(4) 是 function template overloading。
本例由於函式名稱相同,函式參數個數也相同,
所以(1)(2)(3)(4)也就是 function template specialization 的關係。
見 C++ Primer 3/e p.522
*/
template <typename I, typename T>
I find(I begin, I end, const T& value)   // (4)
{
  cout << "jjhou(4)" << ' ';
  while (begin != end && *begin != value)
     ++begin;
  return begin;
}
int main()
{
  int ia[5] = { 0,1,2,3,4};
  int* pi = find(ia, ia+5, 2);
  cout << *pi << endl;       // jjhou(4) 2
  double da[5] = { 0,1,2,3,4};
  double* pd = find(da, da+5, 2.0);
  cout << *pd << endl;       // jjhou(4) 2
  list<int> mylist(ia, ia+5);
  list<int>::iterator ite;
  ite = find(mylist.begin(), mylist.end(), 4);
  cout << *ite << endl;      // jjhou(4) 4
}

同學提問:以下標準的 iterator 寫法,
(A)和 (B)會不會喚起 MyIter<T>::operator*  ?
(C)會不會喚起 MyIter<T>::operator++()  ?
template <typename T>
struct MyIter
{
  T* ptr;
  T& operator*()  const { return *ptr; }
  T* operator->() const { return  ptr; }
  MyIter& operator++()
    {
      /*...*/               // depend on what need to do...
      return *this;         // (A)
    }
  const MyIter operator++(int)
    {
      MyIter tmp = *this;   // (B)
      ++*this;              // (C)
      return tmp;
    }
  // ...
};
侯捷回覆:
(A)和 (B)不會喚起 MyIter<T>::operator*  
(C)會喚起 MyIter<T>::operator++() 
為什麼一個會而一個不會?思考一下型別。

 

●程式例1
// C++ Standard:Adaptable Binary Function must inherit from 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;
};      
template <class T>
struct less : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x < y; }
};
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred) {
  typename iterator_traits<InputIterator>::difference_type n = 0;
  for ( ; first != last; ++first)
    if (pred(*first))
      ++n;
  return n;
}
//using:
vector<int> iv(...);
count_if(v.begin(), v.end(), bind2nd(less<int>(),40));

 

●程式例2
// 本例測試 function object(functor), function template,
// function pointer 三者搭配 STL algorithms for_each() 的情況
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// (1) function object (functor)
template <typename T>
class print1
{
public:
  void operator()(const T& elem)
     {  cout << elem << ' ';  }
};
// (2) function template
template <typename T>
void print2(T elem)
{
  cout << elem << ' ';
}
// (3) regular function
void print3(int elem)
{
  cout << elem << ' ';
}
int main()
{
  int ia[6] = { 0,1,2,3,4,5 };
  vector< int > iv(ia,ia+6);
  // (1)
  // 以下,print1<int>() 是個暫時物件
  for_each(iv.begin(), iv.end(), print1<int>());  // 0 1 2 3 4 5
  // (2)
  // 以下,需先以 pfi 將 print2 具現化。由於 function template
  // 的具現行為屬於隱式行為(在取址或呼叫時發生),所以我們無法以
  // print2<int> 直接做為 for_each() 的第三參數。
  void (*pfi)(int) = print2;
  for_each(iv.begin(), iv.end(), pfi);            // 0 1 2 3 4 5
  // (3)
  // 將函式名稱(函式指標)當做 function object 來用。
  for_each(iv.begin(), iv.end(), print3);         // 0 1 2 3 4 5
}
同學對上例的疑問:C++ Primer 3/e p505 不是可以明白指定 template 引數嗎?
換句話說可以寫這樣的型式:print2<int>(5); 那為什麼上述的 (2) 不能寫成:
     for_each(iv.begin(), iv.end(), print2<int>);
回覆:p.505 是explicit template arguments,不是 explicit instantiation.  
p.512 有 explicit instantiation declarations,但各家支援程度不一,效果如何也不知。
上例若改為 for_each(iv.begin(), iv.end(), print2<int>); 可通過 CB4,卻通不過 VC6
和 GCC2.91。

 

習題:利用春假時間,寫一個 list(參考 C++ Primer 5.11),
並針對該 list 設計其 iterator。再寫一個測試程式。

 

■第6週:04/05 春假
■第7週:04/12

C++ Primer 3/e, chap16 : class templates

specialization, partial specialization.
partial specialization非常重要,千萬不要缺課。否則你的 GP 功力將失大半。

今天可能會提到一點 iterator 和 iterator traits 的概念,尤其重要。
同學提問:為什麼使用 VC++ <iostream>,會和 friend 產生怪異的結果 
侯捷回覆:課程一開始我就請同學上網看「C++ 標準與實作之間」這篇文章,
          為什麼到現在還有人詢問這種問題。我很失望。
同學提問:C++ Primer p699 的 default ctor 不甚了解。
侯捷回覆:再參考 Effective C++ item45: 
          Know what functions C++ silently writes and calls
同學們不要奇怪老師為什麼常常要你們看這本書,看那本書,看不完的書。
學精一樣東西,一本書是不夠的。好書就只是那幾本,做為一個學習者,
你必須齊備那些好書。老師把那些書譯出來,對各位而言,應該是很幸福
的事了。學生沒錢買書,這不在老師的解題範圍內。

我會在課程上對 default ctor 再做一次解釋。
同學提問:在看到您網站上的"芝麻開門 從 Iterator 談起"中的 auto_ptr
有些疑問想請教:
(1) auto_ptr 中的 operator= 用到了 rhs.release() 及reset(), 其中
release() 及reset 的作用為何?
(2) 對於 auto_ptr 這個例子,其中某些函式的省略原則為何?
    希望能學起來,因為可以訓練表達能力

侯捷回覆:(1) 這種問題查書可得答案,例如 The C++ Standard Library.
(2) 沒有可以省略的。我們前幾堂課曾經以 auto_ptr 為藍本,以其中一小部份
完成一個 smart pointer,其他部份捨棄,那是因為其他部份對我們當時的目的
而言沒有必要。但它們對 auto_ptr 是不可省略的。

同學提問:我在這裡依照老師的意思寫了一個 iterator, 叫做 list_ite
但我們常見一種宣告方式  list<int>::iterator ite;
這兩種有何差別??是因為後者是被定義在"容器"內嗎??

侯捷回覆:是的。如果你要 iterator 定義於一個容器之內(事實上應該如此),
今天就會講到。主要是利用 nested typedef 做一點小改裝。


同學該思考期末作業的解法了。
■第8週:04/19 期中考(本課程無期中考。本週停課)
傳送日期: 2001年4月21日 AM 09:32
主旨: 你怎麼捨得睡覺?
侯老師,我是個工程師,從台北慕名前來聽您的GP,看到您上課求解的態度,
循循誘導學生思索問題的方向,說真的,聽有關程式語言理論與實務的課,
從來不曾如此享受過,您也一再身體力行,show出複雜技術的本質面,
偶而點出這些不凡技術背後的平凡動機,還諄諄地告訴我們該去看哪本哪本書,
這豈是一句感動了得!您把偉大的東西變平凡了,我想,大師風範,當如是也。

那天,正在聽您替一位同學解惑,也正"享受"時,忽而從我左後及右後座位,
間或傳來『好睏』『好想睡覺』,於是,一時興起,舉手發言,想用此舉,
看能不能使那幾位同學振作精神,而老師果然是大師氣度,還兩次說謝,
真令我自慚。我聽說,諾貝爾得主,不約而同都很謙虛,我覺得有可能。

就業以後,再進修的成本大增許多,挑書,挑老師,由於時間預算有限,
變得十分緊縮。元智大學有眼光,侯老師更是慷慨大方,傾囊相授,許多同學
應該也慕名,或者知道「侯sir」在這領域的地位,前來修課,不至於迷迷糊糊
開錯房間闖進來,睡覺,罷。

十幾年前,我有沒有睡覺,錯過重要技術呢?一定有。 

侯捷回覆:偶而收到這樣的來信,便是我「不遠千里」去上課的最大動機。
同學們不知道,上一堂課3小時,我得 4:30pm 從新竹出發,10:30pm 才回到家。
你從台北來聽課,也是夠辛苦的了。

什麼樣的學生都有。教書這麼多年了,我習以為常。但凡課堂上有一兩位努力用功
的學生,我便感到欣慰。

本學期努力用功的學生還算不少。

> 十幾年前,我有沒有睡覺,錯過重要技術呢?一定有。

我也有 :) 人嘛,總是一代一代犯下同樣的錯誤。看看歷史書,古今對照
一下便知。有時我看著學生,看著他們的天真斑爛,看著他們的熱情激昂,
看著他們的愚蠢幼稚,想著,如果是我的子弟,有我引導他們,真不知對他們是
多大的幸福。我的大學生涯,也沒有什麼父兄師長開拓我的視野,教誨我的行止
(也許是因為我的愚蠢幼稚,沒去親近值得親近的師長),因而對此特別感懷。

 

■第9週:04/26
C++ Primer 3/e, chap12,iterator 相關部份

侯捷 STL系列文章第二篇:泛型指標與 Traits 技術
《程序員》雜誌 2001/03 芝麻開門, 從Iterator談起
補充:type_traits
traits 是 GP/STL 的敲門磚。沒有這項技術能力,你很難深入 GP/STL 的世界。
缺了這門課,同學,你將遺憾終身。

課堂上同學提了一個問題,令我愣了一下,一時回答不出來。這個問題是:

Q: STL 正規作法是對 iterator_traits 做 partial specialization,例:
template<I>
struct iterator_traits { ... };
template<T>
struct iterator_traits<T*> {... };

但如果我們在 iterator 層面就做 partial specialization,例:

template<T>
class Iter { ... };
template<T>
struct Iter<T*> {... };

有何利弊得失?
A: 根本不對頭。iterator 的行為在於模仿指標,其template 型別參數應該是其
所指之物的型別,不應該又是一個指標。將 iterator 特化,是違背了
iterator 的設計理念。

 

以下是 SGI STL 的 iterator_traits 源碼節錄,並加上我自己的一些測試。測試並不全面,你可以加上你自己的想法。這份源碼也就是《泛型程式設計與STL》p42 的程式碼整理。至於 type_traits 的作法,請參考 SGI STL <type_traits.h>。

// 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 Value     iterator_value;
  typedef 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;
}

 

 

■第10週:05/03
再論 iterators:insert iterators, stream iterators.
MSDN 2001/04: An STL Iterator for the Internet Explorer Cache, 
by Samir Bajaj
能解以下題目,學期成績 95 分以上:
寫一個 file_iterator,以及三個 functors,使以下行為能夠成功:
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: ";
  cout << accumulate(file_iterator(), file_iterator(0), 0,
                     file_size())
       << "bytes." << endl;

  return 0;
}
執行結果:例如,在 Windows DOS-box 中執行如下:
c:\> mydir <enter>
Total count: 3
...(filename)
...(filename)
...(filename)
Total: 102487 bytes.
提示:
1. 運用 Win32 APIs : FindFirstFile(), FindNextFile(),
    GetCurrentDirectory().
2. file_iterator 應該對 operator++, operator*, operator==, 
   operator!= 加以多載化。
3. 參考前面所說的文章 MSDN 2001/04,An STL Iterator for the 
   Internet Explorer Cache, by Samir Bajaj
4. 參考 STL istream_iterator, ostream_iterator 的源碼。


同學來信:透過老師親手為我們,演繹一遍iterator_traits的技術由來與實作,
相信許多同學跟我一樣感覺,被隔空打通任督二脈,內功又增一旬,
過癮至極!

 

■第11週:05/10
functor, adaptor 源碼剖析, allocator 剖析
同學來信:昨晚,又見老師展現魅力,親手為我們重建functor adaptor的
發明過程,精彩絕倫,BRAVO!在這麼短的時間,可以從原始動機,
一路演化,到一個solid 版本的誕生,呼,我差點喊 ENCORE!


同學來信:老師這星期的上課內容真的很棒很棒!! 我敢說昨晚的收穫絕不是
在短時間內自讀所能達到!! 不過老師卻只花了1.2個小時的時間就
讓我們有如沐春風的感受, 實在是相當的感謝老師!!
害我那天晚上不顧隔天的考試, 趕快將老師所教授的內容從頭到尾
重做一次, 深怕過了那天晚上就忘記了該堂課所收穫的點點滴滴.
ㄟ....希望考試成績不會受太大的影響....^_^""

有一位同學,每週四從台北下班後直奔元智,旁聽 GP 課程。通常到達之後只剩最後一個小時可以聽。一方面我佩服他的毅力,一方面我對他的遺漏感到惋惜。但他總是說能夠聽這一小時,也很滿足。

這一週我從 count_if() 的第三個參數談起,談到一般的 functor, 談到 adaptable functor,談到 functor adaptor。這個「問題的發生與解決,以及進一步的彈性擴大」的流程與演繹,是各位絕不可能在任何一本書上看到的。這位遠道而來的同學沒有能夠聽到這一段,我非常為他惋惜。為此,我把這個流程整理放在網上。

 

以下是仿函式和配接器的標準用法

// vc6[o] cb4[o] gcc[o]
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int main()
{
  int ia[10] = { 0,1,2,3,4,5,6,7,8,9 };
  vector<int> iv(ia, ia+10);
  // 以下計算滿足 "less than 5" 的元素個數。採用 STL components
  cout << count_if(iv.begin(), iv.end(), bind2nd(less<int>(),5));
}
以下分析問題的由來、解決、和擴充。
問題分析:如果不採用bind2nd(less<int>(),5),而是直接使用一般的 
functor,如下可行:

// vc6[o] cb4[o] gcc[o]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 以下這個仿函式,用來實作出「小於5」的條件判斷式(predicate)
template <class T>
class less_than_5
{
public:
  bool operator()(const T& n) const
  { return n < (T)5; }    // 相當於 operator<(n, (T)5);
};
int main()
{
  int ia[10] = { 0,1,2,3,4,5,6,7,8,9 };
  vector<int> iv(ia, ia+10);
  // 以下計算滿足 "less than 5" 的元素個數
  cout << count_if(iv.begin(), iv.end(), less_than_5<int>());
}
為了令上一例的 less_than_5<T> 更具彈性,我們可以設計一個 functor,
使它接受某個動作 op(取代前例的 operator<)和某個數值 n(取代前例的 5),
並令 n 為 op 的第二引數。為此,我們將此 functor 命名為 Jbinder2nd
(前面加 J 以便與 STL component 區分)。為了接受動作op 和數值 n,
必須有兩個data members用來儲存它們:

template <class OP, class T>
class Jbinder2nd
{
protected:
  OP _op;
  T _n;
...
};
但由於 n 既然要做為 OP 的第二引數,其型別 T 和 OP 之間便有一種相依性,
所以我們可以捨棄 T,以 OP::second_argument_type 取而代之(前提是 OP 為
可配接的,adaptable)。由於 OP 未定,所以我們必須加上關鍵字 typename 以
協助編譯器判斷 OP::second_argument_type 是啥東西:

template <class OP>
class Jbinder2nd
{
protected:
  OP _op;
  typename OP::second_argument_type _n;
為了讓 Jbinder2nd 接受動作 op 和數值 n,我們可以設計在其 ctor 中接受之。
於是變成:
template <class OP>
class Jbinder2nd
{
protected:
  OP _op;
  typename OP::second_argument_type _n;
public:
  Jbinder2nd(const OP& op, const typename OP::second_argument_type& n)
    : _op(op), _n(n) { }
以下是完整內容

// vc6[o] cb4[o] gcc[x]
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
template <class OP>
class Jbinder2nd
{
protected:
  OP _op;
  typename OP::second_argument_type _n;
public:
  Jbinder2nd(const OP& op, const typename OP::second_argument_type& n)
    : _op(op), _n(n) { }
  typename OP::result_type		// 傳回值型別
  operator()(const typename OP::first_argument_type& x) const
  { return _op(x, _n); }
};
int main()
{
  int ia[10] = { 0,1,2,3,4,5,6,7,8,9 };
  vector<int> iv(ia, ia+10);
  // 先產生一個 Jbinder2nd object(這是個 predicate)
  // 這個動作對於一般程式員有點困難。
  Jbinder2nd< less<int> > jb(less<int>(),
                             (less<int>::second_argument_type)5); // GCC error
  // 然後餵給 count_if() 做為第三參數
  cout << count_if(iv.begin(), iv.end(), jb);
}
由於「直接產生 Jbinder2nd object」(如前例)在語法上有點難度,
我們可以利用function template 的「引數自動推導」能力,幫我們
簡化工作。加上這一中介層,使客端所需面對的難度降低了不少。同時,
為了讓 Jbinder2nd<OP> 也具備adaptable 能力,最好是令它繼承自 
std::unary_function。

// vc6[o] cb4[o] gcc[o]
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
// class template
template <class OP>
class Jbinder2nd 
  : public unary_function<typename OP::first_argument_type,
                          typename OP::result_type> {
{
protected:
  OP _op;
  typename OP::second_argument_type _n;
public:
  Jbinder2nd(const OP& op, const typename OP::second_argument_type& n)
    : _op(op), _n(n) { }
  typename OP::result_type
  operator()(const typename OP::first_argument_type& x) const
  { return _op(x, _n); }
};
template <class OP, class T>
inline
Jbinder2nd<OP>    // 傳回值型別
Jbind2nd(const OP& op, const T& n) 	// 函式名稱與參數列
{
  // 以下,型別過長,另取一個簡短別名
  typedef typename OP::second_argument_type OpSat;  
  return Jbinder2nd<OP>(op, (OpSat)n);
  // 以上產生一個 Jbinder2nd object。
}
int main()
{
  int ia[10] = { 0,1,2,3,4,5,6,7,8,9 };
  vector<int> iv(ia, ia+10);
  cout << count_if(iv.begin(), iv.end(), Jbind2nd(less<int>(),5));
}

請拿這份歷經一步一步階段演化而來的代碼,與第一例(使用標準的STL組件)
比較,並取這份代碼中的 Jbinder2nd<OP> 和 Jbind2nd(),與 STL 的 
binder2nd<OP> 和 bind2nd() 比較,你會發現它們完全一樣。
換句話說,你現在知道 binder2nd<OP> 和 bind2nd() 是怎麼設計出來的了。

 

■第12週:05/17
deque 剖析
■第13週:05/24
set/map 剖析 (兼談 Red-Black Tree), 
hash table 剖析
set algorithms 剖析
 
傳送日期: 2001年5月25日 PM 08:13
主旨: 感激!!
侯老師,您好:
        雖然您獲得來自各方的答謝已頻頻不斷,但我還是以心存萬分感激的心情,
謝謝您允許學生旁聽您的課程.自從在網路上得知老師要在元智大學於晚間 教
授"Generic Programming and STL"這門課時,我因為信奉佛教,頓時認為是平日唸
佛方能獲得如此的因緣.此外, 課前曾多次電話聯繫學校確定開課時間與教室
號碼並以現地勘查方式到該校一遊,深怕錯失機會.
       在此,還是要再次向您道歉,因為從第一天上課至課程結束都未曾向您報告;
在最後為了聊表心意,送您的咖啡豆,還不知是否合您的口味,亦或又為您增加處
理的困擾.
       此次課程不僅幫我節省了最寶貴的學習時間並能達到事半功倍的效果;而且
能現場聆聽一位在此領域研究如此透徹的老師所教授的課程真是令人興奮.課堂
裡得知您作學問的精神與問題思考的方式,更有助於我們日後引為作學問的借鏡.
想想那些能在大學時代就接受您的薰陶的學生,在佛家來說是上輩子修來的.我雖
然不像他們,但是有此機會,我以為比起其他許多想來上課,但因為種種因素而無法
如願的人又幸運多了.
      最後,再次謝謝您的教導.
 
    敬祝        身體健康   
                    萬事如意
  
侯捷回覆:相逢自是有緣。這是我們的緣份。您的咖啡讓我很感動,很開心。
                                                              
 
■第14週:05/31  停課

 

■第15週:06/07  期末作業檢討.1
以下各組於本周課堂上交出作業及報告。上台次序如同組別次序。
每組需提供書面報告一份,原始碼磁片一份給老師,並推派一位(或多位)同學
上台主講。原始碼當場編譯(請使用 command line 模式),機器由老師準備。
講述內容請自己構思(你認為什麼是該講的呢?你認為聽眾想聽什麼呢?)
提示一點:書面報告對於你的成績,影響很大。
課堂上未能呈交作業及報告,或是當天缺席者,作業成績以0分計。
2001/06/29 補註:名單之後為學期總成績。我曾說過,選擇 file-iterator 題目者,
成績在 95 分以上。這是個口誤,我真正的意思是,總成績中的「程式表現」部份
將獲得 95% 的分數。總成績包括 (1)口頭報告、(2)書面報告、(3)程式表現、
(4) 平時表現 四項。
組別 (0)
864029	王詔凱(未按時間編列組別,總成績扣5分)67
874003	蔡遠銘(未按時間編列組別,總成績扣5分)67

組別 (1)
874021    周岳樺(未按時間編列組別,總成績扣3分)79
874023    黃思偉(未按時間編列組別,總成績扣3分)79
874026    朱仕任(未按時間編列組別,總成績扣3分)79
874055    張賢宗(未按時間編列組別,總成績扣3分)79

組別 (2)
874067 王再發 71
874095 林奕璋 71
874115 盧威杉 71
874117 朱義勝 71

組別 (3)
孟憲君 874073   82
鄭博文 874074   82
劉智強 874121   82
鄭人豪 874125   82
傅重嘉 874113(未按時間編列組別,總成績扣3分) 79
趙元鰲 874081(未按時間編列組別,總成績扣5分) 77

組別 (4)
874011     林烺    69
874013     林學謙  69
874053     黃信錩  71

組別 (5)
882355	蔡秉霖 85
882357	吳俊德 85
882333	李文智 85
882207  施威年 85

組別 (6)
874006 周樹偉 88
874008 王彥凱 88
874017 陳??   88
874060 邱致瑋 88
874063 徐之豪 88

■第16週:06/14  期末作業檢討.2
以下各組於本周課堂上交出作業及報告。上台次序如同組別次序。
每組需提供書面報告一份,原始碼磁片一份給老師,並推派一位(或多位)同學
上台主講。原始碼當場編譯(請使用 command line 模式),機器由老師準備。
講述內容請自己構思(你認為什麼是該講的呢?你認為聽眾想聽什麼呢?)
提示一點:書面報告對於你的成績,影響很大。
課堂上未能呈交作業及報告,或是當天缺席者,作業成績以0分計。
2001/06/29 補註:名單之後為學期總成績。我曾說過,選擇 file-iterator 題目者,
成績在 95 分以上。這是個口誤,我真正的意思是,總成績中的「程式表現」部份
將獲得 95% 的分數。總成績包括 (1)口頭報告、(2)書面報告、(3)程式表現、
(4) 平時表現 四項。
組別 (7)
874075  梁懷中 75
874082  楊士賢 75
874089  陳世光 75
874106  簡銀谷 75

組別 (8)
874002    王志暐 83
874004    李凱勛 83
874016    黃正和 83
874052    吳炳宜 83
874057    吳慶鑫 83
874061    劉志孝 83

組別 (9)
882204 劉新玫 80
882218 林康司 80
882219 邱世雄 80
882250 洪一菁 80

組別 (10)
864131 羅衝聘 90
865121 廖志彬 90
864138 史永建 95
864127 詹儒忠 90
864105 郭裔銘 90

組別 (11)
874076 徐慶豪 82
874077 賴宜辰 82
874097 李昇家 82
874093 施志翰 82
874103 吳承熹 82
874112 鄭欣智 82
874116 黃琨富 82

組別 (12)
882234    趙品權 92
882203    陳純怡 92
882224    陳韻如 92
882227    劉本傑 92
882235    廖茂育 92
882236    李光曜 95
組別 (13)
874019  林韋彤 94
874020  謝彥偉 99
874027  李建勳 94
874032  彭彥璁 94
874058  李德昇 94
■第18週:06/21  期末考 停課