vc++网址.txt

STL之父访谈录 翻译者 : myan

a: 1993年夏, andy koenig跑到斯坦福来讲c++课, 我把一些有关的材料给他看, 我想他当时确实是很兴奋.他安排我9月到圣何塞给c++标准委员会做一个演讲. 我演讲的题目是"c++程序设计的科学", 讲得很理论化, 要点是存在一些c++的基本元素所必须遵循的, 有关基本操作的原则. 我举了一些例子, 比如构造函数, 赋值操作, 相等操作. 作为一种语言, c++没有什么限制. 你可以用operator==()来做乘法. 但是相等操作就应该是相等操作. 它要有自反性, a == a; 它要有对称性, a == b 则 b == a; 它还要有传递性. 作为一个数学公理, 相等操作对于其他操作是基本的要素. 构造函数和相等操作之间的联系就有公理性的东西在里边. 你用拷贝构造函数生成了一个新对象, 那么这个对象和原来那个就应该是相等的. c++是没有做强行要求, 但是这是我们都必须遵守这个规则. 同样的, 赋值操作也必须产生相等的对象. 我展示了一些基本操作的"公理", 还讲了一点迭代子(iterator), 以及一些通用算法怎样利用迭代子来工作. 我觉得那是一个两小时的枯燥演讲, 但却非常受欢迎. 不过我那时并没有想把这个东西塞在标准里, 它毕竟是太过先进的编程技术, 大概还不适于出现在现实世界里, 恐怕那些做实际工作的人对它没什么兴趣.

我是在9月做这个演讲的, 直到次年(1994)月, 我都没往ansi标准上动过什么脑筋. 1月6日, 我收到andy koenig的一封信(他那时是标准文档项目编辑), 信中说如果我希望stl成为标准库的一部分, 可以在1月25日之前提交一份建议到委员会. 我的答复是:"andy, 你发疯了吗?", 他答复道:"不错, 是的我发疯了, 为什么咱们不疯一次试试看?"

当时我们有很多代码, 但是没有文档, 更没有正式的建议书. 李小姐和我每星期工作80小时, 终于在期限之前写出一份正式的建议书. 当是时也, 只有andy一个人知道可能会发生些什么. 他是唯一的支持者, 在那段日子里他确实提供了很多帮助. 我们把建议寄出去了, 然后就是等待. 在写建议的过程中我们做了很多事. 当你把一个东西写下来, 特别是想到你写的可能会成为标准, 你就会发现设计中的所有纰漏. 寄出标准后,我们不得不一段一段重写了库中间的代码, 以及几百个组件, 一直到3月份圣迭戈会议之前. 然后我们又重新修订了建议书, 因为在重新写代码的过程中, 我们又发现建议书中间的很多瑕疵.

q: 您能描述一下当时委员会里的争论吗? 建议一开始是被支持呢, 还是反对?
a: 我当时无法预料会发生些什么. 我做了一个报告, 反响很好. 但当时有许多反对意见. 主要的意见是:这是一份庞大的建议, 而且来得太晚, 前一次会议上已经做出决议, 不在接受任何大的建议. 而这个东西是有史以来最大的建议, 包括了一大堆新玩艺. 投票的结果很有趣, 压倒多数的意见认为应对建议进行再考虑, 并把投票推迟到下次会议, 就是后来众所周知的滑铁卢会议.

bjarne stroustrup成了stl的强有力支持者. 很多人都通过建议、更改和修订的方式给予了帮助。bjarne干脆跑到这来跟我们一起工作了一个礼拜。andy更是无时无刻的帮助我们。c++是一种复杂的语言，不是总能搞得清楚确切的含义的。差不多每天我都要问andy和bjarne c++能不能干这干那。我得把特殊的荣誉归于andy， 是他提出把stl作为c++标准库的一部分；而bjarne也成了委员会中stl的主要鼓吹者。其他要感谢的人还有：mike vilot，标准库小组的负责人； rogue wave公司的nathan myers(rogue wave是boland c++builder中stl方案的提供商 —— 译者)，andersen咨询公司的larry podmolik。确实有好多人要致谢。

在圣迭戈提出的stl实际与当时的c++，我们被要求用新的ansi/iso c++语言特性重写stl，这些特性中有一些是尚未实现的。为了正确使用这些新的、未实现的c++特性，bjarne和andy花了无以计数的时间来帮助我们。

