简单来说,问题是如何在不必复制/重写算法的情况下实现使用相似算法但具有不同接口的两个结构? 最好的方式是什么,指的是最易于维护和调试的方法。
我认为显而易见的是,您不希望有两份相同算法的副本。
动机:
假设您有一个结构(称之为“map”),其中包含一组相关函数(“map_*()”)。 由于地图需要将任何内容映射到任何内容,因此我们通常会采用“void * key”和“void * data”来实现它。 但是,请考虑将int映射到int的地图。 在这种情况下,您需要将所有键和数据存储在另一个数组中,并将其地址提供给地图,这不太方便。
现在想象一下是否有类似的结构(称之为“mapc”,其中c代表“copies”),在初始化期间需要采用“sizeof(your_key_type)”和“sizeof(your_data_type)”,并在插入时给出“void * key”和“void * data”,它将使用“memcpy”将键和数据复制到地图中,而不仅仅是保留指针。 以下是用法示例:
int i;
mapc m;
mapc_init(&m, sizeof(int), sizeof(int));
for (i = 0; i < n; ++i)
{
int j = rand(); /* whatever */
mapc_insert(&m, &i, &j);
}
这很好,因为我不需要再维护另一个i和的数组。
我的想法
在上面的示例中,map
和mapc
非常相似。如果你考虑一下,map
和set
结构和函数也非常相似。我已经想到了以下几种方法来实现它们的算法,只需实现一次即可用于所有情况。但是,它们都不太令我满意。
Use macros. Write the function code in a header file, leaving the structure dependent stuff as macros. For each structure, define the proper macros and include the file:
map_generic.h #define INSERT(x) x##_insert int INSERT(NAME)(NAME *m, PARAMS) { // create node ASSIGN_KEY_AND_DATA(node) // get m->root // add to tree starting from root // rebalance from node to root // etc } map.c #define NAME map #define PARAMS void *key, void *data #define ASSIGN_KEY_AND_DATA(node) \ do {\ node->key = key;\ node->data = data;\ } while (0) #include "map_generic.h" mapc.c #define NAME mapc #define PARAMS void *key, void *data #define ASSIGN_KEY_AND_DATA(node) \ do {\ memcpy(node->key, key, m->key_size);\ memcpy(node->data, data, m->data_size);\ } while (0) #include "map_generic.h"
This method is not half bad, but it's not so elegant.
Use function pointers. For each part that is dependent on the structure, pass a function pointer.
map_generic.c int map_generic_insert(void *m, void *key, void *data, void (*assign_key_and_data)(void *, void *, void *, void *), void (*get_root)(void *)) { // create node assign_key_and_data(m, node, key, data); root = get_root(m); // add to tree starting from root // rebalance from node to root // etc } map.c static void assign_key_and_data(void *m, void *node, void *key, void *data) { map_node *n = node; n->key = key; n->data = data; } static map_node *get_root(void *m) { return ((map *)m)->root; } int map_insert(map *m, void *key, void *data) { map_generic_insert(m, key, data, assign_key_and_data, get_root); } mapc.c static void assign_key_and_data(void *m, void *node, void *key, void *data) { map_node *n = node; map_c *mc = m; memcpy(n->key, key, mc->key_size); memcpy(n->data, data, mc->data_size); } static map_node *get_root(void *m) { return ((mapc *)m)->root; } int mapc_insert(mapc *m, void *key, void *data) { map_generic_insert(m, key, data, assign_key_and_data, get_root); }
This method requires writing more functions that could have been avoided in the macro method (as you can see, the code here is longer) and doesn't allow optimizers to inline the functions (as they are not visible to
map_generic.c
file).
那么,您如何实现这样的功能?
注:我是在 stack-overflow 的问题形式中编写代码的,所以如果有小错误,请原谅。
附带问题:有没有更好的后缀来表示“此结构体复制数据而不是指针”? 我使用 c
表示“copy”,但可能还有更好的英文单词我不知道。
更新:
我想出了第三个解决方案。 在这个解决方案中,仅编写一个版本的 map
,即保留数据副本的版本(mapc
)。此版本将使用 memcpy
复制数据。另一个 map
是对此的接口,它采用 void *key
和 void *data
指针,并将 &key
和 &data
发送到 mapc
,以便复制它们包含的地址(使用 memcpy
)。
这种解决方案的缺点是通过 memcpy
进行普通指针赋值,但它完全解决了其他问题,并且非常干净。
或者,可以只实现 map
并使用一个额外的带有 mapc
的 vectorc
,它首先将数据复制到向量中,然后将地址提供给 map
。这会产生副作用,即从 mapc
中删除要比其他结构慢得多,或者留下垃圾(或需要其他结构来重用垃圾)。
更新2:
我得出结论,粗心的用户可能会像编写 C++ 一样使用我的库,不停地复制。因此,我放弃了这个想法,只接受指针。