C++ STL编程

2019-03-23 本文已影响8人 konishi5202

一、STL简介

1.1 初识STL

STL（Standard Template Library，即标准模版库）是一个具有工业级强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域所常用的基本数据结构和基本算法。为广大C++程序员提供了一个可扩展的应用框架，高度体现了软件的可复用性。这种现象有些类似于Microsoft Visual C++中的MFC（Microsoft Foundation Class Library），或者是Borland C++ Builder中的VCL（Virsual Component Library）。

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

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

1.2 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的框架

2.1 STL的分类

STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器）。几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

在C++标准中，STL被组织为下面13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。

2.2 算法

大家都能取得的一个共识是函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——你可以将所有的类型划分为少数的几类，然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。

算法（algorithm）是应用在容器上以各种方法处理其内容的行为和功能。例如：有对容器内容排序、复制、检索、合并等算法。在STL中，算法是由模板函数表现的。这些函数不是容器类的成员函数，相反它们是独立的函数。令人吃惊的特点之一就是其算法是如此的通用，不仅可以将其用于STL容器，而且可以用于普通的C++数组或任何其他应用程序指定的容器。

STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以你所指定的规则对序列进行稳定性排序等等。这样一来，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。

算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。

<algorithm>：是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模板函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等；
<numeric>：体积很小，只包括几个在序列上面进行简单数学运算的模版函数，包括加法和乘法在序列上的一些操作；
<functional>：其中定义了一些模板类，用以声明函数对象。

2.3 容器

在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。

经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模版类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。

容器是数据在内存中的组织的方法，例如：数组、堆栈、队列、链表、二叉树等（这些都不是STL标准容器）。STL中的容器是一种存储T（Template）类型值的有限集合的数据结构，容器的内部实现一般是类。这些值可以是对象本身，如果数据类型T代表的是class的化。

容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表总结一下它们和相应头文件的对应关系。

向量（vector）：连续存储的元素<vector>；
列表（list）：由节点组成的双向列表，每个节点包含着一个元素<list>；
双队列（deque）：连续存储的指向不同元素的指针所组成的数组<deque>；
集合（set）：由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序<set>；
多重集合（multiset）：允许存在两个次序相等的元素的集合<set>；
栈（stack）：后进先出的值的排列<stack>；
队列（queue）：先进先出的值的排列<queue>；
优先队列（priority_queue）：元素的次序是由作用于所存储的值对上的某种谓词决定的一种队列<queue>；
映射（map）：由{键,值}对组成的集合，以某种作用于键对上的谓词排列<map>；
多重映射（multimap）：允许键对有相等的次序的映射<map>。

2.4 迭代器

一旦选定一种容器类型和数据行为（算法），那么剩下唯一要做的就是用迭代器使其相互作用。可以把迭代器看作一个指向容器中元素的普通指针，可以如递增一个指针那样递增迭代器，使其依次指向容器中每一个后继的元素。迭代器是STL中的一个关键部分，因为它将算法和容器连接在一起。

下面要说的迭代器从作用上来说是最基本的部分，可是理解起来比前两者都要费力一些（至少笔者是这样）。软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在STL中就是用迭代器来完成的。

概括来说，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。

迭代器部分主要由头文件<utility>,<iterator>和<memory>组成。

<utility>：是一个很小的头文件，它包括了贯穿使用在STL中的几个模版的声明；
<iterator>：提供了迭代器使用的许多方法
<memory>：它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制；<memory>中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。

对于之前不太了解STL的读者来说，上面的文字只是十分概括地描述了一下STL的框架，对您理解STL的机制乃至使用STL所起到的帮助微乎甚微，这不光是因为深入STL需要对C++的高级应用有比较全面的了解，更因为STL的三个部分算法、容器和迭代器三部分是互相牵制或者说是紧密结合的。从概念上讲最基础的部分是迭代器，可是直接学习迭代器会遇到许多抽象枯燥和繁琐的细节，然而不真正理解迭代器又是无法直接进入另两部分的学习的（至少对剖析源码来说是这样）。可以说，适应STL处理问题的方法是需要花费一定的时间的，但是以此为代价，STL取得了一种十分可贵的独立性，它通过迭代器能在尽可能少地知道某种数据结构的情况下完成对这一结构的运算，所以下决心钻研STL的朋友们千万不要被一时的困难击倒。其实STL运用的模式相对统一，只要适应了它，从一个STL工具到另一个工具，都不会有什么大的变化。

对于STL的使用，也普遍存在着两种观点。第一种认为STL的最大作用在于充当经典的数据结构和算法教材，因为它的源代码涉及了许多具体实现方面的问题。第二种则认为STL的初衷乃是为了简化设计，避免重复劳动，提高编程效率，因此应该是“应用至上”的，对于源代码则不必深究。笔者则认为分析源代码和应用并不矛盾，通过分析源代码也能提高我们对其应用的理解，当然根据具体的目的也可以有不同的侧重。

三、50条忠告

