我正在尝试queue
使用 C 实现一个结构。我的实现非常简单;队列只能容纳int
s 而不能容纳其他任何东西。我想知道我是否可以在(可能通过使用预处理器)中模拟C++
模板,以便我可以保存任何数据类型。C
#define
queue
注意:我不想使用void*
. 我认为这有点冒险,很容易导致奇怪的运行时错误。
您可以使用微妙而丑陋的技巧来创建这种模板。这是我要做的:
我将首先创建一个宏——我们称之为它define_list(type)
——它将为给定类型的列表创建所有函数。然后,我将创建一个包含指向所有列表函数的函数指针的全局结构,然后在列表的每个实例中都有一个指向该全局结构的指针(注意它与虚拟方法 table有多么相似)。这种事情:
#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)
请注意,如果您使用相同的结构来设计除列表之外的其他集合,您将能够将 last 函数用于存储好指针的任何集合。
最后,用一个小例子来说明如何使用我们的新列表模板:
/* 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 */
如果要创建嵌套列表,则必须使用相同的技巧。
好吧,我想到的唯一可能是宏(#define
s)。也许是这样的:
队列.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% 确定,不是这样的预处理器专家),它应该给你 structsint_queue
和float_queue
,以及函数
void int_queue_insert(int_queue *queue, int data);
void float_queue_insert(float_queue *queue, float data);
当然,对于所有需要的类型,您必须自己进行“模板”的实例化,但这相当于在queue.h
. 实际的实现只需要编写一次。当然你可以进一步细化这个,但是基本的想法应该是清楚的。
这至少会为您提供完美的类型安全队列模板,尽管缺少完全匹配接口的便利(函数必须携带类型名称,因为 C 不支持重载函数)。
实现一个包含 void* 数据的队列,并将这个 void* 解释为指向任何类型的指针,甚至是像 int 这样的原始类型。
使用#define 是可能的,但考虑调试,如果有问题......
我想了很长时间,但现在我有了一个任何人都可以理解的明确答案;看哪!
当我学习数据结构课程时,我不得不阅读 Standish 关于数据结构、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 执行此操作的示例:
简单数组.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
);
}
};
?>
主文件
#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 是一种带有许多方括号的 smalltalkish 语言)。主要区别在于,据我所知,Objective C 没有一种方法来制作“静态”构造,就像我们在这里所做的那样。它的对象实际上是运行时的,因此访问成本要高得多,但更灵活,并且可以保留结构,而 C 结构一旦标头离开范围就会崩溃为字节(而对象可以反映回它们的原始使用内部标记工会的状态)...
这是一个版本,可以让您实例化(通过预处理器)并在同一个 C 文件中使用多种类型(小心,它使用令牌连接):
#include <stdio.h>
#define DEFINE_LL_NODE(CONCRETE_TYPE) \
struct node_of_ ## CONCRETE_TYPE \
{ \
CONCRETE_TYPE data; \
struct node_of_ ## CONCRETE_TYPE *next; \
};
#define DECLARE_LL_NODE(CONCRETE_TYPE,VARIABLE_NAME) \
struct node_of_ ## CONCRETE_TYPE VARIABLE_NAME;
/* Declarations for each type. */
DEFINE_LL_NODE(int)
DEFINE_LL_NODE(char)
int main (void)
{
/* Declaration of instances of each type. */
DECLARE_LL_NODE (int, foo)
DECLARE_LL_NODE (char, bar)
/* And you can then use these instances. */
foo.data = 1;
foo.next = NULL;
bar.data = 'c';
bar.next = NULL;
}
如果我用 预处理它cpp
,我会得到:
struct node_of_int { int data; struct node_of_int *next; };
struct node_of_char { char data; struct node_of_char *next; };
int main (void)
{
struct node_of_int foo;
struct node_of_char bar;
foo.data = 1;
foo.next = ((void *)0);
bar.data = 'c';
bar.next = ((void *)0);
}
在 C 中使用预处理器宏无法真正获得高质量的模板工作;因为,这些宏只扩展一次,所以充其量你可以得到一个可以重新输入的数据结构,但一旦处理,整个程序的类型就是这种类型。
这意味着您需要考虑void *
类型解决方案,这会削弱 C 的类型检查。要尝试修复削弱的类型检查,请考虑在您的结构中嵌入一个“类型”字段,该字段是一个表示非 void* 类型的“在构造时分配一次”字符串。然后,您可以改进与维护结构相关的函数中缺少类型检查的问题。也就是说,如果这样的事情对你来说甚至很重要。
#define q(t) \
typedef struct _q_##t {t v; struct q_##t *next} q_##t;
q(char);
q(int);
int main(void)
{
q_char qc;
q_int qi;
qc.v = 'c';
qc.next = (void *) 0;
qi.v = 42;
qi.next = (void *) 0;
return 0;
}
但我不确定这就是你要找的......
如果你真的想这样做,可以通过一个简单的方法来解决typedef
:
typedef int data_t;
struct queue
{
data_t* data;
}
您现在可以data_t
在所有地方使用而不是普通int
的 s。但是请注意,您将无法同时使用多种类型(至少,我看不到如何在纯 C 中模拟 C++ 模板的这种特殊行为)。
在另一个答案中使用其中一个代码生成宏,然后用一些 C11 重载宏完成它,这样您就不必在呼叫站点上乱扔太多类型信息。
根据我在回复中看到的一些评论。
事实上,在 C 中解决这个问题的方法是使用 #define 宏和函数指针。问题是,C++ 模板,在他们的第一个版本中,几乎就是这样——一种复制一些代码和生成一些符号的方式,在文本上“参数化”原始文件。天空是如何在这里发挥您的想象力的极限,请小心,因为在许多方面,您在类型检查等方面都是靠自己的,不要期望编译器提供太多帮助。
时不时说“为什么不只使用 C++”在这里会适得其反。问题具体是如何在没有该功能时模拟该功能。我不得不说,根据我的经验,我曾经在 C++ 中模拟过模板。敢猜为什么?因为那是 1990 年初,所以有 C++,还有 C++ 模板的想法,但几乎没有这样的实现。这就是为什么。好吧,在那之前我也用C做过。C++ 让它变得更容易了,因为至少你不必再使用函数指针来模拟类方法,因为,你得到了本地语言的支持。否则,那时,就像在 C 中一样,#define 是你唯一的参数编程朋友。