大话设计模式C语言之迭代器模式

迭代器模式

迭代器模式 (IteratorPattern) 是一种行为设计模式，让你能在不暴露集合底层表现形式（列表、栈和树等）的情况下遍历集合中所有的元素。

案例代码

迭代器

迭代器对外接口 iterator.h

迭代器（Iterator）接口声明了遍历集合所需的操作：获取下一个元素、获取当前位置和重新开始迭代等。

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef ITERATOR_H
#define ITERATOR_H

typedef struct Iterator Iterator;

int  iterator_first(Iterator *it);
int  iterator_next(Iterator *it);
int  iterator_is_done(Iterator *it);
int  iterator_current(Iterator *it);
void iterator_destroy(Iterator *it);

#endif

迭代器内部抽象接口 iterator_internal.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef ITERATOR_INTERNAL_H
#define ITERATOR_INTERNAL_H

#include "iterator.h"

Iterator *iterator_create(
    void *impl,
    int (*first)(void *),
    int (*next)(void *),
    int (*is_done)(void *),
    int (*current)(void *),
    void (*destroy)(void *)
);

#endif

迭代器实现 iterator.c

具体迭代器（Concrete Iterators）实现遍历集合的一种特定算法。迭代器对象必须跟踪自身遍历的进度。这使得多个迭代器可以相互独立地遍历同一集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdlib.h>
#include "iterator_internal.h"

struct Iterator {
    void *impl;
    int (*first)(void *);
    int (*next)(void *);
    int (*is_done)(void *);
    int (*current)(void *);
    void (*destroy)(void *);
};

int iterator_first(Iterator *it) {
    return it->first(it->impl);
}

int iterator_next(Iterator *it) {
    return it->next(it->impl);
}

int iterator_is_done(Iterator *it) {
    return it->is_done(it->impl);
}

int iterator_current(Iterator *it) {
    return it->current(it->impl);
}

void iterator_destroy(Iterator *it) {
    if (!it) return;
    it->destroy(it->impl);
    free(it);
}

Iterator *iterator_create(
    void *impl,
    int (*first)(void *),
    int (*next)(void *),
    int (*is_done)(void *),
    int (*current)(void *),
    void (*destroy)(void *)
) {
    Iterator *it = malloc(sizeof(*it));
    if (!it) return NULL;

    it->impl = impl;
    it->first = first;
    it->next = next;
    it->is_done = is_done;
    it->current = current;
    it->destroy = destroy;

    return it;
}

集合

集合抽象接口 aggregate.h

集合（Collection）接口声明一个或多个方法来获取与集合兼容的迭代器。 请注意返回方法的类型必须被声明为迭代器接口，因此具体集合可以返回各种不同种类的迭代器。

1
2
3
4
5
6
7
8
9
10
11
#ifndef AGGREGATE_H
#define AGGREGATE_H

typedef struct Aggregate Aggregate;
typedef struct Iterator Iterator;

Iterator *aggregate_create_iterator(Aggregate *agg);
void aggregate_destroy(Aggregate *agg);

#endif

动态数组集合 int_array.c

具体集合（Concrete Collections）会在客户端请求迭代器时返回一个特定的具体迭代器类实体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <stdlib.h>
#include <string.h>
#include "aggregate.h"
#include "iterator_internal.h"

/* ================= Aggregate ================= */

typedef struct {
    int *data;
    size_t size;
} IntArray;

struct Aggregate {
    void *impl;
    Iterator *(*create_iterator)(void *);
    void (*destroy)(void *);
};

static void int_array_destroy(void *impl) {
    IntArray *arr = impl;
    free(arr->data);
    free(arr);
}

/* ================= Iterator ================= */

typedef struct {
    IntArray *array;
    size_t index;
} IntArrayIterator;

static int arr_first(void *impl) {
    ((IntArrayIterator *)impl)->index = 0;
    return 0;
}

static int arr_next(void *impl) {
    ((IntArrayIterator *)impl)->index++;
    return 0;
}

static int arr_is_done(void *impl) {
    IntArrayIterator *it = impl;
    return it->index >= it->array->size;
}

