简明STL

主要内容

泛型、模板、STL基本组件及之间的关系

泛型

Generic Programming，泛型程序设计，是程序设计语言的一种风格或范式。泛型允许程序员在强类型程序设计语言中编写代码时使用一些以后才指定的类型，在实例化时作为参数指明这些类型。 ——wikipedia.org

简单来说，泛型就是编写不依赖于具体数据类型的程序，将算法从特定的数据结构中抽象出来，成为通用的。

术语

概念：用来界定具备一定功能的数据类型。例如：
- 将 可以比大小的所有数据类型（有比较运算符） 这一概念记为Comparable；
- 将 具有公有的复制构造函数并可以用=赋值的数据类型 这一概念记为Assignable；
- 将 “可以比大小、具有公有的复制构造函数并可以用=赋值的所有数据类型 这个概念记作Sortable。
子概念：对于两个不同的概念A和B，如果概念A所需求的所有功能也是概念B所需求的功能，那么就说概念B是概念A的子概念。例如：
- Sortable既是Comparable的子概念，也是Assignable的子概念。
用概念做模板参数名：很多STL的实现代码就是使用概念来命名模板参数的——为概念赋予一个名称，并使用该名称作为模板参数名。
model 模型：符合一个概念的数据类型称为该概念的模型。例如：
- int是Comparable概念的模型；
- 静态数组类型无法用=给整个静态数组赋值，故不是Assignable概念的模型。

模板

C++的模板为泛型程序设计奠定了关键的基础。

函数模板

从函数重载到函数模板

重载的函数，如果其解决问题的逻辑一致、函数体语句相同，仅仅处理的数据类型不同，写多个相同的函数体就是一种重复劳动，而且还可能因为代码的冗余造成不一致性（即修改算法时需要多次修改，容易导致bug的出现）。为了解决这一问题，可以引入函数模板的概念，将函数与它所处理的数据类型分离开来。

1 2	template <模板参数表> 函数定义

其中模板参数表的内容可以有以下三种：

类型参数：class|typename 标识符
常量参数：类型说明符标识符
模板参数：template <模板参数表> class 标识符

函数模板固然好，但是也是有使用条件的。应当注意以下几点：

一个函数模板并非能够处理所有数据类型的数据，有时候我们也需要为某一或某些数据类型声明独立的函数；
一种数据类型要能够进行模板中涉及到的运算或操作，才可以函数模板的类型实参；
同样，自定义的类需要重载函数模板涉及到的运算符，才可作为类型实参。

类模板

有时候，我们希望类的一些属性、方法参数和返回值可以不受到数据类型的限制，我们可以类模板。使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型，这包括基本类型的和用户自定义类型。

template <模板参数表>
class 类名 [继承方式: 基类名] {
    //类成员声明
};

如果需要在类模板以外定义其成员函数，则要采用以下的形式：

template <模板参数表>
类型名 类名<模板参数标识符列表>::函数名(参数表) {
    //……
}

即每个成员函数都相当于一个函数模板。

此外，在模块化编程（多文件编程）中，使用类模板的类的定义和实现要写在一个头文件中。

与函数模板不同的是，在类模板的类实例化产生对象时，要为其提供提供类型实参：类名<类型列表> 对象名。

标准模板库-STL

Standard Template Library，标准模板库，简称STL，提供了一些非常常用的数据结构和算法。定义了一套概念体系，为泛型程序设计提供了逻辑基础。

STL中的各个类模板、函数模板的参数都是用这个体系中的概念来规定的。
使用STL的模板时，类型参数既可以是C++标准库中已有的类型，也可以是自定义的类型——只要这些类型是所要求概念的模型。

STL的基本组件

STL有四大基本组件：

Container 容器
Iterator 迭代器
Algorithms 算法
Function Object 函数对象（仿函数）

Container

容器，顾名思义，就是容纳、包含并管理一组元素的对象。

每一种容器都有其优点和缺点。为满足程序的各种需求，STL 准备了多种容器类型。基本容器类模板如下：

顺序容器：顺序容器是一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。这个位置和元素本身无关，而和操作的时间和地点有关，即顺序容器不会根据元素的特点排序而是直接保存了元素操作时的逻辑顺序。

大致包含以下几类容器：array（数组）、vector（向量）、deque（双端队列）、forward_list（单链表）、list（列表）
关联容器：关联式容器是非线性的树结构，更准确的说是二叉树结构。以键值的方式来保存数据，各元素之间没有严格的物理上的顺序关系，但是关联容器提供了对根据元素特点排序的功能，这样迭代器就能根据元素的特点**“顺序地”**（双引号是指我们可以自己规定这种顺序）获取元素。

大致包含以下几类容器：
- 有序关联容器：set（集合）、multiset（多重集合）、map（映射）、multimap（多重映射）
- 无序关联容器：unordered_set （无序集合）、unordered_multiset（无序多重集合）unordered_map（无序映射）、unorder_multimap（无序多重映射）
有序关联容器通过比较运算符来组织元素；而无序关联容器通过哈希函数和==来组织元素，故表现为无序。
容器适配器：适配器是使一事物的行为类似于另一事物的行为的一种机制，让一种已存在的容器类型采用另一种不同的抽象类型的工作方式的一种机制。可以理解为容器的接口，而具体采用哪种容器类型可以自己决定。

大致有三种适配器：stack（栈）、queue（队列）、priority_queue（优先队列）

使用容器需要包含相应容器对应的头文件。

Iterator

迭代器用于在一个对象群集的元素上进行遍历动作。对象群集可能是容器，也可能是容器的一部分。迭代器为容器提供一组公共接口。每种容器基本上都提供了各自的迭代器，且迭代器了解该容器的内部结构。

迭代器是泛化的指针，提供了访问容器中每个元素的方法。

同样，迭代器的本质是指针，指针也具有迭代器同样的特性，因此指针本身就是一种迭代器。

可以使用++运算符来获得指向下一个元素的迭代器；
可以使用*运算符访问一个迭代器所指向的元素，如果元素类型是类或结构体，还可以使用->运算符直接访问该元素的一个成员；
有些迭代器还支持通过--运算符获得指向上一个元素的迭代器。

使用独立于STL容器的迭代器，需要包含头文件<iterator>。

Algorithms

算法用来处理群集内的元素，可以出于不同目的搜寻、排序、修改、使用那些元素。所有容器的迭代器都提供一致的接口，通过迭代器的协助，算法程序可以用于任意容器。

STL包括70多个算法，可以广泛用于不同的对象和内置的数据类型。

例如：排序算法，消除算法，计数算法，比较算法，变换算法，置换算法和容器管理等等。

使用STL的算法，需要包含头文件<algorithm>。

Function Object

函数对象是泛化的函数：函数对象是一个行为类似函数的对象，对它可以像调用函数一样调用。

任何普通的函数和任何重载了()运算符的类的对象（或者结构体）都可以作为函数对象使用。

使用STL的函数对象，需要包含头文件<functional>。

基本组件间的关系

Iterators（迭代器）是 Algorithms（算法）和 Container（容器）的桥梁。

将迭代器作为算法的参数、通过迭代器来访问容器而不是把容器直接作为算法的参数。
将函数对象作为算法的参数而不是将函数所执行的运算作为算法的一部分。
使用STL中提供的或自定义的迭代器和函数对象，配合STL的算法，可以组合出各种各样的功能。