01 STL概论与版本介绍_stl版本
赞
踩
STL源码剖析
前言
源码之前 了无秘密
参观飞机工厂不能让你学到流体力学，也不能让你学会开飞机。然而如果你会开飞机又懂流体力学，参观工厂可以带给你最大的乐趣和价值。
一、STL概论
长久以来，软件界一直希望建立一种可重复运用的东西， 以及一种得以制造出“可重复运用的东西”的方法，让工程师/程序员的心血不 致于随时间迁移、人事异动 、私心欲念、人谋不臧 而烟消云散。从子程序（subroutines）、程序（procedures）、 函式（functions）、类别（classes），到函式库（function libraries）、类别库（class libraries）、各种组件（components），从结构化设计、模块化设计、面向对象 （object oriented）设计，到样式（patterns）的归纳整理，无一不是软件工程的漫漫奋斗史。
复用性的提高一直都是软件界一直在做的事情，为了建立数据结构和算法的一套标准，并降低其间的耦合关系以提升各自的独立性、弹性、交互操作性（相互合作性），C++社群里诞生了STL。
STL所实现的，是依据泛型思维架设起来的一个概念结构。
STL 的价值在两方面：
-
低层次：STL 带给我们一套极具实用价值的零组件， 以及一个整合的组织。这种价值就像 MFC 或 VCL 之于 Windows 软件开发过程 所带来的价值一样，直接而明朗，令大多数人有最立即明显的感受。
-
高层次：以泛型思维（Generic Paradigm）为基础的、系统化的、 条理分明的「软件组件分类学（components taxonomy）」。从这个角度来看，STL 是个抽象概念库（library of abstract concepts），这些「抽象概念」包括最基础的 Assignable（可被赋值）、Default Constructible（不需任何自变量就可建构）、 Equality Comparable（可判断是否等同）、LessThan Comparable（可比较大 小）、Regular （正规）…，高阶一点的概念则包括 Input Iterator（具输入功能的迭代器）、 Output Iterator（具输出功能的迭代器）、Forward Iterator（单向迭代器）、 Bidirectional Iterator（双向迭代器）、Random Access Iterator（随机存取迭代 器）、Unary Function （一元函式）、Binary Function（为元函式）、Predicate（传回真假值的一元判断 式）、Binary Predicate（传回真假值的二元判断式）…更高阶的概念包括 sequence container（序列式容器）、associative container（关系型容器）…
STL 的创新价值便在于具体叙述了上述这些抽象概念，并加以系统化。 换句话说，STL 所实现的，是依据泛型思维架设起来的一个概念结构。这个以抽 象概念（abstract concepts）为主体而非以实际类别（classes）为主体的结构，形成 了一个严谨的接口标准。在此接口之下，任何组件有最大的独立性，并以所谓迭 代 器（iterator）胶合起来，或以所谓配接器（adapter）互相配接，或以所谓仿函数（functor）动态选择某种策略（policy 或 strategy）。
目前没有任何一种程序语言提供任何关键词（keyword）可以实质对应上述所谓的 抽象概念。但是 C++ classes 允许我们自行定义型别，C++ templates 允许我们将型别参数化，藉由两者结合并透过traits编程技法，形成了 STL 的绝佳温床。
1.1 STL的历史
-
STL系由 Alexander Stepanov创造于1979年前后，这也正是Bjarne Stroustrup 创造C++的年代。虽然 David R. Musser 于 1971 开始即在计算器几何领域中发展并倡导某些泛型程序设计观念，但早期并没有任何程序语言支持泛型编程。第一个支持泛型概念的语言是 Ada。Alexander 和 Musser 曾于 1987 开发出一套相关的 Ada library。然而 Ada 在美国国防工业以外并未被广泛接受，C++ 却如星火燎原 般地在程序设计领域中攻城略地。当时的C++ 尚未导入template 性质，但Alexander 却已经意识到，C++ 允许程序员透过指针以极佳弹性处理内存，这一点正是既 要 求㆒般化（泛型）又不失效能的一个重要关键。3
-
更重要的是，必须研究并实验出一个“建立在泛型编程之上”的组件库完整架构。 Alexander 在AT&T 实验室以及惠普公司的帕罗奥图（Hewlett-Packard Palo Alto） 实验室，分别实验了多种架构和算法公式，先以C 完成，而后再以 C++ 完成。 1992 年 Meng Lee 加入 Alex 的项目，成为 STL 的另一位主要贡献 者。
-
贝尔（Bell）实验室的 Andrew Koenig 于1993 年知道这个研究计划后，邀请 Alexander 于是年 11 月的 ANSI/ISO C++ 标准委员会会议上展示其观念。获得热烈回应。 Alexander 于是再接再励于次年夏天的 Waterloo（滑铁卢）会议开幕前，完成正式提案，并以压倒性多数一举让这个巨大的计划成为 C++ 标准规格的一部份。
1.3 STL与C++标准链接库
-
1993年9月，Alexander Stepanov 和他一手创建的 STL，与 C++ 标准委员会有了第一次接触。
-
1994年1月6日 Alexander 收到 Andy Koenig（C++ 标准委员会成员，当时的 C++ Standard 文件审核编辑）来信，言明 如果希望 STL 成为 C++ 标准链接库的一部份，可于 1994年1月25日 前送交一份提案 报告到委员会。Alexander 和 Lee 于是拼命赶工完成了那份提案。
-
然后是 1994年3月 的圣地牙哥会议。STL 在会议上获得了很好的回响，但也有许多 反对意见。主要的反对意见是，C++ 即将完成最终草案，而 STL 却是如此庞大， 似乎有点时不我予。投票结果压倒性地认为应该给予这份提案一个机会，并把决 定 性投票延到下次会议。
-
下次会议到来之前，STL 做了几番重大的改善，并获得诸如 Bjarne Stroustrup、 Andy Koenig 等人的强力支持。
-
然后便是滑铁卢会议。这个名称对拿破仑而言，标示的是失败，对Alexander 和 Lee， 以及他们的辛苦成果而言，标示的却是巨大的成功。投票结果，80 % 赞 成，20 % 反 对，于是 STL 进入了 C++ 标准化的正式流程，并终于成为 1998年9月 定案的 C++ 标 准规格中的 C++ 标准链接库的一大脉系。影响所及，原本就有的 C++ 链接库如 stream, string 等也都以 template 重新写过。到处都是 templates！ 整个 C++ 标准 链接库呈现"春城无处不飞花"的场面。
-
Dr Dobb’s Journal 曾于 1995年03 刊出一篇名为 Alexander Stepanov and STL 的访谈 文 章，对于 STL 的发展历史、Alexander 的思路历程、STL 纳入 C++ 标准链接库 的 过程，均有详细叙述。
二、STL的六大组件
-
容器（containers）
STL提供六大组件，彼此可以组合套用：
各种数据结构，如vector, list, deque, set,map，用来存放数据，从实现的角度看，STL 容器是一种class template。就体积而言，这一部份很像冰山在海面下的比率。 -
算法（algorithms）
各种常用算法如sort,search,copy,erase…，从实现的角度看，STL算法是一种function template。 -
迭代器（iterators）：
扮演容器与算法之间的胶着剂，是所谓的“泛型指标”。共有五种类型，以及其他衍生变化。
从实作的角度看， 迭代器是一种将 operator*, operator->, operator++, operator–等指标相关操作予以多载化的class template。所有STL容器都附带有自己专属的迭代器——是的，只有容器设计者才知道如何遍历自己的元素。原生指标（native pointer）也是一种迭代器。 -
仿函数（functors）：
行为类似函式，可做为算法的某种策略（policy），从实现的角度看，仿函数是一种重载了operator()的class或class template。一般函式指标可视为狭义的仿函数。 -
配接器（adapters）：
一种用来修饰容器（containers）或仿函数（functors） 或迭代器（iterators）接口的东西
例如STL提供的queue和stack，虽然看似容器，其实只能算是一种容器配接器，因为它们的底部完 全借重 deque，所有动作都由底层的 deque 供应。改变functor接口者，称 为function adapter，改变 container 接口者，称为 container adapter，改变 iterator 接口者，称为 iterator adapter -
配置器（allocators）：
负责空间配置与管理，从实作的角度 看， 配置器是一个实现了动态空间配置、空间管理、空间释放的 class template。
六大组件的交互关系：
三、STL实现版本
- HP是所有STL实现版本的始祖。
- P.J.Plauger版本是由P.J.Plauger开发，其被Visual C++采用。
- RougeWave版本由Rouge Wave公司开发，其被C++Builder采用。
- STLport版本，网络上有个STLport提供一个以SGI STL为蓝本的高度可移植性实现版本。
- SGI STL版本由Silicon Graphics Computer System,Inc公司发展，继承HP版本，其被GCC采用。
总结
更多精彩内容请关注：公众号《写Bug那些事》
