在C中模拟模板(用于队列数据类型)

Question

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

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

Answer 1

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

创建模板列表

用于定义列表的宏

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

#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()

通用接口

下面是一些宏,只需通过存储的函数指针调用列表的函数:

#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)

请注意,如果使用相同的结构来设计除列表之外的其他集合,则可以将最后的函数用于存储指针的任何集合.

使用示例

最后,举例说明如何使用我们的新列表模板:

/* 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

限制

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

定义一次

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

多字类型

如果你想创建一个List它的模板类型是由几个单词(signed char,unsigned long,const bar,struct foo...)或者其模板类型为指针(char*,void*...),你将有typedef该类型第一.

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 */

如果要创建嵌套列表,则必须使用相同的技巧.

Answer 2

好吧,我想到的唯一可能性是宏#define.也许是这样的:

queue.h:

#define TYPE int
#define TYPED_NAME(x) int_##x
#include "queue_impl.h"
#undef TYPE
#undef TYPED_NAME

#define TYPE float
#define TYPED_NAME(x) float_##x
#include "queue_impl.h"
#undef TYPE
#undef TYPED_NAME
...

queue_impl.h:

//no include guard, of course
typedef struct
{
    TYPE *data;
    ...
} TYPED_NAME(queue);

void TYPED_NAME(queue_insert) (TYPED_NAME(queue) *queue, TYPE data)
{
    ...
}

如果它的工作原理(这我不是100%肯定的,是不是这样的预处理器专家),它应该给你的结构int_queue和float_queue与功能一起

void int_queue_insert(int_queue *queue, int data);
void float_queue_insert(float_queue *queue, float data);

当然,您必须自己为所需的所有类型实例化"模板",但这相当于重复了5行块queue.h.实际实现只需编写一次.当然你可以进一步完善它,但基本的想法应该是清楚的.

这至少会为您提供完全类型安全的队列模板,但缺乏完全匹配接口的便利性(函数必须携带类型名称,因为C不支持重载函数).

Answer 3

实现一个包含void*数据的队列,并将此void*解释为指向任何类型的指针,甚至是像int这样的基本类型.

使用#define是可能的,但如果出现问题,请考虑调试...

Answer 4

我想了很长时间，但现在我有了一个明确的答案，任何人都可以理解；所以看哪！

当我学习数据结构课程时，我必须阅读Standish的《Data Structures, Algorithms in C》一书；这很痛苦；它没有泛型，充满了糟糕的符号和一大堆全局状态突变，而它没有理由在那里；我知道采用他的代码风格意味着搞砸我未来所有的项目，但我知道有更好的方法，所以看，更好的方法：

这就是我触摸它之前的样子（实际上我还是触摸了它，使其以人类可以阅读的方式格式化，不客气）；它在很多层面上都非常丑陋和错误，但我将列出它以供参考：

#include <stdio.h>

#define MaxIndex 100

int Find(int A[])
{
    int j;

    for (j = 0; j < MaxIndex; ++j) {
        if (A[j] < 0) {
            return j;
        }
    }

    return -1;
}

int main(void)
{
    // reminder: MaxIndex is 100.
    int A[MaxIndex];

    /**
     * anonymous scope #1
     *     initialize our array to [0..99],
     *     then set 18th element to its negative value(-18)
     *     to make the search more interesting.
     */
    {
        // loop index, nothing interesting here.
        int i;

        // initialize our array to [0..99].
        for (i = 0; i < MaxIndex; ++i) {
            A[i] = i * i;
        }

        A[17]= -A[17];
    }

    /**
     * anonymous scope #2
     *     find the index of the smallest number and print it.
     */
    {
        int result = Find(A);

        printf(
            "First negative integer in A found at index = %d.\n",
            result
        );
    }

    // wait for user input before closing.
    getchar();

    return 0;
}

这个程序以一种极其糟糕的方式做了很多事情；特别是，它设置了一个仅在单个范围内使用的全局宏，但随后继续污染任何代码；非常糟糕，并且造成Windows API规模的全球范围的大规模污染。

此外，该程序将参数作为数组传递，而没有结构体来包含它；换句话说，一旦数组到达函数Find，它就死了；我们不再知道数组的大小，所以我们现在 main 和 Find 依赖于全局宏，非常糟糕。

有两种强力方法可以解决这个问题，但仍然保持代码简单；第一种方法是创建一个全局结构体，将数组定义为包含 100 个整数的数组；这样传递结构将保留其中数组的长度。第二种方法是将数组的长度作为 find 的参数传递，并且仅在创建数组之前使用 #define 该行，并在创建数组之后立即使用 #undef ，因为作用域仍然可以通过 sizeof 知道数组的大小(A)/sizeof(A[0]) 运行时开销为 0，编译器将推导出 100 并将其粘贴进去。

