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

前面我们通过组合的方法，用双向链表实现了队列。大家已经看到，它的实现非常简单。有的读者可能会问了：你说过双向链表和动态数组都有各自的适用范 围，在有的情况下，用双向链表合适，在有的情况下，用动态数组合适。你用双向链表实现了队列，是不是有必要用动态数组再实现一次呢？如果对栈同样如此，那 是不是做了太多重复的工作，有违背DRY(don’t repeat yourself)原则呢？

问得好，这就是本章要学习的。我们请读者实现一个队列，要求如下：

o由调用者决定用双向链表实现还是用动态数组实现，
o 在运行时决定，而不是在编译时决定（宏定义）。
o 如果调用者乐意，他以后还可以选择用单向链表来实现，而不必修改队列的实现代码。
o Don’t Repeat Yourself。

请读者不要急着看后面的内容，先仔细想想，尝试完成这个任务。

容器

在运行时动态选择实现方式，这个问题可是有点难度的。我很少见人能独立完成，最常见的做法是：用一个参数来决定调用双向链表的函数还是动态数组的函数。如：

Ret      queue_head(Queue* thiz, void** data)
{
    return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS);

    if(thiz->use_dlist)
    {
        return dlist_get_by_index(thiz->dlist, 0, data);
    }
    else
    {
        return darray_get_by_index(thiz->darray, 0, data);
    }
}

这种方法满足了前面两个要求，但无法满足第三个要求，它限定了只能使用双向链表和动态数组两种方法来实现队列，要添加其它实现方法(如单向链表)就 要修改队列的本身了。当然你可以选择把目前所知的实现方式全部写在里面，但那样会带来复杂度上升，性能下降，空间浪费和错误增加等种种不利因素。更何况在 现实中，我们是无法预知所有可能出现的实现方式的。

在经过前面反复的练习之后，提到一个对象有多种不同的实现方式时，大部分读者都会想到用接口了，这是很好的。于是有人提出，抽象出一个队列的接口，分别用双向链表和动态数组来实现，这样就可以把调用者和队列的不同实现分开了。

这个想法不错，至少通过队列接口可以解决前面三个问题了。但问题是，用双向链表实现的队列和与用动态数组实现的队列，从逻辑上来看，它们完全是重复 的，从代码的角度来看，它们又有些差别。如果你亲手去写过，总感觉到里面有点不太对劲，这种感觉通常是需要改进的征兆。在仔细思考之后，我们会发现队列的 逻辑是不变的，变化的只是容器。也就是说应该抽象的是容器接口而不是队列接口。

最小粒度抽象原则。这个原则是我命名的，虽然不是出自大师之手，但它同样是有效的。接口隔离了调用者和具体实现，不管抽象的粒度大小，接口都能起到 隔离变化的作用。但是粒度越大造成的重复越多，上面的例子或许不太明显，假设我们要开发一个OS内核，这个OS可以在不同的硬件平台上运行，硬件平台是变 化的，我们只要对硬件平台进行抽象就好了，如果对OS整体进行抽象，则意味着每个硬件平台写一个OS，那样就存在太多重复工作了。

前面我们在引入Locker这个接口时，是先有这个接口然后再去实现它。这里不过是已经有实现好的双向链表和动态数组，我们再引入容器这个接口而已。它们的目的是一样的：隔离变化。回到正题，下面看看容器的接口：

struct _LinearContainer;
typedef struct _LinearContainer LinearContainer;

typedef Ret (*LinearContainerInsert)(LinearContainer* thiz, size_t index, void* data);
typedef Ret (*LinearContainerPrepend)(LinearContainer* thiz, void* data);
typedef Ret (*LinearContainerAppend)(LinearContainer* thiz, void* data);
typedef Ret (*LinearContainerDelete)(LinearContainer* thiz, size_t index);
typedef Ret (*LinearContainerGetByIndex)(LinearContainer* thiz, size_t index, void** data);
typedef Ret (*LinearContainerSetByIndex)(LinearContainer* thiz, size_t index, void* data);
typedef size_t (*LinearContainerLength)(LinearContainer* thiz);
typedef int    (*LinearContainerFind)(LinearContainer* thiz, DataCompareFunc cmp, void* ctx);
typedef Ret    (*LinearContainerForeach)(LinearContainer* thiz, DataVisitFunc visit, void* ctx);
typedef void   (*LinearContainerDestroy)(LinearContainer* thiz);

struct _LinearContainer
{
    LinearContainerInsert     insert;
    LinearContainerPrepend    prepend;
    LinearContainerAppend     append;
    LinearContainerDelete     del;
    LinearContainerGetByIndex get_by_index;
    LinearContainerSetByIndex set_by_index;
    LinearContainerLength     length;
    LinearContainerFind       find;
    LinearContainerForeach    foreach;
LinearContainerDestroy    destroy;