static int arr_current(void *impl) {
    IntArrayIterator *it = impl;
    return it->array->data[it->index];
}

static void arr_it_destroy(void *impl) {
    free(impl);
}

static Iterator *int_array_create_iterator(void *impl) {
    IntArrayIterator *real = malloc(sizeof(*real));
    real->array = impl;
    real->index = 0;

    return iterator_create(
        real,
        arr_first,
        arr_next,
        arr_is_done,
        arr_current,
        arr_it_destroy
    );
}

/* ============== Factory API ================= */

Aggregate *int_array_create(const int *data, size_t size) {
    Aggregate *agg = malloc(sizeof(*agg));
    IntArray *arr = malloc(sizeof(*arr));

    arr->data = malloc(sizeof(int) * size);
    memcpy(arr->data, data, sizeof(int) * size);
    arr->size = size;

    agg->impl = arr;
    agg->create_iterator = int_array_create_iterator;
    agg->destroy = int_array_destroy;

    return agg;
}

Iterator *aggregate_create_iterator(Aggregate *agg) {
    return agg->create_iterator(agg->impl);
}

void aggregate_destroy(Aggregate *agg) {
    if (!agg) return;
    agg->destroy(agg->impl);
    free(agg);
}


链表集合 linked_list.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdlib.h>
#include "aggregate.h"
#include "iterator_internal.h"

/* ================= Aggregate ================= */

typedef struct Node {
    int value;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
} LinkedList;

struct Aggregate {
    void *impl;
    Iterator *(*create_iterator)(void *);
    void (*destroy)(void *);
};

static void list_destroy(void *impl) {
    LinkedList *list = impl;
    Node *cur = list->head;
    while (cur) {
        Node *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    free(list);
}

/* ================= Iterator ================= */

typedef struct {
    Node *current;
} ListIterator;

static int list_first(void *impl) {
    (void)impl;
    return 0;
}

static int list_next(void *impl) {
    ListIterator *it = impl;
    if (it->current)
        it->current = it->current->next;
    return 0;
}

static int list_is_done(void *impl) {
    return ((ListIterator *)impl)->current == NULL;
}

static int list_current(void *impl) {
    return ((ListIterator *)impl)->current->value;
}

static void list_it_destroy(void *impl) {
    free(impl);
}

static Iterator *list_create_iterator(void *impl) {
    LinkedList *list = impl;

    ListIterator *real = malloc(sizeof(*real));
    real->current = list->head;

    return iterator_create(
        real,
        list_first,
        list_next,
        list_is_done,
        list_current,
        list_it_destroy
    );
}

/* ============== Factory API ================= */

Aggregate *linked_list_create(const int *data, size_t size) {
    Aggregate *agg = malloc(sizeof(*agg));
    LinkedList *list = malloc(sizeof(*list));
    list->head = NULL;

    for (int i = (int)size - 1; i >= 0; --i) {
        Node *n = malloc(sizeof(*n));
        n->value = data[i];
        n->next = list->head;
        list->head = n;
    }

    agg->impl = list;
    agg->create_iterator = list_create_iterator;
    agg->destroy = list_destroy;

    return agg;
}

测试客户端代码 main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include "aggregate.h"
#include "iterator.h"

Aggregate *int_array_create(const int *, size_t);
Aggregate *linked_list_create(const int *, size_t);

static void test(Aggregate *agg) {
    Iterator *it = aggregate_create_iterator(agg);

    for (iterator_first(it);
         !iterator_is_done(it);
         iterator_next(it)) {

        printf("%d ", iterator_current(it));
    }
    printf("\n");

    iterator_destroy(it);
    aggregate_destroy(agg);
}

int main(void) {
    int data[] = {1, 2, 3, 4, 5};

    test(int_array_create(data, 5));
    test(linked_list_create(data, 5));
    
    while(1);
    return 0;
}

总结

   单一职责原则。通过将体积庞大的遍历算法代码抽取为独立的类，你可对客户端代码和集合进行整理。开闭原则。 你可实现新型的集合和迭代器并将其传递给现有代码， 无需修改现有代码。你可以并行遍历同一集合，因为每个迭代器对象都包含其自身的遍历状态。