泛型编程、STL的概念、STL模板思想及其六大组件的关系,以及泛型编程(GP)、STL、面向对象编程(OOP)、C++之间的关系

时间:2021-05-10 16:14:24

2013-08-11 10:46:39

介绍STL模板的书,有两本比较经典:

一本是《Generic Programming and the STL》,中文翻译为《泛型编程与STL》,这本书由STL开发者 Matthew H.Austern编著,由STL之父alexander Stepanov等大师审核的,介绍STL思想及其使用技巧,适合初学者使用,中文版是由侯捷翻译的;

另一本书是《STL源码剖析》,是《深入浅出MFC》的作者侯捷编写的,介绍STL源代码的实现,适合深入学习STL,不适合初学者;

另外,STL之父访谈录,对STL创始人Alexander Stepanov的采访, 这份访谈纪录是迄今为止对于STL发展历史的最完备介绍。

下面主要介绍泛型编程、STL的概念、STL模板思想及其六大组件的关系,以及泛型编程(GP)、STL、面向对象编程(OOP)、C++之间的关系。

泛型编程(GP-Generic Programming)思想

  泛型编程与C++ templates和STL不该混为一谈,模板是泛型编程的基础,而STL是泛型编程思想的实现。

  在《泛型编程与STL模板》的中文版译序中,指出STL是泛型编程的第一份重要实现品。可以这样理解,STL是泛型编程思想的产物,是以泛型编程为指导而产生的。因此,在介绍STL之前,先了解泛型编程的思想是必要的。

  暂时没有找到泛型编程的权威定义,即使在《Generic Programming and the STL》一书中,下面是在上面列出的三本参考书中搜集懂啊的关于泛型编程的一些概念。

  《泛型编程与STL》的前言中指出,泛型编程和模型对象编程不同,它并不要求你通过额外的间接层来调用函数;它让你撰写完全一般化并可重复运用的算法,其效率和“针对特定数据型别而设计”的算法旗鼓相当。

  泛型编程抽离(抽象化)于特定型别和特定数据结构之外,使得以接受尽可能一般化的引数型别。这意味着一个泛型算法实际上具有两部分:(1)用来描述算法步骤的实际指令;(2)正确指定“其引数型别必须满足之性质”的一组需求条件。

  所谓泛型,具有“在多种数据型别上可操作”的含义。

  在“STL之父访谈录”中,根据STL之父关于泛型编程的回答,可以这样看待泛型编程:

泛型编程是不依赖于数据结构的特定实现,而只是依赖于该结构的几个基本的语义属性,将算法用这种方法从特定实现中抽象出来, 而且效率无损(也就是对于不同的数据类型效率旗鼓相当)的编程方法。

  在《C++ Primer》第16章中,泛型编程的定义为:所谓的泛型编程就是以独立于任何特定类型的方式编写代码。使用泛型程序时,我们需要提供具体程序实例所操作的类型或值。模板是泛型编程的基础。

  泛型编程与面向对象编程(OOP)一样,都依赖于某种形式的多态性(面向对象编程所依赖的多态性称为运行时多态性,泛型编程所依赖的多态性称为运行时多态性或参数式多态性)。面向对象编程中的多态性在运行时应用于存在继承关系的类。(摘自《C++ Primer》第16章)

STL(Standard Template Library)思想

引入STL的原因

  STL的设计目是复用性的提升,复用性必须建立在某种标准之上-不论是语言层次的标准,或数据交换的标准,或通讯协议的标准。但是,在许多工作环境下,就连软件开发最基本的数据结构和算法都还迟迟未能有一套标准,大量程序员*从事大量重复工作,竟是为了完成前人早已完成而自己手上并未拥有的程序代码,这不仅是人力资源的浪费,也是挫折与错误的来源。

  为了建立数据结构与算法的一套标准,并且降低器件的耦合性(coupling)关系以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),C++社群里诞生了STL。

STL概念

  C++ STL(Standard Template Library)可以让你重复运用既有的算法,而不必在环境类似的情况下一再重新撰写相同代码。STL算法是泛型的,不与任何特定数据结构或对象型别束缚在一起,但是却像为你量身定做一样,有很高的效率。STL甚至是可库充的,是的,就像STL组件彼此之间可以相互配合运用一样,STL组件亦可以和你所写的组件永久水乳交融地搭配运用。(-摘自《泛型编程与STL》第一章 STL巡礼)

