C语言中迭代器的设计与使用

59 阅读 0 评论 39 点赞

我是靠谱客的博主结实书本，最近开发中收集的这篇文章主要介绍C语言中迭代器的设计与使用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

　　经常使用C＋＋、JAVA等面向对象语言开发的程序员都会比较喜欢容器的迭代器功能，用起来方便简洁。象一些常用的数据结构，如：哈希表、动态数组、链表等，在这些面向对象语言中都可以非常方便地使用迭代器。当然，在C语言中也有对这些常用数据结构的函数封装，但要对容器中元素的遍历，则一般会通过注册回调函数的方式。如下：

/* 以C语言中非常流行的 glib 库中的哈希表操作为例 */

static void print_record(gpointer key, gpointer val, gpointer ctx)
{
    printf("%s: key(%s), value(%s)/n", (char*) ctx, (char*) key, (char*) val));
}

static void free_record(gpointer key, gpointer val, gpointer ctx)
{
    printf("%s: free(%s) now/n", (char*) ctx, (char*) key);
    free(val);
}

static void htable_test(void)
{
    char *myname = "hash_test";
    char key[32], *value;
    GHashTable *table;
    int   i;

    /* 创建哈希表 */
    table = g_hash_table_new(g_str_hash, g_str_equal);

    /* 依次向哈希表中添加数据 */
    for (i = 0; i < 10; i++) {
        snprintf(key, sizeof(key), "key:%d", i);
        value = malloc(64);
        snprintf(value, 64, "value:%d", i);
        g_hash_table_insert(table, key, value);
    }

    /* 遍历并输出哈希表中的数据 */
    g_hash_table_foreach(table, print_record, myname);

    /* 依次释放哈希表中的数据 */
    g_hash_table_foreach(table, free_record, myname);

    /* 销毁哈希表 */
    g_hash_table_destroy(table);
}

这是C函数库中比较常用的回调函数方式，它主要有两个缺点：多写了一些代码，使用不太直观。下面介绍一下ACL库中的设计与实现是如何克服这两个缺点的。首先先请看一个ACL库中使用哈希表的例子：

void htable_test(void)
{
    ACL_HTABLE *table = acl_htable_create(10, 0); /* 创建哈希表 */
    ACL_ITER iter; /* 通用迭代器对象 */
    char key[32], *value;
    int   i;

    /* 依次向哈希表中添加数据 */
    for (i = 0; i < 20; i++) {
        snprintf(key, sizeof(key), "key: %d", i);
        value = acl_mymalloc(32);
        snprintf(value, 32, "value: %d", i);
        assert(acl_htable_enter(table, key, value));
    }

    printf("/n>>>acl_foreach for htable:/n");
    /* 正向遍历哈希表中数据 */
    acl_foreach(iter, table) {
        printf("hash i=%d, [%s]/n", iter.i, (char*) iter.data);
    }

    /* 释放哈希表中数据 */
    acl_foreach(iter, table) {
        acl_myfree(iter.data);
    }

    /* 销毁哈希表 */
    acl_htable_free(table, NULL);
}

　　由以上例子可以明显看出ACL库中的哈希表遍历更加简单直观，不需要回调函数方式便可以遍历哈希表中的所有元素。ACL库不仅哈希表可以用 "ACL_ITER iter; acl_foreach(iter, hash_table) {}" 的方式进行遍历，其它的通用数据结构容器都可以如此使用，如ACL库中的先进先出队列：ACL_FIFO 使用迭代器的例子：

static void fifo_iter(void)
{
    ACL_FIFO fifo;
    ACL_ITER iter;
    ACL_FIFO_INFO *info;
    int   i;
    char *data;

        /* 初始化堆栈队列 */
    acl_fifo_init(&fifo);

    /* 向队列中添加数据 */
    for (i = 0; i < 10; i++) {
        data = acl_mymalloc(32);
        snprintf(data, 32, "data: %d", i);
        acl_fifo_push(&fifo, data);
    }

    printf("/n>>> acl_foreach for fifo:/n");
    /* 正向遍历队列中数据 */
    acl_foreach(iter, &fifo) {
        printf("i: %d, value: %s/n", iter.i, (char*) iter.data);
    }

    printf("/n>>> acl_foreach_reverse for fifo:/n");
    /* 反向遍历队列中数据 */
    acl_foreach_reverse(iter, &fifo) {
        printf("i: %d, value: %s/n", iter.i, (char*) iter.data);
    }

    /* 弹出并释放队列中数据 */
    while (1) {
        data = acl_fifo_pop(&fifo);
        if (data == NULL)
            break;
        acl_myfree(data);
    }
}

