STL源码剖析

STL 源码剖析 侯捷 清晰扫描版sSTL源码剖析The Annotated stl sources向专家学习型别技术、内存管理、算法、数据结构、STL各类组件之高阶实现技巧侯捷华中科技大学出版社图书在版编目(CIP)数据STL源码剖析/侯捷武汉:华中科技大学出版社,2002年6月ISBN7-5609-2699-1侯Ⅲ,计算机软件-STL源码Ⅳ.TP311.1本书封面贴有华中科技大学出版社(原华中理工大学出版社激光防伪标志,无标志者不得销售版权所有盗印必究STL源码剖析侯捷责任编辑:周筠!tp:/ yeka. xilubbs comjunzhou@public.wh.hb.cn封面设计:潘群技术编辑:孟岩责任监印:张正林责任校对:张兴田出版发行:华中科技大学出版社武昌喻家山邮编:430074电话:(027)87545012录排:华中科技大学惠友科技文印中心印刷:湖北新华印务有限公司开本:787×10921/16印张:33插页:2字数:600000版次:2002年6月第1版印次:2002年6月第1次印刷印数:1-10000ISBN7-5609-2699-1/TP·464定价:68.00元本书若有印装质量问题,请向出版社市场部调换源码之前了无秘密献给每一位对GP/STL有所渴望的人天下大事必作于细侯捷高屋建瓴细致入徵——《STL源码剖析》引介高屋建瓴细致入微《STL源码剖析》弓介身为C十+标准库最重要的组成部分,STL(标准模板库)不仅是一个可复用组件库而且是-个包罗算法与数据结构的软件框架( framework)。“框架”这个词,本身就有庞大、稳定、完整而可扩展的涵义。软件框架,则是用一行行精细准确的源码,构造个庞大、稳定、完整而可扩展的软件架构。稍有软件开发经验的人都知道,要做到这些,谈何容易!STL在1994年走入C++标准,使得原本即将推出的C十准延迟4年问世而无怨无悔,并为之对内容做巨幅改进。而今STL不仅为千千万万C++程序员所日常运用,而且获得极高的学术赞誉,成为一个典范、一种境界。作为一个软件框架STL所取得的成功,实在可以用“辉煌”来形容,其所内涵的软件思想和技术经验,更是无比的深厚与精致学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。源码之前,了无秘密。大师们的缜密思维、经验结晶、技术思路、独到风格,都原原本本体现在源码之中。在你仔细推敲之中,迷惑不解之时,恍然大悟之际,你的经验、思维、视野、知识乃至技术品位都会获得快速的成长。特别是面对STL这样优秀而普遍的作品,无论你是为了满足作为程序员第二天性的求知欲,还是在日常工作中解决实际问题,总有一天,你会打开一个叫做< vector>或者<≤ algorithIn>的头文件,想把ST背后的秘密看个究竟英文里有一个常用短语,叫做“ under the hood”,钻进魔术师的帐篷,屏住呼吸,瞪大眼睛,把那些奇妙的魔法看个通透,让自己的理解和技艺获得巨幅的提升,这种诱惑任何一个程序员都无法抵挡不过,要想研读STL源码,绝对没有那幺简单。STL是精致的软件框架,是为优化效率而无所不用其极的艺术品,是数据结构与算法大师经年累月的智能结晶,是泛型思想的光辉诗篇,是C十高级技术的精彩亮相!这些灿烂的赞誉,体现在数万行源码里,对于一个初涉此道的学习者来说,就是一个感觉:“难!”无论你是浅尝辄止,便退出The annotated stl sourcesSTL源码剖析这次探险,还是勇敢地向浓雾中前进,当你受困于STL精致的大网之中,为那些迷一般的结构和操作感到茫然无措的时侯,所有人都会冒出一个念头:“如果有这样一本书,既能够提纲挈领,为我理顺思绪,指引方向,同时又能够照顾小节,阐述细微,帮助我更快更好地理解STL源码,那该有多好!望着长长的STL著作列表,一个“真正”的C++程序员,多少会有一点遗憾。自从STL问世以来,出版了大量的书籍,帮助读者了解它的思想,学习它的用法,掌握它的技巧。其中佼佼者如 Matt Auster的《 Generic Programming and StL》, Nicolai josuttis的巛TheC++ Standard Library》, Scott Meyers的《 ffective StL》,已成C+经典名著然而,定位在引导学丬者进行STL源码分析的著作,可以说是凤毛麟角。毕竞,既要能高屋建瓴,剖析大架构,不为纷繁琐碎之细节而迷乱,又能具体而微,体现细致之处的精妙缜密,不因为宏大体系而失之粗略,无论对于专家高手还是技术作家,都是太难达到的目标读了这本《STL源码剖析》之后,我认为,这个遗憾终于被补足了本书的作者侯捷先生是蜚声海峡两岸的著名I技术作家,在C++、 Windows系统原理、泛型理论和STL等技术领域有极深的造诣。然而,侯先生最令人称道之处,乃是他剖析大架构的能力。所谓剖析大架构,就是要在洋洋洒洒数以万行计的源码中,精准定位,抽取核心观念,高屋建瓴,纲举目张,将看上去乱麻一般的源码梳理得头绪清晰,条理分明,同时又照顾细节,参透精微,把一个个关键动作阐述得通通透透。这种能力,我以为至少在华人技术作家中,侯先生堪执牛耳!在他的名作《深人浅出MFC》中,侯先生将自己这方面的能力展现得淋漓尽致,而在这本《STL源码剖析》中,我们看到了又一次更加精彩的表现我有机会作为大陆最早的几个读者之一,详细拜读了侯先生的这本STL专着,内心产生了一种强烈的技术冲动。说得俗一点,就是觉得很过瘾!具体来说,我认为这本书至少有四大特点,使它成为我所见过的最出色的一本STL源码剖析类著作首先,选材精当,立足高远。STL是一个标准,因而有各种实现版本。本书所剖析的 SGI STL,可以说是设计最巧妙、思想最深刻、获得赞誉最盛、认同最广的SI实现品。当然,这份出自SL之父 Alex Stepanov,以及 Matt Austern, Dayid musser等巨匠之手的经典作品,剖析阐述起来自然也需要花费更大的心力。侯先生藉其扎实的理论与技术素养,毅然选择这份作品来剖析,是需要极大勇气与自信的。同样,本书对读者的预期,也是很高的,读者不但要有扎实的基本功,更要有掌握STL的兴趣与坚韧意志读这本书,你可以有允分的信心,学到的是超一流大师的思想和经验,所谓名门正派,高屋建瓴The annotated stl sources高屋建瓴细致人微—《STL源码剖析》引介其次,脉络清晰,组织順序匠心独具。仼何人打算系统阅读STL源码,所必须做出的第一个决定就是,从何处开始?我在初读此书时,一个最感疑惑的地方就是侯先生竞然把 allocator放在所有组件之前讲述。要知道, allocator这个东西,对一般的使用者完全透明,根本感觉不到其存在,以至于在名著《TheC++ Standard libaray》中, NicolaiJosuttis将这一部分放在全书最后。既然如此,又何必让这个无名小卒占据头版头条?我开始还真是不理解。直到后来,我自己有些扩展STL的实践,才发现,用的时候你固然可以对 allocator不闻不问,但-旦要领悟STL的工作原理,或者要自己扩展STL的功能,则对于 allocator的掌握几乎是第一先决条件,不了解 allocator,则无论剖析也好,扩展也罢,必然处处碰壁。侯先生毫不迟疑,首先帮读者搬开这块绊脚石,理出头绪,实在是匠心独具,紧接着的第三章 Iterator及 traits,直入STL的核心观念与关键技术,剑走中锋,直取要害,高举高打,开诚布公,直接把理解STL的钥匙交到读者手上此章一过,读者神完气足,就可以大刀阔斧地打通STL的重重关隘。此布局只要稍有变化,读者的学习难度势必猛增。侯先生的此种安排,实在是大家手笔!此外,本书在技术上迎难而上,详略得当,完整而重点突出。了解 SGI STL的读者都知道,这份作品对C+标准中的STL做了大量的扩充,增加了专用的高效 allocator,用以操作巨型字符串的rope,单链表 slist,以及万众企盼的hash容器等等,再加上STL本身就有很多精微之处,技术上的难点不少。此类书籍的作者,但凡稍有一丝懈怠之心,大可以冠冕堂皇地避重就轻。然而侯先生在此书中对重点难点亳不避讳,无论是标准功能还是非标准功能,只要对读者理解STL架构有益,只要有助于提高读者的技术,增长读者的视野与经验,书中必然不畏繁难,将所有技术细节原原本本和盘托出。另一·方面,所谓剖析源码,其目的在于明理、解惑,提高自身水平,并不是要穷经皓首,倒背如流因此,一旦道理讲消楚,书中就将重复与一般性的内容一笔带过,孰轻孰重,一目了然,详略十分得当,这一点对于提高读者的学习效率,有着巨大的意义最后一点,本书通过大量生动范例和插图讲解基本思想,在同类书籍中堪称典范虽然我把这一点放在最后,但我相信大部分读者站在书店,随手翻过这本书,得到的第印象便是这一点。STL之所以为大家所津津乐道,除了其思想深刻之外,最大的因素是它实用。它所包装的,是算法与数据结构的基本功能。作为一个程序员,如果你是做数据库编程的,大可以不懂汇编语言,如果你是写驱动程序的,大可以不必通晓人工智能,写编译器的可以不用懂什幺计算机图形学,操作系统内核高手不用精通网站架设然而,如果你不懂数据结构与算法的基础知识,不具备数据结构与算法的基本技能,那就完全丧失称为一个程序员的资格!市面上讲述算法与数据结构的专着汗牛充栋,俯拾皆是。相比之下,本书倒并不是以此为核心月标的。但是,可曾有哪位读者看到任何The annotated stl SourcesISTL源码剖析夲书像本书一样,将红黑树用一张张清晰生动的图解释得如此浅显易懂?所谓一图胜千言,在教授基本数据结构与算法方面,我想不出还有任何一种方法,能够比幻灯般的图片更生动更令人印象深刻了。读过此书的每一位读者,我想都会为书中那一幅幅插图所打动,作者细致严谨的作风,时刻为读者考虑的敬业精神,也许是值得我们尊敬的东西。我非常荣幸有机会与侯先生和华中科技大学出版社的周筠女士再次合作,担任了这本书的繁简转译工作。在术语转译方面,我们基本上保持了与《 Effective c++中文版》相一致的标准。其中有一些术语不完全符合国内的习惯译法,下面是一个简单的对比表英文术语大陆惯用译法本书译法adapter适配器配接器argument实参(实质参数)引数by reference传参考,传地址传址by value传值传值dereference反引用解参考提领evaluate评估计算评估,核定instance案例,实例实体instantiated|实例化实体化、具现化librar库函数库程序库range范围区间(使用于STL时)resolve解析决议parameter形参(形式参数)刂参数t类型型别侯先生在一篇影晌頗为广泛的STL技术杂文中,将STL的学习境界划分为三个阶段:会用,明理,能扩展。阅读STL源码是由第层次直贯第二层次,而渐达于第三层次的一条捷径,当然也是一条满是荆棘之路。如果你是一个勇于征服险峰的程序员,如果你是一个希望了解 under the hood之奥秘的程序员,那么当你在攀登SL这座瑰丽高山的时候,这本书会大大地帮助你。我非常热情地向您推荐这本着作。当然,再好的书籍也只是工具,能不能成功,关键,还在你自己孟岩2002年4月于北京The annotated stl sources庖丁解牛·侯捷自序庖丁解牛侯捷自序这本书的写作动机,纯属偶然2000年下半年,我开始为计划中的《泛型思维》一书陆续准备并热身。为了对泛型编程技术以及STL实现技术有更深的体会,以便在讲述整个STL的架构与应用时更能虎虎生风,我常常深入到STL源码中去刨根究底。200l年2月的某天,我突然有所感触:既然花了大把精力看过STL源码,写了眉批,做了整理,何不把它再加一点功夫,形成一个更完善的面貌后出版?对我个人而言,一份批注详尽的STL源码,价值不菲;如果我从中获益,一定也有许多人能够从中获益这样的念头使我极度兴奋剖析大架构本是侯捷的拿手,这个主题又可以和《泛型思维》相呼应。于是我便一头栽进去了我选择 SGI STL作为剖析对象。这份实现版本的可读性极佳,运用极广,被选为GNUC++的标准程序库,又开放自由运用。愈是细读 SGI STL源码,愈令我震惊抽象思维层次的落实、泛型编程的奥妙,及其效率考虑的缜密。不仅最为人广泛运用的各种数据结构( data structures)和算法( algorithms)在STL中有良好的实现,连内存配置与管理也都重重考虑∫最佳效能。一切的一切,除了实现软件积木的高度复用性,让各种组件( components)得以灵活搭配运用,更考虑了实用上的关键议题:效率1庄子养生主:“彼节者有间,而刀刃者无厚:以无厚入有间,恢恢乎其于游刃必有余地矣.”侯捷不让,以此自况The Annotated stL Sources