模板
教程
环境
性能
功能
管理
另一片：Genericity/STL 大系（有关于泛形的讨论）1
发表于：2007-06-30来源：作者：点击数：
标签：
侯捷观点（系列书评 2/2） 【Genericity/STL 大系】 《 程序员 》2001.02 作者简介：侯捷，台湾电脑技术作家，着译评兼擅。常着文章自娱，颇示己志。 个人网站：www.jjhou.com 北京镜站：www.csdn.net/expert/jjhou 如果有一项技术，可以让你的程式码处理各
侯捷观点（系列书评 2/2） 【Genericity/STL 大系】 《程序员》2001.02 | ||
作者简介：侯捷，台湾电脑技术作家，着译评兼擅。常着文章自娱，颇示己志。 个人网站：www.jjhou.com 北京镜站：www.csdn.net/expert/jjhou 如果有一项技术，可以让你的程式码处理各种不同的资料型别，甚至是目前未知的资料型别，你喜欢吗？ 我会欣喜若狂。 基本上这就是「可复用性（reusibility）」的表现。当我们有新的资料型态产生，而过去完成的码完全无需修改即可沿用，不正是一种完美的「可复用性」吗？ 物件导向技术中的多型（polymorphism），以及泛型技术中的泛型（genericity）都可以达到这个目标。它们的字义，也明白标示出其特色。对大多数人而言，polymorphism（多型技术）早已如雷灌耳，genericity（泛型技术）则稍感陌生。这是一个你有必要尽快进入的重要领域。 ●勤前教育 数年前我第一次接触泛型程式设计（generic programming）与 STL（Standard Template Library）的时候，就深深被它吸引。虽然那时候我还不怎麽了解 STL 里头一大堆的术语像是 container、iterator、adaptor、function object、allocator┅。甚至连泛型技术深度依赖的基本技法 C++ template，当时的我都还只一知半解，但光只「泛型」这两个字就够把我吸引到那个世界里面了。 但愿我这麽说不至於误导你把泛型程式设计和 STL 划上等号。泛型概念滥觞於 Doug McIlroy 於 1968 年发表的一篇着名论文 "Mass Produced Software Components"，那篇论文提出了 "reusable components"（可复用软体组件，又称为软体积木或软体 IC）的愿景。过去数十年中，泛型技术仍属於研究单位中的骄客，实作产品付之阙如。直到 C++ 不断加强 template 机制，并将 Alexander Stepanov 创作的 STL 纳入标准，泛型技术才终於在标准资料结构和标准演算法领域中有一套可被大众运用的实作品出现，向现实跨一大步。 让我们先复习一下。下面是多型的标准形式： void func(Shape* ps) // Shape 是某个 class 继承体系的基础类别 { // ... ps->draw(); // draw() 是个虚拟函式 (virtual function) } func() 的呼叫者可以自由传入 Shape 继承体系下任何一个 Shape 衍生类别的物件指标，func() 函式所唤起的将是实际传入之物件（指标）所对应的那个 draw() 虚拟函式。这种写法所带来的好处是，即使将来 Shape 继承体系衍生出前所未见的子型别，只要该子型别本身提供了 draw() 虚拟函式，上面这个 func() 就完全不必更改，可继续使用。 那麽，泛型又是什麽呢？简单地说，这是一种「将资料型别叁数化」的思维模式。C++ 的 template 机制就是泛型技术的一个具体载具。在 C++ 中，不论 functions 或是 classes，皆可将其中所需要的资料型别以一个保留器（placeholder）代表，这个保留器亦即所谓的 template 叁数。例如 function template： template<typename T1, typename T2) void func(T1 param1, T2 param2) { /* ... */ } 或是 class template： template<typename T1, typename T2) class A { /* ... */ } 从此，一旦程式中使用上述的 func() 或 class A，例如： func(5, 2.3); A<int, double> a; 编译器即根据 function template 的函式引数（上例的 5 和 2.3），或根据被我们明白标示出来的 class template 引数（上例的 int 和 double），自动推导出一份 function 实体或 class 实体。这个所谓的具现化动作（instantiation）在编译期就完成，不会增加执行期的成本。关於 template 的详细语法与性能，请叁考任何一本完备的 C++ 百科型书籍。 以上这种「将资料型别叁数化，再由编译器视使用当时的情况，为我们完成实体具现化」的概念，即是泛型的实际展现。template 是 C++ 语言中支援泛型概念的一个工具，而 STL 则是泛型概念的一套实作品。从学理上来说，STL 其实是一套严谨的 "concepts" 分类学。这里所谓的 concepts 有其严谨定义，意指「对某种型别的某些条件需求」。满足这些条件之型别，称为该 concept 的一个 model。举个例子，如果我们能够复制型别为 T 之物件，并可以将数值指派给 T 型别的变数身上，那麽型别 T 便符合 Assignable 这一 concept，而 T 便是 Assignable 的一个 model。STL 的六大组件 containers, algorithms, iterators, function objects, allocators, adaptors, 全都是 concepts，实作品如 vector, list, sort(), swap() 等等 templates, ... 全都是 models。 这样的学理概念，对大部份人勿宁是不可承受之重。大部份人只着眼 STL 的实用性，因为 STL 非常好用，弹性非常大，执行效率也很理想，可大幅提升软体开发效率。从实作的角度来看，以各种方式完成，符合 STL concepts 需求之各种 C++ classes 和 C++ functions，就是大家一般印象中的 STL，它们实际存在於各个相应的含入档中，如 <vector>,<functional>, <algorithms>. ●剖析 STL 任何学习，如果直接从抽象思维开始，对大部份人是一件困难的工作。通常我们需要一个具体可操作的东西，慢慢再由具象操作转为抽象思考。 那麽，先学会使用 STL，应该是学习泛型思维的最好途径。事实上，自从 STL 以及整个 C++ 标准程式库定案之後，很多专家，包括 Bjarne Stroustrup，都认为 C++ 程式语言的教学，首先应从如何使用标准程式库（含 STL）开始。 我当然无法在这篇文章中告诉你 STL 乃至整个标准程式库的用法。但是我可以给你一些概念，让你知道 STL 的架构。 STL 是一个完全以 template 技术完成的程式库。它构成了 C++ 标准程式库的绝大部份骨干 ─ 粗略估计应该占 80% 以上的面积。STL 有六大组件（components）： 1 containers（容器），各种基本资料结构如 vector, list, deque, set, map┅，共约 11 种。其中有些亦被归类为 adaptors。 2 algorithms（演算法），各种基本演算法如 sort, search, copy, erase┅，共约 70 个。 3 iterators（迭代器）：应用於容器与演算法身上的一种泛型指标，扮演两者间的胶着剂。[Gamma95] 对於 iterator 这种设计样式（design pattern）的定义是：提供一种方法，俾得依序巡访某个聚合物件（容器）所含的各个元素，而又不需曝露该聚合物件的内部表述方式。STL 共提供了五种 iterators 型态，以及各种衍生变化。Iterator 是 STL 中最重要最抽象的一个组件，它使容器与演算法可以各自独立发展，这是一种突破性的观念。不论就实作技术或抽象观念，iterator 都是 STL 中最关键的成份。了解了 iterators，也就进入了 STL 的大门。 4 function object：行为类似 function，但其实是一种 object。以实作技术而言，这是一个改写了 "call operator" 的 class。STL 提供 15 个现成的 function objects。 5 adaptors（调适器）：用来改变（修饰）其他组件的介面。[Gamma95] 对於 adaptor 这种设计样式（design pattern）的定义是：将一个 class 的介面转换为另一个 class 的介面，使原本因介面不相容而不能合作的 classes，可以一起运作。在 STL 中，改变 function object 介面者，称为 function adaptor，改变 container 介面者，称为 container adaptor。改变 iterator 介面者，称为 iterator adaptor。例如 STL 提供的两个容器 queue 和 stack，其实都只不过是 adaptor，修饰了 deque 的介面而成就出另一种容器风貌。 6 allocator（记忆体配置器）：容器空间配置系统。STL 提供有现成的 allocator。 下面这个例子，用上了 STL 的所有六种组件，目的是找出某个数列之中数值大於 40 的元素个数，答案为 4。从这个例子，你可以看到 STL 不同组件间的接合，发展到了一个怎样灵活的程度，像乐高积木一样，有无限可能。 #include <algorithm> #include <functional> #include <vector> #include <iostream> using namespace std; int main() { int ia[ ] = { 27, 210, 12, 47, 109, 83, 40 }; vector<int, allocator<int> > vec( ia, ia+7 ); cout << count_if(vec.begin(), vec.end(), not1(bind2nd(less_equal<int>(), 40))); return 0; } // vector 是一个 STL 容器 // count_if 是一个 STL 演算法 // not1 和 bind2nd 都是 STL function adaptors // less_equal<> 是一个 STL function object // allocator<> 是一个 STL 记忆体配置器 // vec.begin() 和 vec.end() 分别传回两个 iterator，指向容器 vec 的头尾。 ●软体组件分类学 STL 的实用价值当然很高。但是工具的使用对於技术的探究乃至学理的钻研，已属末流。要掌握 STL 的精神，乃至将来得以自行发展组件，与既有的 STL 水乳交融，就必须更深一层看看 STL 的背後学理。 前面说过，STL 其实是在泛型思维模式之下建立起一个系统化的、条理分明的「软体组件分类学」。这个分类学严谨定义了什麽是 concept, 什麽是 model, 什麽是 refinement, 什麽是 range，也定义了什麽是 predicate, 什麽是 iterator, 什麽是 adaptor┅。我将在此试述其中一二，让你在最短时间内对 STL 的本质有一个初步的认识。 ⊙所谓 concept 和 model 所谓 concept，描述某个抽象型别的条件（或说需求，requirements）。concept 并不是一个 class，也不是一个变数或是一个 template 叁数；C++ 语言之中没有任何东西可以直接代表一个concept。然而，在每一个用到泛型程式设计方法的 C++ 程式中，concept 非常重要。由 concepts 所构成的阶层体系，正是 STL 的主体结构。 当某个型别满足某个 concept 的所有条件，我们便说此型别是该 conecpt 的一个model。concept 可被视为一组型别条件。如果型别 T 是 concept C 的一个 model，那麽 T 就一定满足 C 的所有条件。因此，concept 亦可被视为是一组型别。如果型别 T 是 concept C 的一个 model，我们便可说 T 隶属於「C 所表现的一组型别」。 举个例子，STL 规范了一些基本 concepts 如下，其中并描述了欲符合那些条件，必须以 C++ 完成哪些建设。 1. Assignable：型别 T 如果是 concept Assignable 的一个 model，我们便可以将 T 物件的内容拷贝并指派给型别为 T 的另一个物件，换言之型别 T 必须有一个 copy constructor。如果 x, y 都有 Assignable 性质，那麽保证以下动作中的 x, y 有着相同的值： X x(y) x = y tmp = y, x = tmp 2. Default Constructible：如果型别 T 是 Default Constructible 的一个 model，它必须有一个 default constructor。也就是说我们可以这麽写而产生出一个 T 物件： T() 欲产生出一个型别为 T 名称为 t 的变数，可以这样写： T t; C++ 的所有内建型别如 int 和 void，都隶属於 Default Constructible。 3. Equality Comparable：如果型别 T 是 Equality Comparable 的一个 model， 我们便可以这样比较两个 T 物件是否相等： x==y 或 x!=y 换言之 T 必须支援 operator== 和 operator!=。 4. LessThan Comparable：如果型别 T 是 LessThan Comparable 的一个 model， 我们可以这样测试某个 T 物件是否小於另一个 T 物件： x < y 或 x > y 换句话说如果某个型别能够以某种次序排列，它便隶属於 LessThan Comparable， 它必须能够以 operator< 做为比较动作，而 operator< 必须定义出某种顺序性。 如果某个型别同时符合 Assignable, Default Constructible, Equality Comparable 三种 concepts，我们称此型别为 regular type。大部份的 C++ 内建基本型别都是 regular types，例如 int 便是。几乎所有定义於 STL 中的型别（class templates）也都是 regular types。 现在我们看看具体的 STL 容器 vector，由哪些 concepts 衍生过来。图一是根据 STL 定义而绘制的 vector 概念衍化体系。 图一 / 根据 STL 定义而绘制的 vector 概念衍化体系 http://jjhou.csdn.net/vector.jpg ⊙所谓 refinements 如果 concept C2 供应 concept C1 的所有机能，并且（可能）加上其他机能，我们便说 C2 是 C1 的一个 refinement（强化）。 Modeling 和 refinement 必须满足以下三个重要特性。只要把 concepts 想像为一组型别，以下三者就很容易验证： 1. Reflexivity（反身性）。每一个 concept C 是其本身的一个 refinement。 2. Containment（涵盖性）。如果型别 X 是 concept C2 的一个 model，而 C2 是 concept C1 的一个 refinement，那麽 X 必然是 C1 的一个 model。 3. Transitivity（递移性）。如果 C3 是 C2 的一个 refinement，而 C2 是 C1 的一个 refinement，那麽 C3 是 C1 的一个 refinement。 一个型别可能是多个 concepts 的 model，而一个 concept 可能是多个 concept 的 refinement。 ⊙所谓 range（范围） 对於 range [first, last)，我们说，只有当 ][first, last) 之中的所有指标都是可提领的（dereferenceable），而且我们可以从 first 到达 last（也就是说对 first 累加有限次数之後，最终会到达 last），我们才说 ][first, last) 是有效的。所以，][A, A+N) 是一个有效的 range，empty range ][A, A) 也是有效的。][A+N, A) 就不是一个有效的 range。 一般而言，ranges 满足以下性质： 1. 对任何指标 p 而言，][p, p) 是一个有效的 range，代表一个空范围。 2. 如果 ][first, last) 是有效而且非空的 range，那麽 ][first+1, last) 也是一个有效的 range。 3. 如果 ][first, last) 是有效的 range，而且 mid 是一个可由 first 前进到达的指标，而且 last 又可以由 mid 前进到达，那麽 ][first, mid) 和 ][mid, last) 都是有效的 ranges. 4. 反向而言，如果 ][first, mid) 和 ][mid, last) 都是有效的 ranges，那麽 ][first, last) 便是有效的 ranges。 有人开始吃不消了，这是数学还是编程呀?! 的确，我们面对的是一个有着数学般严谨定义的「软体组件分类学」。整个 STL 就是由这些 concepts 构成。至於真正的实作品，不过是在这样的观念基础上，以 C++ 实践出来而已。 ●效率的疑虑 人们对於 STL 的最大误解是效率。事实上 STL 提供的是一个不损及效率的抽象性。泛型编程和物件导向编程不同，它并不要求你透过额外的间接层来呼叫函式；它让你撰写一般化、可复用的演算法，其效率和「针对特定资料型别而设计」的演算法旗鼓相当。每一个演算法、每一个容器的操作行为，其复杂度都有明确规范 ─ 通常是最佳效率或极佳效率。在接受规格书明定的复杂度之後，我想你不会认为自己亲手撰写的码，能够更胜通过严格检验、通行世界、无数人使用的程式库。 人们对 STL 效率的误解，有一大部份是把编译期效率和执行期效率混为一谈了。的确，大量而巢状地运用 templates，会导致编译器在进行 template引数推导（argument deduction）及具现化（instantiation）时耗用大量时间。但它绝不影响执行效率。至於对专案开发时程所带来的影响，我要说，和 STL 为我们节省下来的开发时间相比，微不足道。 STL 的严重缺点在於，它尚未支援 persistence（物件的永续性）。在良好的解决方案尚未开发出来之前，persistence 必须由使用者自行完成。 ●泛型技术的三个学习阶段 王国维说大事业大学问者的人生有三个境界。依我看，泛型技术的学习也有三个境界： ]第一个境界是使用 STL。对程式员而言，诸多抽象描述，不如实象的程式码直指人心。 第二个境界是了解泛型技术的内涵与 STL 的学理。除了前述的软体概念分类学，最好再对数个 STL 组件（不必太多，但最好涵盖各类型）做一番深刻追踪。STL 原始码都在手上（就是相应的那些表头档嘛），好好做几个个案研究，便能够对泛型技术以及 STL 的学理有深刻的掌握。 第三个境界是扩充 STL。当 STL 不能满足我们的需求，我们必须有能力动手写一个可融入 STL 体系中的软体组件。要到达这个境界之前，可得先彻底了解 STL，也就是先通过第二境界的痛苦折磨。 也许还应该加上所谓的第０境界：C++ template 机制。这是学习泛型技术及 STL 的门槛， |
