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

　　1.1 STL的理念

　　那么什么是STL呢？到目前为止，它作为标准C++的一部分已经快十年了，因此你的确应该知道它，但是如果你不熟悉现代的C++，那么我就有必要对它的想法和语言使用方式作一些简单的介绍。

　　我们来考虑一个问题：把对象存储在容器中，并编写算法来操作这些对象。我们按照直接、独立和概念的混合表现方式来考虑这个问题。自然地，我们希望能够在多种容器（例如列表、向量、映射）中存储多种类型（例如整型、Point、Shape）的对象，并在容器中的对象上应用大量的算法（例如排序、检索、积聚）。此外，我们希望使用的这些对象、容器和算法都是静态类型安全的、尽可能地快速、尽可能地简洁、不冗长、易于阅读。同时实现这些目标并不容易。实际上，为了解决这个难题，我差不多花费了十年还是没有找到成功的方法。


　　STL解决方案是以带元素类型的参数化容器以及与容器完全分离的算法为基础的。容器的每种类型都提供一种迭代子（iterator）类型，只使用这些迭代子就可以实现对容器中所有元素的访问。通过这种方式，我们可以编写算法来使用迭代子而不用知道提供迭代子的容器的信息。每种迭代子类型与其它类型都是完全独立的，除非要为必要的操作（例如*和++）提供了相同语义（semantics）。我们可以用图形来说明。

　

　　我们来看一个很恰当的例子，它在不同的容器中查找不同类型的元素。首先，下面是两个容器：

vectorvi; // 整型向量
listvd; // 双精度型列表

　　目前存在一些向量和列表概念的标准类库，它们是作为模板实现的。假如你已经用相应的元素类型值恰当地初始化过它们，那么在vi中查找第一个值为7的元素和在vd中查找第一个值为3.14的元素的语法如下：

vector::iterator p = find(vi.begin(),vi.end(),7);
list::iterator q = find(vd.begin(),vd.end(),3.14);

　　其基本的想法是，你能够把任何容器的（所有）元素都作为一个元素序列（sequence）。容器"知道"第一个元素在哪儿，最后一个元素在哪儿。我们把指向一个元素的对象称为"迭代子"。接着我们就可以使用一对迭代子（begin()和end()）来表示容器中的元素，其中begin()指向第一个元素，end()指向最后一个元素前面。

　　end()迭代子指向最后一个元素后面，而不是指向最后一个元素，这就使空序列不会成为一种特殊情况。

　　你能对迭代子做什么样的操作？你可以得到迭代子指向的元素的值（像指针一样使用*），可以使迭代子指向下一个元素（像指针一样使用++），可以比较两个迭代子，看它们是否指向同一个元素（使用==或!=）。令人惊讶的是，这已经足以实现find()（查找功能）了：

templateIter find(Iter first, Iter last, const T& val)
{
　while (first!=last && *first!=val) ++first;
　return first;
}

　　这是一个简单的--真的非常简单的--模板函数。熟悉C和C++指针的人应该发现这些代码很容易阅读的：first!=last检查我们是否到了序列末尾，*first!=val检查我们是否找到了值val。如果没有找到，我们增加first迭代子，使它指向下一个元素并重复。因此，当find()返回的时候，它的值要么指向值为val的第一个元素，要么指向最后一个元素后面（end()）。于是我们可以编写下面的代码：

vector::iterator p = find(vi.begin(),vi.end(),7);
if (p != vi.end()) {
　// 我们找到了 7
　// …
}
else {
　// vi 中没有 7
　// …
}

　　这是非常非常简单的。它简单得像数学书的前面几页，速度也很快。但是，我知道自己不是唯一一个花时间来研究它到底是如何实现的、以及为什么它是一个好的想法的人。与简单的数学相似，最初的STL规则和原理的概括也是难以置信的。

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