STL与C++的关系

  如C++之父访谈录中提到的,C++继承机制不大用在泛型编程中, C++的继承机制及与之相关的编程风格有着戏剧性的局限. 用这种方式进行通用编程, 连等于判断这类的小问题都解决不了。而模板才是泛型编程的基础。

  第一个实验性质的泛型程序库并非易C++写成,而是以Ada和Scheme完成。(摘自《泛型编程与STL模板》前言)最终的载体还是语言,没有语言没法编程。STL使用C++,你也可以用Ada 来实现,用其他的语言来实现也行,结果会有所不同,但基本的东西是一样的。当前,C++是GP的最佳载体。我试过其他的语言,最后还是C++最理想地达成了抽象和高效的统一。

  下面摘自网络文档《C++标准模板库STL_VC开发》:

  一般而言,STL作为一个泛型化的数据结构和算法库,并不牵涉具体语言(当然,在C++里,它被称为STL)。也就是说,如果条件允许,用其他语言也可以实现之。这里所说的条件,主要是指类似于"模板"这样的语法机制。如果你没有略过前一节内容的话,应该可以看到,Alexander Stepanov在选择C++语言作为实现工具之前,早以采用过多种程序设计语言。但是,为什么最终还是C++幸运的承担了这个历史性任务呢?原因不仅在于前述那个条件,还在于C++在某些方面所表现出来的优越特性,比如:高效而灵活的指针。但是如果把C++作为一种OOP(Object-Oriented Programming,面向对象程序设计)语言来看待的话(事实上我们一般都是这么认为的,不是吗?),其功能强大的继承机制却没有给STL的实现帮上多大的忙。在STL的源代码里,并没有太多太复杂的继承关系。继承的思想,甚而面向对象的思想,还不足以实现类似STL这样的泛型库。C++只有在引入了"模板"之后,才直接导致了STL的诞生。这也正是为什么,用其他比C++更纯的面向对象语言无法实现泛型思想的一个重要原因。当然,事情总是在变化之中,像Java在这方面,就是一个很好的例子,JDK1.4中已经加入了泛型的特性。

  此外,STL对于C++的发展,尤其是模板机制,也起到了促进作用。比如:模板函数的偏特化(template function partial specialization),它被用于在特定应用场合,为一般模板函数提供一系列特殊化版本。这一特性是继STL被ANSI/ISO C++标准委员会通过之后,在Bjarne和Stepanov共同商讨之下并由Bjarne向委员会提出建议的,最终该项建议被通过。这使得STL中的一些算法在处理特殊情形时可以选择非一般化的方式,从而保证了执行的效率。

STL与C++标准库函数的关系

STL是最新的C++标准函数库中的一个子集,这个庞大的子集占据了整个库的大约80%的分量。而作为在实现STL过程中扮演关键角色的模板则充斥了几乎整个C++标准函数库。

STL与OOP的关系

  一句话,通用编程是OOP基本思想的自然延续。什么是OOP的基本思想呢?把组件的实现和接口分开,并 且让组件具有多态性。不过,两者还是有根本的不同。OOP强调在程序构造中语言要素的语法。你必须 得继承,使用类,使用对象,对象传递消息。GP不关心你继承或是不继承,它的开端是分析产品的分类, 有些什么种类,他们的行为如何。GP的基本观点是把抽象的软件组件和它们的行为用标准的分类学分类,出发点就是要建造真实的、高效的和不取决于 语言的算法和数据结构;而OOP所强调的(我认为是过分强调的)是清楚的定义类之间的层次关系。OOP告诉了你如何建立层次关系,却没有告诉你这些关系的实质。(-摘自“C++之父访谈录”)

STL与GP的关系

如前所述,STL是泛型编程思想的产物,是以泛型编程为指导而产生的。

STL六大组件的关系

下面摘自《STL源码剖析》1.2节。

STL提供六大组件,彼此可以组合套用:

1、容器(Containers):各种数据结构,如Vector,List,Deque,Set,Map,用来存放数据.从实现的角度来看,STL容器是一各class template,就体积而言,这一部分很像冰山载海面的比率。
2、算法(Algorithms):各种常用算法如Sort,Search,Copy,Erase。从实现的角度来看,STL算法是一种Function Templates。
3、迭代器(Iterators):扮演容器与算法之间的胶合剂,是所谓的“泛型指针”,共有五种类型,以及其它衍生变化,从实现的角度来看,迭代器是一种将:Operators*,Operator->,Operator++,Operator--等相关操作予以重载的Class Template。所有STL容器都附带有自己专属的迭代器——是的,只有容器设计者才知道如何遍历自己的元素,原生指针(Native pointer)也是一迭代器。
4、仿函数(Functors): 行为类似函数,可作为算法的某种策略(Policy),从实现的角度来看,仿函数是一种重载了Operator()的Class 或 Class Template。一般函数指针可视为狭义的仿函数。
5、配接器(Adapters):一种用来修饰容器(Containers)或仿函数(Functors)或迭代器(Iterators)接口的东西,例如:STL提供的Queue和Stack,虽然看似容器,其实只能算是一种容器配接器,因为 它们的底部完全借助Deque,所有操作有底层的Deque供应。改变Functor接口者,称为Function Adapter;改变Container接口者,称为Container Adapter;改变Iterator接口者,称为Iterator Adapter。配接器的实现技术很难一言蔽之,必须逐一分析。
6、配置器(Allocators):负责空间配置与管理,从实现的角度来看,配置器是一个实现了动态空间配置、空间管理、空间释放的Class Template。
 

这六大组件的交互关系:container(容器) 通过 allocator(配置器) 取得数据储存空间,algorithm(算法)通过 iterator(迭代器)存取 container(容器) 内容,functor(仿函数) 可以协助 algorithm(算法) 完成不同的策略变化,adapter(配接器) 可以修饰或套接 functor(仿函数)。如下图:

泛型编程、STL的概念、STL模板思想及其六大组件的关系,以及泛型编程(GP)、STL、面向对象编程(OOP)、C++之间的关系