周立功教授談迭代器模式設(shè)計(jì)

近日周立功教授公開了數(shù)年的心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》，電子版已無償性分享到電子工程師與高校群體下載，經(jīng)周立功教授授權(quán)，特對本書內(nèi)容進(jìn)行連載。

>>>>1.1 迭代器模式

>>>1.1.1 迭代器與容器

在初始化數(shù)組中的元素時，通常使用下面這樣的for循環(huán)語句遍歷數(shù)組：

int i, a[10];

for(i = 0; i < 10; i++)?

a[i] = i;

這段代碼中的循環(huán)變量i，該變量的初始值為0，然后遞增為1、2、3、...，程序在每次i遞增后都將值賦給a[i]。數(shù)組中保存了許多元素，通過指定數(shù)組下標(biāo)，即可從中選擇任意一個元素。for語句中的i++的作用是讓i的值在每次循環(huán)后自增1，這樣就可以訪問數(shù)組中的下一個元素，從而實(shí)現(xiàn)了從頭到尾逐一遍歷數(shù)組元素的功能。

由此可見，常用的循環(huán)結(jié)構(gòu)就是一種迭代操作，在每一次迭代操作中，對迭代器的修改即等價于修改循環(huán)控制的標(biāo)志或計(jì)數(shù)器。而容器是一種保存值的集合的數(shù)據(jù)結(jié)構(gòu)，C有兩種內(nèi)建的容器：數(shù)組和結(jié)構(gòu)體。雖然C沒有提供更多的容器，但用戶可以按需編寫自己的容器，比如，鏈表、哈希表等。

將i的作用抽象化、通用化后形成的模式，在設(shè)計(jì)模式中i稱為迭代器（Iterator）模式，Iterate的字面意思是重復(fù)、反復(fù)聲明，其實(shí)就是重復(fù)做某件事，Iterator模式用于遍歷數(shù)組中的元素。迭代器的基本思想是迭代器變量存儲了容器的某個元素的位置，因此能夠遍歷該位置的元素。通過迭代器提供的方法，可以繼續(xù)遍歷容器的下一個元素。

顯而易見，迭代器是一種抽象的設(shè)計(jì)概念，因?yàn)樵诔绦蛟O(shè)計(jì)語言中并沒有直接對應(yīng)于這個概念的實(shí)物?！对O(shè)計(jì)模式》一書提供了23種設(shè)計(jì)模式的完整描述，其中iterator模式的定義為：在遍歷一個容器對象時，提供一種方法順序訪問一個容器對象中的各個元素，而又不暴露該對象的內(nèi)部表示方式。其中心思想是將數(shù)據(jù)容器和算法分開且彼此獨(dú)立，最后再用黏合劑將它們撮合在一起。

>>>1.1.2 迭代器接口

為什么一定要考慮引入Iterator這種復(fù)雜的設(shè)計(jì)模式呢？如果是數(shù)組，直接使用for循環(huán)語句進(jìn)行遍歷處理不就可以了嗎？為什么要在集合之外引入Iterator這個角色呢？一個重要的理由是，引入Iterator后可以將遍歷與實(shí)現(xiàn)分離。

實(shí)際上無論是單向鏈表還是雙向鏈表，其查找算法與遍歷算法的實(shí)現(xiàn)沒有多少差別，基本上都是重復(fù)勞動。如果代碼中有bug，則需要修改所有相關(guān)的代碼。為什么會出現(xiàn)這樣的情況呢？主要是接口設(shè)計(jì)不合理所造成的，其最大的問題就是將容器和算法放在了一起，且算法的實(shí)現(xiàn)又依賴于容器的實(shí)現(xiàn)，因而必須為每一個容器開發(fā)一套與之匹配的算法。

假設(shè)要在2種容器（雙向鏈表、動態(tài)數(shù)組）中分別實(shí)現(xiàn)6種算法（交換、排序、求最大值、求最小值、遍歷、查找），顯然需要2×6=12個接口函數(shù)才能實(shí)現(xiàn)目標(biāo)。隨著算法數(shù)量的不斷增多，勢必導(dǎo)致函數(shù)的數(shù)量成倍增加，重復(fù)勞動的工作量也越大。如果將容器和算法單獨(dú)設(shè)計(jì)，則只需要實(shí)現(xiàn)6個算法函數(shù)就行了。即算法不依賴容器的特定實(shí)現(xiàn)，算法不會直接在容器中進(jìn)行操作。比如，排序算法無需關(guān)心元素是存放在數(shù)組或線性表中。

在正式引入迭代器之前，不妨分析一下如程序清單3.49所示的冒泡排序算法。

程序清單3.49冒泡排序算法

1 #include

2 #include "swap.h"

3

4 void bubbleSort(int *begin, int *end)