人们希望容器独立于内存模式，这有点过分，因为语言本身并没有包括内存模式。所以我们得要想出一些机制来抽象内存模式。在stl的早期版本里，假定容器的容积可以用size_t类型来表示，迭代子之间的距离可以用ptrdiff_t来表示。现在我们被告知，你为什么不抽象的定义这些类型？这个要求比较高，连语言本身都没有抽象定义这些类型，而且c/c++数组还不能被这些类型定义所限定。我们发明了一个机制称作"allocator"，封装了内存模式的信息。这个机制深刻地影响了库中间的每一个组件。你可能疑惑：内存模式和算法或者容器类接口有什么关系？如果你使用size_t这样的东西，你就无法使用 t* 对象，因为存在不同的指针类型(t*, t huge *, 等等)。这样你就不能使用引用，因为内存模式不同的话，会产成不同的引用类型。这样就会导致标准库产生庞大的分支。

另外一件重要的事情是我们原先的关联类型数据结构被扩展了。这比较容易一些，但是最为标准的东西总是很困难的，因为我们做的东西人们要使用很多年。从容器的观点看，stl做了十分清楚的二分法设计。所有的容器类被分成两种：顺序的和关联的，就好像常规的内存和按内容寻址的内存一般。这些容器的语义十分清楚。

当我到滑铁卢以后，bjarne用了不少时间来安慰我不要太在意成败与否，因为虽然看上去似乎不会成功，但是我们毕竟做到了最好。我们试过了，所以应该坦然面对。成功的期望很低。我们估计大部分的意见将是反对。但是事实上，确实有一些反对意见，但不占上风。滑铁卢投票的结果让人大跌眼镜，80%赞成，20%反对。所有人都预期会有一场恶战，一场大论战。结果是确实有争论，但投票是压倒性的。

q: stl对于1994年2月发行的ansi/iso c++工作文件中的类库有何影响？
a: stl被放进了滑铁卢会议的工作文件里。stl文档被分解成若干部分，放在了文件的不同部分中。mike 
vilot负责此事。我并没有过多地参与编辑工作，甚至也不是c++委员会的成员。不过每次有关stl的
建议都由我来考虑。委员会考虑还是满周到的。

q: 委员会后来又做了一些有关模板机制的改动，哪些影响到了stl？
a: 在stl被接受之前，有两个变化影响到了我们修订stl。其一是模板类增加了包含模板函数的能力。stl广泛地使用了这个特性来允许你建立各种容纳容器的容器。一个单独的构造函数就能让你建立一个能容纳list或其他容器的vector。还有一个模板构造函数，从迭代子构造容器对象，你可以用一对迭代子当作参数传给它，这对迭代子之间的元素都会被用来构造新的容器类对象。另一个stl用到的新特性是把模板自身当作模板参数传给模板类。这项技术被用在刚刚提到的allocator中。

q: 那么stl影响了模板机制吗？
a: 在弗基山谷的会议中，bjarne建议给模板增加一个“局部特殊化”(partial specialization)的特性。这个特性可以让很多算法和类效率更高，但也会带来代码体积上的问题。我跟bjarne在这个建议上共同研究了一段时间，这个建议就是为了使stl更高效而提出的。我们来解释一下什么是“局部特殊化”。你现在有一个模板函数 swap( t&, t& )，用来交换两个参数。但是当t是某些特殊的类型参数时，你想做一些特殊的事情。例如对于swap( int&, int& )，你想用一种特别的操作来交换数据。这一点在没有局部特殊化机制的情况下是不可能的。有了局部特殊化机制，你可以声明一个模板函数如下：

template <class t> void swap( vector<t>&, vector<t>& );

这种形式给vector容器类的swap操作提供了一种特别的办法。从性能的角度讲，这是非常重要的。如果你用通用的形式去交换vector，会使用三个赋值操作，vector被复制三次，时间复杂度是线性的。然而，如果我们有一个局部特殊化的swap版本专门用来交换两个vector，你可以得到一个时间复杂度为常数的，非常快的操作，只要移动vector头部的两个指针就ok。这能让vector上的sort算法运行得更快。没有局部特殊化，让某一种特殊的vector，例如vector<int>运行得更快的唯一办法是让程序员自己定一个特殊的swap函数，这行得通，但是加重了程序员的负担。在大部分情况下，局部特殊化机制能够让算法在某些通用类上表现得更高效。你有最通用的swap，不那么通用的swap，更不通用的swap，完全特殊的swap这么一系列重载的swap，然后你使用局部特殊化，编译器会自动找到最接近的那个swap。另一个例子copy。现在我们的copy就是通过迭代子一个一个地拷贝。使用模板特殊化可以定义一个模板函数：

