《C++代碼設計與重用》——1.6 練習

本節書摘來自異步社群出版社《imperfect c++中文版》一書中的第1章，第1.6節，作者： 【美】martin d.carroll , margaret a.ellis，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

c++代碼設計與重用

1.6 練習

在整本書裡，困難的題目将會在題号後面标示（），特别困難的題目會用（*）标示。

1.1 假設你在實作一個函數，這個函數在一個給定的數組中查找某個給定的值。

a．在什麼情況使用函數時，線性查找的實作比二分查找的實作具有更高的效率。

b．為了能在任何環境下，你的查找算法都可以更加高效地執行，你應該如何（使用什麼算法）實作這個函數呢？

c．假設在這裡，我們并不是查找使用者給定的值，而是查找第一個0出現的位置，那麼需要在什麼樣的條件下，線性查找才能比二叉查找更有效呢？

d．假設我們現在的查找範圍不再是使用者給出的數組，而是一個具體的數組，但查找值仍然是使用者指定的。假設函數is_prime為了判斷某個小于1000的數字是否是素數，需要查找一組所有小于1000的素數。那麼，以這個假設為前提，在什麼樣的條件下，線性查找才能比二叉查找具有更高的效率？

1.2 在這個練習和下面的練習裡，我們将分析一個問題，它是由程式庫設計者未能在開初就顯式聲明程式庫的使用者類型而引起的。

假設我們是可重用類path的設計者，其中path表示我們使用者檔案系統中的路徑名稱。例如，在unix系統中，典型的路徑有：dir、dir/dir2/tmp和../tmp等；在windows系統中，相應的路徑應該寫成：dir、dirdir2tmp和..tmp；而在vms系統中，這些相應的路徑為：dir、［dir.dir2］tmp和[-]tmp。

假設當我們開始設計path時，我們忘記了指定這個類的使用者類型；那麼，在設計過程中途，如果我們是unix程式員，我們可能就隻會以unix路徑的模式來設計path：

上面的代碼中，預設構造函數建立了一個空路徑，另一個構造函數建立了一個規範形式的路徑s。在規範形式裡，.标志符已經被删除，..标志符也盡可能被去掉，多個連續的/被精減為單個/，剩下的/都删除掉了。于是，例如下面字元串

的規範形式是：

a．（*）如果使用者讓path的構造函數自動規範化所給的字元串，那麼對于什麼樣的unix系統使用者，才會出現不可取的行為？（提示：何時dir/../some_file/和some_file表示不同的檔案？）

b．對于windows使用者而言，為什麼第二個構造函數的行為是錯誤的呢？

1.3 為了能夠同時适應windows系統程式員和unix系統程式員，我們可以改變path類的設計，讓使用者指定作為路徑分隔符的字元：

于是，unix系統上的使用者必須指定‘/’為分隔符，而windows使用者必須指定‘’（這實際上是一個轉義後的反斜杠符）分隔符。那麼這個改變會給現在的unix使用者帶來什麼樣的問題呢？你是否可以在避免這種問題發生的前提下，改變path類的設計呢？

1.4 假設我們現在希望為vms使用者提供path類。在vms系統中，沒有特殊的字元被認為是路徑分隔符；于是，練習1.3設計的path接口并不适用于vms的使用者。為了改善path的設計，我們必須再次改變path的實作：

那麼對于目前的unix使用者和windows使用者，這個改變會導緻什麼樣的問題呢？

1.5 給出設計下面4個類的方法：paht、unix_path、windows_path和vms_path，後面3個類派生自第1個類，并且使用者可以如下編寫代碼：

假設不存在早期版本的path類的使用者，那麼與練習1.4的設計相比，請給出這個設計的一個缺點和一個優點。

本文僅用于學習和交流目的，不代表異步社群觀點。非商業轉載請注明作譯者、出處，并保留本文的原始連結。