4.5.1  使用高效的算法

最小化使用空闲存储空间最有效的方法就是使用高效利用空间的算法。假设我们正在实现一个程序库，打算供C++(www.cppentry.com)编程(www.cppentry.com)开发环境使用；我们还希望提供另一个函数，用来编译给定的C++(www.cppentry.com)代码：

bool compile(istream& i, const List<String>& incldirs,  
    ostream& o);  

函数读取i中的文本，并且尝试编译这段文本；使用incldirs作为搜索要#include文件的路径列表。如果在这个过程没有发生错误，compile函数会把编译结果的目标代码写入o中，并返回true；否则，compile函数将返回false。

我们可以分两个阶段来实现compile函数：首先，预处理代码，并把生成的宏扩展文本储存在空闲存储空间中，然后编译这些文本。遗憾的是，上面这个算法使用了大约s个字节的空闲存储空间，其中s是宏扩展文本的大小；因为对于实际程序，s很容易达到500K甚至更大，所以如果我们的用户并没有足够的空闲存储空间来容纳compile函数的实现，那么我们就不得不使用另外一个不同的实现。

与其把宏扩展文本都写入内存里面，还不如把它写入一个文件里面。假设我们实现了下面两个函数：

bool preprocess(istream& i, const List<String>& incldirs,  
          ostream& o);  
bool compile_preprocessed(istream& i, ostream& o)；  

第一个函数先预处理i中的文本，如果没有出现错误，preprocess函数将把宏扩展的结果写入o中，并返回true值；否则返回false值。第二个函数编译i中的已经预处理好（假设已经通过第一个函数的处理）的代码；如果不出现错误，compile_preprocessed将把编译后产生的目标代码写入o中，并返回true值，否则返回false值。

有了上面两个函数，我们就可以如下实现compile函数：

#include<fstream.h> 
bool compile(istream& i, const List<String>& incldirs,  
          ostream& o) {  
    ofstream otmp("tmpfile")；  
    if(preprocess(i, incldirs, otmp)) {  
         otmp.flush()；  
         ifstream itmp("temfile");  
         return compile_preprocessed(itmp，o)；  
    }  
    return false;  
}  

compile函数的上面这个实现使用了文件系统空间-而不是空闲存储空间-来储存宏扩展文本。文件系统空间在大多数系统都是非常充足的。然而，这个实现要求整个宏扩展文本先写入一个文件，然后再从文件中读取出来；而文件I/O显然要比内存存取慢很多。

为了使compile函数在空间使用和运行速度上都达到较高的效率，我们必须每次在内存中预处理一给定大小的文本块。最后，假设我们设计了下面一个完成这种功能的类：

class Preprocessor {  
   public;  
        Preprocessor(istream& i, const List<String>& incldirs);  
        Bool nextchunk(String& s);  
       //...  
   };  

上面的构造函数在字符流i的文本中创建了一个Preprocessor对象。只要预处理操作没有结束；nextehunk：函数就会把s赋值为下一块的宏扩展文本，并返回true值；当流中已经没有文本的时候，它就会返回false值。而且，每一块宏扩展文本的大小都不大于相应给定的常数（即预先已经规定的内存块大小常数）。

我们接下来改变compile_preprocessod的接口，让它接收一个Preprocessor对象；而不是istream&对象：

bool compile_preprocessed(Preprocessor& p, ostream& o); 

bool compile(istream& i, const List<String>& incldirs,  
             ostream& o) {  
       Preprocessor p(i, incldirs);  
       Return compile_preprocessed(p, o);  
   }