5 {

6 int flag = 1; // flag = 1，表示指針的內(nèi)容未交換

7 int *p1 = begin; // p1指向數(shù)組的首元素

8 int *p2 = end; // p2指向數(shù)組的尾元素

9 int *pNext; // pNext指向p1所指向的元素的下一個元素

10

11 while(p2 != begin){

12 p1 = begin;

13 flag = 1;

14 while(p1 != p2){

15 pNext = p1+1;

16 if(*p1>*pNext) //比較指針?biāo)赶虻闹档拇笮?/span>

17 {

18 swap(p1, pNext); //交換2個指針的內(nèi)容

19 flag = 0; // flag = 0，表示2個指針的內(nèi)容交換

20 }

21 p1++; // p1指針后移

22 }

23 if(flag) return; // 沒有交換，表示已經(jīng)有序，則直接返回

24 p2--; // p2指針前移

25 }

26 }

27

28 int main(int argc, char *argv[])

29 {

30 int a[]={5, 3, 2, 4, 1};

31 int i = 0;

34 for(i = 0; i < sizeof(a) / sizeof(a[0]); i++){

35 printf("%d ", a[i]);

36 }

37 return 0;

如果任何一次遍歷沒有執(zhí)行任何交換，則說明記錄是有序的且終止排序。其中，p1指向數(shù)組的首元素，pNext指向p1所指向的元素的下一個元素，p2指向數(shù)組的尾元素（圖 3.21（a））。如果*p1>*pNext，則交換指針?biāo)赶虻膬?nèi)容，p1與pNext后移（圖 3.21（b）），反之指針?biāo)赶虻膬?nèi)容不變，p1與pNext后移，經(jīng)過一輪排序之后，直到p1 = p2為止，最大元素移到數(shù)組尾部。

圖 3.21 內(nèi)部循環(huán)執(zhí)行過程示意圖

當(dāng)最大元素移到數(shù)組的尾部時，則退出內(nèi)部循環(huán)。p2前移后程序跳轉(zhuǎn)到程序清單3.49（15），p1再次指向數(shù)組的首元素，pNext指向p1所指向的元素的下一個元素（圖 3.22（a））。此時，圖 3.22（a）與圖 3.21（a）的差別在于p2指向a[3]。經(jīng)過一輪循環(huán)之后，直到p1 = p2，此時整數(shù)4移到a[3]所在的位置，剩余的排序詳見圖 3.22。當(dāng)p1與p2重合在數(shù)組首元素所在的位置時，表示排序結(jié)束（圖 3.22（d））。

圖 3.22 外部循環(huán)執(zhí)行過程示意圖

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

●比較指針?biāo)赶虻闹档拇笮。?/span>

●交換指針?biāo)赶虻膬?nèi)容；

●指針后移，即指針指向下一個元素；

●指針前移，即指針指向前面一個元素。

由于這里是以int類型數(shù)據(jù)為例實(shí)現(xiàn)冒泡排序的，因此用戶知道如何比較數(shù)據(jù)和如何交換指針?biāo)赶虻膬?nèi)容，以及指針的前后移動。當(dāng)使用支持任意類型數(shù)據(jù)的void *時，雖然算法程序不知道傳入什么類型的數(shù)據(jù)，但調(diào)用者知道，因此在調(diào)用排序算法函數(shù)時，可以由用戶傳遞參數(shù)通過回調(diào)函數(shù)實(shí)現(xiàn)。修改后的冒泡排序函數(shù)原型如下：

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

其中，compare用于比較兩個指針?biāo)赶虻闹档拇笮?/span>，compare_t類型定義如下：

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

swap函數(shù)用于交換兩個指針指向的內(nèi)容，swap_t類型定義如下：

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

顯然無法通過++或--移動指針，因?yàn)椴恢纻魅氲氖鞘裁搭愋偷臄?shù)據(jù)。如果知道數(shù)據(jù)占用4個字節(jié)，則可以通過指針的值加4或減4實(shí)現(xiàn)指針的移動。雖然使用這種方式可以實(shí)現(xiàn)指針的移動，但始終要求數(shù)據(jù)必須以數(shù)組的形式存儲，一旦離開了這個特定的容器，則無法確定指針的行為。如果將算法與鏈表結(jié)合起來使用，顯然代碼中的p1++和p2--不適合鏈表。

基于此，“不妨對指針進(jìn)行抽象，讓它針對不同的容器有不同的實(shí)現(xiàn)，而算法只關(guān)心它的指針接口”。顯然，需要容器提供相應(yīng)的接口函數(shù)，才能實(shí)現(xiàn)指針前移和后移，通常將這樣的指針稱為“迭代器”。從某種意義上來說，迭代器作為算法的接口是廣義指針，而指針滿足所有迭代器的要求。其優(yōu)勢在于對任何種類的容器都可以用同樣的方法順序遍歷容器中的元素，而又不暴露容器的內(nèi)部細(xì)節(jié)，迭代器接口的聲明詳見程序清單3.50。

程序清單3.50 迭代器接口的聲明

1 typedef void *iterator_t; //定義迭代器類型

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

4

5 //迭代器接口（if表示interface，由具體容器實(shí)現(xiàn)，比如，鏈表、數(shù)組等）

