爱问 爱问共享资料 爱问分类
首页 > > > STL源码剖析_简体.pdf

STL源码剖析_简体.pdf

STL源码剖析_简体.pdf

上传者: bpingchang
638次下载 0人收藏 暂无简介 简介 2011-03-25 举报

简介:当前资料暂无简介!

TheAnnotatedSTLSource无限延伸你的视野STL源码剖析侯捷庖丁解牛恢恢乎游刃有余STL源码剖析TheAnnotatedSTLSource(usingSGISTL)侯捷峰碁峰脑图书数据股份有限公司SGISTL源码剖析TheAnnotatedSTLSources向专家学习强型检验、内存管理、算法、数据结构、及STL各类组件之实作技术侯捷着源码之前了无秘密献给每一位对GP/STL有所渴望的人天下大事必作于细–侯捷–TheAnnotatedSTLSources庖丁解牛侯捷自序i庖丁解牛1侯捷自序这本书的写作动机,纯属偶然。2000年下半,我开始为计划中的《泛型思维》一书陆续准备并热身。为了对泛型编程技术以及STL实作技术有更深的体会,以便在讲述整个STL的架构与应用时更能虎虎生风,我常常深入到STL源码去刨根究底。2001/02的某一天,我突然有所感触:既然花了大把精力看过STL源码,写了眉批,做了整理,何不把它再加一点功夫,形成一个更完善的面貌后出版?对我个人而言,一份批注详尽的STL源码,价值不扉;如果我从中获益,一定也有许多能够从中获益。这样的念头使我极度兴奋。剖析大架构本是侯捷的拿手,这个主题又可以和《泛型思维》相呼应。于是我便一头栽进去了。我选择SGISTL作为剖析对象。这份实作版本的可读性极佳,运用极广,被选为GNUC++的标准链接库,又开放自由运用。愈是细读SGISTL源码,愈令我震惊抽象思考层次的落实、泛型编程的奥妙、及其效率考虑的绵密。不仅最为人广泛运用的各种数据结构(datastructures)和算法(algorithms)在STL中有良好的实现,连内存配置与管理也都重重考虑了最佳效能。一切的一切,除了实现软件积木的高度复用性,让各种组件(components)得以灵活搭配运用,更考虑了实用上的关键议题:效率。1庄子养生主:「彼节间有间,而刀刃者无厚;以无厚入有间,恢恢乎其于游刃必有余矣。」侯捷不让,以此自况。TheAnnotatedSTLSourcesiiSTL源码剖析这本书不适合C++初学者,不适合Genericity(泛型技术)初学者,或STL初学者。这本书也不适合带领你学习面向对象(ObjectOriented)技术—是的,STL与面向对象没有太多关连。本书前言清楚说明了书籍的定位和合适的读者,以及各类基础读物。如果你的GenericProgramming/STL实力足以阅读本书所呈现的源码,那么,恭喜,你踏了基度山岛,这儿有座大宝库等着你。源码之前了无秘密,你将看到vector的实作、list的实作、heap的实作、deque的实作、RB-tree的实作、hash-table的实作、set/map的实作;你将看到各种算法(排序、搜寻、排列组合、数据搬移与复制…)的实作;你甚至将看到底层的memorypool和高阶抽象的traits机制的实作。那些数据结构、那些算法、那些重要观念、那些编程实务最重要最根本的珍宝,那些蜇伏已久彷佛已经还给老师的记忆,将重新在你的脑闪闪发光。们常说,不要从轮子重新造起,要站在巨的肩膀。面对扮演轮子角色的这些STL组件,我们是否有必要深究其设计原理或实作细节呢?答案因而异。从应用的角度思考,你不需要探索实作细节(然而相当程度认识底层实作,对实务运用有绝对的帮助)。从技术研究与本质提升的角度看,深究细节可以让你彻底掌握切;不论是为了重温数据结构和算法,或是想要扮演轮子角色,或是想要进步扩张别的轮子,都可因此获得深厚扎实的基础。大事,必作于细!但是别忘了,参观飞机工厂不能让你学得流体力学,也不能让你学会开飞机。然而如果你会开飞机又懂流体力学,参观飞机工厂可以带给你最大的乐趣和价值。TheAnnotatedSTLSources庖解牛y侯捷自序iii我开玩笑对朋友说,这本书出版,给大学课程的「数据结构」和「算法」两门授课老师出了个难题。几乎所有可能的作业题目(复杂度证明题除外),本书都有了详尽的解答。然而,如果学生能够从庞大的SGISTL源码干净抽出某部份,加自己的包装,做为呈堂作业,也足以证明你有资格获得学分和高分。事实,追踪流作品并于其吸取养份,远比自己关起门来写个流作品,价值高得多—我的确认为99.99%的程序员所写的程序,在SGISTL面前都是流水平-。侯捷2001/05/30新竹台湾http://www.jjhou.com(繁体)http://jjhou.csdn.net(简体)jjhou@jjhou.comp.s.以书互有定位,互有关联,彼此亦相呼应。为了不重复讲述相同的内容,我会在适当时候提醒读者在哪本书获得更多数据:z《多型与虚拟》,内容涵括:C++语法、语意、对象模型,面向对象精神,小型framework实作,OOP专家经验,设计样式(designpatterns)导入。z《泛型思维》,内容涵括:语言层次(C++templates语法、Javageneric语法、C++运算符重载),STL原理介绍与架构分析,STL现场重建,STL深度应用,STL扩充示范,泛型思考。z《STL源码剖析》,内容涵括:STL所有组件之实作技术和其背后原理解说。TheAnnotatedSTLSourcesivSTL源码剖析TheAnnotatedSTLSources目录v目录庖解牛(侯捷自序)i目录v前言xvii本书定位xvii合适的读者xviii最佳阅读方式xviii我所选择的剖析对象xix各章主题xx编译工具xx英术语的运用风格xxi英文术语采用原则xxii版面字形风格xxiii源码形式与载xxiv线服务xxvi推荐读物xxvi第1章STL概论与版本简介0011.1STL概论0011.1.1STL的历史0031.1.2STL与C++标准链接库003TheAnnotatedSTLSourcesviSTL源码剖析1.2STL六大组件—功能与运用0041.3GNU源码开放精神0071.4HPSTL实作版本0091.5P.J.PlaugerSTL实作版本0101.6RougeWaveSTL实作版本0111.7STLport实作版本0121.8SGISTL实作版本总览0131.8.1GNUC++header档案分布0141.8.2SGISTL档案分布与简介016STL标准表头档(无扩展名)017C++标准规格定案前,HP规范的STL表头档(扩展名.h)017SGISTL内部档案(SGISTL真正实作于此)0181.8.3SGISTL的组态设定(configuration)0191.9可能令你困惑的C++语法0261.9.1stl_config.h的各种组态027组态3:statictemplatemember027组态5:classtemplatepartialspecialization028组态6:functiontemplatepartialorder028组态7:explicitfunctiontemplatearguments029组态8:membertemplates029组态10:defaulttemplateargumentdependonprevioustemplateparameters030组态11:non-typetemplateparameters031组态:boundfriendtemplatefunction032组态:classtemplateexplicitspecialization0341.9.2暂时对象的产生与运用0361.9.3静态常数整数成员在class内部直接初始化037in-classstaticconstintegraldatamemberinitializationTheAnnotatedSTLSources目录vii1.9.4increment/decrement/dereference运算符0371.9.5「前闭后开」区间表示法[)0391.9.6functioncall运算符(operator())040第2章空间配置器(allocator)0432.1空间配置器的标准接口0432.1.1设计个阳春的空间配置器,JJ::allocator0442.2具备次配置力(sub-allocation)的SGI空间配置器0472.2.1SGI标准的空间配置器,std::allocator0472.2.2SGI特殊的空间配置器,std::alloc0492.2.3建构和解构基本工具:construct()和destroy()0512.2.4空间的配置与释放,std::alloc0532.2.5第级配置器malloc_alloc_template剖析0562.2.6第级配置器default_alloc_template剖析0592.2.7空间配置函式allocate()0622.2.8空间释放函式deallocate()0642.2.9重新充填free-lists0652.2.10记忆池(memorypool)0662.3内存基本处理工具0702.3.1uninitialized_copy0702.3.2uninitialized_fill0712.3.3uninitialized_fill_n071第3章迭代器(iterators)概念与traits编程技法0793.1迭代器设计思维—STL关键所在0793.2迭代器是种smartpointer0803.3迭代器相应型别(associatedtypes)0843.4Traits编程技法—STL源码门钥085TheAnnotatedSTLSourcesviiiSTL源码剖析PartialSpecialzation(偏特化)的意义0863.4.1迭代器相应型别之value_type0903.4.2迭代器相应型别之difference_type0903.4.3迭代器相应型别之pointer_type0913.4.4迭代器相应型别之reference_type0913.4.5迭代器相应型别之五iterator_category0923.5std::iteratorclass的保证0993.6iterator相关源码整理重列1013.7SGISTL的私房菜:type_traits103第4章序列式容器(sequencecontainers)1134.1容器概观与分类1134.1.1序列式容器(sequencecontainers)1144.2vector1154.2.1vector概述1154.2.2vector定义式摘要1154.2.3vector的迭代器1174.2.4vector的数据结构1184.2.5vector的建构与内存管理:constructor,push_back1194.2.6vector的元素操作:pop_back,erase,clear,insert1234.3list1284.3.1list概述1284.3.2list的节点(node)1294.3.3list的迭代器1294.3.4list的数据结构1314.3.5list的建构与内存管理:constructor,push_back,insert1324.3.6list的元素操作:push_front,push_back,erase,pop_front,136pop_back,clear,remove,unique,splice,merge,reverse,sortTheAnnotatedSTLSources目录ix4.4deque1434.4.1deque概述1434.4.2deque的控器1444.4.3deque的迭代器1464.4.4deque的数据结构1504.4.5deque的建构与内存管理:ctor,push_back,push_front1524.4.6deque的元素操作:pop_back,pop_front,clear,erase,insert1614.5stack1674.5.1stack概述1674.5.2stack定义式完整列表1674.5.3stack没有迭代器1684.5.4以list做为stack的底层容器1684.6queue1694.6.1queue概述1694.6.2queue定义式完整列表1704.6.3queue没有迭代器1714.6.4以list做为queue的底层容器1714.7heap(隐性表述,implicitrepresentation)1724.7.1heap概述1724.7.2heap算法174push_heap174pop_heap176sort_heap178make_heap1804.7.3heap没有迭代器1814.7.4heap测试实例1814.8priority-queue183TheAnnotatedSTLSourcesxSTL源码剖析4.8.1priority-queue概述1834.8.2priority-queue定义式完整列表1834.8.3priority-queue没有迭代器1854.8.4priority-queue测试实例1854.9slist1864.9.1slist概述1864.9.2slist的节点1864.9.3slist的迭代器1884.9.4slist的数据结构1904.9.5slist的元素操作191第5章关系型容器(associatedcontainers)1975.1树的导览1995.1.1元搜索树(binarysearchtree)2005.1.2平衡元搜索树(balancedbinarysearchtree)2035.1.3AVLtree(Adelson-Velskii-Landistree)2035.1.4单旋转(SingleRotation)2055.1.5双旋转(DoubleRotation)2065.2RB-tree(红黑树)2085.2.1安插节点2095.2.2个由而的程序2125.2.3RB-tree的节点设计2135.2.4RB-tree的迭代器2145.2.5RB-tree的数据结构2185.2.6RB-tree的建构与内存管理2215.2.7RB-tree的元素操作223元素安插动作insert_equal223元素安插动作insert_unique224TheAnnotatedSTLSources目录xi真正的安插执行程序insert224调整RB-tree(旋转及改变颜色)225元素的搜寻find2295.3set2335.4map2375.5multiset2455.6multimap2465.7hashtable2475.7.1hashtable概述2475.7.2hashtable的桶子(buckets)与节点(nodes)2535.7.3hashtable的迭代器2545.7.4hashtable的数据结构2565.7.5hashtable的建构与内存管理258安插动作(insert)与表格重整(resize)259判知元素的落脚处(bkt_num)262复制(copy_from)和整体删除(clear)2635.7.6hashtable运用实例(find,count)2645.7.7hashfunctions2685.8hash_set2705.9hash_map2755.10hash_multiset2795.11hash_multimap282第6章算法(algorithms)2856.1算法概观2856.1.1算法分析与复杂度表示O()2866.1.2STL算法总览2886.1.3mutatingalgorithms—会改变操作对象之值291TheAnnotatedSTLSourcesxiiSTL源码剖析6.1.4nonmutatingalgorithms—不改变操作对象之值2926.1.5STL算法的般型式2926.2算法的泛化过程2946.3数值算法<stl_numeric.h>2986.3.1运用实例2986.3.2accumulate2996.3.3adjacent_difference3006.3.4inner_product3016.3.5partial_sum3036.3.6power3046.3.7itoa3056.4基本算法<stl_algobase.h>3056.4.1运用实例3056.4.2equal307fill308fill_n308iter_swap309lexicographical_compare310max,min312mismatch313swap3146.4.3copy,强化效率无所不用其极3146.4.4copy_backward3266.5Set相关算法(应用于已序区间)3286.5.1set_union3316.5.2set_intersection3336.5.3set_difference3346.5.4set_symmetric_difference3366.6heap算法:make_heap,pop_heap,push_heap,sort_heap3386.7其他算法338TheAnnotatedSTLSources目录xiii6.7.1单纯的数据处理338adjacent_find343count344count_if344find345find_if345find_end345find_first_of348for_each348generate349generate_n349includes(应用于已序区间)349max_element352merge(应用于已序区间)352min_element354partition354remove357remove_copy357remove_if357remove_copy_if358replace359replace_copy359replace_if359replace_copy_if360reverse360reverse_copy361rotate361rotate_copy365search365search_n366swap_ranges369transform369unique370unique_copy3716.7.2lower_bound(应用于已序区间)3756.7.3upper_bound(应用于已序区间)3776.7.4binary_search(应用于已序区间)3796.7.5next_permutation3806.7.6prev_permutation3826.7.7random_shuffle383TheAnnotatedSTLSourcesxivSTL源码剖析6.7.8partial_sort/partial_sort_copy3866.7.9sort3896.7.10equal_range(应用于已序区间)4006.7.11inplace_merge(应用于已序区间)4036.7.12nth_element4096.7.13mergesort411第7章仿函式(functor,另名函式物件functionobjects)4137.1仿函式(functor)概观4137.2可配接(adaptable)的关键4157.1.1unary_function4167.1.2binary_function4177.3算术类(Arithmetic)仿函式418plus,minus,multiplies,divides,modulus,negate,identity_element7.4相对关系类(Relational)仿函式420equal_to,not_equal_to,greater,greater_equal,less,less_equal7.5逻辑运算类(Logical)仿函式422logical_and,logical_or,logical_not7.6证同(identity)、选择(select)、投射(project)423identity,select1st,select2nd,project1st,project2nd第8章配接器(adapter)4258.1配接器之概观与分类4258.1.1应用于容器,containeradapters4258.1.2应用于迭代器,iteratoradapters425运用实例4278.1.3应用于仿函式,functoradapters428运用实例429TheAnnotatedSTLSources8.2containeradapters4348.2.1stack4348.2.1queue4348.3iteratoradapters4358.3.1insertiterators4358.3.2reverseiterators4378.3.3streamiterators(istream_iterator,ostream_iterator)4428.4functionadapters4488.4.2對參數進行繫結(綁定):bind1st,bind2nd4518.4.3用於函式合成:compose1,compose2(未納入標準)4538.4.4用於函式指標:ptr_fun4548.4.5用於成員函式指標:mem_fun,mem_fun_ref456附錄A參考資料與推薦讀物(Bibliography)461附錄B侯捷網站簡介471附錄CSTLport的移植經驗(by孟岩)473索引481目录xv8.4.1对传回值进行逻辑否定:not1,not2450TheAnnotatedSTLSourcesxviSTL源码剖析TheAnnotatedSTLSources前言xvii前言本书定位C++标准链接库是个伟大的作品。它的出现,相当程度改变了C++程序的风貌以及学习模式1。纳入STL(StandardTemplateLibrary)的同时,标准链接库的所有组件,包括大家早已熟悉的string、stream等等,亦全部以template改写过。整个标准链接库没有太多的OO(ObjectOriented),倒是无处不存在GP(GenericProgramming)。C++标准链接库隶属STL范围者,粗估当在80%以。对软件开发而言,STL是尖利兵,可以节省你许多时间。对编程技术而言,STL是金柜石室—所有与编程工作最有直接密切关联的些最被广泛运用的数据结构和算法,STL都有实作,并符合最佳(或极佳)效率。不仅如此,STL的设计思维,把我们提升到另个思想高点,在那里,对象的耦合性(coupling)极低,复用性(reusability)极高,各种组件可以独立设计又可以灵活无罅结合在起。是的,STL不仅仅是链接库,它其实具备framework格局,允许用户加自己的组件,与之融合并用,是个符合开放性封闭(Open-Closed)原则的链接库。从应用角度来说,任何位C++程序员都不应该舍弃现成、设计良好而又效率极佳的标准链接库,却「入太庙每事问」事事物物从轮子造起—那对组件技术及软件工程是大嘲讽。然而对于个想要深度钻研STL以便拥有扩充能力的,1请参考LearningStandardC++asaNewLanguage,byBjarneStroustrup,C/C++UsersJournal1999/05。译文http://www.jjhou.com/programmer-4-learning-standard-cpp.htmTheAnnotatedSTLSourcesxviiiSTL源码剖析相当程度追踪STL源码是必要的功课。是的,对于个想要充实数据结构与演算法等固有知识,并提升泛型编程技法的,「入太庙每事问」是必要的态度,追踪STL源码则是提升功力的极佳路线。想要良好运用STL,我建议你看《TheC++StandardLibrary》byNicolaiM.Josuttis;想要严谨认识STL的整体架构和设计思维,以及STL的详细规格,我建议你看《GenericProgrammingandtheSTL》byMatthewH.Austern;想要从语法层面开始,学理与应用得兼,宏观与微观齐备,我建议你看《泛型思维》by侯捷;想要深入STL实作技法,窥大家风范,提升自己的编程功力,我建议你看你手这本《STL源码剖析》—事实就在笔此刻,你也找不到任何本相同定位的书2。合适的读者本书不适合STL初学者(当然更不适合C++初学者)。本书不是面向对象(ObjectOriented)相关书籍。本书不适合用来学习STL的各种应用。对于那些希望深刻了解STL实作细节,俾得以提升对STL的扩充能力,或是希望藉由观察STL源码,学习世界流程式员身手,并藉此彻底了解各种被广泛运用之数据结构和算法的,本书最适合你。最佳阅读方式无论你对STL认识了多少,我都建议你第次阅读本书时,采循序渐进方式,遵循书安排的章节先行浏览遍。视个功力的深浅,你可以或快或慢并依个兴趣或需要,深入其。初次阅读最好循序渐进,理由是,举个例子,所有容器(containers)的定义式开头都会出现空间配置器(allocator)的运用,我可以在最初数次提醒你空间配置器于第2章介绍过,但我无法遍及全书再再提醒你。又例如,源码之时而会出现些全局函数调用动作,尤其是定义于<stl_construct.h>之用于物件建构与解构的基本函式,以及定义于2TheC++StandardTemplateLibrary,byP.J.Plauger,AlexanderAl.Stepanov,MengLee,DavidR.Musser,PrenticeHall2001/03,与本书定位相近,但在表现方式大有不同。TheAnnotatedSTLSources前言xix<stl_uninitialized.h>之用于记忆体管理的基本函式,以及定义于<stl_algobase.h>之的各种基本算法。如果那些全局函式已经在先前章节介绍过,我很难保证每次都提醒你—那是种顾此失彼、苦不堪言的劳役,并且容易造成阅读的累赘。我所选择的剖析对象本书名为《STL源码剖析》,然而STL实作品百花齐放,不论就技术面或可读性,皆有高之分。选择份好的实作版本,就学习而言当然是极为重要的。我选择的剖析对象是声名最着,也是我个评价最高的个产品:SGI(SiliconGraphicsComputerSystems,Inc.)版本。这份由STL之父AlexanderStepanov、经典书籍《GenericProgrammingandtheSTL》作者MatthewH.Austern、STL耆宿DavidMusser等投注心力的STL实作版本,不论在技术层次、源码组织、源码可读性,均有卓越的表现。这份产品被纳为GNUC++标准链接库,任何皆可从网际网络载GNUC++编译程序,从而获得整份STL源码,并获得自由运用的权力(详见1.8节)。我所选用的是cygnus3C++2.91.57forWindows版本。我并未刻意追求最新版本,来书籍不可能永远呈现最新的软件版本—软件更新永远比书籍改版快速,来本书的根本目的在建立读者对于STL巨观架构和微观技术的掌握,以及源码的阅读能力,这种核心知识的形成与源码版本的关系不是那么唇齿相依,来SGISTL实作品自从搭配GNUC++2.8以来已经十分稳固,变异极微,而我所选择的2.91版本,表现相当良好;来这个版本的源码比后来的版本更容易阅读,因为许多内部变量名称并不采用划线(underscore)—划线在变数命名规范有其价值,但到处都是划线则对大量阅读相当不利。网络有个STLport(http://www.stlport.org)站点,提供份以SGISTL为蓝本的高度可移植性实作版本。本书附录C列有孟岩先生所写的文章,是份STLport移植到VisualC++和C++Builder的经验谈。3关于cygnus、GNU源码开放精神、以及自由软件基金会(FSF),请见1.3节介绍。TheAnnotatedSTLSourcesxx各章主题STL源码剖析本书假设你对STL已有基本认识和某种程度的运用经验。因此除了第章略作介绍之外,立刻深入STL技术核心,并以STL六大组件(components)为章节之进行依据。以是各章名称,这样的次序安排大抵可使每章所剖析的主题能够于先前章节获得充份的基础。当然,技术之间的关连错综复杂,不可能存在单纯的线性关系,这样的安排也只能说是尽最大努力。第1章STL概论与实作版本简介第2章空间配置器(allocator)第3章迭代器(iterators)概念与traits编程技法第4章序列式容器(sequencecontainers)第5章关系型容器(associatedcontainers)第6章算法(algorithms)第7章仿函式or函式物件(functors,orfunctionobjects)第8章配接器(adapter)编译工具本书主要探索SGISTL源码,并提供少量测试程序。如果测试程序只做标准的STL动作,不涉及SGISTL实作细节,那么我会在VC6、CB4、cygnus2.91forWindows等编译平台分别测试它们。随着对SGISTL源码的掌握程度增加,我们可以大胆做些练习,将SGISTL内部接口打开,或是修改某些STL组件,加少量输出动作,以观察组件的运作过程。这种情况,操练的对象既然是SGISTL,我也就只使用GNUC++来编译4。4SGISTL事实是个高度可携产品,不限使用于GNUC++。从它对各种编译程序的环境组态设定(1.8.3节)便可略知。网络有个STLport组织,不遗余力将SGISTL移植到各种编译平台。请参阅本书附录C。TheAnnotatedSTLSources前言xxi中英术语的运用风格我曾经发表过篇《技术引导乎文化传承乎》的文章,阐述我对专业计算机书籍的英术语运用态度。文章收录于侯捷网站http://www.jjhou.com/article99-14.htm。以简单叙述我的想法。为了学术界和业界的习惯,也为了与全球科技接轨,并且也因为我所撰写的是供专业士阅读的书籍而非科普读物,我决定适量保留专业领域被朗朗口的英文术语。朗朗口与否,见仁见智,我以个阅历做为抉择依据。做为个并非以英语为母语的族裔,我们对英文的阅读困难并不在单字,而在整句整段的文意。做为项技术的学习者,我们的困难并不在术语本身(那只是个符号),而在术语背后的技术意义。熟悉并使用原文术语,至为重要。原因很简单,在科技领域里,你必须与全世界接轨。文技术书籍的价值不在于「建立本国文化」或「让它成为本道的文书」或「完全扫除英汉字典的需要」。文技术书籍的重要价值,在于引进技术、引导学习、扫平阅读障碍、增加学习效率。绝大部份我所采用的英文术语都是名词。但极少数动词或形容词也有必要让读者知道原文(我会时而英并列,并使用斜体英文),原因是:zC++编译程序的错误讯息并未文化,万错误讯息出现以字眼:unresolved,instantiated,ambiguous,override,而编写程序的你却不熟悉或不懂这些动词或形容词的技术意义,就不妙了。z有些动作关系到libraryfunctions,而libraryfunctions的名称并未文化-,例如insert,delete,sort。因此视状况而定,我可能会选择使用英文。z如果某些术语关系到语言关键词,为了让读者有最直接的感受与联想,我会采用原文,例如static,private,protected,public,friend,inline,extern。版面像一张破碎的脸?大量英夹杂的结果,无法避免造成版面的「破碎」。但为了实现合宜的表达方TheAnnotatedSTLSourcesxxiiSTL源码剖析式,牺牲版面的「全文化」在所难免。我将尽量以版面手法来达到视觉的顺畅,换言之我将采用不同的字形来代表不同属性的术语。如果把英文术语视为种符号,这些英夹杂但带有特殊字形的版面,并不会比市面琳琅满目的许多应用软件图解使用手册来得突兀(而后者不是普遍为大众所喜爱吗-)。我所采用的版面,都已经过再试炼,过去以来获得许多读者的赞同。英文术语采用原则就我的观察,们对于英文词或文词的采用,隐隐有个习惯:如果文词发音简短(或至少不比英文词繁长)并且意义良好,那么就比较有可能被业界用于日常沟通;否则业界多半采用英文词。例如,polymorphism音节过多,所以意义良好的文词「多型」就比较有机会被采用。例如,虚拟函式的发音不比virtualfunction繁长,所以使用这个文词的也不少。「多载」或「重载」的发音比overloaded短得多,意义又正确,用的也不少。但此并非绝对法则,否则就不会有绝大多数工程师说datamember而不说「数据成员」、说memberfunction而不说「成员函式」的情况了。以是本书采用原文术语的几个简单原则。请注意,并没有绝对的实践,有时候要看文情况。同时,容我再强调次,这些都是基于我与业界和学界的接触经验而做的选择。z编程基础术语,采用文。例如:函式、指针、变量、常数。本书的英文术语绝大部份都与C++/OOP/GP(GenericProgramming)相关。z简单而朗朗口的词,视情况可能直接使用英文:input,output,lvalue,rvalue...z读者有必要认识的英文名词,不译:template,class,object,exception,scope,namespace。z长串、有特定意义、译名称拗口者,不译:explicitspecialization,partialspecialization,usingdeclaration,usingdirective,exceptionspecialization。z运算符名称,不译:copyassignment运算符,memberaccess运算符,arrow运算符,dot运算符,addressof运算符,dereference运算符...TheAnnotatedSTLSources前言xxiiiz业界惯用词,不译:constructor,destructor,datamember,memberfunction,reference。z涉及C++关键词者,不译:public,private,protected,friend,static,z意义良好,发音简短,流传颇众的译词,用之:多型(polymorphism),虚拟函式(virtualfunction)、泛型(genericity)…z译后可能失掉原味而无法完全彰显原味者,英并列。z重要的动词、形容词,时而英并列:模棱两可(ambiguous),决议(resolve),改写(override),自变量推导(argumentdeduced),具现化(instantiated)。zSTL专用术语:采用文,如迭代器(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.5ptz标题:华康粗圆z视觉加强:华康中黑英文z般文字,TimesNewRoman,9.5pt,例如:class,object,memberfunction,datamember,baseclass,derivedclass,private,protected,public,reference,template,namespace,functiontemplate,classtemplate,local,globalz动词或形容词,TimesNewRoman斜体9.5pt,例如:resolve,ambiguous,override,instantiatedzclass名称,LucidaConsole8.5pt,例如:stack,list,mapz程序代码识别符号,CourierNew8.5pt,例如:int,min(SmallInt*,int)TheAnnotatedSTLSourcesxxivSTL源码剖析z长串术语,Arial9pt,例如:memberinitializationlist,namereturnvalue,usingdirective,usingdeclaration,passbyvalue,passbyreference,functiontryblock,exceptiondeclaration,exceptionspecification,stackunwinding,functionobject,classtemplatespecialization,classtemplatepartialspecialization…zexceptiontypes或iteratortypes或iostreammanipulators,LucidaSans9pt,例如:bad_alloc,back_inserter,boolalphaz运算符名称及某些特殊动作,FootlightMTLight9.5pt,例如:copyassignment运算符,dereference运算符,addressof运算符,equality运算子,functioncall运算符,constructor,destructor,defaultconstructor,copyconstructor,virtualdestructor,memberwiseassignment,memberwiseinitializationz程序代码,CourierNew8.5pt,例如:#include<iostream>usingnamespacestd;要在整本书维护贯的字形风格而没有任何疏漏,很不容易,许多时候不同类型的术语搭配起来,就形成了不知该用哪种字形的困扰。排版者顾此失彼的可能也不是没有。因此,请注意,各种字形的运用,只是为了让您阅读时有比较好的效果,其本身并不具其他意义。局部的致性更重于全体的致性。源码形式与下载SGISTL虽然是可读性最高的份STL源码,但其并没有对实作程序乃至于实作技巧有什么文字批注,只偶而在档案最前面有点点总体说明。虽然其符号名称有不错的规划,真要仔细追踪源码,仍然旷日费时。因此本书不但在正文之解说其设计原则或实作技术,也直接在源码加许多批注。这些批注皆以蓝色标示。条件式编译(#ifdef)视同源码处理,函数调用动作以红色表示,巢状定义亦以红色表示。classes名称、datamembers名称和memberfunctions名称大多以粗体表示。特别需要提醒的方(包括template预设自变量、长度很长的巢状式定义)则加灰阶底纹。例如:template<classT,classAlloc=alloc>//默认使用alloc为配置器classvector{public:typedefTvalue_type;TheAnnotatedSTLSources前言xxvtypedefvalue_type*iterator;...protected://vector采用简单的线性连续空间。以两个迭代器start和end分别指向头尾,//并以迭代器end_of_storage指向容量尾端。容量可能比(尾-头)还大,//多余的空间即备用空间。iteratorstart;iteratorfinish;iteratorend_of_storage;voidfill_initialize(size_typen,constT&value){start=allocate_and_fill(n,value);//配置空间并设初值finish=start+n;//调整水位end_of_storage=finish;//调整水位}...};#ifdefSTL_FUNCTION_TMPL_PARTIAL_ORDERtemplate<classT,classAlloc>inlinevoidswap(vector<T,Alloc>&x,vector<T,Alloc>&y){x.swap(y);}#endif/*STL_FUNCTION_TMPL_PARTIAL_ORDER*/又如://以配接器用来表示某个AdaptableBinaryPredicate的逻辑负值template<classPredicate>classbinary_negate:publicbinary_function<typenamePredicate::first_argument_type,typenamePredicate::second_argument_type,bool>{...};这些作法可能在某些方有少许例外(或遗漏),唯不变的原则就是尽量设法让读者眼抓住源码重点。花花绿绿的颜色乍见之或许不习惯,多看几眼你就会喜欢它-。这些经过批注的SGISTL源码以MicrosoftWord97文件格式,连同SGISTL源码,置于侯捷网站供自由载5。噢,是的,STL涵盖面积广大,

