使用宏在 C 中实现通用向量。这是个好主意吗？

Question

我是一个懂C和C++的程序员。我在自己的项目中使用过这两种语言，但我不知道我更喜欢哪一种。

当我用 C 编程时，我最想念 C++ 的特性是 std::vector 来自 STL（标准模板库）

我仍然没有想出我应该如何在 C 中表示不断增长的数组。到目前为止，我在我的项目中到处复制了我的内存分配代码。我不喜欢代码重复，我知道这是不好的做法，所以这对我来说似乎不是一个很好的解决方案。

前段时间我想到了这个问题，并想出了使用预处理器宏实现通用向量的想法。

这是实现的样子：

#ifndef VECTOR_H_
#define VECTOR_H_

#include <stdlib.h>
#include <stdio.h>

/* Declare a vector of type `TYPE`. */
#define VECTOR_OF(TYPE) struct { \
    TYPE *data; \
    size_t size; \
    size_t capacity; \
}

/* Initialize `VEC` with `N` capacity. */
#define VECTOR_INIT_CAPACITY(VEC, N) do { \
    (VEC).data = malloc((N) * sizeof(*(VEC).data)); \
    if (!(VEC).data) { \
        fputs("malloc failed!\n", stderr); \
        abort(); \
    } \
    (VEC).size = 0; \
    (VEC).capacity = (N); \
} while (0)

/* Initialize `VEC` with zero elements. */
#define VECTOR_INIT(VEC) VECTOR_INIT_CAPACITY(VEC, 1)

/* Get the amount of elements in `VEC`. */
#define VECTOR_SIZE(VEC) (VEC).size

/* Get the amount of elements that are allocated for `VEC`. */
#define VECTOR_CAPACITY(VEC) (VEC).capacity

/* Test if `VEC` is empty. */
#define VECTOR_EMPTY(VEC) ((VEC).size == 0)

/* Push `VAL` at the back of the vector. This function will reallocate the buffer if
   necessary. */
#define VECTOR_PUSH_BACK(VEC, VAL) do { \
    if ((VEC).size + 1 > (VEC).capacity) { \
        size_t n = (VEC).capacity * 2; \
        void *p = realloc((VEC).data, n * sizeof(*(VEC).data)); \
        if (!p) { \
            fputs("realloc failed!\n", stderr); \
            abort(); \
        } \
        (VEC).data = p; \
        (VEC).capacity = n; \
    } \
    (VEC).data[VECTOR_SIZE(VEC)] = (VAL); \
    (VEC).size += 1; \
} while (0)

/* Get the value of `VEC` at `INDEX`. */
#define VECTOR_AT(VEC, INDEX) (VEC).data[INDEX]

/* Get the value at the front of `VEC`. */
#define VECTOR_FRONT(VEC) (VEC).data[0]

/* Get the value at the back of `VEC`. */
#define VECTOR_BACK(VEC) (VEC).data[VECTOR_SIZE(VEC) - 1]

#define VECTOR_FREE(VEC) do { \
    (VEC).size = 0; \
    (VEC).capacity = 0; \
    free((VEC).data); \
} while(0)

#endif /* !defined VECTOR_H_ */

此代码位于名为 "vector.h" 的头文件中。

请注意，它确实缺少一些功能（例如 VECTOR_INSERT 和 VECTOR_ERASE），但我认为它足以展示我的概念。

矢量的使用如下所示：

int main()
{
    VECTOR_OF(int) int_vec;
    VECTOR_OF(double) dbl_vec;
    int i;

    VECTOR_INIT(int_vec);
    VECTOR_INIT(dbl_vec);

    for (i = 0; i < 100000000; ++i) {
        VECTOR_PUSH_BACK(int_vec, i);
        VECTOR_PUSH_BACK(dbl_vec, i);
    }

    for (i = 0; i < 100; ++i) {
        printf("int_vec[%d] = %d\n", i, VECTOR_AT(int_vec, i));
        printf("dbl_vec[%d] = %f\n", i, VECTOR_AT(dbl_vec, i));
    }

    VECTOR_FREE(int_vec);
    VECTOR_FREE(dbl_vec);

    return 0;
}

它使用与 std::vector 相同的分配规则（大小从 1 开始，然后每次需要时加倍）。

令我惊讶的是，我发现此代码的运行速度是使用 std::vector 和编写的相同代码的两倍多，生成的可执行文件更小！（在两种情况下都使用 -O3 使用 GCC 和 G++ 编译）。

我想问你的问题是：

这种方法有什么严重的错误吗？
您会推荐在严肃的项目中使用它吗？
如果没有，那么我希望你能解释一下原因，并告诉我更好的选择是什么。

Answer 1

