9

我正在为 C (这里)实现一组常见但不那么微不足道（或容易出错）的数据结构，并提出了一个让我思考的想法。

简而言之，实现两个使用相似算法但具有不同接口的结构的最佳方法是什么，而无需复制粘贴/重写算法？最好，我的意思是最可维护和可调试的。

我认为很明显为什么你不想拥有相同算法的两个副本。

动机

假设您有一个map带有一组关联函数 ( ) 的结构（称为它map_*()）。由于地图需要将任何东西映射到任何东西，我们通常会用一个void *keyand来实现它void *data。int但是，想想to的映射int。在这种情况下，您需要将所有键和数据存储在另一个数组中，并将它们的地址提供给map，这不太方便。

现在想象一下，如果有一个类似的结构（称为它mapc，c 表示“副本”），在初始化过程中获取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);
}

这非常好，因为我不需要保留另一个is 和js 数组。

我的想法

在上面的例子中，map和mapc是非常密切相关的。仔细想想，map结构set和功能也很相似。我已经想到了以下方法来只实现一次他们的算法并将其用于所有算法。然而，他们都没有让我很满意。

  1. 使用宏。将函数代码写入头文件中，将依赖于结构的内容保留为宏。对于每个结构，定义适当的宏并包含文件：

    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"

    这种方法还不错，但也不是那么优雅。

  2. 使用函数指针。对于依赖于结构的每个部分，传递一个函数指针。

    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);
}

    这种方法需要编写更多可以在宏方法中避免的函数（如您所见，这里的代码更长）并且不允许优化器内联函数（因为它们对map_generic.c文件不可见）。

那么，你将如何实施这样的事情呢？

注意：我在stack-overflow问题形式中编写了代码，如果有小错误请见谅。

附带问题：对于“此结构复制数据而不是指针”的后缀，任何人都有更好的主意吗？我用c的是“副本”，但在英语中可能有一个更好的词，我不知道。

更新：

我想出了第三种解决方案。在此解决方案中，只map编写了一个版本，即保留数据副本的版本 ( mapc)。此版本将用于memcpy复制数据。另一个map是对此的接口，获取void *key和void *data指针并发送&key和&data，mapc以便复制它们包含的地址（使用memcpy）。

这个解决方案的缺点是正常的指针分配是由 完成的memcpy，但它完全解决了这个问题并且非常干净。

或者，只能实现map并使用 extra vectorc，mapc首先将数据复制到 vector ，然后将地址提供给 a map。这有一个副作用，即删除mapc要么会慢很多，要么会留下垃圾（或需要其他结构来重用垃圾）。

更新 2：

我得出的结论是粗心的用户可能会像编写 C++ 一样使用我的库，一个接一个地复制。因此，我放弃了这个想法，只接受指针。

4

3 回答 3

3

您大致涵盖了两种可能的解决方案。

预处理器宏大致对应于 C++ 模板，具有相同的优缺点：

  • 它们很难阅读。
  • 复杂的宏通常很难使用（考虑参数的类型安全等）
  • 它们只是更多代码的“生成器”，因此在编译输出中仍然存在很多重复性。
  • 另一方面，它们允许编译器优化很多东西。

函数指针大致对应于 C++ 多态性，恕我直言，它们更干净且通常更易于使用的解决方案，但它们在运行时带来了一些成本（对于紧密循环，很少额外的函数调用可能会很昂贵）。

我通常更喜欢函数调用，除非性能真的很关键。

于 2012-06-14T14:20:43.330 回答
1

您正在寻找的是多态性。C++、C# 或其他面向对象的语言更适合这项任务。尽管许多人尝试在 C 中实现多态行为。

代码项目有一些关于这个主题的好文章/教程：

http://www.codeproject.com/Articles/10900/Polymorphism-in-C

http://www.codeproject.com/Articles/108830/Inheritance-and-Polymorphism-in-C

于 2012-06-14T14:18:00.907 回答
1

您还没有考虑过第三种选择：您可以创建一个外部脚本（用另一种语言编写）来从一系列模板生成您的代码。这类似于宏方法，但您可以使用 Perl 或 Python 之类的语言来生成代码。由于这些语言比 C 预处理器更强大，因此您可以避免通过宏执行模板时固有的一些潜在问题。在我想使用复杂宏的情况下，我使用了这种方法，例如您的示例 #1。最后，结果证明它比使用 C 预处理器更不容易出错。缺点是在编写生成器脚本和更新 makefile 之间，最初设置起来有点困难（但 IMO 最终值得）。

于 2012-06-14T15:21:12.397 回答