【决战西二旗】|理解标准模板库STL(一)

痛 但是不快乐

作为C++程序员最熟悉的莫过于重复造轮子，这里并不是说你可以造轮子，而是大部分时候我们被困于造轮子。造轮子的要求很高，要做到复用性、稳定性、效率等诸多考量，简单写个api最多算玩具称不上轮子，对此你可能不想承认。

C++作为优秀的服务端语言基本上大公司都有使用，然而C++并不像Python一样有丰富的统一的基础类库和应用类库，这样对于程序猿来说很痛苦。今天在A公司上班写业务代码、一年后换到B公司写业务代码，但是可能完全是另外一种类库和风格，甚至编译都有非常多的模式，经验迁移和学习适应都有一定的成本。

C++软件工程界也一直希望建立一种可重复利用的东西，从类库、各种组件、设计模式等，都可以无惧时间迁移和人员流失，根本上提升代码的复用性和程序猿的知识经验迁移。

虽然理想很美好，但是至今C++开发者都没有获得这种体验，因为如果一门语言没有从最开始就推出一套统一且完备的数据结构算法库、常用库(网络、加解密、编码转换、日志)等，使用者就只能自己造轮子。

最终即使哪天C++真的大一统了，那么也只能是那些没有历史包袱的新公司或者老公司新业务来尝试，因为重构绝非易事，尚能不错的运行，为啥非要改动？这种想法非常现实而合理。

在C++中模板化是代码复用的重要手段，全世界最聪明的一帮人基于模板化实现了一套完备且工业级的基础数据结构和算法库，这就是我们今天要说的主角:C++标准模板库STL。

百花齐放的STL

STL是Standard Template Library的简称，STL背后的技术支撑是模板，并不要把std::string这些算作STL中，也不要把STL简单地当做容器的集合。

STL是基于模板化实现的容器、算法、迭代器等，可以简单认为STL是装载对象的对象，并且提供了操作这些对象的方法，由于使用了模板化，因此对象的类型可以很丰富，从而实现了一个容纳和操作"万能的"对象。

STL是世界上众多聪明人多年的杰作，STL的版本很多常见的有HP STL、PJ STL、 SGI STL等，但是谈的最多的是SGI STL。

• HP STL

HP STL是所有其它STL实现版本的根源。它是STL之父Alexander Stepanov在惠普的Palo Alto实验室工作时和Meng Lee共同完成，这个STL是开源的，后续的很多版本都是基于此优化和开发的，不过现在已经很少直接使用这个版本的STL了。

• PJ STL

VC++里的STL作者是P.J.Plauger，HP STL的一个继承版本。

• SGI STL

STL之父Alexander Stepanov离开HP之后就去了SGI(Silicon Graphics Computer System, Inc)，然后和Matt Austern这些STL大牛一起搞了SGI STL。它也是HP STL的一个继承版本。后SGI STL被GCC所采用，SGI版本的STL在linux平台上的性能相当出色。此外，其源代码的可读性也很好，因此我们后面说的STL版本主要是SGI STL。

• GNU STL

GNU STL是在SGI STL基础上gcc编译器自带的STL版本，在SGI的基础上做了一些扩展，包含在libstdc++这个库里面。

可见HP STL是其他STL版本的基础，其中HP STL和SGI STL算是根红苗正，都是Alexander Stepanov与其他大牛一起开发完成的，并且SGI STL是HP STL的新版本，所以国内讲解STL的优秀书籍《STL源码剖析》也是基于SGI STL来讲解的。

STL之父华山论剑

Alexander Stepanov 1950年11月16日出生在前苏联的莫斯科，曾求学于莫斯科国立大学学习数学，他与C++之父是很要好的朋友。Nginx的作者也是俄罗斯人，战斗民族在基础教育和计算机科学教育方面做到还很到位，出了非常多顶级的编程人员，毕竟那里19岁还不会开坦克都会被嘲笑。想到这里，看看自己还不能熟练地手撕红黑树也真是慌得一批。

在2000年初的时候 Alexander Stepanov有一次著名的访谈，笔者找到了2005年2月的《软件世界》期刊关于对话STL之父Alexander Stepanov的报道：

那个年代信息流还没有、自媒体更没有，也没有动不动就沸腾、一言不合就全世界安静。感兴趣可以搜索关键词"Interview of Alex Stepanov"查阅相关资料。

STL六大组件

STL提供了六大组件，彼此之间可以用组合套用，六大组件分别是容器、算法、迭代器、适配器、空间配置器。

容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据，从实现角度来看，STL容器是一种class template。

算法：各种常用的算法，如sort、find、copy、for_each，从实现的角度来看，STL算法是一种function template。

迭代器：扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种operator*, operator->, operator++, operator–等指针相关操作予以重载的class template，所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。

仿函数：行为类似函数，可以为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class或者class template。

适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。

空间配置器：负责空间的配置与管理，从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

交互关系：容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数。

在C++标准中，STL被组织为下面的13个头文件：

侯捷《STL源码剖析》的视频图:

STL各个组件的详细组成部分:

STL容器简介

C++ STL 提供几大类标准容器类的实现：

顺序性容器

• vector 从后面快速的插入与删除，直接访问任何元素

• deque 从前面或后面快速的插入与删除，直接访问任何元素

• list 双链表从任何地方快速插入与删除

• array C++11

• forward_list C++11

顺序容器对比

• vector是一段连续的内存块，而deque是多个连续的内存块，list 是所有数据元素分开保存，可以是任何两个元素没有连续。

• vector的访问性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。

• list 是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。

• deque 是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有比list好的查询性能，有比vector好的插入、删除性能。如果需要随即存取且关心两端数据的插入和删除，那么deque是最佳之选。

容器适配器

• stack 栈 后进先出

• queue 队列 先进先出

• priority_queue 优先队列 最高优先级元素总是第一个出列

关联容器

• set 集合 快速查找，不允许重复值

• multiset 多重集合 快速查找，允许重复值

• map 基于关键字快速查找，不允许重复值

• multimap 基于关键字快速查找，允许重复值

无序关联容器

• unordered_set 快速查找，不允许重复值

• unordered_multiset 快速查找，允许重复值

• unordered_map 基于关键字快速查找，不允许重复值

• unordered_multimap 基于关键字快速查找，允许重复值

To Be Continued

时间原因 先写这么多 先去上班了 明天继续。

参考资料

• https://www.kancloud.cn/digest/anda0109-dev/141017

• https://www.cnblogs.com/tp-16b/p/9186826.html

原创不易 生活更难
点赞在看 养成习惯
走心走肾不如走一波分享
坚持写的我&坚持读的你 都比昨天更优秀！