template <class t> t** copy( t**, t**, t** );

这可以用memcpy高效地拷贝一系列指针来实现，因为是指针拷贝，我们可以不必担心构造对象和析构对象的开销。这个模板函数可以定义一次，然后供整个库使用，而且用户不必操心。我们使用局部特殊化处理了一些算法。这是个重要的改进，据我所知在弗基山谷会议上得到了好评，将来会成为标准的一部分。(后来的确成了标准的一部分 —— 译者）

q: 除了标准类库外，stl对那一类的应用程序来说最有用处？
a: 我希望stl能够引导大家学习一种新的编程风格：通用编程。我相信这种风格适用于任何种类的应用程序。这种风格就是：用最通用的方式来写算法和数据结构。这些结构所要求的语义特性应该能够被清楚地归类和分类，而这些归类分类的原则应该是任何对象都能满足的。理解和发展这种技术还要很长时间，stl不过是这个过程的起点。

我们最终会对通用的组件有一个标准的分类，这些组件具有精心定义的接口和复杂度。程序员们将不必在微观层次上编程。你再也不用去写一个二分查找算法。就是在现在，stl也已经提供了好几个通用的二分查找算法，凡是能用二分查找算法的场合，都可以使用这些算法。算法所要求的前提条件很少：你只要在代码里使用它。我希望所有的组件都能有这么一天。我们会有一个标准的分类，人们不用再重复这些工作。

这就是douglas mcilroy的梦想，他在1969年关于“构件工厂”的那篇著名文章中所提出来的东西。stl就是这种“构件工厂”的一个范例。当然，还需要有主流的力量介入这种技术的发展之中，光靠研究机构不行，工业界应该想程序员提供组件和工具，帮助他们找到所需的组件，把组件粘合到一起，然后确定复杂度是否达到预期。

q: stl没有实现一个持久化(persistent)对象容器模型。map和multimap似乎是比较好的候选者，它们可以把对象按索引存入持久对象数据库。您在此方向上做了什么工作吗，或者对这类实现有何评论？
a：很多人都注意到这个问题。stl没实现持久化是有理由的。stl在当时已经是能被接受的最巨大的库了。再大一点的话，我认为委员会肯定不会接受。当然持久化是确实是一些人提出的问题。在设计stl，特别是设计allocator时，bjarne认为这个封装了内存模式的组件可以用来封装持久性内存模式。bjarne的洞察秋毫非常的重要和有趣，好几个对象数据库公司正在盯着这项技术。1994年10月我参加了object database management group的一个会议，我做了一个关于演说。他们非常感兴趣，想让他们正在形成中的组件库的接口与stl一致，但不包括allocator在内。不过该集团的某些成员仔细分析了allocator是否能够被用来实现持久化。我希望与stl接口一致的组件对象持久化方案能在接下来的一年里出现。

q：set，multiset，map和multimap是用红黑树实现的，您试过用其他的结构，比如b*树来实现吗？
a：我不认为b*适用于内存中的数据结构，不过当然这件事还是应该去做的。应该对许多其他的数据结构，比如跳表(skip list)、伸展树(splay tree)、半平衡树(half-balanced tree)等，也实现stl容器的标准接口。应该做这样的研究工作，因为stl提供了一个很好的框架，可以用来比较这些结构的性能。结口是固定的，基本的复杂度是固定的，现在我们就可一个对各种数据结构进行很有意义的比较了。在数据结构领域里有很多人用各种各样的接口来实现不同的数据结构，我希望他们能用stl框架来把这些数据结构变成通用的。
（译者注：上面所提到的各种数据结构我以为大多并非急需，而一个stl没有提供而又是真正重要的数据结构是哈希结构。后来在stepanov和matt austern等人的sgi*stl中增补了hashset，hashmap和hashtable三种容器，使得这个stl实现才比较完满。众所周知，红黑树的时间复杂度为o(logn), 而理想hash结构为o(1)。当然，如果实现了持久化，b+树也是必须的。）

q：有没有编译器厂商跟您一起工作来把stl集成到他们的产品中去？