《学习STL》-1.STL简介

2023-05-16

引言

当你C++入门后，学了些C++编程规则，正如《C++Primer》里的内容，你知道C++里面的基本数据类型、循环、判断、函数、类、模板等。这阶段你的确会编写一些基本的程序，例如打印、求最大值、求最大公约最小公倍数等。

当你把这些简单的程序都写对了，你以为你已经熟练掌握了C++，他们告诉你：“程序=算法+数据结构”。于是你终于知道世界上还有“算法“ 和 ”数据结构“ 这两样东西存在！于是你跑去搜索这两样东西，我的天，“算法”和“数据结构“是如此厚的俩本书，这下好了，又要埋头苦学这两本书。

当你吭哧吭哧的学完这两样当西，学会了如何去实现一个数据结构、例如链表（list）、堆栈（heap）、队列（queue）、也学会了排序、查找等基本算法后。今天我要告诉你：“Alexander Stepanov这帮大神已经把常用的“数据结构“及数据结构对应的方法已经实现出来并放在STL中了，你直接使用就完了”。

一.什么是STL?

STL（Standard Template Library），即标准模板库，是一个高效的C++程序库，它1998年被纳入C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming），引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术。

从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。如果查阅任何一个版本的STL源代码，你就会发现，模板作为构成整个STL的基石是一件千真万确的事情。除此之外，还有许多C++的新特性为STL的实现提供了方便。

在我看来，为广大C++程序员造了一些大家都能用（可复用性思想，通用性思想）的并且好用（泛型编程思想）的轮子，C++让程序员专注于项目开发。

二.STL的前世今生

被誉为STL之父的Alexander Stepanov（亚历山大·斯特潘诺夫），出生于苏联莫斯科，早在20世纪70年代后半期，他便已经开始考虑，在保证效率的前提下，将算法从诸多具体应用之中抽象出来的可能性，这便是后来泛型化思想的雏形。为了验证自己的思想，他和纽约州立大学教授Deepak Kapur，伦塞里尔技术学院教授David Musser共同开发了一种叫做Tecton的语言。尽管这次尝试最终没有取得实用性的成果，但却给了Stepanov很大的启示。

在随后的几年中，他又和David Musser等人先后用Schema语言（一种Lisp语言的变种）和Ada语言建立了一些大型程序库。这其间，Alexander Stepanov开始意识到，在当时的面向对象程序设计思想中所存在的一些问题，比如抽象数据类型概念所存在的缺陷。Stepanov希望通过对软件领域中各组成部分的分类，逐渐形成一种软件设计的概念性框架。

1987年左右，在贝尔实验室工作的Alexander Stepanov开始首次采用C++语言进行泛型软件库的研究。但遗憾的是，当时的C++ 语言还没有引入模板（template）的语法，现在我们可以清楚的看到，模板概念之于STL实现，是何等重要。是时使然，采用继承机制是别无选择的。尽管如此，Stepanov还是开发出了一个庞大的算法库。与此同时，在与Andrew Koenig（前ISO C++标准化委员会主席）和Bjarne Stroustrup（C++语言的创始人）等顶级大师们的共事过程中，Stepanov开始注意到C/C++语言在实现其泛型思想方面所具有的潜在优势。就拿C/C++中的指针而言，它的灵活与高效运用，使后来的STL在实现泛型化的同时更是保持了高效率。另外，在STL中占据极其重要地位的迭代子概念便是源自于C/C++中原生指针（ native pointer）的抽象。

1988年，Alexander Stepanov开始进入惠普的Palo Alto实验室工作，在随后的4年中，他从事的是有关磁盘驱动器方面的工作。直到1992年，由于参加并主持了实验室主任Bill Worley所建立的一个有关算法的研究项目，才使他重新回到了泛型化算法的研究工作上来。项目自建立之后，参与者从最初的8人逐渐减少，最后只剩下两个人--Stepanove本人和Meng Lee。经过长时间的努力，最终，信念与汗水所换来的是一个包含有大量数据结构和算法部件的庞大运行库，这便是现在的STL的雏形，STL的一个实现版本--HP STL。

1993年，当时在贝尔实验室的Andrew Koenig看到了Stepanove的研究成果，很是兴奋。在他的鼓励与帮助下，Stepanove于是年9月的圣何塞为ANSI/ISO C++标准委员会做了一个相关演讲（题为"The Science of C++ Programming"），向委员们讲述了其观念。然后又于次年3月，在圣迭戈会议上，向委员会提交了一份建议书，以期使STL成为C++标准库的一部分。尽管这一建议十分庞大，以至于降低了被通过的可能性，但由于其所包含的新思想，投票结果以压倒多数的意见认为推迟对该建议的决定。

随后，在众人的帮助之下，包括Bjarne Stroustrup在内，Stepanove又对STL进行了改进。同时加入了一个封装内存模式信息的抽象模块，也就是现在STL中的allocator，它使STL的大部分实现都可以独立于具体的内存模式，从而独立于具体平台。在同年夏季的滑铁卢会议上，委员们以80%赞成，20%反对，最终通过了提案，决定将STL正式纳入C++标准化进程之中，随后STL便被放进了会议的工作文件中。自此，STL终于成为了C++家族中的重要一员。

此后，随着C++标准的不断改进，STL也在不断地作着相应的演化。直至1998年，ANSI/ISO C++标准正式定案，STL始终是C++标准中不可或缺的一大部件。