    char priv[0];
};

从上面的代码可以看出，容器接口、双向链表和动态数组的基本上是一致的。

下面我们看看基于双向链表的实现：

o 数据结构

typedef struct _PrivInfo
{
    DList* dlist;
}PrivInfo;

这是容器的私有数据，它只是对双向链表的包装，请不要与前面的“组合”搞混了：组合是为了实现新的功能，而这里是为了分隔接口和实现，让实现部分可以独立变化。

o 实现接口函数

static Ret linear_container_dlist_insert(LinearContainer* thiz, size_t index, void* data)
{
    PrivInfo* priv = (PrivInfo*)thiz->priv;

    return dlist_insert(priv->dlist, index, data);
}

static Ret linear_container_dlist_delete(LinearContainer* thiz, size_t index)
{
    PrivInfo* priv = (PrivInfo*)thiz->priv; 

    return dlist_delete(priv->dlist, index);
} 

...

同样这里只是对参数做简单转发，调用都是一一对应的，其它函数的实现类似，这里就不一个一个的分析了。

o 创建函数

LinearContainer* linear_container_dlist_create(DataDestroyFunc data_destroy, void* ctx)
{
    LinearContainer* thiz = (LinearContainer*)malloc(sizeof(LinearContainer) + sizeof(PrivInfo)); 

    if(thiz != NULL)
    {
        PrivInfo* priv = (PrivInfo*)thiz->priv;
        priv->dlist = dlist_create(data_destroy, ctx); 

        thiz->insert        =  linear_container_dlist_insert;
        thiz->prepend       =  linear_container_dlist_prepend;
        thiz->append        =  linear_container_dlist_append;
        thiz->del           =  linear_container_dlist_delete;
        thiz->get_by_index  =  linear_container_dlist_get_by_index;
        thiz->set_by_index  =  linear_container_dlist_set_by_index;
        thiz->length        =  linear_container_dlist_length;
        thiz->find          =  linear_container_dlist_find;
        thiz->foreach       =  linear_container_dlist_foreach;
        thiz->destroy       =  linear_container_dlist_destroy; 

        if(priv->dlist == NULL)
        {
            free(thiz);
            thiz = NULL;
        }
    }
}

创建函数的主要工作是把函数指针指向实际的函数。

有的读者可能会问，你用双向链表和动态数组实现了两个容器，我用双向链表和动态数组实现了两个队列，这没有什么差别啊，至少你的代码量并不会减少。能想到这点是不错的，所谓不怕不识货就怕货比货，这两种方法到底有什么差别呢？

前面我们说过，快速排序在元素很少的情况下，它的性能甚至不如冒泡排序高，但是随着元素个数的增加，它的优势就越来越明显了。好的设计也是一样的， 在小程序中，它的表现并不比普通设计强多少，但是随着规模的扩大，重用次数的增多，它的优势就会明显起来。单从实现队列来看，容器接口没有什么优势。眼光 再看远一点，我们会发现：用同样的方法实现栈不需要重写这些代码了;双向链表和动态数组可以共用一个测试程序; 如果其它地方还有类似的需求，重用次数会越来越多，它的优势就更明显了。

下面我们来看看用容器来实现队列：

o 数据结构

struct _Queue
{
    LinearContainer* linear_container;
};

o 队列的创建函数

Queue* queue_create(LinearContainer* container)
{
    Queue* thiz = NULL;

    return_val_if_fail(container != NULL, NULL);

    thiz = (Queue*)malloc(sizeof(Queue));

    if(thiz != NULL)
    {
        thiz->linear_container = container;
    }

    return thiz;
}

容器对象由调用者传入，而不是在队列里硬编码，这样它的变化不会影响队列。

o 队列的实现函数

Ret      queue_head(Queue* thiz, void** data)
{
    return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS);

    return linear_container_get_by_index(thiz->linear_container, 0, data);
}

Ret      queue_push(Queue* thiz, void* data)
{
    return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 

    return linear_container_append(thiz->linear_container, data);
}
...

用容器实现的队列和前面用双向链表实现的队列没有多大差别，只是函数名称不一样而已。

由此可见，队列与双向链表和动态数组没有任何关系，队列关心的只是linear_container这个接口，如果调用者想换成单向链表，用单向链 表去实现linear_container接口就好了。在C＋＋的标准模板库(STL)里有类似的做法，STL里的Sequence相当于这里的 LinearContainer接口。

C语言程序中广泛使用上述的做法，但我并不推荐读者这样去实现队列(当然也不反对)。原因是在通常情况下，队列中存放的元素并不多，使用双向链表、动态数组和其它容器都没有多大差别，用最简单的方法实现它就行了。

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