代码重用是软件工程追求的重要目标,人们在工程实践和科学研究中积累了大量成熟的数据结构和优秀算法。早期结构化程序设计支持库函数级代码重用,作为软件工程领域最受欢迎的程序设计语言之一,Ｃ++不断汲取新思想,支持包括面向对象程序设计和泛型编程在内的多种程序设计思维模型。Ｃ++底层的Ｃ内存模型保证了最原始的运行效率,对多态的支持成就了面向对象技术,ｔｅｍｐｌａｔｅｓ及相关特性则展现为一种强大的泛型编程能力。标准模板库ＳＴＬ即是一种具有开放架构的、强大、高效的泛型数据结构和算法库。
1 迭代器模式算法往往和相应数据结构(存储结构)联系在一起,从而形成紧密的偶合关系。假设有Ｎ个不同的算法,Ｍ种不同的数据结构,可能需要Ｎ×Ｍ个不同的算法实现代码,给泛型程序库的实现者和使用者带来极大的负担;同时,亦使库中已有的数据结构和算法难以扩充。因此,长期以来未有合适的数据结构和算法库。软件工程中的许多设计问题可通过增加间接层方法来加以解决. ＧａｎｇＯｆＦｏｕｒ归纳了经常遇到的软件设计问题,形成了可再现的解决方案,提出了23种设计模式。其中有一种行为型模式称为迭代器模式,容许算法使用一个标准接口,即迭代器,依序访问一个数据集。ＳＴＬ应用迭代器模式,提供了ｖｅｃｔｏｒ、ｌｉｓｔ、ｄｅｑｕｅ等序列式容器和ｓｅｔ、ｍａｐ、ｍｕｌｔｉｓｅｔ、ｍｕｌｔｉｍａｐ等关联式容器,实现了各种常用数据结构和泛型算法;同时,每一种ＳＴＬ泛型容器都提供了各自相应的迭代器,作为容器的接口,算法通过迭代器访问容器。ＳＴＬ算法和容器(数据结构)得到了分离,打破了算法和数据结构的偶合关系,迭代器成为泛型容器和泛型算法的粘合剂。ＳＴＬ实现者无须再为不同的容器分别编写不同的算法实现代码,ＳＴＬ使用者可以自行增加新泛型容器、新泛型算法,使ＳＴＬ具有了开放构架。下述代码段展示了ＳＴＬ中泛型容器、泛型算法和迭代器的强大威力,它先从标准输入流中读入系列名字,存入向量容器中,然后,应用ＳＴＬ算法将向量容器内容拷贝到集合容器,再排序向量容器中名字,将集合容器和向量容器内容拷贝到标准输出流,得到排序好的名字序列。
ｖｅｃｔｏｒ<ｓｔｒｉｎｇ>Ｖ;//向量容器
ｓｅｔ<ｓｔｒｉｎｇ>Ｓ;//集合容器
ｓｔｒｉｎｇｎａｍｅ;
ｗｈｉｌｅ(ｇｅｔｌｉｎｅ(ｃｉｎ,ｎａｍｅ))//标准输入流中读入名字
Ｖ.ｐｕｓｈ＿ｂａｃｋ(ｎａｍｅ);//存入向量容器
ｃｏｐｙ(Ｖ.ｂｅｇｉｎ(),Ｖ.ｅｎｄ(),ｉｎｓｅｒｔｅｒ(Ｓ,Ｓ.ｂｅｇｉｎ()));//向量容器拷贝到集器ｓｏｒｔ(Ｖ.ｂｅｇｉｎ(),Ｖ.ｅｎｄ());//排序向量容器名字//将集合容器和向量容器内容拷贝到标准流ｃｏｐｙ(Ｓ.ｂｅｇｉｎ(),Ｓ.ｅｎｄ(),ｏｓｔｒｅａｍ＿ｉｔｅｒａｔｏｒ<ｓｔｒｉｎｇ>
(ｃｏｕｔ,"/ｔ"));
ｃｏｐｙ(Ｖ.ｂｅｇｉｎ(),Ｖ.ｅｎｄ(),ｏｓｔｒｅａｍ＿ｉｔｅｒａｔｏｒ<ｓｔｒｉｎｇ>(ｃｏｕｔ,”/ｔ”));
2 迭代器概念模型事实上,Ｃ/Ｃ++指针类型正是这样一个内建迭代器。Ｃ/Ｃ++程序可以通过指针访问Ｃ/Ｃ++内建容器———数组。Ｃ/Ｃ++指针可以进行复制、提领、提领赋值、++、--、+/-整数、[]、比较等多种运算。作为算法和容器的粘合剂,ＳＴＬ迭代器是一个泛型指针,是具有某种类型的指向其它类型对象的对象。并非所有迭代器都需要支持所有的指针运算,这既无必要,也无可能。ＳＴＬ使用抽象概念描述算法需求和容器接口,只要某个类型满足某组条件,就说此类型符合某个概念,是它的一个模特。定义抽象的概念,并根据抽象的概念来撰写算法与数据结构,正是泛型编程的本质。泛型算法对于参数类型的大部分假设,都可以由符合某概念来描述,迭代器也不例外。依据用途不同,ＳＴＬ将迭代器概念分为5类:输入迭代器,用于刻划输入;输出迭代器,用于指示输出;前向迭代器,可以单向前移;双向迭代器,可以双向移动;随机存取迭代器,支持随机存取。ＳＴＬ详细规定了各类迭代器概念需要支持的运算,Ｃ/Ｃ++指针类型正是一个随机存取迭代器概念的模特。各类迭代器概念间存在纯抽象的强化关系,它不同于图1 ＳＴＬ迭代器概念强化关系阶层模型面向对象程序设计中的继承关系。ＳＴＬ迭代器概念强化关系阶层模型如图1所示。ＳＴＬ各容器根据自身特点,负责提供某种相应类型迭代器。如基于单链表容器提供前向迭代器;基于双向链表容器提供双向迭代器;ｖｅｃｔｏｒ和ｄｅｑｕｅ则提供随机存取迭代器。算法则依据自身需要决定使用何种类型迭代器,处于强化关系阶层模型中的下层迭代器可以代替上层迭代器使用。3 特性萃取机制作为第一个标准规格的泛型程序库,ＳＴＬ不仅具有开放的架构,强大的能力,同时也是一个高效可重用的代码生成器;使用ＳＴＬ生成的代码运行效率可以完全不逊色于手工精制的代码。每一个ＳＴＬ泛型算法、每一个ＳＴＬ泛型容器的操作行为,其复杂程度都有明确规范,通常是最佳效率或极佳效率。ＳＴＬ规定各类迭代器支持的所有本身运算的时间复杂性都在可分摊的常数时间内;此外,各泛型算法可利用Ｃ++ｔｅｍｐｌａｔｅｓ特化、偏特化规则,根据使用的迭代器类型,特化、偏特化算法代码,达成最佳效率。任何迭代器类型,包括自定义迭代器类型都具有多种特性,ＳＴＬ建立了下列特性萃取模板类ｉｔｅｒａ ｔｏｒ＿ｔｒａｉｔｓ,可以萃取出各类迭代器(包括内建指针类型)自身各种特性。
ｔｅｍｐｌａｔｅ<ｃｌａｓｓｉｔｅｒａｔｏｒ>
ｓｔｒｕｃｔｉｔｅｒａｔｏｒ＿ｔｒａｉｔｓ
{
ｔｙｐｅｄｅｆｉｔｅｒａｔｏｒｉｔｅｒａｔｏｒ＿ｃａｔｅｇｏｒｙｉｔｅｒａｔｏｒ＿ｃａｔｅｇｏｒｙ;//迭代器标记特性类型 ｔｙｐｅｄｅｆｉｔｅｒａｔｏｒ:: ｖａｌｕｅ＿ｔｙｐｅｖａｌｕｅ＿ｔｙｐｅ;//迭代器值类型…
};
ｔｅｍｐｌａｔｅ<ｃｌａｓｓＴ>//ｉｔｅｒａｔｏｒ＿ｔｒａｉｔｓ指针偏特化版本ｓｔｒｕｃｔｉｔｅｒａｔｏｒ＿ｔｒａｉｔｓ<Ｔ >
{ ｔｙｐｅｄｅｆｒａｎｄｏｍ＿ａｃｃｅｓｓ＿ｉｔｅｒａｔｏｒ＿ｔａｇｉｔｅｒａｔｏｒ＿ｃａｔｅｇｏｒｙ; ｔｙｐｅｄｅｆＴｖａｌｕｅ＿ｔｙｐｅ;…
};
这样,泛型算法就可以根据需要,萃取出迭代器类型(包括指针)标记特性,分派算法,使算法既具有泛型特点,又具有最佳效率的实现。下面以ａｄｖａｎｃｅ算法为例进行说明:
ｔｅｍｐｌａｔｅ<ｃｌａｓｓＩｎＩｔ,ｃｌａｓｓＤｉｓｔ>ｉｎｌｉｎｅｖｏｉｄａｄｖａｎｃｅ(ＩｎＩｔ＆ｉｔ,Ｄｉｓｔｎ)
{//移动迭代器
ａｄｖａｎｃｅ(ｉｔ,ｎ,ｔｙｐｅｎａｍｅｉｔｅｒａｔｏｒ＿ｔｒａｉｔｓ<ＩｎＩｔ>::ｉｔｅｒａｔｏｒ＿ｃａｔｅｇｏｒｙ());//编译期分派}与迭代器概念强化关系阶层模型相对应,迭代器标记特性类间存在继承关系。所有迭代器ｉｔｅｒａｔｏｒ＿ｃａｔｅｇｏｒｙ标记特性类型,是下列5个ＳＴＬ空标记类之一:
ｓｔｒｕｃｔｉｎｐｕｔ＿ｉｔｅｒａｔｏｒ＿ｔａｇ{};ｓｔｒｕｃｔｏｕｔｐｕｔ＿ｉｔｅｒａｔｏｒ＿ｔａｇ{};ｓｔｒｕｃｔｆｏｒｗａｒｄ＿ｉｔｅｒａｔｏｒ＿ｔａｇ:ｐｕｂｌｉｃｉｎｐｕｔ＿ｉｔｅｒａｔｏｒ＿ｔａｇ{};ｓｔｒｕｃｔｂｉｄｉｒｅｃｔｉｏｎａｌ＿ｉｔｅｒａｔｏｒ＿ｔａｇ:ｐｕｂｌｉｃｆｏｒｗａｒｄ＿ｉｔｅｒａｔｏｒ＿ｔａｇ{};ｓｔｒｕｃｔｒａｎｄｏｍ＿ａｃｃｅｓｓ＿ｉｔｅｒａｔｏｒ＿ｔａｇ:ｐｕｂｌｉｃｂｉｄｉｒｅｃｔｉｏｎａｌ＿ｉｔｅｒａｔｏｒ＿ｔａｇ{};
上述各标记类并无任何数据成员,不占用任何存储空间,纯粹用来规范行为。根据Ｃ++模板函数重载分派规则,使用下层迭代器的算法可以分派至使用上层迭代器的函数;本例中,使用前向迭代器ａｄｖａｎｃｅ算法将分派至使用输入型迭代器的ａｄｖａｎｃｅ函数。同时,可以根据各类迭代器特点,提供对应下层迭代器算法的最佳实现。
ｔｅｍｐｌａｔｅ<ｃｌａｓｓＩｎｐｕｔＩｔｅｒａｔｏｒ,ｃｌａｓｓＤｉｓｔ>//同样适用前向迭代器ａｄｖａｎｃｅ算法ｉｎｌｉｎｅｖｏｉｄａｄｖａｎｃｅ(ＩｎｐｕｔＩｔｅｒａｔｏｒｉｔ,Ｄｉｓｔｎ,ｉｎｐｕｔ＿ｉｔｅｒａｔｏｒ＿ｔａｇ)
{
ｆｏｒ(;ｎ>0;--ｎ,++ｉ){}//只能前进
}ｔｅｍｐｌａｔｅ
<ｃｌａｓｓＢｉｄｉｒｅｃｔｉｏｎａｌＩｔｅｒａｔｏｒ,ｃｌａｓｓＤｉｓｔ>ｉｎｌｉｎｅｖｏｉｄａｄｖａｎｃｅ(ＢｉｄｉｒｅｃｔｉｏｎａｌＩｔｅｒａｔｏｒｉｔ,Ｄｉｓｔｎ,ｂｉｄｉｒｅｃｔｉｏｎａｌ＿ｉｔｅｒａｔｏｒ＿ｔａｇ)
{
ｉｆ(ｎ>=0)
ｆｏｒ(;ｎ>0;--ｎ,++ｉｔ){}//前进
ｅｌｓｅ
ｆｏｒ(;ｎ<0;++ｎ,--ｉｔ){}//倒退
}
ｔｅｍｐｌａｔｅ<ｃｌａｓｓＲａｎｄｏｍＡｃｃｅｓｓＩｔｅｒａｔｏｒ,ｃｌａｓｓＤｉｓｔ>ｉｎｌｉｎｅ ｖｏｉｄａｄｖａｎｃｅ(ＲａｎｄｏｍＡｃｃｅｓｓＩｔｅｒａｔｏｒｉｔ,Ｄｉｓｔｎ,ｒａｎｄｏｍ＿ａｃｃｅｓｓ＿ｉｔｅｒａｔｏｒ＿ｔａｇ)
{
ｉｔ+=ｎ;//发挥随机存取迭代器的最佳效率
}
ａｄｖａｎｃｅ算法具有统一接口,它利用特性萃取机制萃取出各类迭代器的标记类特性,然后利用Ｃ++模板偏特化机制分派恰当处理代码。这一切都在编译期完成,丝毫不影响运行效率。4 结束语迭代器是ＳＴＬ的核心。利用迭代器,ＳＴＬ构成了一个开放的架构,Ｃ++程序员不仅可以将标准泛型算法和泛型容器搭配使用,而且可以自行设计泛型容器、泛型算法,配合标准算法、容器使用。此外,利用配接器和函数对象,可以大大增强ＳＴＬ算法、迭代器、容器能力,形成一个具有威力强大的泛型库。
