c - 使用宏在 C 中实现通用 vector 。这是个好主意吗？

Question

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

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

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

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

这是实现的样子:

#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)，但我认为它足以展示我的概念。

vector 的使用如下所示:

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

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++ 版本更快/更小的三个原因:

1. 执行new在 g++ 使用的标准 C++ 库中是次优的。如果你实现 void* operator new (size_t size)作为调用 malloc()您可以获得比内置版本更好的性能。

2. 如果 realloc()必须使用新的内存块，它以 memmove() 的方式移动旧数据， 一世。 e.它忽略数据的逻辑结构并简单地移动位。该操作很容易加速到内存总线成为瓶颈的程度。 std::vector<> ，另一方面，必须注意可能正确调用构造函数/析构函数，它不能只调用 memmove()。 .在int的情况下和 double归结为移动数据一个 int/double一次，循环在为 std::vector<> 生成的代码中.这还不错，但比使用 SSE 指令更糟糕 memmove()实现即可。

3. 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 中的大小新 vector 的字段将大于为其分配的内存大小。带有 malloc() 的行调用将增加 baz变量，新值将存储在 capacity 中以前的成员(member)baz第二次递增。您应该以一种只对它们的参数求值一次的方式编写所有宏。

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<> 的风格编写一个通用的容器类。 ，既不通过(ab)使用预处理器，也不通过(ab)使用 void* .

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

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

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

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