泛型算法

泛型算法能够针对不同的元素类型实现特定的算法，即针对各种类型的元素给出一个通式；其实现方式常常是通过指针对底层的地址进行操作，从而避免了因为顶层数据结构不同导致的差异。

引子：一个问题

若给定一个存储整形的vector，以及一个整数值，希望能在此vector种查找该值，若有则返回，无则返回0

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

若想针对所有数据类型，则可以使用函数模板

  1. template <typename elemType>
  2. elemType* find(const vector<elemType> &vec, const elemType &value)

通过指针传入数组

若想针对vector和array都能进行呢；该问题实际上是：

  • 将array元素传递进入find()而不指明该array
  • 将vector元素传入find()而不指明该vector :::tips 数组传递给函数时，或是从函数中返回，仅由第一个元素的地址会被传递；注意：若要返回数组，留心数组是否是在函数中定义的，是否会被销毁从而导致返回错误； :::

两种方案：

  • 传入数组的首地址以及数组的大小
  • 传入另一个地址指示读取的终点

第二种方案能够完全消除array或vector；

下标运算符

即使通过指针访问，也可以用下标运算符来操作
所谓的下标就是将array的起始地址加上索引值，产生出某个元素的地址，然后再将该地址提领以返回元素的值
如array[2];和*(array+2)；此外array+2表达的是指针的算术运算。在指针算术运算中，会把指针所指的类型的大小考虑进去，比如int型对应的存储空间是4Byte，那么array+2对应的地址应该在array的物理地址上+8；同时通过下标运算符会自动进行提领的操作；
于是，最终可以采用如下形式来隐藏数据结构：

  1. template <typename elemType>
  2. elemType* find(const elemType *first, const elemType *last,const elemType &value)
  3. {
  4.     if(!first||!last)
  5.         return 0;
  6.     for(;first!=last;++first)
  7.         if(*first==value)
  8.             return first;
  9.     return 0;
  10. }

若需要对list结构也能实现呢？则可以通过泛型指针（iterator）实现

小结

  • 数组传递给函数时，或是从函数中返回，仅由第一个元素的地址会被传递
  • 隐式的将数组传递给函数有两种方法；其中第二种更普适，即根据数组首尾地址来界定数组的大小
  • 函数中的指向数组的指针也可以当作数组名称使用，可以采用下标调用
  • 下标包含了地址计算以及提领的操作
  • 在指针算术运算中，会把指针所指的类型的大小考虑进去