STL简介

STL是惠普实验室开发的一系列标准化组件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。在1994年被纳入C++标准，使之成为了C++库的重要组成部分。STL现在是C++的一部分，被内置于C++编译器中，所以学习STL不需要额外安装什么。

STL的内容从广义上讲分为三个主要部分：容器（container）、迭代器（iterator）和算法

（algorithm）。STL的一个基本理念就是将数据和操作分离，数据由容器类别加以管理，操作则由可定制的算法定义，迭代器在两者之间充当粘合剂。STL的结构可以用一张图来诠释，如图1所示。

图1 STL结构图

由图1可知， STL中的所有组件都由模板构成，其元素可以是任意类型，程序员通过选用恰当的群集类别，调用其成员函数和算法数据就万事大吉了。

在C++的标准中，STL被组织在13个头文件中：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>、<utility>，使用不同的内容，需要包含不同的头文件。接下来我们就容器、迭代器、算法这三个组件做简要介绍。

1、容器

容器类在面向对象的语言中特别重要，几乎所有的面向对象语言中都伴随着一个容器集，在C++中，这个容器集就是标准模板库（STL）。

在C++中，容器被定义为：在数据存储上，有一种对象类型，它可以装入其它对象或指向其他对象的指针，这种对象类型就叫作容器。简单说，容器就是保存其它对象的对象。

当然，这是一种朴素的理解。这种“对象”还包含一系列处理“其它对象”的方法，因为这些方法在程序设计上经常被用到，所以容器也体现了一个好处，就是“容器类是一种对特定代码重用问题的良好的解决方案”。

容器的另一个特点是，容器可以自行扩展，在解决问题时我们常常不知道需要存储多少个对象，也就是说我们不知道应该创建多大的内存空间来保存我们的对象，显然，数组在这一方面也力不从心。容器的优势就在这里，它不需要预先知道要存储多少个对象，只要创建一个容器，所有的处理将由容器自身完成。它可以自行申请或释放内存，并且用最优的算法来执行命令。

STL主要包含的容器有以下几种：

● vector<T>，是一种向量；

● list<T>，是一个双向链表容器，完成标准C++数据结构中链表的所有功能；

● queue<T>，是一种队列容器，完成了标准C++数据结构中队列的所有功能；

● stack<T>，是一种栈容器，完成了标准C++数据结构中栈的所有功能；

● deque<T>，是双端队列容器，完成了标准C++数据结构中栈的所有功能；

● priority<T>，是一种按值排序的队列容器；

● set<T>，是一种集合容器；

● multiset<T>，是一种允许出现重复元素的集合容器；

● map<key, value>，是一种关联数组容器；

● multimap<key, value>，是一种允许出现重复key值的关联数组容器。

上面的容器可分为两大类：序列式容器和关联式容器。序列式容器主要有vector、list和deque；关联式容器包括set、map、multiset和multimap等容器类模板。

2、迭代器

迭代器是STL中最基本的一部分内容，它将容器与算法联系起来，起着粘合剂的作用，几乎STL提供的所有算法都是通过迭代器存取元素来实现的。它有些类似于指针，当参数化类型是C++内部类型时，迭代器就是指针。

STL定义了5种类型的迭代器：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器，每种容器都支持某一种类型的迭代器。

● 输入迭代器（Input iterators）：用于为程序中需要的数据源提供输入接口，数据源一般指容器、数据流等。输入迭代器只能从一个序列中读取数值，输入迭代器可以被修改、被引用。

● 输出迭代器（Output iterators）：用于输出程序中已经得到的数据结果（容器、数据流）。输出迭代器只能向一个序列中写入数据，输出迭代器可以被修改、被引用。

● 前向迭代器（Forward iterators）：前向迭代器只能向前移动，它不仅具有输入和输出迭代器都具有的功能，还可以多次解析一个迭代器指定的位置，因此可以对一个值进行多次读写。

● 双向迭代器（Bidirectional iterators）：既可以用来读又可以用来写，它与前向迭代器相类似。双向迭代器可以同时进行前向和后向元素操作。所有的STL容器都提供了双向迭代器功能，既有利于数据的写入和读出，还有利于提供更加灵活的数据操作。

● 随机访问迭代器(Random access iterators)：它可以通过跳跃的方式访问容器中的任意数据类型，随机访问迭代器具有双向迭代器的所有功能，是功能最强大的迭代器。

迭代器的诞生使算法和容器分离成为可能，STL库通过迭代器给用户提供访问接口，可以隐藏内部实现细节，满足了封装性的设计要求。使访问容器元素变的简单、易用，使代码更加紧凑、简洁。

3、算法

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

对于初学者来说，学习STL确实有一定的难度，需要一定的时间，但只要适应了STL处理问题的方式，那么在以后的开发中，往往会事半功倍。