三.什么时候使用STL

如果你要在程序中用到堆栈、队列、链表、数组、键值对、集合等一些基本数据结构和对应数据结构的方法，而不想自己去实现，那么你就可以考虑使用STL。

另外，STL作为一种标准，便于交流，掌握它，一方面可以让你写的程序，易于让别人理解，另一方面你也能够比较容易地理解别人写的程序。

四.STL有什么内容

STL所包括的内容如下图所示，先看看以下这幅图像有个感性认识：

STL提供六大组件，彼此可以组合套用：

1. 容器（Containers）：各种数据结构，用来存放数据。从实现的角度来看，STL容器是一种class template。具体包括:vector、deque、list、set、multiset、map、multimap、queue、priority_queue、stack这10个容器。

2. 算法（algorithms）：各种常用算法，如：sort、search、copy、erase。从实现的角度来看，STL算法是一种 function template。STL中算法大致分为四类，总共70个算法：
https://blog.csdn.net/luxiaoyu_sdc/article/details/6416043?utm_source=app&from=singlemessage

非可变序列算法：指不直接修改其所操作的容器内容的算法。
可变序列算法：指可以修改它们所操作的容器内容的算法。
排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
数值算法：对容器内容进行数值计算。

3. 迭代器（iterators）：容器与算法之间的胶合剂，是所谓的“泛型指针”。共有五种类型，以及其他衍生变化。从实现的角度来看，迭代器是一种将 operator*、operator->、operator++、operator- - 等指针相关操作进行重载的class template。所有STL容器都有自己专属的迭代器，只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

4. 仿函数（functors）：行为类似函数，可作为算法的某种策略（policy）。从实现的角度来看，仿函数是一种重载了operator（）的class或class template。一般的函数指针也可视为狭义的仿函数。

5. 配接器（adapters）：一种用来修饰容器、仿函数、迭代器接口的东西。例如：STL提供的queue 和 stack，虽然看似容器，但其实只能算是一种容器配接器，因为它们的底部完全借助deque，所有操作都由底层的deque供应。改变 functors接口者，称为function adapter；改变 container 接口者，称为container adapter；改变iterator接口者，称为iterator adapter。

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

这六大组件的交互关系：container（容器）通过 allocator（配置器）取得数据储存空间，algorithm（算法）通过 iterator（迭代器）存取 container（容器）内容，functor（仿函数）可以协助 algorithm（算法）完成不同的策略变化，adapter（配接器）可以修饰或套接 functor（仿函数）。

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

【算法】STL算法部分主要由头文件<algorithm>,<numeric>,<functional>组成。要使用 STL中的算法函数必须包含头文件<algorithm>，对于数值算法须包含<numeric>，<functional>中则定义了一些模板类，用来声明函数对象。

【迭代器】迭代器提供对集合(容器)元素的操作能力, 迭代器提供的基本操作就是访问和遍历.

<iterator> 定义了C++ STL标准中的一些迭代器模板类，这些类都是以std::iterator为基类派生出来的。

【容器】STL中的容器定义在std命名空间下，需要引入头文件<vector>,<set>,<map>,<list>,<deque>,<stack>等。容器可以分为三大类：

顺序容器：
<vector>   vector：尾端插入元素有较高性能，动态数组实现
<deque>   deque：首尾插入元素都有较高性能，动态数组实现
<list>   list：可以常数时间在任何地方插入元素，链表实现

关联容器：
<set> set:不同元素的集合，平衡二叉树实现，检索时间是O(log(N))；multiset同上set，但可以包含相同元数据。
<map> map:同set，但存放的是键值对；multimap:同map，但可以包含相同键。

容器适配器：
<queue> queue、priority_queue
<stack> stack

上述容器通用方法有：empty、size、swap、max_size，前两类容器支持迭代器，成为第一类容器。

顺序容器还有以下通用方法：front、back、pop_back、push_back。其中，front()和back()返回的是容器的首尾元素的引用。

容器之间的比较取决于第一个不等的元素，如果长度相同且所有元素相等，两个容器相等；如果一个是另一个的子序列，则较短的容器小于较长的容器。

容器适配器是逻辑数据结构，需要用一种顺序容器来实现。例如，stack默认使用deque来实现，也可指定它的实现方式。

【配置器】

<memory> memory是C++空间配置器及new delete定义的头文件，里面定义了空间配置器，new delete及用于调用构造函数的函数。
<utility> 定义重载的关系运算符，简化关系运算符的写入，它还定义了pair类型，该类型是一种模板类型，可以存储一对值。这些功能在库的其他地方使用

参考：

https://blog.csdn.net/tanqiuwei/article/details/7323374.html （c++中STL库简介及使用说明）

https://blog.csdn.net/Keungchao1/article/details/50932397.html （STL概述）

https://blog.csdn.net/huayehanshan/article/details/3864191.html （STL六大组件）

https://blog.csdn.net/qq_36779888.html (C++ STL详解)

https://blog.csdn.net/summer00072/article/details/81182171.html (STL简单介绍)

https://blog.csdn.net/luxiaoyu_sdc/article/details/6416043.html (STL中的所有算法(70个))

https://blog.csdn.net/fengbingchun/article/details/77985191.html (C++/C++11中头文件iterator的使用)

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

STL