系统程序员成长计划-容器与算法(二)

容器用来存储数据，算法用来处理数据。容器有多种，算法的种类更多，两者的组合数目就数不胜数了。如果同样的算法要为每种容器都写一遍，写的时候单调不说，维护起来也很困难。所以我们一直在寻找让算法独立于容器的方法，让同一种算法能适用于所有(或多种)的容器。

在开始的时候，我们通过foreach遍历函数＋回调函数的方法，第一次分离了算法和容器，算法不但可以独立于容器变化，而且同时适用于多种容器：大/小写转换函数只需要写一次，就可以在双向链表、动态数组、队列、栈和哈希表等多种容器中重用。

前面又我们抽象了容器的接口，容器的使用者不需要关心容器的实现，也就是说同一个算法可以适用于多种不同的容器(不是全部，前面只抽象了线形的容器)。我们用这种方面实现了队列和栈，还重用了双向链表和动态数组的测试程序。

可惜上面两种方法仍然不能解决让算法独立于容器的全部问题。这里请读者先实现这样一个算法：

o 反序排列容器中的元素：第一个元素与最后一元素交换，第二个元素与倒数第二个元素交换，以此类推。

o 这个算法同时适用双向链表和动态数组。

o在双向链表和动态数组上的运行效率处于同一级别。

这个反序函数的原理很简单，有的读者很快就写出来了：

Ret invert(LinearContainer* linear_container)
{
    int i = 0;
    int j = 0;
    void* data1 = NULL;
    void* data2 = NULL; 

    return_val_if_fail(linear_container != NULL, RET_INVALID_PARAMS); 

    j = linear_container_length(linear_container) - 1;
    for(; i < j; i++, j--)
    {
        linear_container_get_by_index(linear_container, i, &data1);
        linear_container_get_by_index(linear_container, j, &data2);
        linear_container_set_by_index(linear_container, i, data2);
        linear_container_set_by_index(linear_container, j, data1);
    } 

    return RET_OK;
}

这种实现利用我们抽象的 LinearContainer接口，它同时适用于双向链表和动态数组，可惜无法满足第三个条件，双向链表和动态数组的性能差异很大。原因是，动态数组通 过偏移量可以定位，而双向链表则需要一个一个的移动指针才能定位，在循环内部调用get_by_index/ set_by_index更加剧它们在性能上的差异。

有的读者可能尝试了用foreach去实现，foreach确实很好用，但它的缺点是只能按固定的顺序去遍历元素，不能同时即反序又顺序的遍历，所 以用foreach实现上述算法是有点困难的。这里我们引入一个新的概念：迭代器。迭代器是一种更灵活的遍历行为的抽象，它可以按任意顺序去访问容器内的 元素，而又不暴露容器的内部结构。

在引入迭代器之前，我们分析一下invert的算法，先考虑针对双向链表的实现：

1. 定义两个指针，一个指向链表的首结点，一个指向链表的尾结点。
2. 交换两个指针指向的内容。
3. 前面的指针向后移，后面的指针向前移，重复第二步直到两个指针相遇。

仔细看看上面的算法，我们发现在整个过程中，操作的只是两个指针。关于这个指针，它具有下列行为：

o 获取指针指向的数据。
o 设置指针指向的数据。
o 指针向后移。
o 指针向前移。
o 比较的大小。

在前面的算法中，指针是依赖于双向链表的，离开了这个特定的容器，我们无法确定指针的行为。那么我们可以对这里指针进行抽象，让它针对不同容器有不同的实现，而算法只关心它的指针这个接口。为了遵循一些约定俗成的规则，我们把这里的指针称为迭代器(iterator)。

迭代器(iterator)的接口定义如下：

typedef Ret  (*IteratorSetFunc)(Iterator* thiz, void* data);
typedef Ret  (*IteratorGetFunc)(Iterator* thiz, void** data);
typedef Ret  (*IteratorNextFunc)(Iterator* thiz);
typedef Ret  (*IteratorPrevFunc)(Iterator* thiz);
typedef Ret  (*IteratorAdvanceFunc)(Iterator* thiz, int offset);
typedef int  (*IteratorOffsetFunc)(Iterator* thiz);
typedef Ret  (*IteratorCloneFunc)(Iterator* thiz, Iterator** cloned);
typedef void (*IteratorDestroyFunc)(Iterator* thiz); 

