泛型程式设计与STL

类别:VC语言 点击:0 评论:0 推荐:

                              泛型程式设计与STL


如果有一项技术,可以让你的程式码处理各种不同的资料型别,甚至是目前未知的资料型别,你喜欢吗?
我会欣喜若狂。
基本上这就是「可重用性(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 纳入标准,泛型技术才终于在标准资料结构和标准演算法领域中有一套可被大众运用的实作品出现,向现实跨一大步。
简单地说,泛型程式设计是一种「将资料型别参数化」的思维模式。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 的函式引数、或是明白标示的class template 引数,自动推导出一份函式实体或class 实体。换言之这项具现化动作在编译时期就完成,不会增加执行时期的成本。(关于template 的语法与性能,请参考任何一本「年轻的」C++ 全貌型书籍)
STL 是泛型概念的一套实作品。从学理上来说,它其实是一套严谨的"concepts" 分类学。这里所谓的concepts 有其严肃定义,意指「对某种型别的一些条件需求」。满足这些条件者,称为该concepts 的models。STL concepts 并没有实际对应到C++ 或其他语言的任何东西。
这样的学理概念,对大多数人勿宁是不可承受之重。大部份人只着眼STL 的实用性。是的,STL 非常好用,弹性非常大,效率也很理想。从实作的角度来看,以各种间接方式完成STL concepts 需求之各种C++ classes 和C++ functions,就是大家印象中的STL,它们实际存在于各个相应的含入档中,如<vector>,<functional>, <algorithms>.
以下,我便为各位介绍四本STL 相关书籍,涵盖不同的切入层次。其中前两本是著名的C++ 全貌(百科)型书籍,我只挑其中的STL 相关章节介绍。
 
●C++ Primer 3/e
【基本资料】
书名:C++ Primer 3/e
作者:Stanley B. Lippman & Josee Lajoie
出版:Addison Wesley, 0-201-82470-1, 1998
定价:US$ 45.95
页数:1237(含索引)
template & STL 相关章名:
chap6: Abstract Container Types
chap10: Function Templates
chap12: The Generic Algorithms
chap16: Class Templates
appendix: The Generic Algorithms Alphabetically
 
 
这本书向以内容广泛说明详尽著称。上列各章对于泛型基础技术template 以及STL 的各个组件(除了allocators)都做了应用上的说明。书中有大量范例,尤其附录列出所有的STL 泛型演算法的规格、说明、实例,是极佳的学习资料。
 
 
●The C++ Programming Language 3/e
【基本资料】
书名:The C++ Programming Language 3/e
作者:Bjarne Stroustrup
出版:Addison Wesley, 0-201-88954-4, 1997
定价:未列
页数:910(含索引)
template & STL 相关章名:
chap3: A Tour of the Standard Library
chap13: Templates
chap17: Standard Containers
chap18: Algorithms and Function Objects
chap19: Iterators and Allocators
 
 
这本书向以学术权威性著称(看看作者是谁:))。若非具备一定程度,对于书中内容或表达方式,浅尝之下会有艰涩的口感。上列各章涵盖了泛型基础技术template 以及STL 各组件。第19 章对Iterators Traits 技术的介绍,在C++ 语法书中难得一见,但此为正面或负面殊难定论,因为你必须知道Traits 技术之发展原由(问题之所在),才能够了解为什么变成现在这般抽象模样。当然,我们不能期望一本C++ 语言书籍对此有深刻的表现,但是这么高阶的技术,蜻蜓点水式的说明并不会引导出阅读兴趣,反而会重挫许多读者的信心。关于Traits 技术,稍后介绍的Generic Programming and the STL 一书表现极佳。
 