为了以第三种方式解决这个问题，我制作了一个可以很好地创建通用数组的标头；它是一种抽象数据类型，但我想将其称为自动化数据结构。

简单数组.h

/**
 * Make sure that all the options needed are given in order to create our array.
 */
#ifdef OPTION_UNINSTALL
    #undef OPTION_ARRAY_TYPE
    #undef OPTION_ARRAY_LENGTH
    #undef OPTION_ARRAY_NAME    
#else 
    #if (!defined OPTION_ARRAY_TYPE) || !defined OPTION_ARRAY_LENGTH || (!defined OPTION_ARRAY_NAME)
        #error "type, length, and name must be known to create an Array."
    #endif

    /** 
     * Use the options to create a structure preserving structure for our array.
     *    that is, in contrast to pointers, raw arrays.
     */
    struct {
        OPTION_ARRAY_TYPE data[OPTION_ARRAY_LENGTH];
    } OPTION_ARRAY_NAME;

    /**
     * if we are asked to also zero out the memory, we do it.
     * if we are not granted access to string.h, brute force it.
     */
    #ifdef OPTION_ZERO_MEMORY
        #ifdef OPTION_GRANT_STRING
            memset(&OPTION_ARRAY_NAME, 0, OPTION_ARRAY_LENGTH * sizeof(OPTION_ARRAY_TYPE));
        #else
            /* anonymous scope */
            {
                int i;
                for (i = 0; i < OPTION_ARRAY_LENGTH; ++i) {
                    OPTION_ARRAY_NAME.data[i] = 0;
                }
            }
        #endif
        #undef OPTION_ZERO_MEMORY
    #endif
#endif

如果您被迫使用 C 预处理器（与 PHP/模板工具包/ASP/您自己的嵌入式脚本语言，无论是 lisp 相比），这个头本质上就是每个 C 数据结构头应该看起来像的样子。

让我们来试一下：

#include <stdio.h>

int Find(int A[], int A_length)
{
    int j;

    for (j = 0; j < A_length; ++j) {
        if (A[j] < 0) {
            return j;
        }
    }

    return -1;
}

int main(void)
{
    // std::array<int, 100> A;
    #define OPTION_ARRAY_TYPE int
    #define OPTION_ARRAY_LENGTH 100
    #define OPTION_ARRAY_NAME A
    #include "SimpleArray.h"    

    /**
     * anonymous scope #1
     *     initialize our array to [0..99],
     *     then set 18th element to its negative value(-18)
     *     to make the search more interesting.
     */
    {
        // loop index, nothing interesting here.
        int i;

        // initialize our array to [0..99].
        for (i = 0; i < (sizeof(A.data) / sizeof(A.data[0])); ++i) {
            A.data[i] = i * i;
        }

        A.data[17]= -A.data[17];
    }

    /**
     * anonymous scope #2
     *     find the index of the smallest number and print it.
     */
    {
        int result = Find(A.data, (sizeof(A.data) / sizeof(A.data[0])));

        printf(
            "First negative integer in A found at index = %d.\n",
            result
        );
    }

    // wait for user input before closing.
    getchar();

    // making sure all macros of SimpleArray do not affect any code
    // after this function; macros are file-wide, so we want to be 
    // respectful to our other functions.
    #define OPTION_UNINSTALL
    #include "SimpleArray.h"

    return 0;
}

看哪，我们在纯 C 和 C 预处理器中发明了一个简单的 std::array！我们使用了宏，但我们并不邪恶，因为我们会自己清理！我们所有的宏在作用域末尾都是 undefd 的。

有一个问题; 我们不再知道数组的大小，除非我们知道(sizeof(A.data) / sizeof(A.data[0]))。这对编译器来说没有任何开销，但对儿童不友好；宏也不是，但我们在这里的框内工作；我们稍后可以使用更友好的预处理器（例如 PHP）来使其对儿童友好。

为了解决这个问题，我们可以创建一个实用程序库，它充当“自由”数组数据结构上的方法。

SimpleArrayUtils.h

/**
 * this is a smart collection that is created using options and is 
 *      removed from scope when included with uninstall option.
 *
 * there are no guards because this header is meant to be strategically
 *     installed and uninstalled, rather than kept at all times.
 */
#ifdef OPTION_UNINSTALL
    /* clean up */
    #undef ARRAY_FOREACH_BEGIN
    #undef ARRAY_FOREACH_END
    #undef ARRAY_LENGTH
