泛型算法(ｇｅｎｅｒｉｃｉｔｙａｌｇｏｒｉｔｈｍ)是一种以对它所作用数据结构进行尽可能少的假设方式来表达的算法.当然,模板使得某种程度上的泛型更加容易,它可以处理不同数据类型为参数的函数;但是关于泛型还有很多事情可做,例如已知存在一些搜索算法,不论搜索对象是存储在数组中,还是存储在其他的数据结构,比如说链表中,都可以非常高效的运行.如果有可能编写某一个程序表述这种算法并且能够同时适用于五种基本数据结构(集合、序列、包、树、图),还能获得很高的运行效率,那将很有意义.
以下将使用一个基于简单问题的例子,然后在泛型思维的指导下一步步扩展,使它能够运用于越来越复杂的情况,最后能够解决上面的问题.先展示这个例子,它的功能是在给定整数数组ａｒｒａｙ中找到第一个等于某个既定值ｘ的元素所在位置.规约如下:
Ｑ:给定数组ａｒｒａｙ[0..ｎ]∧ｎ〉=0
Ｒ:(0<=ｉ<ｎ∧ｘ=ａｒｒａｙ[ｉ])∨(ｉ=ｎ∧ｘ～∈ａｒｒａｙ[0..ｎ-1])
程序如下:
ｉｎｔ ｆｉｎｄ1(ｉｎｔ ａｒｒａｙ,ｉｎｔｎ,ｉｎｔｘ)
{
ｉｎｔ ｐ=ａｒｒａｙ;
ｆｏｒ(ｉｎｔｉ=0;ｉ<ｎ;ｉ++)
{
ｉｆ( ｐ==ｘ)
ｒｅｔｕｒｎｐ;
++ｐ;
}
ｒｅｔｕｒｎｐ;
}
关于ｆｉｎｄ1使用的数据结构,我们必须知道哪些情况呢?(1)正在查找某个类型为ｉｎｔ的值;(2)正在一个ｉｎｔ对象数组中进行查找;(3)已经预先知道了数组中元素的数目;(4)知道第一个元素的地址所有这些必须知道的情况都降低了算法的实用性.在下面的例子中,我们将通过尽可能的去除假设条件来提高这个算法的通用性.可以通过使用函数模板,逐步泛型化元素类型、推迟记数、地址独立性,得到下面的程序:ｔｅｍｐｌａｔｅ<ｃｌａｓｓＰ,ｃｌａｓｓＴ>
Ｐ ｆｉｎｄ4(Ｐ ｓｔａｒｔ,Ｐ ｂｅｙｏｎｄ,Ｔ＆ｘ)
{
ｗｈｉｌｅ(ｓｔａｒｔ!=ｂｅｙｏｎｄ＆＆ ｓｔａｒｔ!=ｘ)
++ｓｔａｒｔ;
ｒｅｔｕｒｎｓｔａｒｔ;
}
1 迭代算子的引入-泛型化数据结构到目前为止,我们使用一个通用的算法ｆｉｎｄ4,它能够基于数组、链表进行查找操作.但是,注意到通用的算法ｆｉｎｄ4,如果要在链表中运行还必须在定义链表结构Ｎｏｄｅ后再定义Ｎｏｄｅｐ,Ｎｏｄｅｐ其本质是能够访问链表中的每一个元素.如果再进一步,ｆｉｎｄ4要运行于文件中甚至是树或图中呢?可见,ｆｉｎｄ4还不是很抽象.如果我们要得到一个统一的算法,它不但能够基于数组、链表还能够基于其他基本数据结构进行查找操作,则必须为每一种基本数据结构设计出能访问数据结构中每一个元素的单独模块,现在我们的问题是要抽象出这个单独模块的本质.如果问题得到解决,我们将可以构建出基于5种基本数据结构上所有常用算法的可重用部件的宏伟蓝图.如果不解决这个问题,其本质是数据结构和算法将不能独立的发展,最后无间隙的连接在一起,这将严重阻碍算法泛化于各种数据结构.那么,解决这个问题前途究竟在那里?由什么来充当数据结构和算法之间的粘和剂是解决这一问题的关键,循环中计数问题是解决这一问题的突破口.例如就上文列举的对一个数组或者是链表进行查找的算法,对数组循环中计数是ｉ+1,而对链表是ｐ->ｎｅｘｔ,我们要抽象出其共同点,Ｃ/Ｃ++中指针可以实现这一点,它可以得到每一种数据类型的内存大小,从而进行推导计数.正是受到这个启发,ＡｌｅｘａｎｄｅｒＳｔｅｐａｎｏｖ(ＳＴＬ的创造者)意识到允许程序员利用指针,以非常弹性的方式处理内存,而这正是又要一般化(泛型)又要不失效率的一个重要关键.Ａｌｅｘａｎｄｅｒ在数据结构和算法之间引入迭代算子(Ｉｔｅｒ ａｔｏｒ),解决了这一问题.其实,薛锦云为基于有效的实现循环控制抽象和循环计算抽象这一目的,曾给出过迭代算子一种新的统一定义,定义迭代算子是为访问组合数据类型对象中的所有元素而设置的一种抽象数据类型(ＡＤＴ)[1].
2 ＳＴＬ的产生背景、基本框架及一个实例
2.1 ＳＴＬ的产生背景让我们先说明ＳＴＬ的产生背景,这将有助于我们深刻理解迭代算子对ＳＴＬ的产生所起的作用.第一个支持泛型概念的语言是Ａｄａ,ＡｌｅｘａｎｄｅｒＳｔｅｐａｎｏｖ和Ｍｕｓｓｅｒ曾于1987开发出一套相关的Ａｄａｌｉｂｒａｒｙ,然而Ａｄａ在美国国防工业以外并未被广泛接受,Ｃ++却如星火燎原般地在程序设计领域中攻城略地.当时的Ｃ++尚未引入ｔｅｍｐｌａｔｅ机制,但是Ａｌｅｘａｎｄｅｒ已经了解到,Ｃ/Ｃ++允许程序员经由指针、以非常弹性的方式处理内存,而这正是又要一般化(泛型)又要不失效率的一个重要关键.Ａｌｅｘａｎｄｅｒ认为,最重要的是,必须研究并实验出一个“立基于泛型程序设计之上的ｃｏｍｐｏｎｅｎｔｌｉｂｒａｒｙ的完整架构”.Ａｌｅｘ在ＡＴ＆Ｔ实验室及Ｈｅｗｌｅｔｔ-ＰａｃｋａｒｄＰａｌｏＡｌｔｏ实验室,分别实验许多种架构和算法公式,先以Ｃ而后以Ｃ++完成.Ｂｅｌｌ实验室的ＡｎｄｒｅｗＫｏｅｎｉｇ于1993年知道这个研究计划后,邀请Ａｌｅｘ于是年11月的ＡＮＳＩ/ＩＳＯＣ++标准委员会会议上展示其观念.获得热烈的回应.Ａｌｅｘ于是再接再励于次年夏天在Ｗａｔｅｒｌｏｏ举行的会议前完成其正式的提案,并以压倒性多数,一举让这个巨大的计划成为Ｃ++Ｓｔａｎｄａｒｄ的一部份,即ＳＴＬ.
2.2 ＳＴＬ的基本框架ＳＴＬ最重要的价值,是在泛型思维模式(ＧｅｎｅｒｉｃＰａｒａｄｉｇｍ)下建立起一个系统化的、条理分明的“软件组件分类学”,其核心是建立基本数据结构和基本算法的标准界面,而在此之前,标准化尚未建立.ＳＴＬ有6大组件(ｃｏｍｐｏｎｅｎｔｓ):
(1)ｃｏｎｔａｉｎｅｒｓ:泛型容器,各种基本数据结构如ｖｅｃｔｏｒ,ｌｉｓｔ,ｄｅｑｕｅ,ｓｅｔ,ｍａｐ…;
(2)ａｌｇｏｒｉｔｈｍｓ:泛型算法,各种基本算法如ｓｏｒｔ,ｓｅａｒｃｈ,ｃｏｐｙ,ｅｒａｓｅ…,ＳＴＬ提供了70个;
(3)ｉｔｅｒａｔｏｒ:应用于ｃｏｎｔａｉｎｅｒｓ与ａｌｇｏｒｉｔｈｍｓ身上的所谓“泛型指针”,或称迭代算子(迭代器),扮演两者间的粘和剂.共有5种形态,还有各种衍生变化.ｉｔｅｒａｔｏｒ是ＳＴＬ中最重要最抽象的一个组件,它使ｃｏｎｔａｉｎｅｒｓ和ａｌｇｏｒｉｔｈｍｓ可以各自独立发展,互不干连;
(4)ｆｕｎｃｔｉｏｎｏｂｊｅｃｔ:每个ｏｂｊｅｃｔ都是一个ｃｌａｓｓｔｅｍｐｌａｔｅ.Ｃ/Ｃ++的函数指针,可以指向不同的函数,被用来做为一个ｆｕｎｃｔｉｏｎｏｂｊｅｃｔ.ＳＴＬ提供有15个现成的ｆｕｎｃｔｉｏｎｏｂｊｅｃｔｓ;
(5)ａｄａｐｔｏｒ:可改变(修饰)ｃｏｎｔａｉｎｅｒｓ或ｆｕｎｃｔｉｏｎｏｂｊｅｃｔ接口的一种组件.例如ＳＴＬ提供的ｑｕｅｕｅ和ｓｔａｃｋ,虽然看似泛型容器,但它其实只是一种ｃｏｎｔａｉｎｅｒａｄａｐｔｏｒ.这里和薛锦云提出的基于部分实现理论的可重用部件模式不谋而和;(6)ａｌｌｏｃａｔｏｒ:内存配置系统.ＳＴＬ提供有现成的ａｌｌｏｃａｔｏｒ.三者之间的关系:泛型指针充当泛型容器和泛型算法之间的粘和剂,它使得泛型容器和泛型算法可以独立的发展,最后无间隙的连接在一起.在实现技术上,注意到泛型指针在不同的泛型容器上有不同的实现方式,很自然地我们应该在泛型容器上添加其相应的泛型指针.我们都知道泛型指针应该遍历循环中的每一个元素,这个类的对象显然应该能够描述迭代过程的状态,所以相关的操作有:
(1)一个构造函数,用来创建要处理的对象,同时得到序列的首元素索引;
(2)一种请求序列中的下一个元素的方法;
(3)一种告知遍历何时完成的方法;
(4)一个赋值操作符,使这些对象可以被当作值来使用.这就是迭代算子(或称迭代器)工作方式的基本概括,即其抽象实现,其本质是一个ＩｔｅｒａｔｏｒＡＤＴ.如果要在程序中实现迭代算子,必须将其针对不同数据结构具体化.
2.3 实例下面我们将举一实例,将迭代算子分别引入数组、链表和文件ＡＤＴ中.以后我们就可以将所有基于数组、链表和文件的算法(不管是已有的还是未知的)运用到数组、链表和文件中,而不需要再对数组、链表和文件ＡＤＴ进行任何修改,这才是真正的目标.第一步,先定义好数组、链表、ｉｓｔｒｅａｍ(文件流)类的ＡＤＴ,为了使其能够作用于不同的元素类型,数组、链表、ｉｓｔｒｅａｍ(文件流)类可以设计成ｃｌａｓｓｔｅｍｐｌｅｔｅ.第二步,分别设计基于数组、链表、ｉｓｔｒｅａｍ(文件流)类的迭代器(描述略),这样以后我们不再需要依据不同算法而为数组、链表、ｉｓｔｒｅａｍ(文件流)类重新设计迭代器.第三步:根据迭代器改写ｆｉｎｄ4,改写后的程序命名为ｆｉｎｄ5Ｔｅｍｐｌａｔｅ〈ｃｌａｓｓＴ〉Ｔｆｉｎｄ5(Ｉｔｅｒａｔｏｒ〈Ｔ〉＆ｉｒ,Ｔ＆ｘ){ｗｈｉｌｅ(ｉｒ.ｖａｌｉｄ()＆＆ ｉｒ!=ｘ) ｉｒ.ｎｅｘｔ(); ｒｅｔｕｒｎｉｒ;}第四步:实证ｄｏｕｂｌｅａｒｒａｙ[ｎ];ｆｉｎｄ5(Ｉｔｅｒａｔｏｒ＿ａｒｒａｙ(ａｒｒａｙ,ｎ-1),ｘ) / 在实型数组中查找元素ｘ /Ｎｏｄｅｐ;ｆｉｎｄ5(Ｉｔｅｒａｔｏｒ＿ｌｉｎｋ(ｐ),ｘ) / 在字符串链表中查找元素ｘ /ｉｓｔｒｅａｍｃｉｎ;ｆｉｎｄ5〈Ｒｅａｄｅｒ(ｃｉｎ),ｘ) / 在ｉｓｔｒｅａｍ(文件流)中查找元素ｘ /如果我们再为树、图定义相应的迭代算子Ｉｔｅｒａｔｏｒ＿ｔｒｅｅ、Ｉｔｅｒａｔｏｒ＿ｇｒａｐｈ,查找算法ｆｉｎｄ5可以推广运用到树、图中.而且,算法ｆｉｎｄ5产生过程大部分是在编译期间,这只会损耗编译时间,丝毫不会影响程序的运行效率,即算法Ｆｉｎｄ5还能获得很高的运行效率,这样已经完成了我们最早提出的目标.综上所述,可以构建整个标准模板库,就象Ｃ构建标准函数库,Ｃ++构建标准类库,ＶＣ++构建ＭＦＣ一样.如果说,标准函数库是过程式思维下的产物,标准类库是面向对象思维下的产物,则可以说模板是泛型思维下的一个雏形作品,标准模板库是泛型思维下的一个完美典范作品,它的抽象程度最高。
[ 此贴被handsoft在2005-09-13 11:33重新编辑 ]
