stl之父访谈录.txt

学习STL编程非常好的教程

   论化, 要点是存在一些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*树来实现吗？