版本1和2间的区别

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(*begin == value)
   5             return begin;
   6         begin ++;
   7     }
   8     return NULL;
   9 }

这个程序当中不再出现数组类型或者vector类型了。我们可以用各种数组来测试它：

   1 int ia[] = {1, 1, 2, 3, 5, 8, 13, 21, 34};
   2 double da[] = {1.5, 2.0, 2.5, 3.0, 3.5, 4.0};
   3 string sa[] = {"lion", "tiger", "leopard"}
   4 
   5 int *pi = find(ia, ia+9, 3);
   6 double *pd = find(da, da+6, 3.5);
   7 string *ps = find(sa, sa+3, "cat");

如果要在vector用find

   1 vector<string> svec;
   2 svec.push_back("lion");
   3 svec.push_back("tiger");
   4 svec.push_back("leopard");
   5 string *ps = find(&svec[0], &svec[svec.size()], "cat");

2. 迭代子iterator

如何让这个函数也可以作用在链表list上？在链表上，指针的运算就会发生变化，++,*,和!=都和指针不同。这时我们用迭代子来代替指针。

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

这时，我们可以这样使用这个函数：

   1 int ia[] = {1, 1, 2, 3, 5, 8, 13, 21, 34};
   2 int *pa = find(ia, ia+9, 13);
   3 if(pa != ia+9)
   4     cout << "found";
   5 
   6 vector<int> ivec;
   7 vector<int>::iterator it;
   8 it = find( ivec.begin(), ivec.end(), 13);
   9 if( it != ivec.end() )
  10     cout << "found";
  11 
  12 list<int> ilist;
  13 list<int>::iterator iter;
  14 iter = find(ilist.begin(), ilist.end(), 13);
  15 if( iter != ilist.end() )
  16     cout << "found"

3. 函数对象

我要找出满足特定条件的元素，则我们给函数传一个判断标准而不是一个具体的值：

Iterator find_if(Iterator begin, Iterator end, FunctionObject op);

   1 int ia[] = {1, 1, 2, 3, 5, 8, 13, 21, 34};
   2 int *pa = find_if(ia, ia+9, greater_than_ten);

   1 bool greater_than_ten(int a) {
   2     return a > 10;
   3 }

"C++泛型编程"版本比较

C++泛型编程

1. 标准模板库

2. 迭代子iterator

3. 函数对象