模板编程：对循环for分步骤STL如何实现泛型

2020年3月18日下午12:20

基础概念：

C++ 是如何有效解决程序泛型问题的，有三点

第一，它通过类的方式来解决。
- 类里面会有构造函数、析构函数表示这个类的分配和释放。
- 还有它的拷贝构造函数，表示了对内存的复制。
- 还有重载操作符，像我们要去比较大于、等于、不等于。
- 这样可以让一个用户自定义的数据类型和内建的那些数据类型就很一致了。
第二，通过模板达到类型和算法的妥协。
- 模板有点像 DSL，模板的特化会根据使用者的类型在编译时期生成那个模板的代码。
- 模板可以通过一个虚拟类型来做类型绑定，这样不会导致类型转换时的问题。
- 模板很好地取代了 C 时代宏定义带来的问题。
第三，通过虚函数和运行时类型识别。
- 虚函数带来的多态在语义上可以支持“同一类”的类型泛型。
- 运行时类型识别技术可以做到在泛型时对具体类型的特殊处理。

一个良好的泛型编程需要解决如下几个泛型编程的问题：

算法的泛型：算法与类型解耦
数据结构（数据容器）的泛型：不区分顺序型的数据结构、非顺序型的数据结构
类型的泛型：我这里理解是SUM中的问题：那个T假设了 Iter 中出来的类型是T

实例详解：

第一步：算法的泛型：算法与类型解耦

void*指针

函数指针

int search(void* a, size_t size, void* target, 
  size_t elem_size, int(*cmpFn)(void*, void*) )
{
    	for(int i=0; i<size; i++) {
    		// why not use memcmp()
    		// use unsigned char * to calculate the address
    		if ( cmpFn ((unsigned char *)a + elem_size * i, target) == 0 ) {
      		return i;
    		}
		}
  		return -1;
}

第二步：数据结构（数据容器）的泛型：不区分顺序型的数据结构、非顺序型的数据结构

模板编程
不同数据结构：操作符重载

不同数据结构：包含迭代器

// 使用typename T抽象了数据结构中存储数据的类型
// 使用typename Iter，这是不同的数据结构需要自己实现的“迭代器”，这样也就抽象掉了不同类型的数据结构
template<typename T, typename Iter>
Iter search(Iter pStart, Iter pEnd, T target) 
{
		for(Iter p = pStart; p != pEnd; p++) {//通过操作符重载也就泛型掉了遍历
    		if ( *p == target ) 
      		return p;
  		}
  		return NULL;
}

第三步：类型的泛型：我这里理解是SUM中的问题：那个T假设了 Iter 中出来的类型是T

内部类：

迭代器。begin, end返回的是迭代器，其实就是一个内部类对象

迭代器内部类中实现了大量的重载方法。
问题是：

template<typename T, typename Iter>
T sum(Iter pStart, Iter pEnd) {
		T result = 0;
  		for(Iter p=pStart; p!=pEnd; p++) {
    		result += *p;
  		}
  		return result;  
}
/*
这个代码中最大的问题就是 T result = 0
1.那个0假设了类型是int
2.那个T假设了 Iter 中出来的类型是T
*/

解决方法：

//定义result的T应该可以从Iter中来。这样就可以保证类型是一样的，而且不会有被转型的问题
template <class T>
class container {
public:
  class iterator {
  public:
    typedef iterator self_type;
    typedef T   value_type;
    typedef T*  pointer;
    typedef T&   reference;

    reference operator*();
    pointer operator->();
    bool operator==(const self_type& rhs)；
    bool operator!=(const self_type& rhs)；
    self_type operator++() { self_type i = *this; ptr_++; return i; }
    self_type operator++(int junk) { ptr_++; return *this; }
    ...
    ...
  private:
    pointer _ptr;
  };

  iterator begin();
  iterator end();
  ...
  ...
};

template <class Iter>
typename Iter::value_type
sum(Iter start, Iter end, T init) {
		typename Iter::value_type result = init;//这条语句是关键
  		while (start != end) {
    		result = result + *start;
    		start++;
  		}
  		return result;
}

调用算法：

1
2
3

container<int> c;
container<int>::iterator it = c.begin();
sum(c.begin(), c.end(), 0);

基础概念：

C++ 是如何有效解决程序泛型问题的，有三点

一个良好的泛型编程需要解决如下几个泛型编程的问题：

实例详解：

第一步：算法的泛型：算法与类型解耦

第二步：数据结构（数据容器）的泛型：不区分顺序型的数据结构 、非顺序型的数据结构

第三步：类型的泛型：我这里理解是SUM中的问题：那个T假设了 Iter 中出来的类型是T

第二步：数据结构（数据容器）的泛型：不区分顺序型的数据结构、非顺序型的数据结构