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

问题描述

我正在尝试使用C实现 queue 结构.我的实现非常简单；队列只能容纳 int s，而不能容纳其他任何内容.我想知道是否可以在 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)

请注意，如果您使用相同的结构来设计列表以外的其他集合，则可以对存储良好指针的任何集合使用最后一个函数.

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 (带符号的字符，无符号的长， 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屋！