“ 一说到容器，可能就是鼎鼎大名的 C++ STL。在别的编程语言里面也现成的容器可用，单单唯独 C 语言没有像样的容器可用。在闲的蛋疼之际，我为 C 语言实现了一套容器接口，当然不能做到 STL 那么精美绝伦，功能强大，这只为一探容器的究竟”
参考 C++ 的 STL。容器本身有三个主要部分组成：
泛型，C++ 中因为有模版的机制，所以 C++ 中实现泛型就十分简单，实现原理是编译期间的源文件产生和字符串的拷贝。可 C 就没有泛型的机制，它要实现泛型功能，需要把数据在容器内的行为包装成函数，使不同数据在容器中提供统一的接口。
迭代器，可在容器对象（container，例如 链表 或 数组 ）上遍访的接口，设计人员无需关心容器对象的内存分配的实现细节。
容器，对外提供增删查改的接口。
大概就这些了，根据以上内容。我们可以大致做如下的编码设计：
01 泛型
根据初步设计，数据在容器当中的行为有这几种：相等比较、大小比较、赋值、交换、不定参数转化、数据尺寸，于是代码设计如下：
// adapter 是所有行为接口的统一形式。typedef void (*T_adapter)(void);// 比较是否相等的行为接口typedef int (*adpter_eq) (T*, T*);// 比较大小的行为接口typedef int (*adpter_less) (T*, T*);// 不定参数转化行为接口typedef int (*adpter_vargs) (va_list);
复制代码
typedef struct { // 给这个泛型定义起个ID int ty_id; // 指明此泛型的大小 int ty_size;} T_def;
复制代码
typedef struct { // id 及 大小 T_def _def; // 行为接口 T_adapter _adapter[3];} T_clazz;
复制代码
为了开箱即用，需要内定一些常用的数据对象。例如整型（int）和浮点（float）。
// 定义两种内在的数据对象的ID// ID 的用处会在稍后展示。typedef enum { int_t = 1, float} built_in_type_t;
// 再给行为函数也取个IDtypedef enum { adp_eq=0, adp_less, adp_vargs,} adapter_t;
复制代码
// 整型的相等比较int eq_int(T* t1, T* t2){ int v1 = *((int*)(t1)); int v2 = *((int*)(t2)); return v1 == v2;}
// 整型的大小比较int less_int(T* t1, T* t2){ int v1 = *((int*)(t1)); int v2 = *((int*)(t2)); return v1 < v2;}// 整型的不定参数转化int vargs_int(va_list valist, T* t){ int type_v = va_arg(valist, int); *((int*)t) = type_v; return 0;}
复制代码
int eq_float(T* t1, T* t2){ float v1 = *((int*)(t1)); float v2 = *((int*)(t2)); if (fabs(v1 - v2) <= 0.00001) return 1; return 0;}
int less_float(T* t1, T* t2){ float v1 = *((int*)(t1)); float v2 = *((int*)(t2)); return v1 < v2;}
int vargs_float(va_list valist, T* t){ double v = va_arg(valist, double); *((float*)t) = (float)v; return 0;}
复制代码
为了开箱即用，在全局作一数组用于存放整型和浮点型的数据对象。
// 全局的 T_def 的数组。使用 static 定义为私域数组，通过公域接口来获取。static T_def __T_DEFS_BASE[4] = { // 0 {0, 0}, {int_t, sizeof(int)}, {fl_t, sizeof(float)}, // 2 ~ 5 保留备用 {0, 0}};// 存放行为函数的数组。使用 static 定义为私域数组，通过公域接口来获取。static T_adapter __T_ADAPTERS_TAB[4][3] = { {0,0,0}, // eq_int, less_int,vargs_int另外定义在built_in_type.c中 {&eq_int, &less_int, &vargs_int}, {&eq_float, &less_int, &vargs_float}, //备用，当有 {0,0,0}};
复制代码
使用两个全局函数获取 T_def 与 T_adapter
// 根据泛型 ID 返回泛型T_def T_def_get(int T_id) { return __T_DEFS_BASE[T_id];}// 根据泛型的 ID 返回泛型的适配器。T_adapter T_adapter_get(int T_id, int adapter) { return __T_ADAPTERS_TAB[T_id][adapter];}
复制代码
定义几个关于 T_adapter 的宏，方便调用数据对象的行为函数
#define T_size(clazz_ptr) ((clazz_ptr)->_def.ty_size)#define T_eq(clazz_ptr) ((adapter_eq)((clazz_ptr)->_adapter[adp_less]))#define T_less(clazz_ptr) ((adapter_less)((clazz_ptr)->_adapter[adp_less]))#define T_vargs_to(clazz_ptr) ((adapter_vargs) ((clazz_ptr)->_adapter[adp_vargs]))
复制代码
02 迭代器
迭代器就比较容易了。只需要两个字段：指向数据的指针、指向当前迭代器的指针。数据指针是为了获取数据，而指向容器的指针是为了调用迭代器移动的函数。
迭代器的定义如下：
typedef struct _iterator iter_t;struct _iterator { container_t* container; T* reference;};
复制代码
在定义一个方便构造迭代器的宏：
#define __iterator(__refer, __container) \ ({ \ iter_t it = { .reference = (__refer), \ .container = (__container)}; \ it; \ })
复制代码
03 容器
终于到主角了。
这里为了点到为止，就只展示容器的几个关键的接口，返回第一个迭代器、返回最后一个迭代器、移动、添加、删除等这几个接口：
struct _container { // 返回第一个数据的函数指针 iterator_t (*first) (container_t* container_ptr); // 返回最后一个数据的函数指针 iterator_t (*last) (container_t * container_ptr); // 移动的迭代器的函数指针 int (*move) (iterator_t* iter, int step);
// 插入函数 int (*insert) (container_t* container_ptr, iterator_t iter, ...); // 删除函数 int (*remove) (container_t* container_ptr, iterator_t iter); // 当前容器中的数据类型 T_clazz *type_clazz;};
复制代码
以上便是容器接口的定义。可以说是套在容器外的一层壳。那如何将其变成真实能用的容器。
且看下一集：链表。
以上代码均来自：https://github.com/zuweie/boring-code
评论