把C++当成一门新的语言学习；
看《Thinking In C++》，不要看《C++变成死相》；
看《The C++ Programming Language》和《Inside The C++ Object Model》，不要因为他们很难而我们自己是初学者所以就不看；
不要被VC、BCB、BC、MV、TC等词汇所迷惑——他们都是集成开发环境，而我们要学的是一门语言；
不要放过任何一个看上去很简单的小编程问题——他们往往并不那么简单，或者可以引申出很多知识点；
会用Visual C++，并不说明你就会C++；
学class并不难，template、STL、generic programming也不过如此——难的是长期坚持实践和不遗余力的博览群书；
如果不是天才的话，想学编程就不要想玩游戏——你以为你做到了，其实你的C++水平并没有和你通关的能力一起变高——其实可以时刻记住：学习C++是为了编游戏的；
看Visual C++的树，是学不了C++语言的；
把时髦的技术挂在嘴边，还不如把过时的技术记在心里；
学习编程最好的方法之一就是阅读源代码；
在任何时刻都不要认为自己手中的书已经足够了；
请阅读《The Standard C++ Bible》（中文版：标准C++宝典），掌握C++标准；
看得懂的书，请仔细看；看不懂的书，请硬着头皮看；
别指望看一遍书就能记住和掌握什么——请看第二遍、第三遍。。。；
请看《Effective C++》和《More Effective C++》以及《Exceptional C++》；
不要停留在集成开发环境的摇篮上，要学会控制集成开发环境，还要学会用命令行方式处理程序；
和别人一起讨论有意义的C++知识点，而不是真吵XX行不行或者YY与ZZ哪个好；
请看《程序设计实践》，并严格的按照其要求去做；
不要因为C和C++中有一些语法和关键字看上去相同，就认为它们的意义和作用完全一样；
C++绝不是所谓的C的“扩充”——如果C++一开始就起名叫Z语言，你一定不会把C和Z语言联系得那么紧密；
请不要认为学过XX语言再改学C++会有什么问题——你只不过又在学一门全新的语言而已；
读完了《Inside The C++ Object Model》以后再来认定自己是不是已经学会了C++；
学习编程的秘诀是：编程、编程、再编程；
请留意下列书籍：《C++面向对象高效编程（C++ Effective Object-Oriented Software Construction）》、《面向对象软件构造（Object-Oriented Software Construction）》、《设计模式（Design Patterns）》、《The Art of Computer Programming》；
请把书上的程序例子亲手输入到电脑上实践，即使配套光盘中有源代码；
把在书上看到的有意义的例子扩充；
请重视C++中的异常处理技术，并将其切实的运用到自己的程序中；
经常回顾自己以前写过的程序，并尝试重写，把自己学到的新知识运用进去；
不要漏掉书中任何一个练习题——请全部做完并记录下解题思路；
C++语言和C++的集成开发环境要同时学习和掌握；
既然决定了学习C++，就请坚持下去，因为学习程序设计语言的目的是掌握程序设计技术，而程序设计技术是跨语言的；
就让C++语言的各种平台和开发环境去激烈竞争把，我们要以学习C++语言本身为主；
当你写C++程序写到一半却发现自己用的方法很拙劣时，请不要马上停手；请尽快将余下的部分初略的完成以保证这个设计的完整性，然后分析自己的错误并重新设计和编写；
别心急，设计C++的class确实不容易；自己程序中的class和自己的class设计水平是在不断的编程实践中完善和发展的；
决不要因为程序“很小”就不遵循某些你不熟悉的规则——好习惯是培养出来的，而不是一次性记住的；
每学到一个C++难点的时候，尝试着对别人讲解这个知识点并让他理解——你能讲清楚才说明你真的理解了；
记录下在和别人交流时发现的自己忽视或不理解的知识点；
请不断的对自己写的程序提出更高的要求，哪怕你的程序版本号会变成Version 100.xxx；
保存好你写过的所有的程序——那是你最好的积累之一；
请不要做浮躁的人；
请热爱C++。

四、C++头文件

4.1 传统C++

#include <assert.h>　　　　设定插入点
#include <ctype.h>　　　　字符处理
#include <errno.h>　　　　 定义错误码
#include <float.h>　　　　浮点数处理
#include <fstream.h>　　　文件输入／输出
#include <iomanip.h>　　　 参数化输入／输出
#include <iostream.h>　　　数据流输入／输出
#include <limits.h>　　　　定义各种数据类型最值常量
#include <locale.h>　　　　定义本地化函数
#include <math.h>　　　　　定义数学函数
#include <stdio.h>　　　　定义输入／输出函数
#include <stdlib.h>　　　　定义杂项函数及内存分配函数
#include <string.h>　　　　字符串处理
#include <strstrea.h>　　　基于数组的输入／输出
#include <time.h>　　　　　定义关于时间的函数
include <wchar.h>　　　　 宽字符处理及输入／输出
include <wctype.h>　　　　宽字符分类

4.2 标准 C++

#include <algorithm>　　　  通用算法
#include <bitset>　　　　　 位集容器
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>　　　　 复数类
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>　　　　　 双端队列容器
#include <exception>　　　 异常处理类
#include <fstream>
#include <functional>　　　 定义运算函数（代替运算符）
#include <limits>
#include <list>　　　　　　 线性列表容器
#include <map>　　　　　　 映射容器
#include <iomanip>
#include <ios>　　　　　　基本输入／输出支持
#include <iosfwd>　　　　输入／输出系统使用的前置声明
#include <iostream>
#include <istream>　　　　 基本输入流
#include <ostream>　　　　 基本输出流
#include <queue>　　　　　  队列容器
#include <set>　　　　　　 集合容器
#include <sstream>　　　　 基于字符串的流
#include <stack>　　　　　 堆栈容器
#include <stdexcept>　　　 标准异常类
#include <streambuf>　　　底层输入／输出支持
#include <string>　　　　　字符串类
#include <utility>　　　　 通用模板类
#include <vector>　　　　 动态数组容器
#include <cwchar>
#include <cwctype>

4.3 C99增加

#include <complex.h>　　复数处理
#include <fenv.h>　　　　浮点环境
#include <inttypes.h>　　整数格式转换
#include <stdbool.h>　　 布尔环境
#include <stdint.h>　　　整型环境
#include <tgmath.h>　　通用类型数学宏