#else
    /** 
     * array elements vary in number of bytes, encapsulate common use case 
     */
    #define ARRAY_LENGTH(A) \
        ((sizeof A.data) / (sizeof A.data[0]))

    /**
     * first half of a foreach loop, create an anonymous scope,
     * declare an iterator, and start accessing the items. 
     */
    #if defined OPTION_ARRAY_TYPE
        #define ARRAY_FOREACH_BEGIN(name, iter, arr)\
            {\
                unsigned int iter;\
                for (iter = 0; iter < ARRAY_LENGTH(arr); ++iter) {\
                    OPTION_ARRAY_TYPE name = arr.data[iter];
    #endif

    /** 
     * second half of a foreach loop, close the loop and the anonymous scope 
     */
    #define ARRAY_FOREACH_END \
            }\
        }
#endif

这是一个功能相当丰富的库，它基本上导出

ARRAY_LENGTH :: 任何带有数据字段的内容 -> int

如果我们仍然定义或重新定义了 OPTION_ARRAY_SIZE，则标头还定义了如何执行 foreach 循环；这很可爱。

现在让我们疯狂一下：

简单数组.h

/**
 * Make sure that all the options needed are given in order to create our array.
 */
#ifdef OPTION_UNINSTALL
    #ifndef OPTION_ARRAY_TYPE
        #undef OPTION_ARRAY_TYPE
    #endif

    #ifndef OPTION_ARRAY_TYPE    
        #undef OPTION_ARRAY_LENGTH
    #endif

    #ifndef OPTION_ARRAY_NAME    
        #undef OPTION_ARRAY_NAME    
    #endif

    #ifndef OPTION_UNINSTALL
        #undef OPTION_UNINSTALL
    #endif
#else 
    #if (!defined OPTION_ARRAY_TYPE) || !defined OPTION_ARRAY_LENGTH || (!defined OPTION_ARRAY_NAME)
        #error "type, length, and name must be known to create an Array."
    #endif

    /** 
     * Use the options to create a structure preserving structure for our array.
     *    that is, in contrast to pointers, raw arrays.
     */
    struct {
        OPTION_ARRAY_TYPE data[OPTION_ARRAY_LENGTH];
    } OPTION_ARRAY_NAME;

    /**
     * if we are asked to also zero out the memory, we do it.
     * if we are not granted access to string.h, brute force it.
     */
    #ifdef OPTION_ZERO_MEMORY
        #ifdef OPTION_GRANT_STRING
            memset(&OPTION_ARRAY_NAME, 0, OPTION_ARRAY_LENGTH * sizeof(OPTION_ARRAY_TYPE));
        #else
            /* anonymous scope */
            {
                int i;
                for (i = 0; i < OPTION_ARRAY_LENGTH; ++i) {
                    OPTION_ARRAY_NAME.data[i] = 0;
                }
            }
        #endif
        #undef OPTION_ZERO_MEMORY
    #endif
#endif

SimpleArrayUtils.h

/**
 * this is a smart collection that is created using options and is 
 *      removed from scope when included with uninstall option.
 *
 * there are no guards because this header is meant to be strategically
 *     installed and uninstalled, rather than kept at all times.
 */
#ifdef OPTION_UNINSTALL
    /* clean up, be mindful of undef warnings if the macro is not defined. */
    #ifdef ARRAY_FOREACH_BEGIN
        #undef ARRAY_FOREACH_BEGIN
    #endif

    #ifdef ARRAY_FOREACH_END
        #undef ARRAY_FOREACH_END
    #endif

    #ifdef ARRAY_LENGTH
        #undef ARRAY_LENGTH
    #endif
#else
    /** 
     * array elements vary in number of bytes, encapsulate common use case 
     */
    #define ARRAY_LENGTH(A) \
        ((sizeof A.data) / (sizeof A.data[0]))

    /**
     * first half of a foreach loop, create an anonymous scope,
     * declare an iterator, and start accessing the items. 
     */
    #if defined OPTION_ARRAY_TYPE
        #define ARRAY_FOREACH_BEGIN(name, iter, arr)\
            {\
                unsigned int iter;\
                for (iter = 0; iter < ARRAY_LENGTH(arr); ++iter) {\
                    OPTION_ARRAY_TYPE name = arr.data[iter];
    #endif

    /** 
     * second half of a foreach loop, close the loop and the anonymous scope 
     */
    #define ARRAY_FOREACH_END \
            }\
        }
#endif

主程序

#include <stdio.h>

// std::array<int, 100> A;
#define OPTION_ARRAY_TYPE int
#define OPTION_ARRAY_LENGTH 100
#define OPTION_ARRAY_NAME A
#include "SimpleArray.h"  
#define OPTION_UNINSTALL
#include "SimpleArray.h"  

int Find(int A[], int A_length)
{
    int j;

    for (j = 0; j < A_length; ++j) {
        if (A[j] < 0) {
            return j;
        }
    }

    return -1;
}

