首页 > > > STL源码剖析_简体.pdf

STL源码剖析_简体.pdf

STL源码剖析_简体.pdf

上传者: bpingchang 2011-03-25 评分1 评论0 下载638 收藏10 阅读量1424 暂无简介 简介 举报

简介:本文档为《STL源码剖析_简体pdf》,可适用于IT书籍领域,主题内容包含TheAnnotatedSTLSource无限延伸你的视野STL源码剖析侯捷庖丁解牛恢恢乎游刃有余STL源码剖析TheAnnotatedSTLSou符等。

The A n n otated STL S o u rce 无限延伸你的视野 STL源码剖析 侯 捷 庖丁解牛 恢恢乎游刃有余 STL源码剖析 The Annotated STL Source (using SGI STL) 侯捷 峰 碁峰脑图书数据股份有限公司 SGISTL源码剖析 The Annotated STL Sources 向专家学习 强型检验、内存管理、算法、数 据结构、 及 STL各类组件之实作技术 侯 捷 着 源码之前 了无秘密 献给每一位对 GP/STL 有所渴望的人 天下大事 必作于细 – 侯 捷 – The Annotated STL Sources 庖丁解牛 侯捷自序 i 庖丁解牛1 侯捷自序 这本书的写作动机,纯属偶然。 2000 年下半,我开始为计划中的《泛型思维》一书陆续准备并热身。为了对泛型 编程技术以及 STL 实作技术有更深的体会,以便在讲述整个 STL 的架构与应用时 更能虎虎生风,我常常深入到 STL 源码去刨根究底。2001/02 的某一天,我突然 有所感触:既然花了大把精力看过 STL 源码,写了眉批,做了整理,何不把它再 加一点功夫,形成一个更完善的面貌后出版?对我个人而言,一份批注详尽的 STL 源码,价值不扉;如果我从中获益,一定也有许多能够从中获益。 这样的念头使我极度兴奋。剖析大架构本是侯捷的拿手,这个主题又可以和《泛 型 思维》相呼应。于是我便一头栽进去了。 我选择 SGI STL 作为剖析对象。这份实作版本的可读性极佳,运用极广,被选为 GNU C++ 的标准链接库,又开放自由运用。愈是细读 SGI STL 源码,愈令我震 惊抽象思考层次的落实、泛型编程的奥妙、及其效率考虑的绵密。不仅最为人广 泛 运用的各种数据结构(data structures)和算法(algorithms)在 STL 中有良好 的实 现,连内存配置与管理也都重重考虑了最佳效能。一切的一切,除了实现 软件积木 的高度复用性,让各种组件(components)得以灵活搭配运用,更考虑 了实用上的关键议题:效率。 1 庄子养生主:「彼节间有间,而刀刃者无厚;以无厚入有间,恢恢乎其于游刃必有 余矣。」侯捷不让,以此自况。 The Annotated STL Sources ii STL源码剖析 这本书不适合 C++ 初学者,不适合 Genericity(泛型技术)初学者,或 STL 初 学者。这本书也不适合带领你学习面向对象(Object Oriented)技术 — 是的,STL 与面向对象没有太多关连。本书前言清楚说明了书籍的定位和合适的读者,以及 各 类基础读物。如果你的 Generic Programming/STL 实力足以阅读本书所呈现的源 码,那么,恭喜,你踏了基度山岛,这儿有座大宝库等着你。源码之前了无 秘 密,你将看到 vector的实作、list的实作、heap的实作、deque的实作、RB- tree 的实作、hash-table 的实作、set/map 的实作;你将看到各种算法(排 序、搜 寻、排列组合、数据搬移与复制…)的实作;你甚至将看到底层的 memory pool 和 高阶抽象的 traits 机制的实作。那些数据结构、那些算法、那些重要观 念、那些 编程实务最重要最根本的珍宝,那些蜇伏已久彷佛已经还给老师的记 忆,将重 新在你的脑闪闪发光。 们常说,不要从轮子重新造起,要站在巨的肩膀。面对扮演轮子角色的这 些 STL 组件,我们是否有必要深究其设计原理或实作细节呢?答案因而异。从 应 用的角度思考,你不需要探索实作细节(然而相当程度认识底层实作,对实 务运 用有绝对的帮助)。从技术研究与本质提升的角度看,深究细节可以让你彻 底掌握 切;不论是为了重温数据结构和算法,或是想要扮演轮子角色,或是 想要进步 扩张别的轮子,都可因此获得深厚扎实的基础。 大事,必作于细! 但是别忘了,参观飞机工厂不能让你学得流体力学,也不能 让你学会开飞机。然 而如果你会开飞机又懂流体力学,参观飞机工厂可以带给你最大的乐趣和价值。 The Annotated STL Sources 庖解牛 y 侯捷自序 iii 我开玩笑对朋友说,这本书出版,给大学课程的「数据结构」和「算法」 两门授课老师出了个难题。几乎所有可能的作业题目(复杂度证明题除外),本 书 都有了详尽的解答。然而,如果学生能够从庞大的 SGI STL 源码干净抽出某 部份,加自己的包装,做为呈堂作业,也足以证明你有资格获得学分和高分。 事实,追踪流作品并于其吸取养份,远比自己关起门来写个流作品,价 值 高得多 — 我的确认为 99.99 % 的程序员所写的程序,在 SGI STL 面前都是 流 水平 -。 侯捷 2001/05/30 新竹 台湾 http://www.jjhou.com (繁体) http://jjhou.csdn.net (简体) jjhou@jjhou.com p.s. 以书互有定位,互有关联,彼此亦相呼应。为了不重复讲述相同的内容, 我会在适当时候提醒读者在哪本书获得更多数据: z 《多型与虚拟》,内容涵括:C++ 语法、语意、对象模型,面向对象精神, 小型 framework实作,OOP专家经验,设计样式(design patterns)导入。 z 《泛型思维》,内容涵括:语言层次(C++ templates 语法、Java generic 语 法、C++ 运算符重载),STL 原理介绍与架构分析,STL 现场重建,STL 深 度应用,STL扩充示范,泛型思考。 z 《STL源码剖析》,内容涵括:STL所有组件之实作技术和其背后原理解说。 The Annotated STL Sources iv STL源码剖析 The Annotated STL Sources 目 录 v 目录 庖解牛(侯捷自序) i 目录 v 前言 xvii 本书定位 xvii 合适的读者 xviii 最佳阅读方式 xviii 我所选择的剖析对象 xix 各章主题 xx编 译工具 xx 英术语的运用风格 xxi 英文术语采用原则 xxii 版面字形风格 xxiii 源码形式与载 xxiv 线服务 xxvi 推荐读物 xxvi 第 1章 STL 概论与版本简介 001 1.1 STL 概论 001 1.1.1 STL的历史 003 1.1.2 STL与 C++ 标准链接库 003 The Annotated STL Sources vi STL源码剖析 1.2 STL 六大组件 — 功能与运用 004 1.3 GNU源码开放精神 007 1.4 HP STL实作版本 009 1.5 P.J. Plauger STL实作版本 010 1.6 Rouge Wave STL实作版本 011 1.7 STLport 实作版本 012 1.8 SGI STL实作版本 总览 013 1.8.1 GNU C++ header 档案分布 014 1.8.2 SGI STL 档案分布与简介 016 STL 标准表头档(无扩展名) 017 C++ 标准规格定案前,HP规范的 STL表头档(扩展名 .h) 017 SGI STL 内部档案(SGI STL真正实作于此) 018 1.8.3 SGI STL 的组态设定(configuration) 019 1.9可能令你困惑的 C++ 语法 026 1.9.1 stl_config.h 的各种组态 027 组态 3:static template member 027 组态 5:class template partial specialization 028 组态 6:function template partial order 028 组态 7:explicit function template arguments 029 组态 8:member templates 029 组态 10:default template argument depend on previous template parameters 030 组态 11:non-type template parameters 031 组态:bound friend template function 032 组态:class template explicit specialization 034 1.9.2 暂时对象的产生与运用 036 1.9.3 静态常数整数成员在 class 内部直接初始化 037 in-class static const integral data member initialization The Annotated STL Sources 目 录 vii 1.9.4 increment/decrement/dereference 运算符 037 1.9.5 「前闭后开」区间表示法 [ ) 039 1.9.6 function call运算符(operator()) 040 第 2章 空间配置器(allocator) 043 2.1 空间配置器的标准接口 043 2.1.1 设计个阳春的空间配置器,JJ::allocator 044 2.2 具备次配置力(sub-allocation)的 SGI 空间配置器 047 2.2.1 SGI 标准的空间配置器,std::allocator 047 2.2.2 SGI 特殊的空间配置器,std::alloc 049 2.2.3 建构和解构基本工具:construct() 和 destroy() 051 2.2.4 空间的配置与释放,std::alloc 053 2.2.5 第级配置器 malloc_alloc_template 剖析 056 2.2.6 第级配置器 default_alloc_template剖析 059 2.2.7 空间配置函式 allocate() 062 2.2.8 空间释放函式 deallocate() 064 2.2.9 重新充填 free-lists 065 2.2.10 记忆池(memory pool) 066 2.3 内存基本处理工具 070 2.3.1 uninitialized_copy 070 2.3.2 uninitialized_fill 071 2.3.3 uninitialized_fill_n 071 第 3章 迭代器(iterators)概念与 traits 编程技法 079 3.1 迭代器设计思维 — STL关键所在 079 3.2 迭代器是种 smart pointer 080 3.3 迭代器相应型别(associated types) 084 3.4 Traits 编程技法 — STL源码门钥 085 The Annotated STL Sources viii STL源码剖析 Partial Specialzation(偏特化)的意义 086 3.4.1 迭代器相应型别之 value_type 090 3.4.2 迭代器相应型别之 difference_type 090 3.4.3 迭代器相应型别之 pointer_type 091 3.4.4 迭代器相应型别之 reference_type 091 3.4.5 迭代器相应型别之五 iterator_category 092 3.5 std::iteratorclass 的保证 099 3.6 iterator相关源码整理重列 101 3.7 SGI STL的私房菜: type_traits 103 第 4章 序列式容器(sequence containers) 113 4.1 容器概观与分类 113 4.1.1 序列式容器(sequence containers) 114 4.2 vector 115 4.2.1 vector 概述 115 4.2.2 vector 定义式摘要 115 4.2.3 vector 的迭代器 117 4.2.4 vector 的数据结构 118 4.2.5 vector 的建构与内存管理:constructor, push_back 119 4.2.6 vector 的元素操作:pop_back, erase, clear, insert 123 4.3 list 128 4.3.1 list 概述 128 4.3.2 list 的节点(node) 129 4.3.3 list 的迭代器 129 4.3.4 list 的数据结构 131 4.3.5 list 的建构与内存管理:constructor, push_back, insert 132 4.3.6 list 的元素操作:push_front, push_back, erase, pop_front, 136 pop_back, clear, remove, unique, splice, merge, reverse, sort The Annotated STL Sources 目 录 ix 4.4 deque 143 4.4.1 deque 概述 143 4.4.2 deque 的控器 144 4.4.3 deque 的迭代器 146 4.4.4 deque 的数据结构 150 4.4.5 deque 的建构与内存管理 :ctor, push_back, push_front 152 4.4.6 deque 的元素操作:pop_back, pop_front, clear, erase, insert 161 4.5 stack 167 4.5.1 stack 概述 167 4.5.2 stack 定义式完整列表 167 4.5.3 stack 没有迭代器 168 4.5.4 以 list 做为 stack 的底层容器 168 4.6 queue 169 4.6.1 queue 概述 169 4.6.2 queue 定义式完整列表 170 4.6.3 queue 没有迭代器 171 4.6.4 以 list 做为 queue 的底层容器 171 4.7 heap(隐性表述,implicit representation) 172 4.7.1 heap 概述 172 4.7.2 heap 算法 174 push_heap 174 pop_heap 176 sort_heap 178 make_heap 180 4.7.3 heap 没有迭代器 181 4.7.4 heap 测试实例 181 4.8 priority-queue 183 The Annotated STL Sources x STL源码剖析 4.8.1 priority-queue 概述 183 4.8.2 priority-queue 定义式完整列表 183 4.8.3 priority-queue 没有迭代器 185 4.8.4 priority-queue 测试实例 185 4.9 slist 186 4.9.1 slist 概述 186 4.9.2 slist 的节点 186 4.9.3 slist 的迭代器 188 4.9.4 slist 的数据结构 190 4.9.5 slist 的元素操作 191 第 5章 关系型容器(associated containers) 197 5.1 树的导览 199 5.1.1 元搜索树(binary search tree) 200 5.1.2 平衡元搜索树(balanced binary search tree) 203 5.1.3 AVL tree(Adelson-Velskii-Landis tree) 203 5.1.4 单旋转(Single Rotation) 205 5.1.5 双旋转(Double Rotation) 206 5.2 RB-tree(红黑树) 208 5.2.1 安插节点 209 5.2.2 个由而的程序 212 5.2.3 RB-tree 的节点设计 213 5.2.4 RB-tree 的迭代器 214 5.2.5 RB-tree 的数据结构 218 5.2.6 RB-tree 的建构与内存管理 221 5.2.7 RB-tree 的元素操作 223 元素安插动作 insert_equal 223 元素安插动作 insert_unique 224 The Annotated STL Sources 目 录 xi 真正的安插执行程序 insert 224 调整 RB-tree(旋转及改变颜色) 225 元素的搜寻 find 229 5.3 set 233 5.4 map 237 5.5 multiset 245 5.6 multimap 246 5.7 hashtable 247 5.7.1 hashtable 概述 247 5.7.2 hashtable 的桶子(buckets)与节点(nodes) 253 5.7.3 hashtable 的迭代器 254 5.7.4 hashtable 的数据结构 256 5.7.5 hashtable 的建构与内存管理 258 安插动作(insert)与表格重整(resize) 259 判知元素的落脚处(bkt_num) 262 复制(copy_from)和整体删除(clear) 263 5.7.6 hashtable 运用实例(find, count) 264 5.7.7 hash functions 268 5.8 hash_set 270 5.9 hash_map 275 5.10 hash_multiset 279 5.11 hash_multimap 282 第 6章 算法(algorithms) 285 6.1 算法概观 285 6.1.1 算法分析与复杂度表示 O( ) 286 6.1.2 STL算法总览 288 6.1.3 mutating algorithms — 会改变操作对象之值 291 The Annotated STL Sources xii STL源码剖析 6.1.4 nonmutating algorithms — 不改变操作对象之值 292 6.1.5 STL算法的般型式 292 6.2 算法的泛化过程 294 6.3 数值算法 <stl_numeric.h> 298 6.3.1 运用实例 298 6.3.2 accumulate 299 6.3.3 adjacent_difference 300 6.3.4 inner_product 301 6.3.5 partial_sum 303 6.3.6 power 304 6.3.7 itoa 305 6.4 基本算法 <stl_algobase.h> 305 6.4.1 运用实例 305 6.4.2 equal 307 fill 308 fill_n 308 iter_swap 309 lexicographical_compare 310 max, min 312 mismatch 313 swap 314 6.4.3 copy,强化效率无所不用其极 314 6.4.4 copy_backward 326 6.5 Set 相关算法(应用于已序区间) 328 6.5.1 set_union 331 6.5.2 set_intersection 333 6.5.3 set_difference 334 6.5.4 set_symmetric_difference 336 6.6 heap算法:make_heap, pop_heap, push_heap, sort_heap 338 6.7 其他算法 338 The Annotated STL Sources 目 录 xiii 6.7.1 单纯的数据处理 338 adjacent_find 343 count 344 count_if 344 find 345 find_if 345 find_end 345 find_first_of 348 for_each 348 generate 349 generate_n 349 includes (应用于已序区间) 349 max_element 352 merge (应用于已序区间) 352 min_element 354 partition 354 remove 357 remove_copy 357 remove_if 357 remove_copy_if 358 replace 359 replace_copy 359 replace_if 359 replace_copy_if 360 reverse 360 reverse_copy 361 rotate 361 rotate_copy 365 search 365 search_n 366 swap_ranges 369 transform 369 unique 370 unique_copy 371 6.7.2 lower_bound (应用于已序区间) 375 6.7.3 upper_bound (应用于已序区间) 377 6.7.4 binary_search (应用于已序区间) 379 6.7.5 next_permutation 380 6.7.6 prev_permutation 382 6.7.7 random_shuffle 383 The Annotated STL Sources xiv STL源码剖析 6.7.8 partial_sort/ partial_sort_copy 386 6.7.9 sort 389 6.7.10 equal_range(应用于已序区间) 400 6.7.11 inplace_merge(应用于已序区间) 403 6.7.12 nth_element 409 6.7.13 merge sort 411 第 7章 仿函式(functor,另名 函式物件 function objects) 413 7.1 仿函式(functor)概观 413 7.2 可配接(adaptable)的关键 415 7.1.1 unary_function 416 7.1.2 binary_function 417 7.3 算术类(Arithmetic)仿函式 418 plus, minus, multiplies, divides, modulus, negate, identity_element 7.4 相对关系类(Relational)仿函式 420 equal_to, not_equal_to, greater, greater_equal, less, less_equal 7.5 逻辑运算类(Logical)仿函式 422 logical_and, logical_or, logical_not 7.6 证同(identity)、选择(select)、投射(project) 423 identity, select1st, select2nd, project1st, project2nd 第 8章 配接器(adapter) 425 8.1 配接器之概观与分类 425 8.1.1 应用于容器,container adapters 425 8.1.2 应用于迭代器,iterator adapters 425 运用实例 427 8.1.3 应用于仿函式,functor adapters 428 运用实例 429 The Annotated STL Sources 8.2 container adapters 434 8.2.1 stack 434 8.2.1 queue 434 8.3 iterator adapters 435 8.3.1 insert iterators 435 8.3.2 reverse iterators 437 8.3.3 stream iterators (istream_iterator, ostream_iterator) 442 8.4 function adapters 448 8.4.2 對參數進行繫結(綁定):bind1st, bind2nd 451 8.4.3 用於函式合成:compose1, compose2(未納入標準) 453 8.4.4 用於函式指標:ptr_fun 454 8.4.5 用於成員函式指標:mem_fun, mem_fun_ref 456 附錄 A 參考資料與推薦讀物(Bibliography) 461 附錄 B 侯捷網站簡介 471 附錄 C STLport 的移植經驗(by 孟岩) 473 索引 481 目 录 xv 8.4.1 对传回值进行逻辑否定:not1, not2 450 The Annotated STL Sources xvi STL源码剖析 The Annotated STL Sources 前 言 xvii 前言 本书定位 C++ 标准链接库是个伟大的作品。它的出现,相当程度改变了 C++ 程序的风 貌以及学习模式1。纳入 STL(Standard Template Library)的同时,标准链接库的 所有组件,包括大家早已熟悉的 string、stream 等等,亦全部以 template 改写 过。整个标准链接库没有太多的 OO(Object Oriented),倒是无处不存在 GP (Generic Programming)。 C++ 标准链接库隶属 STL 范围者,粗估当在 80% 以。对软件开发而言,STL 是尖利兵,可以节省你许多时间。对编程技术而言,STL 是金柜石室 — 所有 与 编程工作最有直接密切关联的些最被广泛运用的数据结构和算法,STL 都 有实 作,并符合最佳(或极佳)效率。不仅如此,STL 的设计思维,把我们提升 到另 个思想高点,在那里,对象的耦合性(coupling)极低,复用性(reusability) 极 高,各种组件可以独立设计又可以灵活无罅结合在起。是的,STL 不仅仅 是链 接库,它其实具备 framework 格局,允许用户加自己的组件,与之融合 并用,是 个符合开放性封闭(Open-Closed)原则的链接库。 从应用角度来说,任何位 C++ 程序员都不应该舍弃现成、设计良好而又效率极 佳的标准链接库,却「入太庙每事问」事事物物从轮子造起 — 那对组件技术 及 软件工程是大嘲讽。然而对于个想要深度钻研 STL以便拥有扩充能力的, 1 请参考 Learning Standard C++ as a New Language, by Bjarne Stroustrup, C/C++ Users Journal 1999/05。译文 http://www.jjhou.com/programmer-4-learning-standard-cpp.htm The Annotated STL Sources xviii STL源码剖析 相当程度追踪 STL 源码是必要的功课。是的,对于个想要充实数据结构与演 算法等固有知识,并提升泛型编程技法的,「入太庙每事问」是必要的态度, 追 踪 STL源码则是提升功力的极佳路线。 想要良好运用 STL,我建议你看《The C++ Standard Library》 by Nicolai M. Josuttis; 想要严谨认识 STL 的整体架构和设计思维,以及 STL 的详细规格,我 建议你看 《Generic Programming and the STL》by Matthew H. Austern;想要从语法层面开 始, 学理与应用得兼,宏观与微观齐备,我建议你看《泛型思维》by 侯捷;想要 深入 STL 实作技法,窥大家风范,提升自己的编程功力,我建议你看你手这 本《STL 源码剖析》— 事实就在笔此刻,你也找不到任何本相同定位的书 2。 合适的读者 本书不适合 STL 初学者(当然更不适合 C++ 初学者)。本书不是面向对象 (Object Oriented)相关书籍。本书不适合用来学习 STL的各种应用。 对于那些希望深刻了解 STL 实作细节,俾得以提升对 STL 的扩充能力,或是希 望藉由观察 STL 源码,学习世界流程式员身手,并藉此彻底了解各种被广泛运 用之数据结构和算法的,本书最适合你。 最佳阅读方式 无论你对 STL 认识了多少,我都建议你第次阅读本书时,采循序渐进方式,遵 循书安排的章节先行浏览遍。视个功力的深浅,你可以或快或慢并依个 兴 趣或需要,深入其。初次阅读最好循序渐进,理由是,举个例子,所有容器 (containers)的定义式开头都会出现空间配置器(allocator)的运用,我可以 在最初数次提醒你空间配置器于第 2 章介绍过,但我无法遍及全书再再提醒 你。又例如,源码之时而会出现些全局函数调用动作,尤其是定义于 <stl_construct.h> 之用于物 件建构与解构 的基本函式,以及定义于 2 The C++ Standard Template Library, by P.J.Plauger, Alexander Al. Stepanov, Meng Lee, David R. Musser, Prentice Hall 2001/03,与本书定位相近,但在表现方式大有不同。 The Annotated STL Sources 前 言 xix <stl_uninitialized.h> 之用于记忆 体管理 的基本函式,以及定义于 <stl_algobase.h> 之的各种基本算法。如果那些全局函式已经在先前章节 介 绍过,我很难保证每次都提醒你 — 那是种顾此失彼、苦不堪言的劳役,并 且容 易造成阅读的累赘。 我所选择的剖析对象 本书名为《STL 源码剖析》,然而 STL 实作品百花齐放,不论就技术面或可读 性, 皆有高之分。选择份好的实作版本,就学习而言当然是极为重要的。我选 择 的剖析对象是声名最着,也是我个评价最高的个产品:SGI(Silicon Graphics Computer Systems, Inc.)版本。这份由 STL 之父 Alexander Stepanov、 经典书籍 《Generic Programming and the STL》作者 Matthew H. Austern、STL 耆宿 David Musser 等投注心力的 STL实作版本,不论在技术层次、源码组织、源码可读性 ,均有卓越的表现。这份产品被纳为 GNU C++ 标准链接库,任何皆可从网 际网络载 GNU C++ 编译程序,从而获得整份 STL 源码,并获得自由运用的 权 力(详见 1.8节)。 我所选用的是 cygnus3 C++ 2.91.57 for Windows版本。我并未刻意追求最新版本, 来书籍不可能永远呈现最新的软件版本 — 软件更新永远比书籍改版快速, 来 本书的根本目的在建立读者对于 STL 巨观架构和微观技术的掌握,以及源码的 阅 读能力,这种核心知识的形成与源码版本的关系不是那么唇齿相依,来SGI STL 实作品自从搭配 GNU C++2.8 以来已经十分稳固,变异极微,而我所选择的 2.91 版本,表现相当良好;来这个版本的源码比后来的版本更容易阅读,因为许多 内 部变量名称并不采用划线(underscore) — 划线在变数命名规范有其价 值,但到处都是划线则对大量阅读相当不利。 网络有个 STLport(http://www.stlport.org)站点,提供份以 SGI STL 为蓝本 的高度可移植性实作版本。本书附录 C 列有孟岩先生所写的文章,是份 STLport 移植到 Visual C++ 和 C++ Builder 的经验 谈。 3 关于 cygnus、GNU 源码开放精神、以及自由软件基金会(FSF),请见 1.3 节介绍。 The Annotated STL Sources xx 各章主题 STL源码剖析 本书假设你对 STL 已有基本认识和某种程度的运用经验。因此除了第章略作介 绍之外,立刻深入 STL 技术核心,并以 STL 六大组件(components)为章节之进 行依据。以是各章名称,这样的次序安排大抵可使每章所剖析的主题能够于 先 前章节获得充份的基础。当然,技术之间的关连错综复杂,不可能存在单纯 的线 性关系,这样的安排也只能说是尽最大努力。 第 1章 STL 概论与实作版本简介 第 2章 空间配置器(allocator) 第 3章 迭代器(iterators)概念与 traits 编程技法 第 4章 序列式容器(sequence containers) 第 5章 关系型容器(associated containers) 第 6章 算法(algorithms) 第 7章 仿函式 or函式物件(functors, or function objects) 第 8章 配接器(adapter) 编译工具 本书主要探索 SGI STL 源码,并提供少量测试程序。如果测试程序只做标准的 STL 动作,不涉及 SGI STL 实作细节,那么我会在 VC6、CB4、cygnus 2.91 for Windows等编译平台分别测试它们。 随着对 SGI STL 源码的掌握程度增加,我们可以大胆做些练习,将 SGI STL 内部 接口打开,或是修改某些 STL 组件,加少量输出动作,以观察组件的运作过 程。 这种情况,操练的对象既然是 SGI STL,我也就只使用 GNU C++ 来编译4。 4 SGI STL 事实是个高度可携产品,不限使用于 GNU C++。从它对各种编译程序的 环 境组态设定(1.8.3节)便可略知。网络有个 STLport 组织,不遗余力 将 SGI STL 移植到各种编译平台。请参阅本书附录 C。 The Annotated STL Sources 前 言 xxi 中英术语的运用风格 我曾经发表过篇《技术引导乎 文化传承乎》的文章,阐述我对专业计算机书籍 的 英术语运用态度。文章收录于侯捷网站 http://www.jjhou.com/article99-14.htm。 以简单叙述我的想法。 为了学术界和业界的习惯,也为了与全球科技接轨,并且也因为我所撰写的是供 专 业士阅读的书籍而非科普读物,我决定适量保留专业领域被朗朗口的英 文术 语。朗朗口与否,见仁见智,我以个阅历做为抉择依据。 做为个并非以英语为母语的族裔,我们对英文的阅读困难并不在单字,而在整 句 整段的文意。做为项技术的学习者,我们的困难并不在术语本身(那只是个 符 号),而在术语背后的技术意义。 熟悉并使用原文术语,至为重要。原因很简单,在科技领域里,你必须与全世界 接 轨。文技术书籍的价值不在于「建立本国文化」或「让它成为本道的 文 书」或「完全扫除英汉字典的需要」。文技术书籍的重要价值,在于引进技 术、 引导学习、扫平阅读障碍、增加学习效率。 绝大部份我所采用的英文术语都是名词。但极少数动词或形容词也有必要让读者 知 道原文(我会时而英并列,并使用斜体英文),原因是: z C++ 编译程序的错误讯息并未文化,万错误讯息出现以字眼: unresolved, instantiated, ambiguous, override,而编写程序的你却不熟悉或不懂 这些动词或形容词的技术意义,就不妙了。 z 有些动作关系到 library functions,而 library functions的名称并未文化-, 例 如 insert, delete, sort。因此视状况而定,我可能会选择使用英文。 z 如果某些术语关系到语言关键词,为了让读者有最直接的感受与联想,我会 采用原文,例如 static, private, protected, public, friend, inline, extern。 版面像一张破碎的脸? 大量英夹杂的结果,无法避免造成版面的「破碎」。但为了实现合宜的表达方 The Annotated STL Sources xxii STL源码剖析 式,牺牲版面的「全文化」在所难免。我将尽量以版面手法来达到视觉的顺 畅,换言之我将采用不同的字形来代表不同属性的术语。如果把英文术语视为 种 符号,这些英夹杂但带有特殊字形的版面,并不会比市面琳琅满目的许多 应用 软件图解使用手册来得突兀(而后者不是普遍为大众所喜爱吗-)。我所采 用的版 面,都已经过再试炼,过去以来获得许多读者的赞同。 英文术语采用原则 就我的观察,们对于英文词或文词的采用,隐隐有 个习惯:如果文词发 音简短(或至少不比英文词繁长)并且意义良好,那么就 比较有可能被业界用于 日常沟通;否则业界多半采用英文词。 例如,polymorphism 音节过多,所以意义良好的文词「多型」就比较有机会被 采用。例如,虚拟函式的发音不比 virtual function 繁长,所以使用这个文词的 也不少。「多载」或「重载」的发音比 overloaded 短得多,意义又正确,用的 也不少。 但此并非绝对法则,否则就不会有绝大多数工程师说 data member 而不说「数据 成员」、说 member function 而不说「成员函式」的情况了。 以是本书采用原文术语的几个简单原则。请注意,并没有绝对的实践,有时候 要 看文情况。同时,容我再强调次,这些都是基于我与业界和学界的接触 经验 而做的选择。 z 编程基础术语,采用文。例如:函式、指针、变量、常数。本书的英文术 语绝大部份都与 C++/OOP/GP(Generic Programming)相关。 z 简单而朗朗口的词,视情况可能直接使用英文:input, output, lvalue, rvalue... z 读者有必要认识的英文名词,不译:template, class, object, exception, scope, namespace。 z 长串、有特定意义、译名称拗口者,不译:explicit specialization, partial specialization, using declaration, using directive, exception specialization。 z 运算符名称,不译:copy assignment 运算符,member access 运算符, arrow 运算符,dot 运算符,address of 运算符,dereference 运算符... The Annotated STL Sources 前 言 xxiii z 业界惯用词,不译:constructor, destructor, data member, member function, reference。 z 涉及 C++ 关键词者,不译:public, private, protected, friend, static, z 意义良好,发音简短,流传颇众的译词,用之:多型(polymorphism),虚 拟 函式(virtual function)、泛型(genericity)… z 译后可能失掉原味而无法完全彰显原味者,英并列。 z 重要的动词、形容词,时而英并列:模棱两可(ambiguous), 决议(resolve), 改写(override),自变量推导(argument deduced),具现化(instantiated)。 z STL 专用术语:采用文,如迭代器(iterator)、容器(container)、仿函 式 (functor)、配接器(adapter)、空间配置器(allocator)。 z 数据结构专用术语:尽量采用英文,如 vector, list, deque, queue, stack, set, map, heap, binarysearchtree, RB-tree, AVL-tree, priorityqueue. 援用英文词,或不厌其烦英并列,获得的项重要福利是:本书得以英文做 为 索引凭借。 http://www.jjhou.com/terms.txt列有我个整理的份英繁简术语对照表。 版面字型风格 中文 z 本文:细明 9.5pt z 标题:华康粗圆 z 视觉加强:华康中黑 英文 z 般文字,Times New Roman, 9.5pt,例如:class, object, member function, data member, base class, derived class, private, protected, public, reference, template, namespace, function template, class template, local, global z 动词或形容词,Times New Roman斜体9.5pt,例如:resolve, ambiguous, override, instantiated z class名称,Lucida Console 8.5pt,例如:stack, list, map z 程序代码识别符号,Courier New 8.5pt,例如:int, min(SmallInt*, int) The Annotated STL Sources xxiv STL源码剖析 z 长串术语,Arial 9pt,例如:member initialization list, name return value, using directive, using declaration, pass by value, pass by reference, function try block, exception declaration, exception specification, stack unwinding, function object, class template specialization, class template partial specialization… z exception types 或 iterator types 或 iostream manipulators,Lucida Sans 9pt, 例 如: bad_alloc, back_inserter, boolalpha z 运算符名称及某些特殊动作,Footlight MT Light 9.5pt ,例如:copy assignment 运算符,dereference 运算符,address of 运算符,equality 运 算子,function call 运算符,constructor, destructor, default constructor, copy constructor, virtual destructor,memberwise assignment, memberwise initialization z 程序代码,Courier New 8.5pt,例如: #include <iostream> using namespace std; 要在整本书维护贯的字形风格而没有任何疏漏,很不容易,许多时候不同类 型 的术语搭配起来,就形成了不知该用哪种字形的困扰。排版者顾此失彼的可能 也不 是没有。因此,请注意,各种字形的运用,只是为了让您阅读时有比较好的 效果, 其本身并不具其他意义。局部的致性更重于全体的致性。 源码形式与下载 SGI STL 虽然是可读性最高的份 STL 源码,但其并没有对实作程序乃至于实 作技巧有什么文字批注,只偶而在档案最前面有点点总体说明。虽然其符号名 称 有不错的规划,真要仔细追踪源码,仍然旷日费时。因此本书不但在正文之 解说 其设计原则或实作技术,也直接在源码加许多批注。这些批注皆以蓝色 标示。 条件式编译(#ifdef)视同源码处理,函数调用动作以红色表示,巢状定 义亦以 红色表示。classes 名称、data members 名称和 member functions 名称大多以 粗体表 示。特别需要提醒的方(包括 template 预设自变量、长度很长的巢状式定 义) 则加灰阶底纹。例如: template <class T, class Alloc = alloc> // 默认使用 alloc 为配置器 class vector { public: typedef T value_type; The Annotated STL Sources 前 言 xxv typedef value_type* iterator; ... protected: // vector采用简单的线性连续空间。以两个迭代器 start和 end分别指向头尾, // 并以迭代器 end_of_storage指向容量尾端。容量可能比(尾-头)还大, // 多余的空间即备用空间。 iterator start; iterator finish; iterator end_of_storage; void fill_initialize(size_type n, const T& value) { start = allocate_and_fill(n, value); // 配置空间并设 初值 finish = start + n; // 调整水位 end_of_storage = finish; // 调整水位 } ... }; #ifdef STL_FUNCTION_TMPL_PARTIAL_ORDER template <class T, class Alloc> inline void swap(vector<T, Alloc>& x, vector<T, Alloc>& y) { x.swap(y); } #endif /* STL_FUNCTION_TMPL_PARTIAL_ORDER */ 又如: // 以配接器用来表示某个 Adaptable Binary Predicate 的逻辑负值 template <class Predicate> class binary_negate : public binary_function<typename Predicate::first_argument_type, typename Predicate::second_argument_type, bool> { ... }; 这些作法可能在某些方有少许例外(或遗漏),唯不变的原则就是尽量设法 让 读者眼抓住源码重点。花花绿绿的颜色乍见之或许不习惯,多看几眼你就 会喜 欢它-。这些经过批注的 SGI STL 源码以 Microsoft Word 97 文件格式,连同 SGI STL 源码,置于侯捷网站供自由载5。噢,是的,STL 涵盖面积广大,

该用户的其他资料

  • 名称/格式
  • 评分
  • 下载次数
  • 资料大小
  • 上传时间

用户评论

0/200
    暂无评论
上传我的资料

相关资料

资料评价:

/ 261
所需积分:0 立即下载
返回
顶部
举报
资料
关闭

温馨提示

感谢您对爱问共享资料的支持,精彩活动将尽快为您呈现,敬请期待!