用C编写类模板类泛型代码的最佳方式是什么？

Question

我需要用C语言编写泛型类型的AVL-tree，我所知道的最好的方法是使用void*，并编写一些用于创建、复制、赋值和销毁的函数。请告诉我一些更好的方法。

Answer 1

我将给你一个例子，告诉你如何用C实现泛型功能。这个例子是在一个链表上，但我相信如果需要，你可以在你的AVL树上修改它。

首先，您需要为list元素定义一个结构。一种可能的(最简单的实现)：

struct list_element_s {
    void *data;
    struct list_element_s *next;

};
typedef struct list_element_s list_element;

其中'data‘将充当保存信息的“容器”，'next’是对直接链接元素的引用。(注意:您的二叉树元素应该包括对右/左子元素的引用)。

创建元素结构后，您将需要创建列表结构。一个不错的做法是让一些成员指向函数:析构函数(需要用来释放‘data’持有的内存)和比较器(用来比较两个列表元素)。

列表结构实现可能如下所示：

struct list_s {
    void (*destructor)(void *data);    
    int (*cmp)(const void *e1, const void *e2);
    unsigned int size;
    list_element *head;
    list_element *tail;

};
typedef struct list_s list;

在设计数据结构之后，您应该设计数据结构接口。假设我们的列表将具有以下最简单的接口：

nmlist *list_alloc(void (*destructor)(void *data));
int list_free(list *l);
int list_insert_next(list *l, list_element *element, const void *data);
void *list_remove_next(list *l, list_element *element);

其中：

数据元素:将为您的元素分配内存:将释放为列表分配的内存，并且所有由list_element(s).

• list_insert_next持有的‘

• ’将在‘list_alloc’旁边插入一个新元素。如果‘list.

• list_remove_next’为NULL，则将在元素的头部插入:将移除并返回(void*)由'element->next‘持有的’data‘。如果'element‘为空，将执行"list->head removal“。

现在来看函数的实现：

list *list_alloc(void (*destructor)(void *data))
{
    list *l = NULL;
    if ((l = calloc(1,sizeof(*l))) != NULL) {
        l->size = 0;
        l->destructor = destructor;
        l->head = NULL;
        l->tail = NULL;
    }
    return l;
}

int list_free(list *l)
{
    void *data;
    if(l == NULL || l->destructor == NULL){
        return (-1);
    }    
    while(l->size>0){    
        if((data = list_remove_next(l, NULL)) != NULL){
            list->destructor(data);
        }
    }
    free(l);
    return (0);
}

int list_insert_next(list *l, list_element *element, const void *data)
{
    list_element *new_e = NULL;
    new_e = calloc(1, sizeof(*new_e));
    if (l == NULL || new_e == NULL) {
        return (-1);
    }
    new_e->data = (void*) data;
    new_e->next = NULL;
    if (element == NULL) {
        if (l->size == 0) {
            l->tail = new_e;
        }
        new_e->next = l->head;
        l->head = new_e;
    } else {
        if (element->next == NULL) {
            l->tail = new_e;
        }
        new_e->next = element->next;
        element->next = new_e;
    }
    l->size++;
    return (0);
}

void *list_remove_next(list *l, list_element *element)
{
    void *data = NULL;
    list_element *old_e = NULL;
    if (l == NULL || l->size == 0) {
        return NULL;
    }
    if (element == NULL) {
        data = l->head->data;
        old_e = l->head;
        l->head = l->head->next;
        if (l->size == 1) {
            l->tail = NULL;
        }
    } else {
        if (element->next == NULL) {    
            return NULL;    
        }    
        data = element->next->data;
        old_e = element->next;
        element->next = old_e->next;
        if (element->next == NULL) {
            l->tail = element;
        }
    }
    free(old_e);
    l->size--;
    return data;
}

现在，如何使用简单的泛型链表实现。在下面的示例中，列表的作用就像一个堆栈：

#include <stdlib.h>
#include <stdio.h>
#include "nmlist.h"

void simple_free(void *data){
    free(data);
}

int main(int argc, char *argv[]){
    list *l = NULL;
    int i, *j;

    l = list_alloc(simple_free);
    for(i = 0; i < 10; i++){
        j = calloc(1, sizeof(*j));
        if(j != NULL){
            *j = i;
            list_insert_next(l, NULL, (void*) j);
        }
    }

    for(i = 0; i < 10; i++){
        j = (int*) list_remove_next(l, NULL);
        if(j != NULL){
            printf("%d \n", *j);
        }
    }

    list_free(l);

    return (0);
}

请注意，您可以使用引用更复杂结构的指针来代替"int *j“。如果你这样做了，别忘了相应地修改你的'list->destructor‘函数。

Answer 2

亚历克斯说的话。在c中，void *就是存在的东西。

假设你必须在C中工作，尽管...为什么需要给库提供创建/复制/分配/销毁功能？这个库的哪些功能需要AVL-tree代码来使用这些操作？

搜索树上的主要操作是插入、删除和查找，对吗？您将需要为所有这些操作提供一个比较函数，但是您应该让这个库的客户端处理所有其他操作。在这种情况下，简单可能更好。

Answer 3

要在C中实现真正的、高性能的泛型，需要使用预处理器。这种方法有许多与C++模板方法相同的缺点；即所有(无论如何)代码都必须放在头文件中，而且调试和测试非常麻烦。优点也是存在的:你可以获得更好的性能，让编译器做各种内联来加快速度，通过减少间接性来最大限度地减少分配，以及少量的类型安全。

定义看起来像这样(假设我们有一个哈希集)

int my_int_set(int x);
#define HASH_SET_CONTAINED_TYPE int
#define HASH_SET_TYPE my_int_set
#define HASH_SET_FUNC hash_int
#include "hash_set.h"

然后，要使用它，只需使用上面创建的类型：

my_int_set x;
my_int_set_init(&x);
my_int_set_add(&x, 7);
if (my_int_set_check(&x, 7)) printf("It worked!\n");
...
// or, if you prefer
my_int_set *x = my_int_set_create();

在内部，这是通过一大堆令牌粘贴等实现的，并且(如上所述)测试起来非常痛苦。

所以就像这样：

#ifndef HASH_SET_CONTAINED_TYPE
    #error Must define HASH_SET_CONTAINED_TYPE
#endif
...  /// more parameter checking

#define HASH_SET_ENTRY_TYPE HASH_SET_TYPE ## _entry
typedef struct HASH_SET_ENTRY_TYPE ## _tag {
    HASH_SET_CONTAINED_TYPE key;
    bool present;
} HASH_SET_ENTRY_TYPE;
typedef struct HASH_SET_TYPE ## _tag {
    HASH_SET_TYPE ## _entry data[];
    size_t elements;
} HASH_SET_TYPE;

void HASH_SET_TYPE ## _add(HASH_SET_CONTAINED_TYPE value) {
    ...
}
...
#undef HASH_SET_CONTAINED_TYPE
...  // remaining uninitialization

您甚至可以添加选项；比如#define HASH_SET_VALUE_TYPE或#define HASH_SET_DEBUG。