3.6 C++

我们的第三个实现将在C++ 中完成。因为C++ 语言几乎是C的一个超集，它也能以C的形式使用，只要注意某些写法规则。实际上，前面C版本的markov也是一个完全合法的C++ 程序。对C++而言，更合适的用法应该是定义一些类，建立起程序中需要的各种对象，或多或少像我们写Java程序时所做的那样，这样可以隐蔽起许多实现细节。我们在这里希望更前进一步，使用C++的Standard Template Library( 标准模板库)，即STL。因为STL提供了许多内部机制，能完成我们需要做的许多事情。ISO的C++ 标准已经把STL作为语言定义的一部分。

STL提供了许多容器类，例如向量、链表、集合等，还包括了许多检索、排序、插入和删除的基本算法。通过利用C++ 的模板特性，每个STL算法都能用到很多不同的容器类上，容器类的元素可以是用户定义类型的或者是内部类型的(如整数)。这里的容器都被描述为C++ 模板，可以针对特定类型进行实例化。例如，STL里有一个vector容器类，由它可以导出各种具体类型，比如vector<int>或vector<string>等。所有的vector操作，包括排序的标准算法等，都可以直接用于这些数据类型。

在STL里，除了有vector容器(它与Java的vector类差不多)，还提供了一个deque容器类。deque(念为deck)是一种双端队列，它正好能符合我们对前缀操作的需要：可以用它存放NPREF个元素，丢掉最前面的元素并在后面添一个新的，这都是O(1)操作。实际上，STL的deque比我们需要的东西更一般，它允许在两端进行压入和弹出，而执行性能方面的保证是我们选择它的原因。

STL还提供了一个map容器，其内部实现基于平衡的树。在map中可以存储关键码—值对。map的实现方式保证，从任何关键码出发提取相关值的操作都是O(logn)。虽然map可能不如O(1)的散列表效率高，但是，直接使用它就可以不必写任何代码，这样也很不错(某些非标准的C++库提供了hash或hash_map容器，它们的性能可能更好些)。

我们也可以使用内部提供的比较函数，用于对前缀中各字符串做比较。

手头有了这些组件，有关代码可以流畅地做出来了。下面是有关声明：

STL提供了deque的模板，记法deque<string>将它指定为以字符串为元素的deque。由于这个类型将在程序里多次出现，在这里用一个typedef声明，将它另外命名为Prefix。映射类型中将存储前缀和后缀，因为它在程序里只出现一次，我们就没有给它命名。这里声明了一个map类型的变量statetab，它是从前缀到后缀向量的映射。在这里工作比在C或Java中更方便，根本不需要提供散列函数或者equal方法。

main函数对前缀做初始化，读输入(对于标准输入，调用C++ iostream里的cin)，在输入最后加一个尾巴，然后产生输出。和前面各个版本完全一样。

函数build使用iostream库，一次读入一个词：

字符串buf能够根据输入词的长度需要自动增长。函数add能够进一步说明使用STL的优越性：这几个非常简单的语句确实做了不少事情。map容器类重载了下标运算符([]运算符)，使它在这里成为一种查询运算。表达式statetab[prefix]在statetab里完成一次查询，以prefix作为查询的关键码，返回对于所找到的项的一个引用。如果对应的向量不存在，这个操作将建立一个新向量。vector和deque类的push_back函数分别把一个新字符串加到向量或deque的最后；pop_front从deque里弹出头一个元素。