C++向量的最佳C实现是什么？

Question

我一直在研究使用C而非C++，因为我认为它更加简洁，但唯一缺少的是类似于向量的数组。

最佳实现方式是什么？

我希望只需要调用像vector_create、vector_at、vector_add等函数即可。

- Will03uk

---

我不认为这会使代码更清晰或更简洁。这就像创建一个用于添加2个数字的函数。C仍然是C，它不是面向对象编程。 - m0skit0

可能是你自己的。维基百科是一个不错的起点。 - user786653

STL为集合类型带来的两个优点是模板和资源获取即初始化（RIIA）；鉴于在C语言中无法表达这两个概念，因此重建STL在C语言中并没有太大的动力。 - SingleNegationElimination

Answer 1

编辑

这个回答很久以前发布，但是我曾经实现了一个基于宏的高效、类型安全的C语言向量模拟器，它涵盖了所有典型的特性和需求。你可以在这里找到它:

https://github.com/eteran/c-vector

以下是原始回答。

---

你想要复制向量的哪些功能？最终，它都会归结为类似于这样的东西:

int *create_vector(size_t n) {
    return malloc(n * sizeof(int));
}

void delete_vector(int *v) {
    free(v);
}

int *resize_vector(int *v, size_t n) {
    return realloc(v, n * sizeof(int));
    /* returns NULL on failure here */
}

您可以将所有内容都包装在一个结构体中，这样它也“知道自己的大小”，但您需要为每种类型都执行此操作（使用宏？），但这似乎有点不必要...也许可以尝试以下方法：

typedef struct {
    size_t size;
    int *data;
} int_vector;

int_vector *create_vector(size_t n) {
    int_vector *p = malloc(sizeof(int_vector));
    if(p) {
        p->data = malloc(n * sizeof(int));
        p->size = n;
    }
    return p;
}

void delete_vector(int_vector *v) {
    if(v) {
        free(v->data);
        free(v);
    }
}

size_t resize_vector(int_vector *v, size_t n) {
    if(v) {
        int *p = realloc(v->data, n * sizeof(int));
        if(p) {
            v->data = p;
            v->size = n;
        }
        return v->size;
    }
    return 0;
}

int get_vector(int_vector *v, size_t n) {
    if(v && n < v->size) {
        return v->data[n];
    }
    /* return some error value, i'm doing -1 here, 
     * std::vector would throw an exception if using at() 
     * or have UB if using [] */
    return -1;
}

void set_vector(int_vector *v, size_t n, int x) {
    if(v) {
        if(n >= v->size) {
            resize_vector(v, n);
        }
        v->data[n] = x;
    }
}

之后，您可以执行以下操作：

int_vector *v = create_vector(10);
set_vector(v, 0, 123);

我不知道，它似乎并不值得那么大的努力。

- Evan Teran

---

不过要小心避免引入O(N ** 2)的行为。此外，我从未见过对realloc返回值进行这种测试，你可能是正确的，但我觉得有点奇怪。 - user786653

@Will03uk：这个你只有在愿意通过函数调用来访问“向量”时才能拥有。C++使用运算符重载（特别是operator[]）来实现这一点，而C语言则没有。 - Evan Teran

@user786653：我认为你说得对，我的realloc检查有点问题，现在想想。如果块成功调整大小，我不认为需要显式地释放旧数据。 - Evan Teran

int *p = realloc(v->data, n * sizeof(int)); if(p) { p->data = p; p->size = n; } return v->size; doesn't make sense to me... shoudn't it be: if (p) { v->data = p; ... } - isedev

@isdev，它正在调整已分配的数组v->data的大小，如果成功，则将v->data设置为新的调整大小的数组。 - Evan Teran

Answer 2

我所知道的最全面的在C语言中创建一套综合性实用类型的努力是GLib。对于您的特定需求，它提供了g_array_new、g_array_append_val等函数。请参阅GLib数组文档。

- Ben Jackson

Answer 3

如果您能够进行乘法运算，那么当您拥有malloc()或者甚至是calloc()函数时，就真的没有必要再使用vector_create()函数了。您只需要跟踪两个值，即指针和分配的大小，并将这两个值发送到传递给“向量”的任何函数中（如果该函数确实需要指针和大小两个参数）。malloc()保证内存块可以被视为任何类型的地址，因此将其void *返回值赋值给例如struct car *，并使用[]对其进行索引。大多数处理器访问array[index]的速度几乎与variable相同，而vector_at()函数可能会慢很多倍。如果您在结构体中将指针和大小一起存储，请仅在非时间关键代码中执行此操作，否则您将不得不使用vector.ptr[index]进行索引。使用free()函数删除空间。

重点是编写一个好的realloc()函数包装器，它仅在每个2或1.5的幂次方上重新分配。请参见user786653的Wikipedia链接。

当然，如果你的内存不足，calloc()、malloc()和realloc()也可能失败，这是需要使用向量类型的另一个可能原因。C++有异常处理机制，如果你没有捕获异常，程序会自动终止，但C语言没有。但这是另一个讨论话题。

- potrzebie

Answer 4

我觉得与其在@EvanTeran's answer的评论中离题，不如在这里提交一个更长的回复。

正如一些评论所暗示的那样，由于C语言缺乏模板和RAII机制，试图复制std::vector的完全行为实际上没有太多意义。

然而，有一个有用的动态数组实现可以使用字节进行操作。这显然可以直接用于char*字符串，但只要您小心地将大小参数乘以sizeof(the_type)，它也可以轻松适用于任何其他类型。

- user786653

Answer 5

Apache Portable Runtime拥有一套不错的数组函数，并且全部使用C语言。

查看教程以快速入门。

- kichik

Answer 6

C语言缺乏模板功能，因此无法支持类似向量的结构。最好的方法是通过预处理器定义一个“通用”的结构，然后为要支持的每种类型进行“实例化”。

- K-ballo

---

或者使用 void * 和显式的 size_t element_size，但那样太丑陋并容易出错了。 - user395760