C 中的模板模拟(用于队列数据类型) [英] Simulation of templates in C (for a queue data type)

问题描述

我正在尝试使用 C 实现一个 queue 结构.我的实现非常简单；队列只能容纳 ints 而不能容纳其他任何东西.我想知道是否可以在 C 中模拟 C++ 模板(可能通过使用预处理器 #define)，以便我的 queue 可以保存任何数据类型.

I' m trying to implement a queue structure using C. My implementation is very simple; the queue can hold only ints and nothing else. I was wondering if I could simulate C++ templates in C(probably by using the preprocessor #define) so that my queue can hold any data type.

注意:我不想使用void*.我认为这有点冒险，很容易导致奇怪的运行时错误.

Note: I do not want to use void*. I think it is a bit risky and can easily cause bizarre runtime errors.

推荐答案

您可以使用微妙和丑陋的技巧来创建那种模板.这是我会做的:

You can use subtle and ugly tricks in order to create that kind of templates. Here's what I would do:

我将首先创建一个宏——我们称之为define_list(type)——它将为给定类型的列表创建所有函数.然后我将创建一个包含指向所有列表函数的函数指针的全局结构，然后在列表的每个实例中都有一个指向该全局结构的指针(注意它与 虚拟方法表).这种事情:

I would first create a macro - let's call it say define_list(type) - that would create all the functions for a list of a given type. I would then create a global structure containing function pointers to all the list's functions and then have a pointer to that global structure in each instance of the list (note how similar it is to a virtual method table). This kind of thing:

#define define_list(type) 

    struct _list_##type; 
    
    typedef struct 
    { 
        int (*is_empty)(const struct _list_##type*); 
        size_t (*size)(const struct _list_##type*); 
        const type (*front)(const struct _list_##type*); 
        void (*push_front)(struct _list_##type*, type); 
    } _list_functions_##type; 
    
    typedef struct _list_elem_##type 
    { 
        type _data; 
        struct _list_elem_##type* _next; 
    } list_elem_##type; 
    
    typedef struct _list_##type 
    { 
        size_t _size; 
        list_elem_##type* _first; 
        list_elem_##type* _last; 
        _list_functions_##type* _functions; 
    } List_##type; 
    
    List_##type* new_list_##type(); 
    bool list_is_empty_##type(const List_##type* list); 
    size_t list_size_##type(const List_##type* list); 
    const type list_front_##type(const List_##type* list); 
    void list_push_front_##type(List_##type* list, type elem); 
    
    bool list_is_empty_##type(const List_##type* list) 
    { 
        return list->_size == 0; 
    } 
    
    size_t list_size_##type(const List_##type* list) 
    { 
        return list->_size; 
    } 
    
    const type list_front_##type(const List_##type* list) 
    { 
        return list->_first->_data; 
    } 
    
    void list_push_front_##type(List_##type* list, type elem) 
    { 
        ... 
    } 
    
    _list_functions_##type _list_funcs_##type = { 
        &list_is_empty_##type, 
        &list_size_##type, 
        &list_front_##type, 
        &list_push_front_##type, 
    }; 
    
    List_##type* new_list_##type() 
    { 
        List_##type* res = (List_##type*) malloc(sizeof(List_##type)); 
        res->_size = 0; 
        res->_first = NULL; 
        res->_functions = &_list_funcs_##type; 
        return res; 
    }

#define List(type) 
    List_##type

#define new_list(type) 
    new_list_##type()

通用接口

这里有一些宏通过存储的函数指针简单地调用列表的函数:

Generic interface

Here are some macros that simply call the list's functions via the stored function pointers:

#define is_empty(collection) 
    collection->_functions->is_empty(collection)

#define size(collection) 
    collection->_functions->size(collection)

#define front(collection) 
    collection->_functions->front(collection)

#define push_front(collection, elem) 
    collection->_functions->push_front(collection, elem)

请注意，如果您使用相同的结构来设计除列表之外的其他集合，您将能够对任何存储好指针的集合使用 last 函数.

Note that if you use the same structure to design other collections than lists, you'll be able to use the last functions for any collections that stores the good pointers.

最后，一个关于如何使用我们的新列表模板的小例子:

And to conclude, a small example of how to use our new list template:

/* Define the data structures you need */
define_list(int)
define_list(float)

int main()
{
    List(int)* a = new_list(int);
    List(float)* b = new_list(float);

    push_front(a, 5);
    push_front(b, 5.2);
}

如果你真的想在 C 中有某种模板，你可以使用那么多的技巧，但这相当丑陋(只使用 C++，它会更简单).唯一的开销将是每个数据结构实例多一个指针，因此每当您调用函数时都会多一个间接(不进行强制转换，您不必存储 void* 指针，是的 o/).希望你永远不会使用它:p

You can use that amount of tricks if you really want to have some kind of templates in C, but that's rather ugly (just use C++, it'll be simpler). The only overhead will be one more pointer per instance of data structure, and thus one more indirection whenever you call a function (no cast is done, you don't have to store void* pointers, yeah o/). Hope you won't ever use that :p

当然有一些限制，因为我们仅使用文本替换宏，而不是真正的模板.

There are of course some limitations since we are using mere text replacement macros, and not real templates.

每个编译单元只能定义一次类型，否则程序将无法编译.这可能是一个主要缺点，例如，如果您编写一个库并且您的某些标头包含一些 define_ 指令.

You can only define each type once per compile unit, otherwise, your program will fail to compile. This can be a major drawback for example if you write a library and some of your headers contain some define_ instructions.

如果你想创建一个List，它的模板类型由几个词组成(signed char, unsigned long, constbar, struct foo...) 或者其模板类型是指针 (char*, void*...)，你必须先typedef那个类型.

If you want to create a List whose template type is made of several words (signed char, unsigned long, const bar, struct foo...) or whose template type is a pointer (char*, void*...), you will have to typedef that type first.

define_list(int) /* OK */
define_list(char*) /* Error: pointer */
define_list(unsigned long) /* Error: several words */

typedef char* char_ptr;
typedef unsigned long ulong;
define_list(char_ptr) /* OK */
define_list(ulong) /* OK */

如果你想创建嵌套列表，你将不得不求助于同样的技巧.

You will have to resort to the same trick if you want to create nested lists.

这篇关于C 中的模板模拟(用于队列数据类型)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！