int main(void)
{
    #define OPTION_ARRAY_NAME A
    #define OPTION_ARRAY_LENGTH (sizeof(A.data) / sizeof(A.data[0]))
    #define OPTION_ARRAY_TYPE int

    #include "SimpleArray.h"

    /**
     * anonymous scope #1
     *     initialize our array to [0..99],
     *     then set 18th element to its negative value(-18)
     *     to make the search more interesting.
     */
    {
        #include "SimpleArrayUtils.h"

        printf("size: %d.\n", ARRAY_LENGTH(A));

        ARRAY_FOREACH_BEGIN(item, i, A)
            A.data[i] = i * i;
        ARRAY_FOREACH_END

        A.data[17] = -A.data[17];


        // uninstall all macros.
        #define OPTION_UNINSTALL
        #include "SimpleArrayUtils.h"
    }

    /**
     * anonymous scope #2
     *     find the index of the smallest number and print it.
     */
    {
        #include "SimpleArrayUtils.h"        
        int result = Find(A.data, (sizeof(A.data) / sizeof(A.data[0])));

        printf(
            "First negative integer in A found at index = %d.\n",
            result
        );

        // uninstall all macros.
        #define OPTION_UNINSTALL
        #include "SimpleArrayUtils.h"
    }

    // wait for user input before closing.
    getchar();

    // making sure all macros of SimpleArray do not affect any code
    // after this function; macros are file-wide, so we want to be 
    // respectful to our other functions.
    #define OPTION_UNINSTALL
    #include "SimpleArray.h"

    return 0;
}

如你看到的; 我们现在有能力表达自由抽象（编译器代替我们），我们只为我们需要的东西（结构）付费，其余的被扔掉，并且不会污染全局范围。

我在这里强调 PHP 的强大功能，因为很少有人在 HTML 文档的上下文之外看到它；但您可以在 C 文档或任何其他文本文件中使用它。您可以使用模板工具包将任何您喜欢的脚本语言放入宏中；这些语言会比 C 预处理器好得多，因为它们有命名空间、变量和实际函数；这使得它们更容易调试，因为您正在调试生成代码的实际脚本；不是 C 预处理器，它很难调试，很大程度上是因为熟悉（头脑正常的人会花几个小时来玩弄并熟悉 C 预处理器？很少有人这样做）。

下面是使用 PHP 执行此操作的示例：

SimpleArray.php

<?php
    class SimpleArray {
        public $length;
        public $name;
        public $type;

        function __construct($options) {
            $this->length = $options['length'];
            $this->name = $options['name'];
            $this->type = $options['type'];
        }

        function getArray() {
            echo ($this->name . '.data');
        }

        function __toString() {            
            return sprintf (
                "struct {\n" .
                "    %s data[%d];\n" .
                "} %s;\n"
                ,
                $this->type,
                $this->length,
                $this->name
            );          
        }
    };
?>

main.php

#include <stdio.h>
<?php include('SimpleArray.php'); ?>

int Find(int *A, int A_length)
{
    int i;

    for (i = 0; i < A_length; ++i) 
    {
        if (A[i] < 0) {
            return i;
        }
    }

    return -1;
}

int main(int argc, char **argv)
{
    <?php 
        $arr = new SimpleArray(array(
            'name' => 'A',
            'length' => 100,
            'type' => 'int'
        ));
        echo $arr;
    ?>

    printf("size of A: %d.\n", <?php echo($arr->length); ?>);

    /* anonymous scope */
    {
        int i;

        for (i = 0; i < <?php echo($arr->length)?>; ++i) {
            <?php $arr->getArray(); ?>[i] = i * i;
        }   
        <?php $arr->getArray(); ?>[17] = -<?php $arr->getArray()?>[17];
    }

    int result = Find(<?php $arr->getArray();?>, <?php echo $arr->length; ?>);
    printf(
        "First negative integer in A found at index = %d.\n",
        result
    );

    getchar();       

    return 0;
}

跑步php main.php > main.c

然后

gcc main.c -o main
./main

这看起来很像 Objective C，因为这本质上就是 Objective C 所做的，除了它倾向于将编译时的“宏”链接到实际的运行时（就好像 php 在 C 运行时在运行时可用，并且在让你的 C 可以与 php 对话，而 php 也可以与 C 对话，只是 php 是带有许多方括号的小型语言）。主要区别在于，据我所知，Objective C 没有办法像我们在这里所做的那样创建“静态”构造；它的对象实际上是运行时的，因此访问起来要昂贵得多，但更灵活，并且保留结构，而 C 结构体一旦标头离开作用域就会崩溃为字节（而对象可以反射回其原始状态）使用内部标记联合的状态）...