经常使用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); }
ACL中有哪些常见的容器实现了 ACL_ITER 所要求的功能,可以通过 samples/iterator/ 下的例子进行查看.
ACL 库下载位置:http://acl.sourceforge.net/
QQ 群:242722074
相关推荐
$ ls 备忘录模式.pdf 工厂模式.pdf 模板模式.pdf 中介者...迭代器模式.pdf 开篇.pdf 原型模式.pdf 访问者模式.pdf 命令模式.pdf 责任链模式.pdf $ http://blog.csdn.net/feixiaoxing/article/category/951264的mirror
5.MFC_使用向导快速进行MFC程序设计.mp4 50.MFC_CFile.mp4 51.MFC_CArchive.mp4 52.MFC_四个对象四种方法.mp4 53. MFC_Ruler.mp4 54.MFC_Ruler.mp4 55.MFC_Ruler.mp4 56.MFC_SdiSquares.mp4 57.MFC_Scroll_...
使用C语言实现的“泛型链表”,该链表为循环双链表,它的设计参考了C++的STL容器库中的容器list及泛型算法的接口,并使用迭代器来遍历链表。使用时只需要include头文件即可,隐藏了List类型的具体实现。用户并不需要...
C++程序设计思想与方法 C++ 面向对象 程序设计 设计思想 思想与方法 ...第二部分重点介绍面向对象的思想,包括类的设计与使用、运算符的重载、继承、多态性、输入/输出、异常处理、容器和迭代器等。
cards.txt 是存储上网卡记录用的 records.txt 是存储上网记录用的 初始都为空 ...list<type> A; 是用来创建一个类型为type的链表A ...这段代码是对链表的遍历 literator 是迭代器,作用和for循环中的循环变量相同(如i,j)
第2章讲解了C++泛型编程的容器、迭代器和常用算法;第3章讲解了ACM程序设计的基本编程技巧;第4章讲解了50道原版ACM竞赛题的解题思路,并配有C++泛型编程参考答案和题目的中文翻译。 《ACM程序设计》是一本专门对...
范例1-44 单循环链表中元素的删除 101 ∷相关函数:ListDelete_CL函数 1.3.14 单循环链表的清除和销毁 107 范例1-45 单循环链表的清除和销毁 107 ∷相关函数:DestroyList函数 1.3.15 仅设表尾指针循环链表的...
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
对于2FSK,调制就是把输入数字序列变成适合于信道传输的正弦波。产生 正弦波有差分迭代法、泰勒级数法、查表法等多种方法。查表法虽然要占用较多 ...本书旨在DSP设计2FSK调制解调器,C语言,包含CCS下的编译调试
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
本书是经典程序设计思想与C++开发实践的完美...第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
第20章 容器和迭代器 第21章 算法和映射 第四部分 拓宽视野 第22章 理念和历史 第23章 文本处理 第24章 数值计算 第25章 嵌入式系统程序设计 第26章 测试 第27章 C语言 术语表 参考书目 第...
《妙趣横生的算法(C语言实现)》可作为算法入门人员的教程,也可以作为学习过C语言程序设计的人士继续深造的理想读物,也可作为...第10章 算法设计与数据结构面试题精粹 10.1 常见的算法设计题 10.2 常见的数据结构题