C++之父Bjarne谈C++中的STL模板

　　考虑第一个实现：在调用find(vi.begin(),vi.end(),7)中，迭代子vi.begin()和vi.end()会相应地成first为last，在find()内部有些东西指向int（整型）、int*。在这样的实现中，*成为了指针，++成为了指针增加操作符，!=成为了指针比较操作符。也就是说，find()的实现是明显的、理想的。特别地，我们没有使用函数调用来访问那些作为运算法则的有效参数的操作符（例如*和!=），因为它们依赖于模板参数。在这种情况中，模板与"泛型"的大多数机制从根本上都是不同的，它依赖于当前编程语言中的间接函数调用（类似虚拟函数）。如果有一个好的优化程序（optimizer），vector::iterator可以成为一个把*和++作为内建函数（inline function）的、没有资源花费（overhead）的类。这种优化程序现在很少，它通过捕捉无保证的假设（如下所示）来进行类改善类型检查。

int* p = find(vi.begin(),vi.end(),7); // 迭代子类型不能是 int*

　　那么为什么我们不省去所有的"迭代子材料"和使用指针呢？其中一个原因是vector::iterator可能已经成为了一个提供了范围检查访问的类。我们看看find()的其它调用：

list::iterator q= find(vd.begin(),vd.end(),3.14);
if (q != vd.end()) {
　// 我们找到了3.14
　// …
}
else {
　// vi 中没有3.14
　// …
}

　　此处list::iterator不会成为double*。实际上，在最普通的链表实现方式中，应该是Link*类型的，其中是链表节点类型的，例如：

templatestruct Link {
　T value;
　Link* suc;
　Link* pre;
};

　　这意味着，*的意思是p->value（返回值字段），++的意思是p->suc（使指针指向下一个链接），!=指针比较的意思是（比较Link*s）。同样，这种实现也是明显的、理想的。但是，它与我们前面看到的vector::iterator完全不同了。

　　我们使用了模板组合（combination）和重载解决方案为find()的单一源代码定义和使用来挑选根本不同的、也是理想的代码。请注意，这儿不存在运行时分派（dispatch）、没有虚拟函数调用。实际上，它只有琐碎的内联函数和指针的基本操作（例如*和++）的调用。在速度和代码大小方面，我们都到取得了很大的成功。

　　为什么没有把"序列"或"容器"作为基本的概念，而使用了"一对迭代子"呢？部分原因在于"一对迭代子"只不过比"容器"的概念更普通。例如，给定迭代子，我们可以只对容器的前一半进行排序：sort(vi.begin(), vi.begin()+vi.size()/2)。另一个原因是STL遵循了C++的设计原则，我们必须一律地提供转换（transition）路径、支持内建的和用户定义类型。如果某个人把数据保存在普通的数组中会怎么样呢？我们仍然可以使用STL算法。例如：

char buf[max];
// … 填充buf …
int* p = find(buf,buf+max,7);
if (p != buf+max) {
　// 我们找到了 7
　// …
}
else {
　// buf 中没有 7
　// …
}

　　此处，find()中的*、++和!=都是指针操作符！与C++本身不同，STL与一些旧的概念（例如C数组）是兼容的。我们始终提供转换路径，平等地对待用户定义类型和内建类型（如数组）。

　　STL像ISO C++标准库所采用的容器和算法框架一样，包含一打容器（例如vector、list和map）和数据结构（例如数组），它们可以被当作序列使用。此外，还有大约60种算法（例如find、sort、accumulate和merge）。你可以查阅资料看到更详细的信息。

　　STL的优雅和性能的关键在于--与C++本身类似--它是基于直接的内存和计算硬件模型的。STL的序列的概念基本上是把内存作为一组对象序列的硬件视点。STL的基本语法直接映射到硬件指令，允许算法最佳地实现。接下来，模板的编译时解析和他们支持的完美内联成为了把STL高级表达式高效率地映射到硬件层的关键因素。

[1] [2] [3] [4]