Timothy

链接

C++ / OOP大系 [转:侯捷作品]
From Com to Com[转:侯捷作品]

Genericity/STL 大系[转:侯捷作品]

Timothy posted @ 2010年7月09日 01:34 in Learning Plan , 12010 阅读

 如果有一项技术,可以让你的程式码处理各种不同的资料型别,甚至是目前未知的资料型别,你喜欢吗?

 

我会欣喜若狂。

 

基本上这就是「可复用性(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 概念衍化体系

 

 

 

⊙所谓 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,也就是先通过第二境界的痛苦折磨。

 

也许还应该加上所谓的第0境界:C++ template 机制。这是学习泛型技术及 STL 的门槛,

 

 

 

以下,我便为各位介绍六本相关书籍,涵盖不同的切入角度,也涵盖上述三个学习层次。首先的两本是着名的 C++ 百科型书籍,我只挑其中与 STL 相关的章节做介绍。为求方便,以下以学术界习惯的标示法,标示书籍代名。本文使用这些代名。凡有中文版者,我会特别加注。

 

 

[Lippman98]: C++ Primer, 3rd Editoin, by Stanley Lippman and Josee Lajoie,

Addison Wesley Longman, 1998. 1237 pages.

繁体中文版:《C++ Primer 中文版》,侯捷译, 峰 1999. 1237 页

 

[Struostrup97]: The C++ Programming Language, 3rd Editoin, by Bjarne Stroustrup, Addison Wesley Longman, 1997. 910 pages

繁体中文版:《C++ 程式语言经典本》,叶秉哲译,儒林 1999.(未录总页数)

 

[Josuttis99]: The C++ Standard Library - A Tutorial and Reference, by Nicolai M. Josuttis, Addison Wesley 1999. 799 pages

繁体中文版:侯捷计划中

 

[Austern98]: Generic Programming and the STL - Using and Extending the C++ Standard Template Library, by Matthew H. Austern, Addison Wesley 1998. 548 pages

繁体中文版:《泛型程式设计与 STL》,侯捷/黄俊尧合译, 峰 2000。548页

 

[Jjhou01]: 泛型技术 - 从具象工具到抽象思维, by 侯捷, 峰 2001. 页数未定

简体中文版:洽谈中

 

[Gamma95]: Design Patterns: Elements of Reusable Object-Oriented Software, by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides, Addison-Wesley, 1995. 395 pages

简体中文版:《设计模式》,李英军等译,机械工业出版社,2000. 254 页

 

●第零境界:泛型技术的基本门槛

 

在 C++ 环境中学习泛型技术,首要是把 template 相关语法与语意搞清楚。包括 class templates, function templates, member templates, specialization, partial specialization。更往基础看去,由於 STL 大量运用了 operater overloading(运算子多载化),所以这个技法也必须熟捻。

 

[Lippman98] 是一本 C++ 百科全书,向以内容广泛说明详尽着称。本书内容与 template 及 STL 直接相关的章节有:

 

chap6: Abstract Container Types

chap10: Function Templates

chap12: The Generic Algorithms

chap16: Class Templates

appendix: The Generic Algorithms Alphabetically

 

间接相关的章节有:

 

chap15: Overloaded Operators and User Defined Conversions

 

书中有大量范例,尤其附录列出所有的 STL 泛型演算法的规格、说明、实例,是极佳的学习资料。不过书上有极少数例子,因为作者的疏忽,未能完全遵循 C++ 标准,仍沿用旧式写法。更正作法可上繁体版支援网站(侯捷网站)看看。此书的学习方式以及华人读者的技术讨论也都可在繁体版支援网站上看到。

 

 

[Struostrup97] 也是一本 C++ 百科全书,向以学术权威(以及涩味极重)着称。若非具备一定程度,对於书中内容的表达方式,浅尝之下会有艰涩的口感。本书内容与 template 及 STL 直接相关的章节有:

 

chap3: A Tour of the Standard Library

chap13: Templates

chap16: Library Organization and Containers 

chap17: Standard Containers

chap18: Algorithms and Function Objects

chap19: Iterators and Allocators

 

间接相关的章节有:

 

chap11: Operator Overloading 

 

第 19 章对 Iterators Traits 技术的介绍,在 C++ 语法书中难得一见,但此为正面或负面殊难定论,因为你必须知道 Traits 技术之发展原由(问题之所在),才能够了解为什麽变成现在这般抽象模样。当然,我们不能期望一本 C++ 语言书籍对此有深刻的表现,但是这麽高阶的技术,蜻蜓点水式的说明并不会引导出阅读的兴趣,反而可能会重挫读者的信心。关於 Traits 技术,[Austern98] 表现极佳。

 

上面所说的这两本 C++ 百科全书,基本上并不是以介绍泛型技术的角度出发,而是以「C++ 涵盖了 template 和 STL,所以我介绍它」的态度出发。因此,在相关组织上,稍嫌凌乱。不过我想,没有人会因此对他们求全责备。

 

 

●第一境界:熟用 STL

 

一旦你开始学习 STL,乃至开始实际运用 STL,[Josuttis99] 绝对可以为你节省大量的翻查、叁考、错误尝试的时间。本书各章如下:

 

1. About the Book

2. Introduction to C++ and the Standard Library

3. General Concepts

4. Utilities

5. The Standard Template Library

6. STL Containers

7. STL Iterators

8. STL Function Objects

9. STL Algorithms

10 Special Containers

11 Strings

12 Numerics

13 Input/Output Using Stream Classes

14 Internationalization

15 Allocators

Internet Resources

Bibliography

Index

 

正如其副标所示「本书兼具学习用途及叁考价值」,既不夸张也当之无愧。本书涵盖的不仅是 STL,而是整个 C++ 标准程式库,详细介绍每一个组件的规格及运用方式,并佐以范例。作者的整理功夫做得非常好非常扎实。在观念解说方面,经常以图表形式让读者一目了然。

 

由於本书介绍的对象是整个 C++ 标准程式库,所以少见於其他书籍的某些组件,如 valvarry, mem_fun, ptr_fun, locales 等等,也都涵盖其中。标准程式库的几个大家伙,像是 string, iostream, locale, 也都有极具水准的介绍。本书的另一个特色是,对於与 STL 相关的各种异常讯息(exceptions),亦有介绍。这很少见。

 

[Josuttis99] 不仅介绍 STL 组件的运用,也导入 STL 的源码。这些源码都经过作者的节录整理,砍去枝节,留下主干,较易入目。这是我对此书最激赏的一部份。换句话说,阅读此书,不但进入我所说的第一学习境界,甚且进入了第二境界。这种对於白盒子(注)的阐释方式和侯捷的写作风格十分近似,我一向也喜欢繁中取简,在百万军中取敌首级。这可不是容易的动作,首先得对庞大的源码有清晰的认识,再有自己的诠释主轴,知道什麽要砍,什麽要留,什麽要注解。

 

注:附源码的工具我们称为白盒子,未附源码者我们称为黑盒子。

 

 

本书也适度介绍某些 STL 扩充技术。例如 6.8 节介绍如何以 smart pointer 使 STL 容器具有 "reference semantics" (原本 STL 容器只支援 "value semantics")。又例如 7.5.2 节介绍一个订制型 iterator,10.1.4 节介绍一个订制型 stack,10.2.4 节介绍一个订制型 queue。15.4 节介绍一个订制型 allocator。虽然都只短短一些篇幅,列出基本技法,但对於想要扩充 STL 的程式员而言,起了个头,终究是一种实质上的莫大帮助。就这点而言,本书又进入了我所说的第三学习境界。

 

 

通常,英文电脑书的字体都相当小,程式码尤其更小。本书字行之间的距离特别大些,程式码与书後索引尤然。阅读时眼睛应该轻松不少。喜欢以「页数/售价 比」来评断书籍的人,这下会高兴些了,系数高不少嘛 ─ 真像朝三暮四里头的猴子!盼望书籍轻一点薄一点便利携带的人,则可能略有愠意。我常在 BBS/News 上看到一些关於书厚薄与书价格的言论,令人发噱。有人拿侯捷的《深入浅出 MFC》比鹿挢的《未央歌》,说两本都是好书,但买一本《深入浅出 MFC》可买五本未央歌,言下之意不以为然。真是苹果比橘子,张飞战岳飞!

 

基本上谈书的价值,不应该扯上书的价格与页数。谈书的价格,则不应该扯上书的页数。我对买卖的看法是这样:电脑书不是写真集,没有用保鲜膜包起来,内容与页数都明白呈现你的眼前;你愿意买,就表示你承认它的价值匹配它的价格;否则就别买。我对书价的看法则是这样:书籍是卖知识,不是卖纸,重要的是含金量,不是页数与厚薄。如果你不愿意花比较多的钱买比较好的书,你还期望别人花比较多的精力与比较高的成本写作/出版好书吗?

 

话说远了。让我们回到主题。

 

●第二境界:了解泛型技术的内涵与 STL 的学理

 

[Austern98] 是一本艰深的书。没有三两三,别想过梁山,你必须对 C++ template 技法、STL 的运用、泛型设计的基本精神都有相当基础了,才得一窥此书堂奥。

 

本书第一篇对 STL 的设计哲学有很好的导入,第二篇是详尽的 STL concepts 完整规格,第三篇则是详尽的 STL components 完整规格,并附运用范例。

 

PartI : Introduction to Generic Programming

1. A Tour of the STL

2. Algorithms and Ranges

3. More about Iterators

4. Function Objects

5. Containers

PartII : Reference Manual: STL Concepts

6. Basic Concepts

7. Iterators

8. Function Objects

9. Containers

PartIII : Reference Manual : Algorithms and Classes

10. Basic Components

11. Nonmutating Algorithms

12. Basic Mutating Algorithms

13. Sorting and Searching

14. Iterator Classes

15. Function Object Classes

16. Container Classes

Appendix A. Portability and Standardization

Bibliography

Index

 

本书通篇强调 STL 的泛型理论基础,以及 STL 的实作规格。你会看到 conecpt, model, refinement, range, iterator 等字词的意义,也会看到诸如 Assignable, Default Constructible, Equality Comparable 等观念的严谨定义。我绝对不赞成在讨论、思考这些知识时,将这些原文术语转换为中文来使用,那会非常令自己和同伴感到困惑。所幸目前为止应该不存在这样的困扰,因为泛型的中文书籍(不论着译)非常少,不至於对那些可能不够统一、不够明确的中文术语推波助澜。

 

虽然一本既富学术性又带叁考价值的工具书,给人严肃又艰涩的表象,但本书第二章及第三章解释 iterator 和 iterator traits 时的表现,却让我不由自主地击节赞赏,大叹精彩。当我藉由这两章彻底解放了 traits 编程技术,并因而有能力观看 STL 源码(STL 源码几乎无所不在地运用 traits 技术)、撰写符合规格的自定型 STL 组件,我真不禁要激越昂扬,仰天长啸。

 

traits 是 STL 的关键编程技术。这个观念无法在这里三言两语带出,我就不多费事儿了。[Austern98] 书中那麽好的解说与导引,你自个儿去看。

 

就像其他任何 framework 一样,STL 以开放原始码的方式呈现市场。这种白盒子方式,使我们在更深入剖析其技术时(可能是为了透彻,可能是为了扩充),有一个终极依恃。因此,观看 STL 源码的能力,我认为对技术的养成与掌握,极为重要。

 

总的来说,本书在 STL 规格及 STL 学理概念的资料及说明方面,目前书市无有出其右者。我个人在元智大学开授一门「泛型程式设计」课程,[Austern98] 便是我指定给同学的高阶叁考书。本书在 (1) 泛型观念之深入浅出、(2) STL 架构组织之井然剖析、(3) STL 叁考文件之详实整理 三方面,均有卓越表现。可以这麽说,在泛型技术和 STL 的学习道路上,本书并非万能(它不适合初学者),但如果你希望彻底掌握泛型技术与 STL,没有此书万万不能。

 

 

●第三境界:扩充 STL

 

要撰写与 STL 相容 ─ 也就是可以和 STL 组件自由拼凑组装在一起 ─ 的个人自定组件,我们需要两种书籍。你已经知道,STL 的背後是一个严谨的「软体概念分类学」,为了与 STL 水乳交融,自定组件一定必须满足那严谨的架构 ─ 回头看看图一那张 vector 概念衍化图吧。因此,我们首先需要一份详尽的 STL concepts 规格书,而 [Austern98] 正是最好的(可能也是唯一的)候选人。

 

第二,万事起头难,我们可能需要足够的范例,带引我们上路。目前市面上缺乏这样的书籍。我看过 "Designing Components with the C++ STL",书名很吸引人,实则未能进入侯捷的推荐名单。幸好 [Josuttis99] 分担了部份这样的角色,聊堪倚仰。

 

 

●侯捷的理想

 

做为一个对泛型思维及 STL 产品有深刻体会的人,本身又是一名技术写作者,我不可能没有自己的论述理想。

 

由於泛型与 STL 对许多人而言,相对之下毕竟是新鲜玩意儿,语言层面的技法也还算新鲜而高阶,所以我希望为读者铺陈一条由摇篮到坟墓的路。从 C++ 相关语法、到 traits 编程技术、到 STL 的各种运用,再到 STL 的学理探究,最後示范数个扩充组件。一书而竟全功。具叁考价值的查阅型工具书我写不来(那需要完备的资料和大量的细心),观念阐述型的书籍则是我的拿手,也是我的兴趣。

 

下面便是暂名「泛型技术 - 从具象工具到抽象思维」的 [Jjhou01] 新书目录(暂定)。

 

第1章 泛型大局观(Overview of Generic Programming)

第2章 C++ 运算子多载化(Operator Overloading)基本技法

第3章 C++ 泛型基本技法 (1):Function Template

第4章 C++ 泛型基本技法 (2):Class Template

第5章 Traits 编程技法

第6章 Iterator(泛型指标)

第7章 Container(容器)

第8章 Function Object(函式物件)

第9章 Generic Algorithms(泛型演算法)

第10章 Adaptor(配适器)

第11章 Allocator(记忆体配置器)

附录 叁考书目

索引 Index

 

当你看到这篇文章的同时,我正在台湾南部的一个农村,我的老家,做这本书的最後整理。

 

 

●旁徵博引 左右逢源

 

[Gamma95] 与泛型或 STL 并没有直接关系。但是 STL 有两大类组件,却被收录於 [Gamma95] 的 23 个设计样式(design patterns)中:Iterator 和 Adaptor。其他设计样式在 STL 之中也有所发挥。两相比照,尤其是看过 STL 的源码之後,对於这些设计样式会有更深的体会,返映过来面对 STL 也会有更深一层的体会.

 

 

●一点感想

 

自从被全球软体界广泛运用以来,C++ 有了许多演化与变革。然而就像人们总是把目光放在艳丽的牡丹而忽略了花旁的绿叶,做为一个广为人知的物件导向程式语言(Object Oriented Programming Language),C++ 所支援的另一种思维 ─ 泛型编程 ─ 被严重忽略了。说什麽红花绿叶,好似主观上划分了主从,其实物件导向思维和泛型思维两者之间无所谓主从。两者相辅相成,肯定能对程式开发有更大的突破。

 

永远记住,面对新技术,程序员最大的障碍在於心中的怯弱。To be or not to be, that is the question! 不要和哈姆雷特一样犹豫不决,当你面对一项有用的技术,必须果敢。

 

--- the end

 

 

Avatar_small
DHSE +1 Model Paper 说:
2022年8月25日 12:58

Kerala Plus Two Old Important Model Question Paper 2023 PDF 2023 is Released in Online Mode. Kerala DHSE Board 11th Arts, Science and Commerce Group Important Model Question Paper 2023 Attachments are Available on This Page. DHSE +1 Model Paper 2023 Important Model Question Paper 2023 are an Important Two for the Students to Getting High Scores in the Board Examinations. Kerala Plus Two Malayalam, English, Computer Science, Computer Application, Hindi, Chemistry, Statistics, Economics, History, Geology, Physics, Maths, Tamil, Kannada and Other Subjects Last Year Important Model Question Paper 2023 are Download on the Official Website. Kerala State Board Important Model Question Paper 2023 PDF are Given Below.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter