C++泛型编程

所谓泛型编程（Generic Programming）是指编程与类型无关，编写的算法可以在各种类型上使用。标准模板库是一个典型的使用泛型编程思想设计的C++库。

1. 标准模板库

在C++中提供了一个STL（Standard Template Library）库，这个库中提供了基本的数据结构和算法。比如：链表、集合等。

容器分为两类：

• 顺序容器：元素按照线性排列的容器，比如向量、链表等
• 关联容器：元素按照关键字关系存储，能够通过关键字快速找到元素，比如map、set等

注：数组也是一种特殊的顺序容器，字符串也是一种特殊的顺序容器。

算法提供了可以在多种容器上进行的一些通用操作，比如find、min等，它们可以作用在数组、向量、链表等容器上。为了实现算法与容器无关，算法不用容器为参数，而是以迭代子为参数。

写一个算法find，在一个存放整数的vector中查找一个整数值。

   1 int *find(const vector<int> &vec, int value) {
   2     for(int i = 0; i < vec.size(); i++) {
   3         if(vec[i] == value)
   4             return &vec[i];
   5     }
   6     return NULL;
   7 }

现在将这个程序改成在存放任何类型的vector中都可以查找一个值，我们可以使用template

   1 template<class T>
   2 T* find(const vector<T> &vec, T value) {
   3     for(int i = 0; i < vec.size(); i++) {
   4         if(vec[i] == value)
   5             return &vec[i];
   6     }
   7     return NULL;
   8 }

接下来让这个find既可以在vector中查找，也可以在数组中查找。我们可以用函数重载的方式实现，但是这样要写两个函数。

如果要用一个函数实现，我们就不能传vector或者array，而是它们共同的东西。我们用起始元素和终止元素的地址来标识。

   1 template<class T>
   2 T* find(T* begin, T* end, T value) {
   3     while(begin != end) {
   4         if(*first == value)
   5             return first;
   6         first ++;
   7     }
   8     return NULL;
   9 }