My questions to you are: Are there any serious faults with this approach?

是的，您正在尝试重新发明 the wheel。

Would you recommend using this in a serious project?

不，特别是因为您的加速通常表明您可能缺少一些安全检查。

If not then I would like you to explain why and tell me what a better alternative would be.

上面的 VPool，或类似的东西。如果您搜索 "C growable buffer"，您会在 Whosebug 上和通过 google

找到一些提示

Answer 2

Are there any serious faults with this approach?

您正在以一种与 C 的类型系统交互不良的方式重新发明模板。例如，您的 VECTOR 类型是匿名的，所以我不能编写一个将 VECTOR_OF(int) 作为参数的函数。

即使你确实以某种方式命名你的类型，我也无法编写通用的函数 --- 需要 VECTOR_OF(T) 的任意 T 并用它做点什么。

这些可能不是严重的错误，但我在 C 中看到的每一种使用宏的泛型方法都有一百个这样的小缺点。这一切都是因为该语言不试图支持泛型编程完全没有。

Would you recommend using this in a serious project?

当然；您可以使用这样的容器类型开发一个严肃的项目，它们甚至不一定会出现在您面前。您可能需要输入 void * 来传递这些东西，这会导致一些容易出错的转换。

Answer 3

To my surprise I found out that this code runs more than twice as fast as the same code written using std::vector and generates a smaller executable! (compiled with GCC and G++ using -O3 in both cases).

您的 C 版本比 C++ 版本 faster/smaller 有以下三个原因：

g++ 使用的标准 C++ 库中 new 的实现不是最佳的。如果您将 void* operator new (size_t size) 实现为对 malloc() 的调用，您将获得比内置版本更好的性能。
如果 realloc() 必须使用新的内存块，它会按照 memmove() 的方式移动旧数据，即。 e.它忽略数据的逻辑结构并简单地移动位。该操作很容易加速到内存总线成为瓶颈的程度。另一方面，std::vector<> 必须注意可能正确调用 constructors/destructors，它不能直接调用 memmove()。在 int 和 double 的情况下，归结为一次移动数据一个 int/double，循环在为 [=17 生成的代码中=].这还不错，但比使用 SSE 指令更糟糕 memmove() 实现会做。
realloc() 函数是动态链接到您的可执行文件的标准 C 库的一部分。而std::vector<>生成的内存管理代码，恰恰是：生成的。因此，它必须是您的可执行文件的一部分。

Are there any serious faults with this approach?

这是一个品味问题，但我认为，这种方法很臭：你的宏定义与它们的用途相去甚远，它们的行为并不都像简单的常量或内联函数。事实上，它们的行为很像编程语言的元素（即模板），这对预处理器宏来说不是一件好事。尝试使用预处理器修改语言通常不是一个好主意。

您的宏实现也存在严重问题：VECTOR_INIT_CAPACITY(VEC, N) 宏对其 VEC 参数求值四次，对 N 参数求值两次。现在想想如果调用 VECTOR_INIT_CAPACITY(foo, baz++) 会发生什么：存储在新向量 capacity 字段中的大小将大于为其分配的内存大小。带有 malloc() 调用的行将递增 baz 变量，并且在 baz 第二次递增之前，新值将存储在 capacity 成员中。您应该以一种只对它们的参数求值一次的方式编写所有宏。

Would you recommend using this in a serious project?

我想，我不会打扰。 realloc() 代码非常简单，一些复制不会造成太大伤害。但同样，您的里程可能会有所不同。

If not then I would like you to explain why and tell me what a better alternative would be.

正如我之前所说，我不会费心尝试以 std::vector<> 的风格编写通用容器 class，既不通过（滥用）使用预处理器，也不通过（ab）使用 void*.

但我会仔细查看我为之编写的系统上的内存处理：对于许多内核，您极不可能得到 NULL 的 return 值malloc()/realloc() 通话。他们过度承诺他们的记忆，做出他们无法确定能够实现的承诺。当他们意识到他们无法支持他们的承诺时，他们开始通过 OOM-killer 拍摄流程。在这样的系统上（linux 就是其中之一），您的错误处理毫无意义。它永远不会被执行。因此，您可以避免添加它并将其复制到所有需要动态增长数组的地方的痛苦。

我在 C 中的内存重新分配代码通常如下所示：

if(size == capacity) {
    array = realloc(array, (capacity *= 2) * sizeof(*array));
}
array[size++] = ...;

如果没有无功能的错误处理代码，它会非常短，可以根据需要安全地复制多次。

使用宏在 C 中实现通用向量。这是个好主意吗？

Using macros to implement a generic vector in C. Is this a good idea?

c

vector

data-structures

macros

c-preprocessor