1.6 练习
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：
class Path {
public:
Path();
Path(const String& s);
//...
private:
void canonicalize();
}；
上面的代码中，缺省构造函数创建了一个空路径，另一个构造函数创建了一个规范形式的路径s。在规范形式里，.标志符已经被删除，..标志符也尽可能被去掉，多个连续的/被精减为单个/，剩下的/都删除掉了。于是，例如下面字符串
../../dir/./dir2//other_dir/..tem.c/
的规范形式是：
../../dir/dir2/tem.c
a．（*）如果用户让Path的构造函数自动规范化所给的字符串，那么对于什么样的UNIX系统用户，才会出现不可取的行为？（提示：何时dir/../some_file/和some_file表示不同的文件？）
b．对于Windows用户而言，为什么第二个构造函数的行为是错误的呢？
1.3 为了能够同时适应Windows系统程序员和UNIX系统程序员，我们可以改变Path类的设计，让用户指定作为路径分隔符的字符：
class Path {
public;
Path(const String& s, char separator);
//...
};
于是，UNIX系统上的用户必须指定‘/’为分隔符，而Windows用户必须指定‘’（这实际上是一个转义后的反斜杠符）分隔符。那么这个改变会给现在的UNIX用户带来什么样的问题呢？你是否可以在避免这种问题发生的前提下，改变Path类的设计呢？
1.4 假设我们现在希望为VMS用户提供Path类。在VMS系统中，没有特殊的字符被认为是路径分隔符；于是，练习1.3设计的Path接口并不适用于VMS的用户。为了改善Path的设计，我们必须再次改变Path的实现：
class Path {
public:
enum Style { UNIX, Windows, VMS};
Path(const String& s, Style style = UNIX);
//...
};
那么对于当前的UNIX用户和Windows用户，这个改变会导致什么样的问题呢？
1.5 给出设计下面4个类的方法：Paht、Unix_path、Windows_path和Vms_path，后面3个类派生自第1个类，并且用户可以如下编写代码：
Vms_path r("[dir]tmp");
Unix_path p("/dir/tmp");
Windows_path q("\\dir\\tmp");
假设不存在早期版本的Path类的用户，那么与练习1.4的设计相比，请给出这个设计的一个缺点和一个优点。
本文仅用于学习和交流目的，不代表异步社区观点。非商业转载请注明作译者、出处，并保留本文的原始链接。