1 ＳＴＬ的发展20世纪80年代初美国ＢＥＬＬ实验室的ＢｊａｒｎｅＳｔｒｏｕｓｔｒｕｐ开发出世界第1个Ｃ++语言编译器。Ｃ++的成功在于以Ｃ为基础来改造Ｃ:通过引入面向对象技术,又始终保持在Ｃ所定义的机器模型框架内,从而大大扩展了内存中对象的范畴,把Ｃ的机器模型扩展为真正类型系统。ＳＴＬ是ＳｔａｎｄａｒｄＴｅｍｐｌａｔｅＬｉｂｒａｒｙ(标准模板库)的简称,是由ＡｌｅｘａｎｄｅｒＳｔｅｐａｎｏｖ、ＭｅｎｇＬｅｅ和ＤａｖｉｄＲＭｕｓｓｅｒ在惠普实验室工作时所开发出来的Ｃ++通用库。其目的是标准化组件,利用自带的模板,提高程序开发效率和质量。熟悉了Ｃ++ＳＴＬ编程思想后,很多用传统Ｃ++编写的代码,通过简单地调用一两个算法模板,就可以得到一些优雅而高效的代码。模板库相对于传统的函数库和类库来说,可以提供更好的代码重用。ＳＴＬ之父———ＡｌｅｘａｎｄｅｒＳｔｅｐａｎｏｖ开始考虑有关范型的问题是在20世纪70年代末期,当时他注意到有些算法并不依赖于数据结构的特定实现,而只是依赖于该结构的几个基本的语义属性。于是开始研究大量不同的算法,结果发现大部分算法可以用这种方法从特定实现中抽象出来,而且效率无损。在贝尔实验室对Ｃ++的算法库短暂地研究了一段时间后,ＡｌｅｘａｎｄｅｒＳｔｅｐａｎｏｖ于1988年去了位于Ｐａ ｌｏＡｌｔｏ的惠普实验室。作为1个验证性项目,其工作目的是搞清楚到底能不能在使算法尽可能通用化的前提下仍然具有很高的效率。结果发现,算法不仅最通用,而且能与手写的代码一样高效。这种面向高层次的程序设计风格通常被描述为数据抽象、面向对象程序设计和范型程序设计。ＳＴＬ的代码从广义上讲分为3类:ａｌｇｏｒｉｔｈｍ(算法)、ｃｏｎｔａｉｎｅｒ(容器)和ｉｔｅｒａｔｏｒ(迭代器),几乎所有的代码都采用了模板类和模板函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。1994年7月,美国国家标准研究所(ＡＮＳＩ)通过投票决定,将ＳＴＬ纳入Ｃ++标准。在被接纳的过程中,ＳＴＬ又被重新组织并在几个重要环节做了修改。比如原先的关联型数据结构被扩展了。在Ｃ++标准中,ＳＴＬ被组织为下面的13个头文件:<ａｌｇｏｒｉｔｈｍ>、<ｄｅｑｕｅ>、<ｆｕｎｃｔｉｏｎａｌ>、<ｉｔｅｒａｔｏｒ>、<ｖｅｃｔｏｒ>、<ｌｉｓｔ>、<ｍａｐ>、<ｍｅｍｏｒｙ>、<ｎｕｍｅｒｉｃ>、<ｑｕｅｕｅ>、<ｓｅｔ>、<ｓｔａｃｋ>和<ｕｔｉｌｉｔｙ>。
2 与ＭＦＣ的比较1993年,美国微软公司推出ＶｉｓｕａｌＣ++1.0,拉开了以面向对象方法设计Ｗｉｎｄｏｗｓ应用程序的序幕。其基础类库ＭＦＣ(ＭｉｃｒｏｓｏｆｔＦｏｕｎｄａｔｉｏｎＣｌａｓｓ)在当时来说是相当先进的。但Ｃ++之后发生了巨大的变化:1998年,Ｃ++标准正式通过,并且直到现在都保持了1种稳定的状态。ＳＴＬ虽然加入Ｃ++标准库的时间相对较晚,但它却是Ｃ++标准程序库中最具革命性的部分,同时也是Ｃ++标准程序库中最重要的组成部分。与标准Ｃ++相比,ＭＦＣ的体系结构和实现机制就显得落后了,甚至存在为适应ＭＦＣ而修改标准的地方。微软的编译器对ＭＦＣ完全支持,但对ＳＴＬ只是部分支持。ＭＦＣ主要存在以下缺点:消息映射的实现机制十分笨拙,没有采用继承机制,也没有采用委托机制;受Ｄｏｃ/Ｖｉｅｗ体系所限,想突破很难;对于底层的ＳＤＫ封装太薄,面向对象的感觉不足;自己编写的ＲＴＴＩ、Ｃｓｔｒｉｎｇ/ＣＯｂｊＸＸＸ(Ｃｏｎｔａｉｎｅｒ)实现得不太理想;大量使用宏,使代码的可读性很差。而ＳＴＬ通过把容器抽象为统一的接口,算法利用这个接口,通过迭代器来操纵容器。因为接口不变,所以实现的容器可以随意更改,这样就为调试和扩展提供了极大的便利。
3 Ｃ++ＳＴＬ技术3.1 容器作为ＳＴＬ的最主要组成部分———容器,分为向量(ｖｅｃｔｏｒ),队列(ｑｕｅｕｅ),双端队列(ｄｅｑｕｅ),表(ｌｉｓｔ),堆栈(ｓｔａｃｋ),集合(ｓｅｔ),多重集合(ｍｕｌｔｉｓｅｔ),映射(ｍａｐ)和多重映射(ｍｕｌｔｉｍａｐ)。在实际开发过程中,数据结构本身的重要性不会逊于操作于数据结构的算法的重要性。当程序中存在着对时间要求很高的部分时,数据结构的选择就显得更为重要。经典的数据结构数量有限,但是程序员常常重复着一些为了实现向量、链表等结构而编写的代码,这些代码都十分相似,只是为了适应不同数据的变化而在细节上有所出入。ＳＴＬ容器允许重用已有的数据结构来构造自定义的数据结构:通过设置一些模板类,ＳＴＬ容器对最常用的数据结构提供了支持,这些模板的参数允许指定容器中元素的数据类型,可以将以前许多重复而乏味的工作简化。容器部分主要由头文件<ｖｅｃｔｏｒ>,<ｌｉｓｔ>,<ｄｅｑｕｅ>,<ｓｅｔ>,<ｍａｐ>,<ｓｔａｃｋ>和<ｑｕｅｕｅ>组成。3.2 算法算法是经过严格的数学推导,经过相应的定理和公理的证明,不断千锤百炼得出的编程结晶。程序员都能取得的1个共识是对数据类型的选择对函数库的可重用性起着至关重要的作用。举例来说,1个求方根的函数,在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类型要高。而Ｃ++通过模板机制允许推迟对某些类型的选择,直到真正想使用模板或者说对模板进行实例化的时候,ＳＴＬ是在1个有效的框架中完成这些算法的———程序员可以将类型划分为少数的几类,然后就可以在模板的参数中使用1种类型替换掉同一种类中的其他类型。ＳＴＬ提供了大约100个实现算法的模板函数,都是经过长时间的实践检验,采用精炼的编程风格,同时兼顾编译效率和可读性,是ＳＴＬ技术的精华之一。比如算法ｆｏｒ＿ｅａｃｈ将为指定序列中的每一个元素调用指定的函数,ｓｔａｂｌｅ＿ｓｏｒｔ以你所指定的规则对序列进行稳定性排序等等。这样一来,只要熟悉了ＳＴＬ之后,许多代码可以被大大的化简,只需要通过调用一两个算法模板,就可以完成所需要的功能并大大地提升效率。算法部分主要由头文件<ａｌｇｏｒｉｔｈｍ>,<ｎｕｍｅｒｉｃ>和<ｆｕｎｃｔｉｏｎａｌ>组成。<ａｌｇｏｒｉｔｈｍ>是所有ＳＴＬ头文件中最大的1个,它是由一大堆模板函数组成的,可以认为每个函数在很大程度上都是独立的,其中常用到的功能涉及到比较、交换、查找、遍历、复制、修改、移除、反转、排序、合并等操作。<ｎｕｍｅｒｉｃ>体积很小,只包括几个在序列上面进行简单数学运算的模板函数,包括加法和乘法在序列上的一些操作。<ｆｕｎｃｔｉｏｎａｌ>中则定义了一些模板类,用以声明函数对象。使用算法的时候,要针对不同的容器选择合适的函数。比如对集合的查找,最好不要用通用函数ｆｉｎｄ(),而应采用集合自带的ｆｉｎｄ()函数,因为它针对集合进行了专门优化,性能更好。3.3 迭代器软件设计有1个基本方法,通过引进1个间接层来使问题得以简化,在ＳＴＬ中就是用迭代器来完成的。概括来说,迭代器在ＳＴＬ中用来将算法和容器联系起来,起着1种类似黏和剂的作用。几乎ＳＴＬ提供的所有算法都是通过迭代器存取元素序列进行工作的,每一个容器都定义了其本身所专有的迭代器,用以存取容器中的元素。迭代器部分主要由头文件<ｕｔｉｌｉｔｙ>,<ｉｔｅｒａｔｏｒ>和<ｍｅｍｏｒｙ>组成。<ｕｔｉｌｉｔｙ>是1个很小的头文件,它包括了贯穿使用在ＳＴＬ中的几个模板的声明,<ｉｔｅｒａｔｏｒ>中提供了迭代器使用的许多方法,而对于<ｍｅｍｏｒｙ>的描述则十分的困难,它以不同寻址方式为容器中的元素分配存储空间,同时也为某些算法执行期间产生的临时对象提供机制,<ｍｅｍｏｒｙ>中的主要部分是模板类ａｌｌｏｃａｔｏｒ,它负责产生所有容器中的默认分配器。
4 ＳＴＬ的应用ＳＴＬ的设计目标是将不同的算法和数据结构相结合,并获取最佳效率。由于ＳＴＬ以模板为基础,所以能用于任何数据类型和结构。对于ＳＴＬ的使用,存在着两种观点。第一种认为ＳＴＬ的最大作用在于可充当数据结构和算法的教学素材之用,因为它的源代码涉及了许多实现方面的技术问题。第二种则认为ＳＴＬ的初衷乃是为了简化设计,避免重复劳动,提高编程效率,因此应该是“应用至上”的,对于源代码则不必深究。我们认为分析源代码和应用并不矛盾,通过分析源代码也能提高我们对其应用的理解,当然根据具体的目的也可以有不同的侧重。ＳＴＬ的3个部分:算法、容器和迭代器是互相牵制或者说是紧密结合的。从概念上讲最基础的部分是迭代器,可是直接学习迭代器会遇到许多抽象枯燥而且繁琐的细节,然而不真正理解迭代器又无法进入另两部分的学习,至少对剖析源码来说是这样。可以说,适应ＳＴＬ处理问题的思路是需要花费一定的时间的,但是以此为代价,ＳＴＬ取得了1种十分可贵的独立性:它通过迭代器能在尽可能少地知道某种数据结构的情况下完成对这一结构的运算。所以ＳＴＬ运用的模式相对统一,只要适应了范型编程的思想,从一个工具转到另一个工具,都将不会有太大的困难。
5 ＳＴＬ技术是对原来Ｃ++技术的1种补充,相对于Ｃ++而言,它带来以下突出的优点:具有非常优秀的通用性,ＳＴＬ可以应用于任何数据结构和数据对象中,并且和传统的Ｃ++数据结构相兼容;具有无法比拟的高效性,数据结构简明,易于掌握,使用ＳＴＬ技术的程序效率得到明显提高;安全机制完善,内存管理非常优秀;跨平台和可移植性,任何想与ＡＮＳＩ兼容的编译器必须支持ＳＴＬ。ＶｉｓｕａｌＣ++是实践中较常使用的语言,ＭＦＣ支持继承等面向对象的关键技术,但没有提供很好的Ｉｔｅｒ ａｔｏｒ机制,我们可以通过继承ＳＴＬ的Ｉｔｅｒａｔｏｒ使得ＭＦＣ的迭代器技术得以应用,从而各取所长,使两种技术得到较好的统一。
[ 此贴被XChinux在2005-09-14 22:36重新编辑 ]