struct _Iterator
{
    IteratorSetFunc     set;
    IteratorGetFunc     get;
    IteratorNextFunc    next;
    IteratorPrevFunc    prev;
    IteratorAdvanceFunc advance;
    IteratorCloneFunc   clone;
    IteratorOffsetFunc  offset;
    IteratorDestroyFunc destroy; 

    char priv[0];
};

为了让迭代器具有更广的适应能力，在其它算法也可以使用，这里增加了几个接口函数：

o advance 随机定位迭代器位置，由当前位置和偏移量决定。
o offset 得到迭代器的偏移量，主要用作比较迭代器的大小。
o clone拷贝一份迭代器。

现在我们来看针对双向链表的实现：

o 数据结构

typedef struct _PrivInfo
{
    DList* dlist;
    DListNode* cursor;
    int offset;
}PrivInfo;

一个指向双向链表的指针，它表明迭代器所属的容器。
一个指向当前结点的指针，它表明迭代器的位置。
一个标明当前偏移量的值，目的是提高获取偏移量的速度。

o 实现迭代器的函数

static Ret  dlist_iterator_set(Iterator* thiz, void* data)
{
    PrivInfo* priv = (PrivInfo*)thiz->priv;
    return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL, RET_INVALID_PARAMS); 

    priv->cursor->data = data; 

    return RET_OK;
} 

static Ret  dlist_iterator_next(Iterator* thiz)
{
    Ret ret = RET_FAIL;
    PrivInfo* priv = (PrivInfo*)thiz->priv;
    return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL, RET_INVALID_PARAMS); 

    if(priv->cursor->next != NULL)
    {
        priv->cursor = priv->cursor->next;
        priv->offset++; 

        ret = RET_OK;
    } 

    return ret;
} 

...

从这些代码可以看出，双向链表的迭代器其实就是对双向链表结点的包装，经过这个包装之后，可以访问具体的结点而又不暴露双向链表的内部实现，并且调用者不再依赖双向链表了。

o 创建函数

Iterator* dlist_iterator_create(DList* dlist)
{
    Iterator* thiz = NULL;
    return_val_if_fail(dlist != NULL, NULL); 

    if((thiz = malloc(sizeof(Iterator) + sizeof(PrivInfo))) != NULL)
    {
        PrivInfo* priv = (PrivInfo*)thiz->priv; 

        thiz->set      =  dlist_iterator_set;
        thiz->get      =  dlist_iterator_get;
        thiz->next     =  dlist_iterator_next;
        thiz->prev     =  dlist_iterator_prev;
        thiz->advance  =  dlist_iterator_advance;
        thiz->clone    =  dlist_iterator_clone;
        thiz->offset   =  dlist_iterator_offset;
        thiz->destroy  =  dlist_iterator_destroy; 

        priv->dlist  = dlist;
        priv->cursor = dlist->first;
        priv->offset = 0;
    } 

    return thiz;
}

这里我们还遇到另外一个难题：双向链表的迭代器的实现放在哪里？放在dlist.c里还是单独的文件里，放在单独的文件里可读性更强，但是在访问双向链表的内部数据时会遇到一些麻烦。最后选择是：

o dlist_iterator.h提供独立的文件。
o dlist_iterator.c也提供独立的文件，但是它不直接参与编译，而是在dlist.c里include它。

这样就两全其美了：维护方便又可以访问双向链表的内部数据结构。

最后我们来看看用迭代器实现的invert函数：

Ret invert(Iterator* forward, Iterator* backward)
{
    void* data1 = NULL;
    void* data2 = NULL;
    return_val_if_fail(forward != NULL && backward != NULL, RET_INVALID_PARAMS); 

    for(; iterator_offset(forward) < iterator_offset(backward); iterator_next(forward), iterator_prev(backward))
    {
        iterator_get(forward, &data1);
        iterator_get(backward, &data2);
        iterator_set(forward, data2);
        iterator_set(backward, data1);
    } 

    return RET_OK;
}

invert算法同时适用于双向链表和动态数组，而且它们的运行效率相差不大，至少对于双向链表来说已经是比较高效的实现了。

迭代器模式是一种重要的模式，在C＋＋的标准模板库(STL)中有大量的应用。老的C程序员通常是运行效率至上的，所以要在优雅的设计和性能之间做 出选择时，他们通常选择后者，所以很少看到C语言实现的容器提供迭代器，那也不足为奇。重要的是我们学习这种方法，并在适当的时候运用它。

本节示例代码请到这里下载。