C语言中的迭代器的实现方式。

迭代器可以通过一个对象，以一定的序列返回容器对象的内容。在Python中实现迭代器协议要求类实现__iter__方法，且返回一个特殊的迭代器对象，这个迭代器对象实现了__next__方法，并且能通过抛出StopIteration异常来标识迭代器的完成。在C语言中，并没有类似Python中的迭代协议，我们需要自己实现。有被迭代的容器各种各样，迭代器并不是万能的，一般是一种容器对象对于一种迭代器实现。

本文想简述Python中迭代协议的使用，然后在讲述C语言中迭代器的实现。

体会下Python中的实现

以斐波那契数列为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Fib:

    def __init__(self):
        self.a = 0
        self.b = 1

    def __iter__(self):
        return self

    def __next__(self):
        value = self.b
        self.a, self.b = self.b, self.a + self.b
        return value

__iter__特殊方法返回迭代器对象，就是Fib类的实例对象，这个对象实现了__next__，每次迭代的逻辑就在其中实现：斐波那契数列的定义。

实现了迭代协议后，通过创建实例就可以使用：

1
2
3
4
def test():
    fib = Fib()
    for i in fib:
        print(i)

这个迭代器会一直计算下去，除非外界主动终止。如果只想输出部分序列，可以使用迭代器切片。

1
2
3
4
5
6
import itertools

def slice():
    fib = Fib()
    for i in itertools.islice(fib, 1, 20):
        print(i)

对比下，通过函数的实现更简单：

1
2
3
4
5
6
7
def fib(n):
    if n < 0:
        raise ValueError("n must be positive or zero")
    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a+b
    return b

当然也可以改为生成器方法，每次yield一个斐波那契数。

在C语言下，我们也能实现以上优雅的迭代。

C语言下的迭代器

方便起见，我们假定迭代器的对象是双链表链表。可以支持头或尾两个方向开始迭代。在实现思路上我们模仿Python的实现。创建、获取迭代对象(__iter__)，通过next方法获取下一个输出，通过循环获取所有输出(for i in iter)。

结点和链表的定义：

1
2
3
4
5
6
7
8
9
10
11
typedef struct Node {
    struct Node *prev;
    struct Node *next;
    void *value;
} Node；

typedef struct list {
    Node *head;
    Node *tail;
    unsigned long len;
}

迭代对象

1
2
3
4
typedef struct listIter {
    Node *next;
    int direction;
}

创建迭代对象

1
2
3
4
5
6
7
8
9
10
listIter *listGetIterator(list *list, int direction) {
    listIter *iter;
    if ((iter = malloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == 0)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

实现类似Python中的__next__，获取迭代器的一个输出

1
2
3
4
5
6
7
8
9
10
Node *listNext(listIter *iter) {
    Node *current = iter->next;
    if (current != NULL) {
        if (iter->direction == 0)
            iter->next = current->next;
        else
            iter->next = current-prev;
    }
    return current;
}

通过循环“开启”迭代器：

1
2
3
4
5
6
void main(void) {
    listIter *iter = listGetIterator(list, 0);
    while ((node = listNext(iter)) != NULL) {
        do(node);
    }
}

使用类似于Python迭代协议的思路：解决C语言中迭代容器的问题。类似地，其他的数据结构也可以利用上述的思路，不同的是数据结构迭代算法的实现思路不一样。当然，不存在通用的适合任何数据结构的迭代器，因为每个迭代器都需要知道给定数据结构（如序列、树、图）的构造进而定制遍历方式。

转载请包括本文地址：https://allenwind.github.io/blog/4388
更多文章请参考：https://allenwind.github.io/blog/archives/