泛型算法 java泛型算法

第一次发表於 Run!PC 杂志 Feb., 2000




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

我会欣喜若狂。
泛型算法 java泛型算法

基本上这就是「可重用性(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 Templ--ate 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 等概念的严谨定义。我绝对不赞成读者在阅读吸收这些知识时,将这些英文术语转换为中文术语来使用,那会非常地令自己以及别人感到困惑。

  

爱华网本文地址 » http://www.413yy.cn/a/25101016/320283.html

更多阅读

C++洗牌算法 随机洗牌算法

洗牌即产生指定数据的随机序列。  在网上找了半天大体有两种做法  1、  思路:将54个数依次放到随机的位置。关键是每次找一个随机的位置。  下面是找这个随机位置的算法:  1、用一个Bool型数组记录各个位置是否已经放置了数

MMSEG 中文分词算法 java中文分词算法

Nov 1st, 2009 | Comments由于学习需要,我尝试翻译MMSEG算法,目前处于初稿状态,很许多地方的翻译仍不尽准确,在以下几天会加以修改。 算法原文位于:http://technology.chtsai.org/mmseg/MMSEG :一个基于最大匹配算法的两种变体的中文单词

从小到大排序算法 java从小到大排序

查看文章 10种排序算法总结(冒泡、选择、插入、希尔、归并、快速、堆、拓扑、锦标赛、基数)2011年01月20日星期四 08:24P.M.排序算法有很多,所以在特定情景中使用哪一种算法很重要。为了选择合适的算法,可以按照建议的顺序考虑以下标

weka添加算法 java调用weka聚类算法

向weka里面添加算法分为三类:一,添加算法jar包 二,添加下载的算法三,自己写算法添加下面分别介绍这三类。一,添加算法jar包以添加libsvm.jar为例,将jar包放到某一个目录下,比如放在weka-3-6的lib(新建的)目录下。结构为weka-3-6liblibs

声明:《泛型算法 java泛型算法》为网友梦寐已求分享!如侵犯到您的合法权益请联系我们删除