●The C++ Standard Library
【基本资料】
书名:The C++ Standard Library - A Tutorial and Reference
作者:Nicolai M. Josuttis
出版:Addison Wesley, 0-201-37926-0, 1999
定价:US$ 49.95
页数:799(含索引)
章名:
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++ Standard Library。详细介绍每一个组件的规格以及运用方式。整理功夫做得非常好也非常扎实,经常以表格的形式,让读者一目了然。
一旦你开始实际运用STL,本书绝对可以大量节省你翻查参考资料的时间。
由于本书介绍的对象是整个C++ Standard Library,所以一些少见于其他书籍的组件,如valvarry, mem_fun, ptr_fun,locales, 也都有涵盖。本书的另一个特色是,对于STL 相关的exception handling,亦有介绍。
本书不仅介绍STL 组件的运用,也导入STL 的原始码。这些原始码都经过处理与节录,比较容易入目。此外也适度介绍某些扩充技术。例如6.8 节介绍如何以smart pointer 使STL containers具有"reference semantics"(要知道,STL containers 本身只支援"value semantics"),又例如7.5.2 节介绍一个订制型iterator,10.1.4 节介绍一个订制型stack,10.2.4 节介绍一个订制型queue。15.4 节介绍一个订制型allocator。虽然都只是短短一些篇幅,列出基本技法,但对于想要扩充STL
的程式员而言,是一种实质上的莫大帮助。
一般而言,英文电脑书的字体都满小的。本书比较特别,字行之间的距离比较大,程式码与书后索引尤然。阅读起来眼睛应该轻松不少。喜欢以「页数/售价比」来评断书籍的人,可能会高兴一些;希望书籍轻一点薄一点便利携带的人,则可能稍有愠意。我常在BBS/News 上看到一些令人发噱的有关书厚与书价的言论。基本上谈书的价值,不应该扯到书的售价与页数。我对书的售价的看法是这样:电脑书不是写真集,没有用保鲜膜包起来;你愿意买它,就表示你承认它的价值匹配它的价格;否则,就不要买:)
 
●Generic Programming and the STL
【基本资料】
书名:Generic Programming and the STL -
Using and Extending the C++ Standard Template Library
作者:Matthew H. Austern
出版:Addison Wesley, 0-201-30956-4, 1999
定价:US$ 49.95
页数:548(含索引)
章名:
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 的运用、泛型程式设计的基本精神、C++ template 技法都有相当基础了,才得一窥堂奥。但是我认为任何人如对于STL 有更深一层的了解,本书必备。其中PartI 对STL 的学理基础(设计哲学)有很好的导入,PartII 是很详尽的STL concepts 规格书,PartIII 则是很详尽的STL 组件规格书(绝大部份附有运用范例)。
这本书partIII 之前的篇幅,很强调泛型程式设计的理论基础,你会看到conecpt、model、refinement 等字词及其定义,也会看到诸如range, iterator, Assignable, Default Constructible, Equality Comparable 等概念的严谨定义。我绝对不赞成读者在阅读吸收这些知识时,将这些英文术语转换为中文术语来使用,那会非常地令自己以及别人感到困惑。所幸目前为止应该也不存在这种困扰,因为目前为止根本没有任何一本中文书或中译书涉及STL 的学理与概念部份,也就不至于对那些可能不统一又不够明确的中文术语推波助澜。
这本书使你了解,STL 其实是一套有着系统化、严谨定义的「concepts 分类学」。这些STL concepts 并不对应于C++(或任何其他电脑语言)的任何关键字或任何成份。至于一般人所想象的STL「程式库」,则是以C++ template classes 及template functions 完成的各个concepts 的models。(什么是concepts?什么是models?建议你参考我所写的STL 系列文章的第一篇,载于本期)
虽然一本学术性又工具性的书籍,可能给人严肃又艰涩的印象,但是本书第二章以及第三章中解释iterator 及iterator traits 时的表现,却让我不由自主地喊精采。真是出人意表!当我从这两章彻底了解traits 技术,并因而有能力观看STL 原始码(是的,STL 原始码大量而几乎无所不在地运用了traits 技术),以及撰写符合规格的自定型STL 组件,我简直不禁要激越昂扬,仰天长啸。
基本上,STL 就像任何其他的framework 一样,以开放原始码的方式呈现于市场。这种白盒子方式(相较于另一种不开放原始码的所谓黑盒子),使我们在欲更深入剖析其技术时(可能是为了彻底了解,可能是为了扩充),有一个终极依恃。因此,有能力观看其原始码,我认为对技术的提升是十分重要的。
本书大瑜之中有小瑕:笔误不少。少数出现在程式码中的笔误,对学习可能带来一些负担。以下试举数例:
■p13 下,L-7, find() 定义式的回返型别
原文:Iter find(Iterator first, Iterator last, const T& value)
修改:Iterator find(Iterator first, Iterator last, const T& value)
■p41 上,advance() 定义式的内容
原文:advance(i, d, typename iterator_traits<T>::iterator_category());
修改:advance(i, n, iterator_traits<InputIterator>::iterator_category());
■p42 下,struct iterator 定义式的第二、第三个template 参数。
原文:class Pointer = T*,
class Reference = T&,
修改:class Pointer = Value*,
class Reference = Value&,
总的来说,本书在STL 的规格以及STL 学术概念的资料准备及说明方面,
目前书市无有出其右者。
--- the end
 
 
 
 
 

本文地址:http://com.8s8s.com/it/it3927.htm