STL 源码剖析 (2008 年度畅销榜NO.232 )

本书所呈现的源码，使你踏上了基度山岛。源码之前了无秘密，你将看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现；你将看到各种算法（排序、查找、排列组合、数据移动与复制技术）的实现；你甚至能够看到底层的memory pook和高阶抽象的traits机制的实现。

疱丁解牛（侯捷自序）\r\n目录\r\n前言\r\n第1章 STL概论与版本简介\r\n第2章 空间配置器（allocator）\r\n第3章 迭代器（iterators）概念与traits编程技法\r\n第4章 序列式容器（sequence containers）\r\n第5章 关联式容器（associattive containers）\r\n第6章 算法（algorithms）\r\n第7章 仿函数（functors，另名 函数对象function objects）\r\n第8章 配接器（adapters）\r\n附录A 参考书籍与推荐读物\r\n附录B 候捷网站（本书支持站点简介）\r\n附录C STLPort 的移植经验（by孟岩）\r\n索引

本书定位 C++标准程序库是一个伟大的作品。它的出现，相当程度上改变了C++程序的风貌以及学习模式。纳入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以便拥有扩充能力的人来说，相当程度地追踪STL源代码是必要的功课。是的，对于一个想要充实数据结构与算法等固有知识，并提升泛型编程技法的人，“入太庙每事问”是必要的态度，追踪STL源代码则是提升功力的极佳路线。 想要良好运用STL，我建议你看《The C++ Standard Libraryby》Nicolai M．Josuttis；想要严谨认识STL的整体架构和设计思维，以及STL的详细规格，我建议你看《Generic Programming and the STL》by Matthew H. Austere；想要从语法层面开始，学理与应用得兼，宏观与微观齐备，我建议你看《泛型思维》by侯捷；想要深入STL实现技法，一窥大家风范，提升自己的编程功力，我建议你看你手上这本《STL源码剖析》——事实上就在下笔此刻，你也找不到任何一本相同定位的书。 合适的读者 本书不适合STL初学者(当然更不适合C++初学者)。本书不是面向对象(Object Oriented)相关书籍。本书不适合用来学习STL的各种应用。 对于那些希望深刻了解STL实现细节，从而得以提升对STL的扩充能力，或是希望藉由观察STL源代码，学习世界一流程序员身手，并藉此彻底了解各种被广泛运用之数据结构和算法的人，本书最适合你。 最佳阅读方式 无论你对STL认识了多少，我都建议你第一次阅读本书时，采取循序渐进的方式，遵循书中安排的章节先行浏览一遍。视个人功力的深浅，你可以或快或慢并依个人兴趣或需要，深入其中。初次阅读最好循序渐进，理由是，举个例子，所有容器(containers)的定义式一开头都会出现空间配置器(allocator)的运用，我可以在最初数次提醒你空间配置器于第2章介绍过，但我无法遍及全书一再一再提醒你。又例如，源代码之中时而会出现一些全局函数调用操作，尤其是定义于之中用于内存管理的基本函数， 以及定义于之中的各种基本算法。如果那些全局函数已经在先前章节中介绍过，我很难保证每次都提醒你——那是一种顾此失彼、苦不堪言的劳役，并且容易造成阅读上的累赘。 我所选择的剖析对象 本书名为《STL源码剖析》，然而STL实现版本百花齐放，不论就技术面或可读性，皆有高下之分。选择一份好的实现版本，就学习而言当然是极为重要的。我选择的剖析对象是声名最盛，也是我个人评价最高的一个产品：SGI(Silicon Graphics Computer Systems，Inc.)版本。这份由STL之父Alexander Stepanov、经典书籍《Generic Programming and the STL》作者Matthew H. Austern、STL巨匠David Musser等人投注心力的STL实现版本，不论在技术层次、源代码组织、源代码可读性上，均有卓越的表现。这份产品被纳为GNUC++标准程序库，任何人皆可从因特网上下载GNU C++编译器，从而获得整份STL源代码，并获得自由运用的权力(详见1.8节)。 我所选用的是cygnusa 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的经验谈。 各章主题 本书假设你对STL已有基本认识和某种程度的运用经验。因此，除了第一章略作介绍之外，立刻深入STL技术核心，并以STL六大组件(components)为章节的进行依据。以下是各章名称，这样的次序安排大抵可使每一章所剖析的主题能够于先前章节中获得充分的基础。当然，技术之间的关联错综复杂，不可能存在单纯的线性关系，这样的安排也只能说是尽最大努力。 第l章 STL概论与实现版本简介 第2章 空间配置器(allocator) 第3章 迭代器(iterators)概念与traits编程技法 第4章 序列式容器(sequence containers) 第5章 关联式容器(associated containers) 第6章 算法(algorithms) 第7章 仿函数或函数对象(functors，Or function Objects) 第8章 配接器(adapter) 编译工具 本书主要探索SGI STL源代码，并提供少量测试程序。如果测试程序只做标准的STL操作，不涉及SGI STL实现细节，那么我会在VC6、CB4、cygnus2.91 for Windows等编译平台上分别测试它们。 随着对SGI STL源代码的掌握程度增加，我们可以大胆做些练习，将SGI STL内部接口打开，或是修改某些STL组件，加上少量输出操作，以观察组件的运作过程。这种情况下，操练的对象既然是SGI STL，我也就只使用GNU C++来编译。