泛型编程

泛型编程-概观

• 泛型编程(Generic programming) 是一种编程方法，这种方法将类型(type)以一种to-be-specified-later的方式给出，等到需要调用的时候，再以参数方式，通过具体的、特定的类别实例化(instantiate)一个具体的方法或对象
• 泛型编程作为一种编程的想法或思想，不依赖具体的语言
• 大多数面向对象的语言(O O languages)都支持泛型编程，(只不过在C++种以模板的这种形式表现出来)比如：C++、C#、Java、Ada….
• C++里面的泛型是通过模板以及相关性质表现出来

特性(Traits)

- 什么是traits以及为什么使用traits？

假设给定一个数组，计算数组种所有元素的和：
A[0] | A[1] |…| A[n]   $\sum_{k=0}^n A[k]$

• 我们可以很直接地写出如下的计算函数:

  template <typename T> 
  inline T Sigma(const T const* start, const T const* end) {
      T total = T(); // suppose T() actually creates a zero value
  
      //T()是一个构造函数目的将total初始化为0；
      
      while (start != end) {
          total += *start ++ ;
      }
  
      return total;
  }

• 当我们使用char类型调用模板函数是，问题就来了：

  char szNames[] = "abc";
  std :: size_t nLength = strlen(szNames);
  char* p = szNames;
  char* q = szNames + nLength;
  printf("sigma(ezNames) = %d\n", Sigma(p,q));

  $$294 = 0x0126$$ $$0000 | 0001 | 0010 | 0110$$

  Char类型能hold住的最大值为0xFF = 255 也就是两个字节所以0010和0110可容纳的但是abc加起来大于255就溢出到溢出到1这个bit

• 调用Sigma(szNames)的结果是38( = 0x26)!而并不是所期望的值(97 + 98 + 99 = 294)

• 原因显而易见的：char无法存下这个294这个值
• 如果要得到正确的结果，我们就不得不强制使用int类型：

  int s = Sigma<int>(p,q);

• 但是这种不必要的转换是完全可以避免的!
• 解决方法是：为每个Sigma函数的参数类型T创建一种关联(association)，关联的类别就是用来储存Sigma结果的类型
• 这种关联可以看作是类型T的一种特性(characteristic fo the type T),因为sigma函数返回值的类型叫做T的trait
• T与其trait的关系推演如下：
  T -> association -> characteristic of T -> another type -> trait
• Traits可以实现为模板类，而关联(association)则是针对每个具体类型T的特化。在这个例子里我们将trait命名为SigmaTraits, 叫做traits模板(traits template)

Traits实现：

template <typename T>
class SigmaTraits { };
//可以人为的将返回的数值边得相对的大

template <>
class SigmaTraits<char> {
public:
    typedef int ReturnType;
};

template <>
class SigmaTraits<short> {
public:
    typedef int ReturnType;
};

template <>
class SigmaTraits<int> {
public:
    typedef long ReturnType;
};

template <>
class SigmaTraits<unsigned int> {
public:
    typedef  unsigned long ReturnType;
};

template <>
class SigmaTraits<float> {
public:
    typedef double ReturnType;
};

• 模板类SigmaTraits叫做traits template， 它含有其参数类型T的一个特性(trait), 即ReturnType

• 现在Sigma函数可以改写成:

  template <typename T>
  inline typename SigmaTraits<T> :: ReturnType Sigma (const T const* start, const T const* end) {
      typedef typename SigmaTraits<T> :: ReturnType ReturnType;
  
      ReturnType s = ReturnType();
  
      while (start != end) {
          s += *start ++;
      }
  
      return s;
  }

迭代器(iterator)

什么是迭代器？

迭代器是指针的泛化(generalization of pointers)

• 迭代器本身就是一个对象，指向另外一个(可以被迭代的)对象
• 用来迭代一组对象，即如果迭代器指向一组对象种的某个元素，则通过increment以后它就可以指向下组对象中的下一个元素

在STL中迭代器是容器与算法之前的接口

• 算法通常以迭代器作为输入参数
• 容器只要提供一种方式，可以让迭代器访问容器中的元素即可

迭代器的基本思想

• 在STL中，迭代器最终要的思想就是分离算法和容器，使之不需要相互依赖

• 迭代器将算法和容器粘合(stick)在一起从而使得一种算法的实现可以运用到多种不同的容器上，如下面的例子,find算法接受一对迭代器，分别指向容器的开始位置和最终位置

  template <typename _InIt, typename _Ty>
  inline _InIt find(_InIt _First, _InIt _Last, const _Ty& _Val) {
      //find first matching _Val
      for (; _First != _Last; ++_First) {
          if (*_First == _Val)
            break;
      }
  
      return (_First);
  }

  find算法对于不同的容器，比如vector, list, deque均适用：

  std :: vector<int> v(...);
  std :: list<int> l(...);
  std :: deque<int> d(...);
  
  std :: vector<int> :: iterator itv = std :: find(v.begin(), v.end(), elementToFind)
  std :: list<int> :: iterator itl = std :: find(l.begin(), l.end(), elementToFind)
  std :: deque<int> :: iterator it3 = std :: find(d.begin(), d.end(), elementToFind)

  每种容器都有其对应的迭代器