　　可以看出，ACL库中的迭代器都是同样的东东 ACL_ITER, 遍历方式也都一样，这是如何做到的？下面请先看一下ACL库中 ACL_ITER 结构的定义：

#ifndef    __ACL_ITERATOR_INCLUDE_H__
#define    __ACL_ITERATOR_INCLUDE_H__

typedef struct ACL_ITER ACL_ITER;

/**
* ACL 库中数据结构用的通用迭代器结构定义
*/
struct ACL_ITER {
    void *ptr;        /**< 迭代器指针, 与容器相关 */
    void *data;        /**< 用户数据指针 */
    int   dlen;        /**< 用户数据长度, 实现者可设置此值也可不设置 */
    const char *key;    /**< 若为哈希表的迭代器, 则为哈希键值地址 */
    int   klen;        /**< 若为ACL_BINHASH迭代器, 则为键长度 */
    int   i;        /**< 当前迭代器在容器中的位置索引 */
    int   size;        /**< 当前容器中元素总个数 */
};

/**
* 正向遍历容器中元素
* @param iter {ACL_ITER}
* @param container {void*} 容器地址
* @examples: samples/iterator/
*/
#define    ACL_FOREACH(iter, container) /
    if ((container)) /
        for ((container)->iter_head(&(iter), (container)); /
             (iter).ptr; /
             (container)->iter_next(&(iter), (container)))

/**
* 反向遍历容器中元素
* @param iter {ACL_ITER}
* @param container {void*} 容器地址
* @examples: samples/iterator/
*/
#define    ACL_FOREACH_REVERSE(iter, container) /
    if ((container)) /
        for ((container)->iter_tail(&(iter), (container)); /
             (iter).ptr; /
             (container)->iter_prev(&(iter), (container)))

/**
* 获得当前迭代指针与某容器关联的成员结构类型对象
* @param iter {ACL_ITER}
* @param container {void*} 容器地址
*/
#define    ACL_ITER_INFO(iter, container) /
    ((container) ? (container)->iter_info(&(iter), (container)) : NULL)

#define    acl_foreach_reverse    ACL_FOREACH_REVERSE
#define    acl_foreach        ACL_FOREACH
#define    acl_iter_info        ACL_ITER_INFO

#endif

　　其实，ACL_ITER 只是定义了一些规则，具体实现由各个容器自己来实现，如果容器要实现正向遍历，则需要遵守如下原则：

　　1）则容器的结构中必须要有成员变量：iter_head(ACL_ITER* iter, /* 容器本身的对象指针 */), iter_next(ACL_ITER* iter, /* 容器本身的对象指针 */);　如果没有这两个成员变量怎么办？那在编译时如果有函数使用该容器的 acl_foreach(){} 则编译器会报错，这样的好处是尽量让错误发生在编译阶段。

　　2）同时在容器内部需要实现两个注册函数: iter_head()/2, iter_next()/2, 此两函数内部需要将容器的数据赋值给 iter->data；同时改变容器中下一个对象的位置并赋值给 iter->ptr；如果容器本身是由整数值来标识元素索引位置的，则可以把索引位置赋值给 iter->i，但别忘记依然需要将 iter->ptr 赋值－－可以赋与iter->data 同样的值，这样可以避免acl_foreach() 提前退出。

　　至于反向遍历容器中元素，规则约束下正向遍历类似，在此不再详述。

　　下面，以一个大家常用的字符串分隔功能的函数例子来结束本文：

void argv_iter(void)
{
    const char *s = "hello world, you are welcome!"; /* 源串 */
    ACL_ARGV *argv = acl_argv_split(s, " ,!"); /* 对源串进行分隔 */
    ACL_ITER iter; /* 通用的迭代器 */

    printf("/nacl_foreach for ACL_ARGV:/n");
    /* 正向遍历字符串数组 argv 中的所有元素 */
    acl_foreach(iter, argv) {
        printf(">> i: %d, value: %s/n", iter.i, (char*) iter.data);
    }

    printf("/nacl_foreach_reverse for ACL_ARGV:/n");
    /* 反向遍历字符串数组 argv 中的所有元素 */
    acl_foreach_reverse(iter, argv) {
        printf(">> i: %d, value: %s/n", iter.i, (char*) iter.data);
    }
    /* 释放字符串数组 argv */
    acl_argv_free(argv);
}