6 typedef struct _iterator_if{

7 iterator_next_t pfn_next; //迭代器后移函數(shù)，相當(dāng)于p1++

8 iterator_prev_t pfn_prev; //迭代器前移函數(shù)，相當(dāng)于p2--

其中，p_iter指向的內(nèi)容是由容器決定的，它既可以指向結(jié)點(diǎn)，也可以指向數(shù)據(jù)。無論是鏈表還是其它容器實(shí)現(xiàn)的pfn_next函數(shù)，其意義是一樣的，其它函數(shù)同理。如果將迭代器理解為指向數(shù)據(jù)的指針變量，則pfn_next函數(shù)讓迭代器指向容器的下一個數(shù)據(jù)，pfn_prev函數(shù)讓迭代器指向容器的上一個數(shù)據(jù)。

此時，應(yīng)該針對接口編寫一些獲取或設(shè)置數(shù)值的方法。用于讀取變量的方法通常稱為“獲取方法（getter）”，用于寫入變量的方法通常稱為“設(shè)置方法（setter）”。下面以雙向鏈表為例，使用結(jié)構(gòu)體指針作為dlist_iterator_if_get()的返回值，詳見程序清單3.51。

程序清單3.51獲取雙向鏈表的迭代器接口（1）

1 static void __dlist_iterator_next(iterator_t *p_iter) //讓迭代器指向容器的下一個數(shù)據(jù)

2 {

4 }

5

6 static void __dlist_iterator_prev(iterator_t *p_iter) //讓迭代器指向容器的上一個數(shù)據(jù)

7 {

8 *p_iter = ((dlist_node_t *)*p_iter) -> p_prev;

9 }

11 iterator_if_t *dlist_iterator_if_get (void)

12 {

13 static iterator_if_t iterator_if;

14 iterator_if.pfn_next = __dlist_iterator_next;

15 iterator_if.pfn_prev = __dlist_iterator_prev;

16 return &iterator_if; //返回結(jié)構(gòu)體變量地址&iterator_if

其調(diào)用形式如下：

iterator_if_t *p_if = dlist_iterator_if_get(); // 獲得鏈表的迭代器接口，即p_if = &iterator_if

注意，如果省略static，則iterator_if就成了一個局部變量。由于它將在函數(shù)執(zhí)行完后失效，因此返回它的地址毫無意義。這里采用了直接訪問結(jié)構(gòu)體成員的方式對iterator_if_t類型的結(jié)構(gòu)體賦值，顯然不同模塊之間應(yīng)該盡可能避免這種方式，取而代之的是提供相應(yīng)的接口，詳見程序清單 3.52。

程序清單3.52獲取雙向鏈表的迭代器接口（2）

1 void dlist_iterator_if_get(iterator_if_t *p_if)

2 {

3 p_if -> pfn_next = __dlist_iterator_next;

4 p_if -> pfn_prev = __dlist_iterator_prev;

其調(diào)用形式如下：

iterator_if_t iterator_if;

由于iterator_if_t類型的結(jié)構(gòu)體中只有兩個函數(shù)指針，因此對函數(shù)指針的訪問僅包含設(shè)置和調(diào)用，詳見程序清單 3.53。

程序清單3.53迭代器接口（iterator.h）

1 #pragma once;

2

3 typedef void *iterator_t;

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

6

7 typedef struct _iterator_if{

8 iterator_next_t pfn_next; //調(diào)用迭代器后移的函數(shù)指針，相當(dāng)于p1++

9 iterator_prev_t pfn_prev; //調(diào)用迭代器前移的函數(shù)指針，相當(dāng)于p2--

10 }iterator_if_t;

12 void iterator_if_init(iterator_if_t *p_if, iterator_next_t pfn_next, iterator_prev_t pfn_prev);

13 void iterator_next(iterator_if_t *p_if, iterator_t *p_iter); //迭代器后移函數(shù)，相當(dāng)于++

這些函數(shù)的具體實(shí)現(xiàn)詳見程序清單3.54。

程序清單3.54迭代器接口的實(shí)現(xiàn)

1 #include "iterator.h"

2

3 void iterator_if_init(iterator_if_t *p_if, iterator_next_t pfn_next, iterator_prev_t pfn_prev)

5 p_if -> pfn_next = pfn_next;

6 p_if -> pfn_prev = pfn_prev;

7 }

8

9 void iterator_next(iterator_if_t *p_if, iterator_t *p_iter)

10 {

11 p_if -> pfn_next(p_iter);

12 }

14 void iterator_prev(iterator_if_t *p_if, iterator_t *p_iter)

15 {

16 p_if -> pfn_prev(p_iter);

現(xiàn)在可以直接調(diào)用iterator_if_init()實(shí)現(xiàn)dlist_iterator_if_get()，詳見程序清單 3.55。

程序清單3.55獲取雙向鏈表的迭代器接口（3）

1 void dlist_iterator_if_get(iterator_if_t *p_if)

2 {

3 iterator_if_init(p_if, __dlist_iterator_next, __dlist_iterator_prev);