模拟C中的模板（对于队列数据types）
我试图用C实现一个queue结构。我的实现非常简单， 队列只能容纳int而不是别的。 我想知道是否可以在C模拟C++模板（可能通过使用预处理器#define ），以便我的queue可以保存任何数据types。
注意：我不想使用void* 。 我认为这有点冒险，很容易造成奇怪的运行时错误。
您可以使用微妙和丑陋的技巧来创build这种模板。 这是我会做的：
创build一个模板列表
macros来定义列表
我首先要创build一个macros – 让我们把它define_list(type) – 这将创build一个给定types的列表的所有function。 然后创build一个全局结构，它包含所有列表函数的函数指针，然后在列表的每个实例中都有一个指向该全局结构的指针（注意它与虚拟方法表有多相似）。 这样的事情：
#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()
通用接口
以下是一些通过存储函数指针调用列表函数的macros：
#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)
请注意，如果使用相同的结构来devise除列表之外的其他集合，则可以使用存储良好指针的任何集合的最后一个函数。
使用示例
总而言之，一个如何使用我们新的列表模板的小例子：
/* 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
限制
由于我们仅仅使用文本replacemacros，而不是真正的模板，所以当然有一些限制。
定义一次
每个编译单元只能定义一个types，否则程序将无法编译。 例如，如果您编写一个库并且您的一些头文件包含一些define_指令，这可能是一个主要缺点。
多词types
如果你想创build一个模板types由多个单词（ signed char ， unsigned long ， const bar ， struct foo …）或模板types为指针（ char* ， void* …）的List将不得不先键入这个types。
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 */
如果要创build嵌套列表，则必须使用相同的技巧。
那么，我想到的唯一可能是macros（ #define s）。 也许是这样的：
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);
当然，你将不得不自己去实例化所有你需要的types，但是这等于在queue.h重复5行代码块。 实际的实施必须只写一次。 当然，你可以更细化这个，但是基本的想法应该是清楚的。
这将至less为您提供完美的types安全队列模板，尽pipe缺乏完全匹配接口的便利（由于C不支持重载函数，因此函数必须携带types名称）。
实现一个包含void *数据的队列，并将此void *解释为指向任何types的指针，甚至像int这样的基本types。
使用#define是可能的，但想想debugging，如果出了什么问题…
这里是一个版本，可以让你实例化（通过预处理器），并在同一个C文件中使用多个types（小心，它使用令牌串联 ） ：
#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); }
如果你真的想这样做，可以通过简单的typedef来解决：
typedef int data_t; struct queue { data_t* data; }
现在可以在所有地方使用data_t ，而不是纯int 。 但是，请注意，您将无法一次使用多种types（至less，我没有看到在C中如何模拟C ++模板的特定行为）。
我很长时间以来一直在想这个，但是现在我有一个明确的答案，任何人都可以理解。 所以看！
当我参加数据结构课程时，我必须阅读Standish关于数据结构，Calgorithm的书。 这是痛苦的; 它没有generics，它充满了可怜的符号和一大堆全球性的国家突变，在那里没有任何授权。 我知道采用他的代码风格意味着将所有未来的项目搞砸了，但是我知道有一个更好的方法，所以更好的方法是：
这是我触摸它之前的样子（实际上，我曾经触摸它，以人类可以阅读的方式进行格式化，不用客气）。 在很多层面上都是很丑陋的，但是我会列出来供参考：
#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; }
这个程序以一种可怕的坏风格做了许多事情。 特别是，它设置了一个全局macros，它只在一个范围内使用，但是继续污染任何代码; 非常糟糕，并导致全球范围的大规模污染的Windows API规模。
此外，这个程序将参数作为数组传递，而不包含结构体来包含它。 换句话说，一旦到达函数Find，数组就到达了死亡状态; 我们不再知道数组的大小了，所以我们现在有了main和Find依赖的全局macros，非常不好。
有两个蛮力的方法可以让这个问题消失，但是仍然保持代码简单; 第一种方法是创build一个全局结构，将数组定义为100个整数的数组; 这种传递结构的方式将保持数组的长度。 第二种方法是将数组的长度作为find的parameter passing，在创build数组之前只使用#define行，之后使用#undef，因为scope将通过sizeof来知道数组的大小（A）/ sizeof（A [0]），运行时开销为0，编译器将推导出100并粘贴进去。
为了以第三种方式解决这个问题，我制作了一个头文件，可以很好地创build通用数组。 这是一个抽象的数据types，但我想称之为自动化的数据结构。
SimpleArray.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 /你自己的可embedded脚本语言，不pipe它是什么），这个头文件基本上就是每个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; }
BEHOLD，我们在纯C和C预处理器中发明了一个天真的std :: array！ 我们使用macros，但我们不是邪恶的，因为我们自己清理！ 我们所有的macros在我们的范围的末尾都是undefd。
有一个问题; 我们不再知道数组的大小，除非我们这样做(sizeof(A.data) / sizeof(A.data[0])) 。 这对编译器来说没有任何开销，但它不适合儿童使用; macros也不是，但我们正在这里的框内工作; 我们稍后可以使用像PHP这样更友好的预处理器来使其对孩子友好。
为了解决这个问题，我们可以创build一个实用程序库，作为我们的“自由”arrays数据结构的方法。
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循环; 这是可爱的。
现在让我们发疯：
SimpleArray.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
main.c中
#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; }
如你看到的; 我们现在有权力expression自由抽象（编译器替代它们），我们只需要付出我们需要的东西（结构），其余的就被抛弃了，不会污染全球范围。
我在这里强调了PHP的强大function，因为很less有人在HTML文档的上下文之外看到它; 但是可以在C文档或任何其他文本文件中使用它。 你可以使用模板工具包来让你喜欢的任何脚本语言放在macros中; 而且这些语言会比C预处理器好得多，因为它们有命名空间，variables和实际function; 这使得它们更容易debugging，因为您正在debugging生成代码的实际脚本; 不是C预处理器，这是很难debugging的，很大程度上是由于熟悉（正确思维的人花了几个小时来熟悉C预处理器，很less有人这样做）。
这是一个用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，因为这基本上是C所做的目标，除了它将编译时间的“macros”链接到实际的运行时（就像php在运行期间在运行时可用）把你的C可以和php交谈，而php可以和C交谈，除了php是带有许多方括号的小信息语言）。 主要的区别在于，我所知道的Objective C并不像我们在这里所做的那样有“静态”构造的方法; 它的对象实际上是运行时的，因此访问成本要高得多，但是更加灵活，并且保留了结构，而C结构只要头离开作用域就折叠成字节（而对象可以reflection回原来的状态使用内部标记的联合）…
用C预处理macros你不能真正得到一个高质量的模板， 因为这些macros只扩展一次，所以最好你可以得到一个可以重新input的数据结构，但是一旦处理完毕，就是整个程序的types。
这意味着你需要考虑void *types的解决scheme，这会削弱C的types检查。 要尝试修复弱化types检查，可以考虑在结构中embedded一个“types”字段，该字段是一个“在构造时分配一次”string，表示非void *types。 那么你可以改进与维护结构有关的函数中缺lesstypes检查。 也就是说，如果这样的事情对你来说甚至是重要的。
在另一个答案中使用其中一个代码genmacros，然后用一些C11过载macros来完成它，所以你不必乱丢你的呼叫站点太多的types信息。
#define q(t) \ typedef struct _q_##t {tv; 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; }
但我不确定那是你在找什么
