【函式指標 -- 文章勘誤】   1999.04.17 發表


RunPC 雜誌得知我正在翻譯 <C++ Primer> 3/e 後,提出邀請,希望能率先刊登部份稿件。我徵得 Addison Wesley 的同意後欣然接受。

我擷選了八個主題,分期刊載:

1. 函式指標 1999.03
2. 命名空間 1999.04
3. 函式模板 1999.05
4. C++ 異常處理 1999.06
5. 泛型演算法 1999.07
6. 類別 1999.08
7. STL 1999.09
8. 虛擬函式 1999.10

第一篇文章(RunPC 63 期,1999/03)的主題是函式指標。刊出後得到謝勝仁先生的指教。謝勝仁先生指出了原文書中一個考慮未週詳的地方(可說是一個 bug)。謝先生的指教如下。

來信一:

> Hello 侯老師,
>
> 看了您在 RUN!PC 三月號的大作之後, 我定義了 sizeCompare 函式:
>
> int sizeCompare( const string &s1, const string &s2 ) {
>   if (s1.length()==s2.length()) return 0;
>   if (s1.length()>s2.length()) return 1;
>   return -1;
> }
>
>
也修改了 main():
>
> int main() {
>   PFI pfs = sizeCompare;
>   string as[10] = { "a", "light", "drizzle", "was", "falling",
>                     "when", "they", "left", "the", "museum" };
>
>   sort( as, as + sizeof(as)/sizeof(as[0]) - 1, pfs );
>
>   for ( int i = 0; i < sizeof(as)/sizeof(as[0]); ++i )
>     cout << "\t" << as[ i ].c_str() << "\n";
>   return 0;
> }

>
> 但執行的結果仍然是呼叫 lexicoCompare 的排列次序, 我無法理解到底
> 錯在那兒? 承蒙指教, 感激不盡.

來信二:

> Hello 侯老師,
>
> 我找到錯誤了, 問題出在RUN!PC 62期294頁, sort()函式第20,21行
>
> sort(s1,high-1);
> sort(high+1,s2);

>
> 少了第三個參數, compare.
> Best regards,


●讓我做個結論

RunPC 63 期(1999/03)的這篇文章中,有一個 sort() 函式,
利用遞迴方式呼叫自己,完成 quicksort 演算法。此函式有
三個參數,其中第三個參數是個函式指標,有預設參數值:

int lexicoCompare( const string &, const string & );
int sort( string*, string*, PFI2S = lexicoCompare );

1 void sort( string *s1, string *s2,
2 PFI2S compare = lexicoCompare )
3 {
4   // stopping comdition for recursion
5   if ( s1 < s2 ) {
6     string elem = *s1;
7     string *low = s1;
8     string *high = s2 + 1;
9
10    for (;;) {
11      while ( compare( *++low, elem ) < 0 && low < s2 );
12      while ( compare( elem, *--high ) < 0 && high > s1 );
13
14      if ( low < high )
15        low->swap(*high);
16      else break;
17    } // end, for(;;)
18
19    s1->swap(*high);
20    sort( s1, high - 1 ); //
謝勝仁先生指出的錯誤
21    sort( high + 1, s2 ); // 謝勝仁先生指出的錯誤
22  } // end, if ( s1 < s2 )
23 }


由於 <C++ Primer> 一書 p.383~p.384 的 sort() 程式碼(如上)於遞迴呼叫時並沒有指明第三個參數,所以總是使用預設值 lexicoCompare,因此即使我們在最初呼叫 sort() 時指定了另一個自定的 compare 函式,仍然得不到預期結果。

只要修改如下即可:

20 sort( s1, high - 1, compare );
21 sort( high + 1, s2, compare );




非常感謝 謝勝仁先生。這是 <C++ Primer> errata 未記錄的一個 bug。我會在中譯本修正之。

另,不少朋友詢問 <C++ Primer> 中文版的進度。感謝關心,進度不錯。原本預定的出版日期是 1999.09,我想可以提早。

-- the end --