算法的泛化问题，这些坑你可能都经历过！|周立功教你学软件设计

第一章为程序设计基础，本文为1.6.3泛型编程。

 

>>>> 1.      泛型编程

 

下面将进一步以一个简单的循环查找为例，全面考察算法的泛化问题。假设要编写一个findValue()函数，在array数组中寻找一个特定的int值，详见程序清单 1.29。

 

程序清单 1.29 findValue()查找函数（1）

1     int *findValue(int *arrayHead, int arraySize, int value)

2     { 

3            for(int i =0; i < arraySize; ++i) 

4                   if(arrayHead[i] == value) 

5                          break; 

6            return &(arrayHead[i]);

7     }

 

该函数在某个范围内查找value，返回的是一个指针，指向它所找到的第一个符合条件的元素。如果没有找到，则返回最后一个元素的下一个位置（地址）。"最后元素的下一个位置"称为end，其作用是返回end表示"查找无结果"，为何不返回null呢？因为end指针可以对其它种类的数据结构带来泛化的效果，这是null做不到的。

 

在学习数组时，我们就被告诫，千万不要超越其下标范围，但事实上一个指向array元素的指针，不但可以合法地指向array的任何位置，也可以指向array尾端以外的任何位置。只不过，当指针指向array尾端以外的位置时，它只能用于与其它array指针相比较，不能间接引用其值。findValue()函数的使用方式如下：

const int arraySize = 7; 

int array[arraySize] = {0, 1, 2, 3, 4, 5, 6}; 

int *end = array + arraySize; 

 

int *ip = findValue(array, sizeof(array) / sizeof(int), 4); 

if(ip == end) 

       return false; 

else

       return true; 

 

显然，findValue()函数暴露了数组的实现细节，比如，arraySize，太过于依赖特定的数据结构。那么，如何设计一个算法，使它适用于大多数数据结构呢？或者说，如何在即将处理的未知的数据结构上，正确地实现所有的操作呢？事实上，一个序列有开始和结尾，既可以使用++得到下一个元素，也可以使用"*"得到当前元素的值。

 

显然，让阅读代码的人理解你的本意，至关重要是取一个不会让人产生误解的名字。对于包含范围，常用first和last。对于包含/排序范围，常用begin和end。比如，对于大多数需要分片的数组，使用begin和end表示包含/排除范围是最好的选择。遗憾的是，类似limit、filter和length这样具有多义性的英文单词会带来一定的困惑，而定义一个值的上限或下限时，max_和min_就是很好的前缀。

 

为了让findValue()函数适用于所有类型的数据结构，其操作应该更抽象化，让findValue()函数接受两个指针作为参数，表示一个操作范围，详见程序清单 1.30。

 

程序清单 1.30 findValue()查找函数（2）

1     int *findValue(int *begin, int *end, int value)

2     { 

3            while(begin != end && *begin != value) 

4                   ++begin;

5            return begin; 

6     }

 

由于findValue函数的返回值begin是一个指针，因此该函数是一个返回指针的函数，即指针函数。这个函数在"前闭后开"范围[begin, end)内（包含了begin迭代器的当前元素，而到end迭代器的前一个元素为止）查找value，并返回一个指针，指向它所找到的第一个符合条件的元素，如果没有找到就返回end。这里之