周立功教授谈迭代器模式设计

如果任何一次遍历没有执行任何交换，则说明记录是有序的且终止排序。其中，p1指向数组的首元素，pNext指向p1所指向的元素的下一个元素，p2指向数组的尾元素（图 3.21（a））。如果*p1>遍历没有执行任何交换，则说明记录是有序的且终止排序。其中，p1指向数组的首元素，pNext指向p1所指向的元素的下一个元素，p2指向数组的尾元素（图 3.21（a））。如果*p1>*pNext，则交换指针所指向的内容，p1与pNext后移（图 3.21（b）），反之指针所指向的内容不变，p1与pNext后移，经过一轮排序之后，直到p1 = p2为止，最大元素移到数组尾部。

图 3.21  内部循环执行过程示意图

当最大元素移到数组的尾部时，则退出内部循环。p2前移后程序跳转到程序清单 3.49（15），p1再次指向数组的首元素，pNext指向p1所指向的元素的下一个元素（图 3.22（a））。此时，图 3.22（a）与图 3.21（a）的差别在于p2指向a[3]。经过一轮循环之后，直到p1 = p2，此时整数4移到a[3]所在的位置，剩余的排序详见图 3.22。当p1与p2重合在数组首元素所在的位置时，表示排序结束（图 3.22（d））。

图 3.22 外部循环执行过程示意图

由此可见，冒泡排序算法的核心是指针的操作，其主要行为如下：

●比较指针所指向的值的大小；

● 交换指针所指向的内容；

● 指针后移，即指针指向下一个元素；

● 指针前移，即指针指向前面一个元素。

由于这里是以int类型数据为例实现冒泡排序的，因此用户知道如何比较数据和如何交换指针所指向的内容，以及指针的前后移动。当使用支持任意类型数据的void *时，虽然算法程序不知道传入什么类型的数据，但调用者知道，因此在调用排序算法函数时，可以由用户传递参数通过回调函数实现。修改后的冒泡排序函数原型如下：

void iter_sort (void *begin, void *end, compare_t compare, swap_t swap);

其中，compare用于比较两个指针所指向的值的大小，compare_t类型定义如下：

typedef int (*compare_t) (void *p1, void *p2); 

swap函数用于交换两个指针指向的内容，swap_t类型定义如下：

typedef void (*swap_t) (void *p1, void *p2);

显然无法通过++或--移动指针，因为不知道传入的是什么类型的数据。如果知道数据占用4个字节，则可以通过指针的值加4或减4实现指针的移动。虽然使用这种方式可以实现指针的移动，但始终要求数据必须以数组的形式存储，一旦离开了这个特定的容器，则无法确定指针的行为。如果将算法与链表结合起来使用，显然代码中的p1++和p2--不适合链表。

基于此，"不妨对指针进行抽象，让它针对不同的容器有不同的实现，而算法只关心它的指针接口"。显然，需要容器提供相应的接口函数，才能实现指针前移和后移，通常将这样的指针称为"迭代器"。从某种意义上来说，迭代器作为算法的接口是广义指针，而指针满足所有迭代器的要求。其优势在于对任何种类的容器都可以用同样的方法顺序遍历容器中的元素，而又不暴露容器的内部细节，迭代器接口的声明详见程序清单3.50。

程序清单3.50  迭代器接口的声明

1   typedef void *iterator_t;                              // 定义迭代器类型

2    typedef void (*iterator_next_t)(iterator_t *p_iter);

3    typedef void (*iterator_prev_t)(iterator_t *p_iter);

4

5    // 迭代器接口（if 表示 interface，由具体容器实现，比如，链表、数组等）

6    typedef struct _iterator_if{

7        iterator_next_t  pfn_next;                          // 迭代器后移函数，相当于p1++

8        iterator_prev_t  pfn_prev;                          // 迭代器前移函数，相当于p2--

9    }iterator_if_t;

其中，p_iter指向的内容是由容器决定的，它既可以指向结点，也可以指向数据。无论是链表还是其它容器实现的pfn_next函数，其意义是一样的，其它函数同理。如果将迭代器理解为指向数据的指针变量，则pfn_nex