写点什么

如何实现一套容器(C 语言版)1

作者:祖维
  • 2022 年 6 月 23 日
  • 本文字数:2446 字

    阅读完需:约 8 分钟

如何实现一套容器(C语言版)1

 一说到容器,可能就是鼎鼎大名的 C++ STL。在别的编程语言里面也现成的容器可用,单单唯独 C 语言没有像样的容器可用。在闲的蛋疼之际,我为 C 语言实现了一套容器接口,当然不能做到 STL 那么精美绝伦,功能强大,这只为一探容器的究竟



参考 C++ 的 STL。容器本身有三个主要部分组成:


  1. 泛型,C++ 中因为有模版的机制,所以 C++ 中实现泛型就十分简单,实现原理是编译期间的源文件产生和字符串的拷贝。可 C 就没有泛型的机制,它要实现泛型功能,需要把数据在容器内的行为包装成函数,使不同数据在容器中提供统一的接口。

  2. 迭代器,可在容器对象(container,例如 链表 或 数组 )上遍访的接口,设计人员无需关心容器对象的内存分配的实现细节。

  3. 容器,对外提供增删查改的接口。


大概就这些了,根据以上内容。我们可以大致做如下的编码设计:


01 泛型

根据初步设计,数据在容器当中的行为有这几种:相等比较、大小比较、赋值、交换、不定参数转化、数据尺寸,于是代码设计如下:

  • 数据对象行为接口,取名为 T_adapter

// adapter 是所有行为接口的统一形式。typedef void (*T_adapter)(void);// 比较是否相等的行为接口typedef int (*adpter_eq) (T*, T*);// 比较大小的行为接口typedef int (*adpter_less) (T*, T*);// 不定参数转化行为接口typedef int (*adpter_vargs) (va_list);
复制代码


  • 定义一个 T_def 结构体,用于表示,数据对象 ID 及大小:

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

发布于: 刚刚阅读数: 3
用户头像

祖维

关注

还未添加个人签名 2019.08.15 加入

还未添加个人简介

评论

发布
暂无评论
如何实现一套容器(C语言版)1_c_祖维_InfoQ写作社区