C语言运行时创建多数据结构实例的多态实现问题

问题背景 #

需要开发一个读取文件的应用，需处理6种队列（二叉堆、二项堆、左式堆、斜堆、斐波那契堆、Treap）和4种容器（Vector、HashMap、Trie、BST）。由于文件数据随机生成，若不实现多态需处理24种分支情况，因此需要运行时根据读取到的数据结构名称动态创建对应实例，并实现多态逻辑。

测试文件示例：

LeftistHeap - queue

Trie - container
06:18:39 03/05/24 - time start
06:28:39 03/05/24 - time finish
42 - min time for 1 request
53 - max time for 1 request
14 - number of departments
15 25 44 47 48 39 38 32 37 28 11 45 27 11 - count for each department


尝试方案与报错 #

尝试用_Generic实现类型选择，出现编译错误：

void error: ‘_Generic’ selector of type ‘void’ is not compatible with any association

测试代码如下：

void vec() {
    printf("Vector\n");
}

void bst() {
    printf("bst\n");
}

void ht() {
    printf("Ht\n");
}

#define TEST_FUNC(X) _Generic((X), \
    Vector: vec, \
    BST: bst, \
    Hash_Table: ht \
)    

int main()
{
    char* in = "Vector";

    void* data = NULL;
    
    if (strcmp(in, "Vector") == 0) {
 
        data = (Vector*)malloc(sizeof(Vector));
    } else if (strcmp(in, "BST") == 0) {
        data = (BST*)malloc(sizeof(BST));
    } 

    TEST_FUNC(*data); 
} 

解决方案 #

为什么_Generic失效？ #

_Generic是编译期类型选择机制，依赖编译时可确定的类型信息。而你的场景是运行时通过字符串判断类型，此时void*指向的实际类型编译期无法识别，_Generic(*data)会因*data是void类型报错——_Generic不支持void作为选择器类型。

正确的运行时多态实现方式 #

C语言中实现运行时多态，核心是函数指针表（虚表）+ 统一基类结构体，封装不同数据结构的通用操作，步骤如下：

1. 定义统一基类与操作表

所有数据结构都包含指向操作表的指针，作为统一的基类接口：

// 通用操作函数表，定义所有数据结构需实现的操作
typedef struct {
    void (*destroy)(void*);       // 销毁实例
    void (*insert)(void*, int);   // 插入数据（示例操作）
    int (*get_size)(void*);       // 获取实例大小（示例操作）
    // 按需添加其他通用操作
} DataStructureVTable;

// 基类结构体，所有具体数据结构必须将其作为第一个成员
typedef struct {
    const DataStructureVTable* vtable;
} DataStructure;

2. 定义具体数据结构

以Vector和BST为例：

// Vector结构体
typedef struct {
    DataStructure base;  // 必须放在首位，保证基类指针可正确转换
    int* arr;
    int size;
    int capacity;
} Vector;

// BST结构体
typedef struct BSTNode {
    int val;
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

typedef struct {
    DataStructure base;  // 必须放在首位
    BSTNode* root;
    int size;
} BST;

3. 实现具体数据结构的操作函数

以Vector为例：

static void Vector_destroy(void* ds) {
    Vector* vec = (Vector*)ds;
    free(vec->arr);
    free(vec);
}

static void Vector_insert(void* ds, int val) {
    Vector* vec = (Vector*)ds;
    if (vec->size >= vec->capacity) {
        vec->capacity *= 2;
        vec->arr = realloc(vec->arr, vec->capacity * sizeof(int));
    }
    vec->arr[vec->size++] = val;
}

static int Vector_get_size(void* ds) {
    return ((Vector*)ds)->size;
}

// Vector的虚表
static const DataStructureVTable Vector_vtable = {
    .destroy = Vector_destroy,
    .insert = Vector_insert,
    .get_size = Vector_get_size
};

同理实现BST的操作函数与对应虚表。

4. 实现工厂函数，动态创建实例

根据读取到的字符串名称，创建对应数据结构实例：

DataStructure* create_data_structure(const char* name) {
    if (strcmp(name, "Vector") == 0) {
        Vector* vec = malloc(sizeof(Vector));
        vec->base.vtable = &Vector_vtable;
        vec->size = 0;
        vec->capacity = 4;
        vec->arr = malloc(vec->capacity * sizeof(int));
        return (DataStructure*)vec;
    } else if (strcmp(name, "BST") == 0) {
        BST* bst = malloc(sizeof(BST));
        bst->base.vtable = &BST_vtable;
        bst->root = NULL;
        bst->size = 0;
        return (DataStructure*)bst;
    } 
    // 其他数据结构的判断逻辑...
    return NULL;
}

5. 多态方式调用操作

通过基类指针调用操作，自动适配具体数据结构：

int main() {
    // 模拟从文件读取的数据结构名称
    char* ds_name = "Vector";
    DataStructure* ds = create_data_structure(ds_name);
    if (!ds) {
        fprintf(stderr, "未知数据结构：%s\n", ds_name);
        return 1;
    }

    // 调用插入操作，自动执行Vector的insert实现
    ds->vtable->insert(ds, 42);
    printf("实例大小：%d\n", ds->vtable->get_size(ds));

    // 销毁实例
    ds->vtable->destroy(ds);
    return 0;
}

优化建议 #

为避免大量if-else分支，可将数据结构名称与创建函数映射为数组，简化工厂函数逻辑：

typedef DataStructure* (*CreateFunc)(void);

typedef struct {
    const char* name;
    CreateFunc create;
} DSEntry;

static DataStructure* create_vector(void) { /* Vector创建逻辑 */ }
static DataStructure* create_bst(void) { /* BST创建逻辑 */ }

// 数据结构映射表，新增结构时只需添加条目
static const DSEntry ds_entries[] = {
    {"Vector", create_vector},
    {"BST", create_bst},
    // 其他数据结构...
};

DataStructure* create_data_structure(const char* name) {
    int count = sizeof(ds_entries)/sizeof(ds_entries[0]);
    for (int i=0; i<count; i++) {
        if (strcmp(name, ds_entries[i].name) == 0) {
            return ds_entries[i].create();
        }
    }
    return NULL;
}

总结 #

• _Generic是编译期特性，不适合运行时动态类型选择场景；
• C语言运行时多态需通过虚表（函数指针表）+ 基类结构体实现；
• 用工厂函数配合映射表动态创建实例，通过虚表调用通用操作，可避免大量分支判断，实现简洁的多态逻辑。

内容的提问来源于stack exchange，提问作者Роберт Батоян