[cpp][generic-programming] 泛型编程与STL

    面向过程、面向对象、泛型编程(Generic Programming,简称GP)应该是三种重用的编程方法。传统的C++语言中,泛型编程思想仅仅体现于简单的模板技术。而之后引入的标准模板库STL(Standard Template Library)是泛型编程思想的实际体现和具体实现。

1. 问题引入

    面向过程的方法,可以将常用代码段封装在一个函数中,然后通过函数调用来达到目标代码重用的目的。
    面向对象的方法,可以通过类的继承来实现(对象的目标)代码的重用。

    如果需要编写一个可用于不同数据类型的算法，可以采用的方法有：
    1). 面向过程的方法,对源代码进行复制和修改，生成不同数据类型版本的算法函数，调用时需要对数据类型进行手工的判断；
    2). 面向对象的方法,在一个类中，编写多个同名函数，它们的算法一致，但是所处理数据的类型不同，当然函数的输入参数类型也不同，过函数重载来自动调用对应数据类型版本的函数。

     显然, 以上两种方法都需编写多个相同算法的不同函数，不能做到代码重用。它们二者之间的主要差别，只是调用的方便与否。如果采用泛型编程(例如可采用以类型作为参数的传统C++的模板技术),就可以做到源代码级的重用：

     泛型编程方法,编写以类型作为参数的一个模板函数,在调用时再将参数实例化为具体的数据类型。为了实现一个这样的算法，在具有不同组织结构(如数组、链表、队列、堆栈等)、含同一类型(如char、int、float、struct S或class C等)的数据或对象的集合(容器)上的，与具体数据类型无关的参数化通用算法(如排序、检索、复制、合并等)。只有模版是远远不够的，还需要能够表示这种集合的容器、能够在容器中遍历的迭代器、能够为算法和容器实现抽象存储的分配器、能够在不同容器之间进行转换的适配器等等。这些正是泛型编程的研究内容，也是STL要实现的目标。

2. 泛型编程

     泛型(generic)是一种允许一个值取不同数据类型的技术, 而基于此发高效的最抽象表示的编程方法被称为泛型编程(Generic Programming,通用编程/类属编程)。

     泛型编程关注于产生通用的软件组件，让这些组件在不同的应用场合都能很容易地重用。在C++中，类模板和函数模板是进行泛型编程极为有效的机制. 与针对问题和数据的面向对象的方法不同，泛型编程中强调的是算法,是一类通用的参数化算法,它们对各种数据类型和各种数据结构都能以相同的方式进行工作,从而实现源代码级的软件重用。

     例如，不管(容器)是数组、队列、链表、还是堆栈,不管里面的元素(类型)是字符、整数、浮点数、还是对象,都可以使用同样的(迭代器)方法来遍历容器内的所有元素、获取指定元素的值、添加或删除元素，从而实现排序、检索、复制、合并等各种操作和算法。

     泛型编程的通用化算法，是建立在各种抽象化基础之上的：利用参数化模版来达到数据类型的抽象化、利用容器和迭代器来达到数据结构的抽象化、利用分配器和适配器来达到存储分配和界面接口的抽象化。

3. STL

      STL(Standard Template Library,标准模板库)是泛型编程思想的实际体现和具体实现，它是一种为泛型组件建立大型标准库的可扩展架构。STL本身，与面向对象无关，也与具体的程序设计语言无关。 STL的目标是在不损失效率的基础上进行抽象。这里的不损失效率,是指尽最大努力来保证其所有的泛型算法是最优的,并且和手工编码具有同样的运行效率。

      如果用数学语言来描述，STL的本质就是:不同的数据结构,对应于不同的地址代数结构、以及不同的地址连接方式。从数据结构的一个地址,转向下一个地址的一些列操作,就对应于迭代器。在数据结构中添加和删除地址的操作，就对应于容器。

      STL将容器看作是结构的泛化,它们都拥有成员,可以描述整体和局部这一现实世界事物的关键属性。STL使用了赋值的算法,要求采用面向值的语义。STL还假定对容器中的数据和对象，定义了全序。 STL的主要内容是6种组件：容器、泛型算法、迭代器、函数对象、分配器和适配器等。在标准C++中，STL是作为C++标准库的一部分而出现的。