2.3.2 标准模板库概述

标准模板库是所有C++编译器和所有操作系统平台都支持的一种库。STL是 C++的ANSI/ISO标准的一部分，可以用于所有C++语言编译器和所有平台（Windows/UNIX/Linux）。同一段STL代码在不同编译器和操作系统平台上运行的结果都是相同的，但是底层实现可以不同，STL的使用者并不需要了解它的底层实现。

STL从广义上包括三类：Algorithm（算法）、Container（容器）和Iterator（迭代器），几乎所有的代码都采用了类模板和函数模板的方式，这比传统的由函数和类组成的库提供了更好的代码重用机会。下面概述STL的三大组成部分。

1．算法

STL中算法的大部分是泛型函数，每个算法能处理大量不同容器类中的数据。值得注意的是，STL中的算法大多有多种版本，用户可以依照具体的情况选择合适版本。STL的泛型算法包括三种基本类型。

① 变序型队列算法：又称为可修改的序列算法，包括复制（Copy）算法、交换（Swap）算法、替代（Replace）算法、删除（Clear）算法、移动（Remove）算法、翻转（Reverse）算法等。这些算法可以改变容器中的数据（数据值和其值在容器中的位置）。

② 非变序型队列算法：处理容器内的数据而不改变它们。

③ 排序算法：包括对容器中的值进行排序、合并以及搜索的算法、通用数值算法等。2.3.3节将详细介绍排序算法的应用。

2．容器

在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性。经典的数据结构数量有限，但是开发者常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL的容器（如表2-3所示）为开发者提供了这样的方便：它允许开发者重复利用已有的实现构造自己特定类型下的数据结构。通过设置一些类模板，STL的容器对最常用的数据结构提供了支持。STL的容器分为顺序容器（Sequence Container）和关联容器（Associative Container）。

表2-3 STL的常用容器

顺序容器把数据对象组织成有限线性集合，容器中所有对象都属于同一类型。STL的三种基本顺序容器是向量（Vector）、线性表（List）、双向队列（Deque）。

关联容器提供了基于关键码（Key）的快速数据检索能力。容器中的数据元素被排好序，检索数据时可以二分搜索。STL有4种关联容器：当一个关键码对应一个值（Value）时，可以使用集合（Set）和映射（Map）；当对应同一关键码有多个值被存储时，可以使用多集合（MultiSet）和多映射（MultiMap）。

3．迭代器

迭代器实际上是一种泛化指针。如果一个迭代器指向了容器中的某一成员，那么迭代器将可以通过自增或自减来遍历容器中的所有成员。迭代器是联系容器和算法的媒介，是算法操作容器的接口。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每个容器定义了其本身所专有的迭代器，用以存取容器中的元素。

常用的迭代器如下。

① iterator：顺序迭代器，都可以通过自增操作（iterator++）在容器中顺序移动一个位置。需要说明的是，vector的iterator可以使用“+=”“- -”“++”“-=”中的任何一种操作符和“<”“<=”“>”“>=”“==”“!=”等比较运算符。容器的begin和end函数能返回容器的开始和结束位置值。

② reverse_iterator：逆序迭代器，都可以通过自增操作（reverse_iterator++）在容器中向逆序移动一个位置。容器的rbegin和rend函数能返回容器的结束和开始位置值。

③ const_iterator：恒定顺序迭代器，用于指向一个只读的值。

④ const_reverse_iterator：恒定逆序迭代器，也用于指向一个只读的值。