STL源码剖析_简体.pdf

STL源码剖析_简体.pdf

上传者: bpingchang
638次下载 0人收藏 暂无简介 简介 2011-03-25 举报

简介:当前资料暂无简介!

TheAnnotatedSTLSource无限延伸你的视野STL源码剖析侯捷庖丁解牛恢恢乎游刃有余STL源码剖析TheAnnotatedSTLSource(usingSGISTL)侯捷峰碁峰脑图书数据股份有限公司SGISTL源码剖析TheAnnotatedSTLSources向专家学习强型检验、内存管理、算法、数据结构、及STL各类组件之实作技术侯捷着源码之前了无秘密献给每一位对GP/STL有所渴望的人天下大事必作于细–侯捷–TheAnnotatedSTLSources庖丁解牛侯捷自序i庖丁解牛1侯捷自序这本书的写作动机,纯属偶然。2000年下半,我开始为计划中的《泛型思维》一书陆续准备并热身。为了对泛型编程技术以及STL实作技术有更深的体会,以便在讲述整个STL的架构与应用时更能虎虎生风,我常常深入到STL源码去刨根究底。2001/02的某一天,我突然有所感触:既然花了大把精力看过STL源码,写了眉批,做了整理,何不把它再加一点功夫,形成一个更完善的面貌后出版?对我个人而言,一份批注详尽的STL源码,价值不扉;如果我从中获益,一定也有许多能够从中获益。这样的念头使我极度兴奋。剖析大架构本是侯捷的拿手,这个主题又可以和《泛型思维》相呼应。于是我便一头栽进去了。我选择SGISTL作为剖析对象。这份实作版本的可读性极佳,运用极广,被选为GNUC++的标准链接库,又开放自由运用。愈是细读SGISTL源码,愈令我震惊抽象思考层次的落实、泛型编程的奥妙、及其效率考虑的绵密。不仅最为人广泛运用的各种数据结构(datastructures)和算法(algorithms)在STL中有良好的实现,连内存配置与管理也都重重考虑了最佳效能。一切的一切,除了实现软件积木的高度复用性,让各种组件(components)得以灵活搭配运用,更考虑了实用上的关键议题:效率。1庄子养生主:「彼节间有间,而刀刃者无厚;以无厚入有间,恢恢乎其于游刃必有余矣。」侯捷不让,以此自况。TheAnnotatedSTLSourcesiiSTL源码剖析这本书不适合C++初学者,不适合Genericity(泛型技术)初学者,或STL初学者。这本书也不适合带领你学习面向对象(ObjectOriented)技术—是的,STL与面向对象没有太多关连。本书前言清楚说明了书籍的定位和合适的读者,以及各类基础读物。如果你的GenericProgramming/STL实力足以阅读本书所呈现的源码,那么,恭喜,你踏了基度山岛,这儿有座大宝库等着你。源码之前了无秘密,你将看到vector的实作、list的实作、heap的实作、deque的实作、RB-tree的实作、hash-table的实作、set/map的实作;你将看到各种算法(排序、搜寻、排列组合、数据搬移与复制…)的实作;你甚至将看到底层的memorypool和高阶抽象的traits机制的实作。那些数据结构、那些算法、那些重要观念、那些编程实务最重要最根本的珍宝,那些蜇伏已久彷佛已经还给老师的记忆,将重新在你的脑闪闪发光。们常说,不要从轮子重新造起,要站在巨的肩膀。面对扮演轮子角色的这些STL组件,我们是否有必要深究其设计原理或实作细节呢?答案因而异。从应用的角度思考,你不需要探索实作细节(然而相当程度认识底层实作,对实务运用有绝对的帮助)。从技术研究与本质提升的角度看,深究细节可以让你彻底掌握切;不论是为了重温数据结构和算法,或是想要扮演轮子角色,或是想要进步扩张别的轮子,都可因此获得深厚扎实的基础。大事,必作于细!但是别忘了,参观飞机工厂不能让你学得流体力学,也不能让你学会开飞机。然而如果你会开飞机又懂流体力学,参观飞机工厂可以带给你最大的乐趣和价值。TheAnnotatedSTLSources庖解牛y侯捷自序iii我开玩笑对朋友说,这本书出版,给大学课程的「数据结构」和「算法」两门授课老师出了个难题。几乎所有可能的作业题目(复杂度证明题除外),本书都有了详尽的解答。然而,如果学生能够从庞大的SGISTL源码干净抽出某部份,加自己的包装,做为呈堂作业,也足以证明你有资格获得学分和高分。事实,追踪流作品并于其吸取养份,远比自己关起门来写个流作品,价值高得多—我的确认为99.99%的程序员所写的程序,在SGISTL面前都是流水平-。侯捷2001/05/30新竹台湾http://www.jjhou.com(繁体)http://jjhou.csdn.net(简体)jjhou@jjhou.comp.s.以书互有定位,互有关联,彼此亦相呼应。为了不重复讲述相同的内容,我会在适当时候提醒读者在哪本书获得更多数据:z《多型与虚拟》,内容涵括:C++语法、语意、对象模型,面向对象精神,小型framework实作,OOP专家经验,设计样式(designpatterns)导入。z《泛型思维》,内容涵括:语言层次(C++templates语法、Javageneric语法、C++运算符重载),STL原理介绍与架构分析,STL现场重建,STL深度应用,STL扩充示范,泛型思考。z《STL源码剖析》,内容涵括:STL所有组件之实作技术和其背后原理解说。TheAnnotatedSTLSourcesivSTL源码剖析TheAnnotatedSTLSources目录v目录庖解牛(侯捷自序)i目录v前言xvii本书定位xvii合适的读者xviii最佳阅读方式xviii我所选择的剖析对象xix各章主题xx编译工具xx英术语的运用风格xxi英文术语采用原则xxii版面字形风格xxiii源码形式与载xxiv线服务xxvi推荐读物xxvi第1章STL概论与版本简介0011.1STL概论0011.1.1STL的历史0031.1.2STL与C++标准链接库003TheAnnotatedSTLSourcesviSTL源码剖析1.2STL六大组件—功能与运用0041.3GNU源码开放精神0071.4HPSTL实作版本0091.5P.J.PlaugerSTL实作版本0101.6RougeWaveSTL实作版本0111.7STLport实作版本0121.8SGISTL实作版本总览0131.8.1GNUC++header档案分布0141.8.2SGISTL档案分布与简介016STL标准表头档(无扩展名)017C++标准规格定案前,HP规范的STL表头档(扩展名.h)017SGISTL内部档案(SGISTL真正实作于此)0181.8.3SGISTL的组态设定(configuration)0191.9可能令你困惑的C++语法0261.9.1stl_config.h的各种组态027组态3:statictemplatemember027组态5:classtemplatepartialspecialization028组态6:functiontemplatepartialorder028组态7:explicitfunctiontemplatearguments029组态8:membertemplates029组态10:defaulttemplateargumentdependonprevioustemplateparameters030组态11:non-typetemplateparameters031组态:boundfriendtemplatefunction032组态:classtemplateexplicitspecialization0341.9.2暂时对象的产生与运用0361.9.3静态常数整数成员在class内部直接初始化037in-classstaticconstintegraldatamemberinitializationTheAnnotatedSTLSources目录vii1.9.4increment/decrement/dereference运算符0371.9.5「前闭后开」区间表示法[)0391.9.6functioncall运算符(operator())040第2章空间配置器(allocator)0432.1空间配置器的标准接口0432.1.1设计个阳春的空间配置器,JJ::allocator0442.2具备次配置力(sub-allocation)的SGI空间配置器0472.2.1SGI标准的空间配置器,std::allocator0472.2.2SGI特殊的空间配置器,std::alloc0492.2.3建构和解构基本工具:construct()和destroy()0512.2.4空间的配置与释放,std::alloc0532.2.5第级配置器malloc_alloc_template剖析0562.2.6第级配置器default_alloc_template剖析0592.2.7空间配置函式allocate()0622.2.8空间释放函式deallocate()0642.2.9重新充填free-lists0652.2.10记忆池(memorypool)0662.3内存基本处理工具0702.3.1uninitialized_copy0702.3.2uninitialized_fill0712.3.3uninitialized_fill_n071第3章迭代器(iterators)概念与traits编程技法0793.1迭代器设计思维—STL关键所在0793.2迭代器是种smartpointer0803.3迭代器相应型别(associatedtypes)0843.4Traits编程技法—STL源码门钥085TheAnnotatedSTLSourcesviiiSTL源码剖析PartialSpecialzation(偏特化)的意义0863.4.1迭代器相应型别之value_type0903.4.2迭代器相应型别之difference_type0903.4.3迭代器相应型别之pointer_type0913.4.4迭代器相应型别之reference_type0913.4.5迭代器相应型别之五iterator_category0923.5std::iteratorclass的保证0993.6iterator相关源码整理重列1013.7SGISTL的私房菜:type_traits103第4章序列式容器(sequencecontainers)1134.1容器概观与分类1134.1.1序列式容器(sequencecontainers)1144.2vector1154.2.1vector概述1154.2.2vector定义式摘要1154.2.3vector的迭代器1174.2.4vector的数据结构1184.2.5vector的建构与内存管理:constructor,push_back1194.2.6vector的元素操作:pop_back,erase,clear,insert1234.3list1284.3.1list概述1284.3.2list的节点(node)1294.3.3list的迭代器1294.3.4list的数据结构1314.3.5list的建构与内存管理:constructor,push_back,insert1324.3.6list的元素操作:push_front,push_back,erase,pop_front,136pop_back,clear,remove,unique,splice,merge,reverse,sortTheAnnotatedSTLSources目录ix4.4deque1434.4.1deque概述1434.4.2deque的控器1444.4.3deque的迭代器1464.4.4deque的数据结构1504.4.5deque的建构与内存管理:ctor,push_back,push_front1524.4.6deque的元素操作:pop_back,pop_front,clear,erase,insert1614.5stack1674.5.1stack概述1674.5.2stack定义式完整列表1674.5.3stack没有迭代器1684.5.4以list做为stack的底层容器1684.6queue1694.6.1queue概述1694.6.2queue定义式完整列表1704.6.3queue没有迭代器1714.6.4以list做为queue的底层容器1714.7heap(隐性表述,implicitrepresentation)1724.7.1heap概述1724.7.2heap算法174push_heap174pop_heap176sort_heap178make_heap1804.7.3heap没有迭代器1814.7.4heap测试实例1814.8priority-queue183TheAnnotatedSTLSourcesxSTL源码剖析4.8.1priority-queue概述1834.8.2priority-queue定义式完整列表1834.8.3priority-queue没有迭代器1854.8.4priority-queue测试实例1854.9slist1864.9.1slist概述1864.9.2slist的节点1864.9.3slist的迭代器1884.9.4slist的数据结构1904.9.5slist的元素操作191第5章关系型容器(associatedcontainers)1975.1树的导览1995.1.1元搜索树(binarysearchtree)2005.1.2平衡元搜索树(balancedbinarysearchtree)2035.1.3AVLtree(Adelson-Velskii-Landistree)2035.1.4单旋转(SingleRotation)2055.1.5双旋转(DoubleRotation)2065.2RB-tree(红黑树)2085.2.1安插节点2095.2.2个由而的程序2125.2.3RB-tree的节点设计2135.2.4RB-tree的迭代器2145.2.5RB-tree的数据结构2185.2.6RB-tree的建构与内存管理2215.2.7RB-tree的元素操作223元素安插动作insert_equal223元素安插动作insert_unique224TheAnnotatedSTLSources目录xi真正的安插执行程序insert224调整RB-tree(旋转及改变颜色)225元素的搜寻find2295.3set2335.4map2375.5multiset2455.6multimap2465.7hashtable2475.7.1hashtable概述2475.7.2hashtable的桶子(buckets)与节点(nodes)2535.7.3hashtable的迭代器2545.7.4hashtable的数据结构2565.7.5hashtable的建构与内存管理258安插动作(insert)与表格重整(resize)259判知元素的落脚处(bkt_num)262复制(copy_from)和整体删除(clear)2635.7.6hashtable运用实例(find,count)2645.7.7hashfunctions2685.8hash_set2705.9hash_map2755.10hash_multiset2795.11hash_multimap282第6章算法(algorithms)2856.1算法概观2856.1.1算法分析与复杂度表示O()2866.1.2STL算法总览2886.1.3mutatingalgorithms—会改变操作对象之值291TheAnnotatedSTLSourcesxiiSTL源码剖析6.1.4nonmutatingalgorithms—不改变操作对象之值2926.1.5STL算法的般型式2926.2算法的泛化过程2946.3数值算法<stl_numeric.h>2986.3.1运用实例2986.3.2accumulate2996.3.3adjacent_difference3006.3.4inner_product3016.3.5partial_sum3036.3.6power3046.3.7itoa3056.4基本算法<stl_algobase.h>3056.4.1运用实例3056.4.2equal307fill308fill_n308iter_swap309lexicographical_compare310max,min312mismatch313swap3146.4.3copy,强化效率无所不用其极3146.4.4copy_backward3266.5Set相关算法(应用于已序区间)3286.5.1set_union3316.5.2set_intersection3336.5.3set_difference3346.5.4set_symmetric_difference3366.6heap算法:make_heap,pop_heap,push_heap,sort_heap3386.7其他算法338TheAnnotatedSTLSources目录xiii6.7.1单纯的数据处理338adjacent_find343count344count_if344find345find_if345find_end345find_first_of348for_each348generate349generate_n349includes(应用于已序区间)349max_element352merge(应用于已序区间)352min_element354partition354remove357remove_copy357remove_if357remove_copy_if358replace359replace_copy359replace_if359replace_copy_if360reverse360reverse_copy361rotate361rotate_copy365search365search_n366swap_ranges369transform369unique370unique_copy3716.7.2lower_bound(应用于已序区间)3756.7.3upper_bound(应用于已序区间)3776.7.4binary_search(应用于已序区间)3796.7.5next_permutation3806.7.6prev_permutation3826.7.7random_shuffle383TheAnnotatedSTLSourcesxivSTL源码剖析6.7.8partial_sort/partial_sort_copy3866.7.9sort3896.7.10equal_range(应用于已序区间)4006.7.11inplace_merge(应用于已序区间)4036.7.12nth_element4096.7.13mergesort411第7章仿函式(functor,另名函式物件functionobjects)4137.1仿函式(functor)概观4137.2可配接(adaptable)的关键4157.1.1unary_function4167.1.2binary_function4177.3算术类(Arithmetic)仿函式418plus,minus,multiplies,divides,modulus,negate,identity_element7.4相对关系类(Relational)仿函式420equal_to,not_equal_to,greater,greater_equal,less,less_equal7.5逻辑运算类(Logical)仿函式422logical_and,logical_or,logical_not7.6证同(identity)、选择(select)、投射(project)423identity,select1st,select2nd,project1st,project2nd第8章配接器(adapter)4258.1配接器之概观与分类4258.1.1应用于容器,containeradapters4258.1.2应用于迭代器,iteratoradapters425运用实例4278.1.3应用于仿函式,functoradapters428运用实例429TheAnnotatedSTLSources8.2containeradapters4348.2.1stack4348.2.1queue4348.3iteratoradapters4358.3.1insertiterators4358.3.2reverseiterators4378.3.3streamiterators(istream_iterator,ostream_iterator)4428.4functionadapters4488.4.2對參數進行繫結(綁定):bind1st,bind2nd4518.4.3用於函式合成:compose1,compose2(未納入標準)4538.4.4用於函式指標:ptr_fun4548.4.5用於成員函式指標:mem_fun,mem_fun_ref456附錄A參考資料與推薦讀物(Bibliography)461附錄B侯捷網站簡介471附錄CSTLport的移植經驗(by孟岩)473索引481目录xv8.4.1对传回值进行逻辑否定:not1,not2450TheAnnotatedSTLSourcesxviSTL源码剖析TheAnnotatedSTLSources前言xvii前言本书定位C++标准链接库是个伟大的作品。它的出现,相当程度改变了C++程序的风貌以及学习模式1。纳入STL(StandardTemplateLibrary)的同时,标准链接库的所有组件,包括大家早已熟悉的string、stream等等,亦全部以template改写过。整个标准链接库没有太多的OO(ObjectOriented),倒是无处不存在GP(GenericProgramming)。C++标准链接库隶属STL范围者,粗估当在80%以。对软件开发而言,STL是尖利兵,可以节省你许多时间。对编程技术而言,STL是金柜石室—所有与编程工作最有直接密切关联的些最被广泛运用的数据结构和算法,STL都有实作,并符合最佳(或极佳)效率。不仅如此,STL的设计思维,把我们提升到另个思想高点,在那里,对象的耦合性(coupling)极低,复用性(reusability)极高,各种组件可以独立设计又可以灵活无罅结合在起。是的,STL不仅仅是链接库,它其实具备framework格局,允许用户加自己的组件,与之融合并用,是个符合开放性封闭(Open-Closed)原则的链接库。从应用角度来说,任何位C++程序员都不应该舍弃现成、设计良好而又效率极佳的标准链接库,却「入太庙每事问」事事物物从轮子造起—那对组件技术及软件工程是大嘲讽。然而对于个想要深度钻研STL以便拥有扩充能力的,1请参考LearningStandardC++asaNewLanguage,byBjarneStroustrup,C/C++UsersJournal1999/05。译文http://www.jjhou.com/programmer-4-learning-standard-cpp.htmTheAnnotatedSTLSourcesxviiiSTL源码剖析相当程度追踪STL源码是必要的功课。是的,对于个想要充实数据结构与演算法等固有知识,并提升泛型编程技法的,「入太庙每事问」是必要的态度,追踪STL源码则是提升功力的极佳路线。想要良好运用STL,我建议你看《TheC++StandardLibrary》byNicolaiM.Josuttis;想要严谨认识STL的整体架构和设计思维,以及STL的详细规格,我建议你看《GenericProgrammingandtheSTL》byMatthewH.Austern;想要从语法层面开始,学理与应用得兼,宏观与微观齐备,我建议你看《泛型思维》by侯捷;想要深入STL实作技法,窥大家风范,提升自己的编程功力,我建议你看你手这本《STL源码剖析》—事实就在笔此刻,你也找不到任何本相同定位的书2。合适的读者本书不适合STL初学者(当然更不适合C++初学者)。本书不是面向对象(ObjectOriented)相关书籍。本书不适合用来学习STL的各种应用。对于那些希望深刻了解STL实作细节,俾得以提升对STL的扩充能力,或是希望藉由观察STL源码,学习世界流程式员身手,并藉此彻底了解各种被广泛运用之数据结构和算法的,本书最适合你。最佳阅读方式无论你对STL认识了多少,我都建议你第次阅读本书时,采循序渐进方式,遵循书安排的章节先行浏览遍。视个功力的深浅,你可以或快或慢并依个兴趣或需要,深入其。初次阅读最好循序渐进,理由是,举个例子,所有容器(containers)的定义式开头都会出现空间配置器(allocator)的运用,我可以在最初数次提醒你空间配置器于第2章介绍过,但我无法遍及全书再再提醒你。又例如,源码之时而会出现些全局函数调用动作,尤其是定义于<stl_construct.h>之用于物件建构与解构的基本函式,以及定义于2TheC++StandardTemplateLibrary,byP.J.Plauger,AlexanderAl.Stepanov,MengLee,DavidR.Musser,PrenticeHall2001/03,与本书定位相近,但在表现方式大有不同。TheAnnotatedSTLSources前言xix<stl_uninitialized.h>之用于记忆体管理的基本函式,以及定义于<stl_algobase.h>之的各种基本算法。如果那些全局函式已经在先前章节介绍过,我很难保证每次都提醒你—那是种顾此失彼、苦不堪言的劳役,并且容易造成阅读的累赘。我所选择的剖析对象本书名为《STL源码剖析》,然而STL实作品百花齐放,不论就技术面或可读性,皆有高之分。选择份好的实作版本,就学习而言当然是极为重要的。我选择的剖析对象是声名最着,也是我个评价最高的个产品:SGI(SiliconGraphicsComputerSystems,Inc.)版本。这份由STL之父AlexanderStepanov、经典书籍《GenericProgrammingandtheSTL》作者MatthewH.Austern、STL耆宿DavidMusser等投注心力的STL实作版本,不论在技术层次、源码组织、源码可读性,均有卓越的表现。这份产品被纳为GNUC++标准链接库,任何皆可从网际网络载GNUC++编译程序,从而获得整份STL源码,并获得自由运用的权力(详见1.8节)。我所选用的是cygnus3C++2.91.57forWindows版本。我并未刻意追求最新版本,来书籍不可能永远呈现最新的软件版本—软件更新永远比书籍改版快速,来本书的根本目的在建立读者对于STL巨观架构和微观技术的掌握,以及源码的阅读能力,这种核心知识的形成与源码版本的关系不是那么唇齿相依,来SGISTL实作品自从搭配GNUC++2.8以来已经十分稳固,变异极微,而我所选择的2.91版本,表现相当良好;来这个版本的源码比后来的版本更容易阅读,因为许多内部变量名称并不采用划线(underscore)—划线在变数命名规范有其价值,但到处都是划线则对大量阅读相当不利。网络有个STLport(http://www.stlport.org)站点,提供份以SGISTL为蓝本的高度可移植性实作版本。本书附录C列有孟岩先生所写的文章,是份STLport移植到VisualC++和C++Builder的经验谈。3关于cygnus、GNU源码开放精神、以及自由软件基金会(FSF),请见1.3节介绍。TheAnnotatedSTLSourcesxx各章主题STL源码剖析本书假设你对STL已有基本认识和某种程度的运用经验。因此除了第章略作介绍之外,立刻深入STL技术核心,并以STL六大组件(components)为章节之进行依据。以是各章名称,这样的次序安排大抵可使每章所剖析的主题能够于先前章节获得充份的基础。当然,技术之间的关连错综复杂,不可能存在单纯的线性关系,这样的安排也只能说是尽最大努力。第1章STL概论与实作版本简介第2章空间配置器(allocator)第3章迭代器(iterators)概念与traits编程技法第4章序列式容器(sequencecontainers)第5章关系型容器(associatedcontainers)第6章算法(algorithms)第7章仿函式or函式物件(functors,orfunctionobjects)第8章配接器(adapter)编译工具本书主要探索SGISTL源码,并提供少量测试程序。如果测试程序只做标准的STL动作,不涉及SGISTL实作细节,那么我会在VC6、CB4、cygnus2.91forWindows等编译平台分别测试它们。随着对SGISTL源码的掌握程度增加,我们可以大胆做些练习,将SGISTL内部接口打开,或是修改某些STL组件,加少量输出动作,以观察组件的运作过程。这种情况,操练的对象既然是SGISTL,我也就只使用GNUC++来编译4。4SGISTL事实是个高度可携产品,不限使用于GNUC++。从它对各种编译程序的环境组态设定(1.8.3节)便可略知。网络有个STLport组织,不遗余力将SGISTL移植到各种编译平台。请参阅本书附录C。TheAnnotatedSTLSources前言xxi中英术语的运用风格我曾经发表过篇《技术引导乎文化传承乎》的文章,阐述我对专业计算机书籍的英术语运用态度。文章收录于侯捷网站http://www.jjhou.com/article99-14.htm。以简单叙述我的想法。为了学术界和业界的习惯,也为了与全球科技接轨,并且也因为我所撰写的是供专业士阅读的书籍而非科普读物,我决定适量保留专业领域被朗朗口的英文术语。朗朗口与否,见仁见智,我以个阅历做为抉择依据。做为个并非以英语为母语的族裔,我们对英文的阅读困难并不在单字,而在整句整段的文意。做为项技术的学习者,我们的困难并不在术语本身(那只是个符号),而在术语背后的技术意义。熟悉并使用原文术语,至为重要。原因很简单,在科技领域里,你必须与全世界接轨。文技术书籍的价值不在于「建立本国文化」或「让它成为本道的文书」或「完全扫除英汉字典的需要」。文技术书籍的重要价值,在于引进技术、引导学习、扫平阅读障碍、增加学习效率。绝大部份我所采用的英文术语都是名词。但极少数动词或形容词也有必要让读者知道原文(我会时而英并列,并使用斜体英文),原因是:zC++编译程序的错误讯息并未文化,万错误讯息出现以字眼:unresolved,instantiated,ambiguous,override,而编写程序的你却不熟悉或不懂这些动词或形容词的技术意义,就不妙了。z有些动作关系到libraryfunctions,而libraryfunctions的名称并未文化-,例如insert,delete,sort。因此视状况而定,我可能会选择使用英文。z如果某些术语关系到语言关键词,为了让读者有最直接的感受与联想,我会采用原文,例如static,private,protected,public,friend,inline,extern。版面像一张破碎的脸?大量英夹杂的结果,无法避免造成版面的「破碎」。但为了实现合宜的表达方TheAnnotatedSTLSourcesxxiiSTL源码剖析式,牺牲版面的「全文化」在所难免。我将尽量以版面手法来达到视觉的顺畅,换言之我将采用不同的字形来代表不同属性的术语。如果把英文术语视为种符号,这些英夹杂但带有特殊字形的版面,并不会比市面琳琅满目的许多应用软件图解使用手册来得突兀(而后者不是普遍为大众所喜爱吗-)。我所采用的版面,都已经过再试炼,过去以来获得许多读者的赞同。英文术语采用原则就我的观察,们对于英文词或文词的采用,隐隐有个习惯:如果文词发音简短(或至少不比英文词繁长)并且意义良好,那么就比较有可能被业界用于日常沟通;否则业界多半采用英文词。例如,polymorphism音节过多,所以意义良好的文词「多型」就比较有机会被采用。例如,虚拟函式的发音不比virtualfunction繁长,所以使用这个文词的也不少。「多载」或「重载」的发音比overloaded短得多,意义又正确,用的也不少。但此并非绝对法则,否则就不会有绝大多数工程师说datamember而不说「数据成员」、说memberfunction而不说「成员函式」的情况了。以是本书采用原文术语的几个简单原则。请注意,并没有绝对的实践,有时候要看文情况。同时,容我再强调次,这些都是基于我与业界和学界的接触经验而做的选择。z编程基础术语,采用文。例如:函式、指针、变量、常数。本书的英文术语绝大部份都与C++/OOP/GP(GenericProgramming)相关。z简单而朗朗口的词,视情况可能直接使用英文:input,output,lvalue,rvalue...z读者有必要认识的英文名词,不译:template,class,object,exception,scope,namespace。z长串、有特定意义、译名称拗口者,不译:explicitspecialization,partialspecialization,usingdeclaration,usingdirective,exceptionspecialization。z运算符名称,不译:copyassignment运算符,memberaccess运算符,arrow运算符,dot运算符,addressof运算符,dereference运算符...TheAnnotatedSTLSources前言xxiiiz业界惯用词,不译:constructor,destructor,datamember,memberfunction,reference。z涉及C++关键词者,不译:public,private,protected,friend,static,z意义良好,发音简短,流传颇众的译词,用之:多型(polymorphism),虚拟函式(virtualfunction)、泛型(genericity)…z译后可能失掉原味而无法完全彰显原味者,英并列。z重要的动词、形容词,时而英并列:模棱两可(ambiguous),决议(resolve),改写(override),自变量推导(argumentdeduced),具现化(instantiated)。zSTL专用术语:采用文,如迭代器(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.5ptz标题:华康粗圆z视觉加强:华康中黑英文z般文字,TimesNewRoman,9.5pt,例如:class,object,memberfunction,datamember,baseclass,derivedclass,private,protected,public,reference,template,namespace,functiontemplate,classtemplate,local,globalz动词或形容词,TimesNewRoman斜体9.5pt,例如:resolve,ambiguous,override,instantiatedzclass名称,LucidaConsole8.5pt,例如:stack,list,mapz程序代码识别符号,CourierNew8.5pt,例如:int,min(SmallInt*,int)TheAnnotatedSTLSourcesxxivSTL源码剖析z长串术语,Arial9pt,例如:memberinitializationlist,namereturnvalue,usingdirective,usingdeclaration,passbyvalue,passbyreference,functiontryblock,exceptiondeclaration,exceptionspecification,stackunwinding,functionobject,classtemplatespecialization,classtemplatepartialspecialization…zexceptiontypes或iteratortypes或iostreammanipulators,LucidaSans9pt,例如:bad_alloc,back_inserter,boolalphaz运算符名称及某些特殊动作,FootlightMTLight9.5pt,例如:copyassignment运算符,dereference运算符,addressof运算符,equality运算子,functioncall运算符,constructor,destructor,defaultconstructor,copyconstructor,virtualdestructor,memberwiseassignment,memberwiseinitializationz程序代码,CourierNew8.5pt,例如:#include<iostream>usingnamespacestd;要在整本书维护贯的字形风格而没有任何疏漏,很不容易,许多时候不同类型的术语搭配起来,就形成了不知该用哪种字形的困扰。排版者顾此失彼的可能也不是没有。因此,请注意,各种字形的运用,只是为了让您阅读时有比较好的效果,其本身并不具其他意义。局部的致性更重于全体的致性。源码形式与下载SGISTL虽然是可读性最高的份STL源码,但其并没有对实作程序乃至于实作技巧有什么文字批注,只偶而在档案最前面有点点总体说明。虽然其符号名称有不错的规划,真要仔细追踪源码,仍然旷日费时。因此本书不但在正文之解说其设计原则或实作技术,也直接在源码加许多批注。这些批注皆以蓝色标示。条件式编译(#ifdef)视同源码处理,函数调用动作以红色表示,巢状定义亦以红色表示。classes名称、datamembers名称和memberfunctions名称大多以粗体表示。特别需要提醒的方(包括template预设自变量、长度很长的巢状式定义)则加灰阶底纹。例如:template<classT,classAlloc=alloc>//默认使用alloc为配置器classvector{public:typedefTvalue_type;TheAnnotatedSTLSources前言xxvtypedefvalue_type*iterator;...protected://vector采用简单的线性连续空间。以两个迭代器start和end分别指向头尾,//并以迭代器end_of_storage指向容量尾端。容量可能比(尾-头)还大,//多余的空间即备用空间。iteratorstart;iteratorfinish;iteratorend_of_storage;voidfill_initialize(size_typen,constT&value){start=allocate_and_fill(n,value);//配置空间并设初值finish=start+n;//调整水位end_of_storage=finish;//调整水位}...};#ifdefSTL_FUNCTION_TMPL_PARTIAL_ORDERtemplate<classT,classAlloc>inlinevoidswap(vector<T,Alloc>&x,vector<T,Alloc>&y){x.swap(y);}#endif/*STL_FUNCTION_TMPL_PARTIAL_ORDER*/又如://以配接器用来表示某个AdaptableBinaryPredicate的逻辑负值template<classPredicate>classbinary_negate:publicbinary_function<typenamePredicate::first_argument_type,typenamePredicate::second_argument_type,bool>{...};这些作法可能在某些方有少许例外(或遗漏),唯不变的原则就是尽量设法让读者眼抓住源码重点。花花绿绿的颜色乍见之或许不习惯,多看几眼你就会喜欢它-。这些经过批注的SGISTL源码以MicrosoftWord97文件格式,连同SGISTL源码,置于侯捷网站供自由载5。噢,是的,STL涵盖面积广大,
  • 相关资料
  • 该用户的其他资料
  • 名称/格式
  • 下载次数
  • 资料大小
  • 名称/格式
  • 下载次数
  • 资料大小

用户评论

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

资料阅读排行

关闭

请选择举报的类型

关闭

提示

提交成功!

感谢您对爱问共享资料的支持,我们将尽快核实并处理您的举报信息。

关闭

提示

提交失败!

您的举报信息提交失败,请重试!

关闭

提示

重复举报!

亲爱的用户!感觉您对爱问共享资料的支持,请勿重复举报噢!

全屏 缩小 放大
收藏
资料评价:

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

温馨提示

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