我们可以在数组末尾插入元素而不复制它的所有内容吗？

Question

我正在尝试在 C 中重现 std::vector 的行为，我有一些想法：向量具有连续分配的内存，这意味着当您在末尾添加一个元素时它不会将所有数组复制到另一个内存块，而是在最后分配另一个元素，从而提高性能，但在 C 中我无法找到重现该行为的方法，这是我能找到的唯一方法添加一个最后的元素是这样做的：

void *new_array;
size_t new_size = old_size + size_type;
new_array = (char*)malloc(size_type * new_size);
memcpy(new_array, old_array, old_size * size_type);
memcpy(new_array, new_value, size_type);

而且我很确定 std::vector 不会那样进行，是否可以在不分配大块内存的情况下重现它？

Answer 1

您可能正在寻找的是 realloc from <stdlib.h>. It doesn't necessarily copy the entire data, because memory isn't necessarily stored contiguously depending on the implementation and as William Pursell 在另一个答案的评论中提到的：

Quite often, realloc can grow a chunk of memory without needing to do a copy.

我在下面提供了一个如何使用 realloc 的简单示例。

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

int main(void)
{
    /* last character will be `[=10=]` */
    char *str = malloc(6);
    strcpy(str, "Hello");

    str = realloc(str, 7);
    str[5] = '!';
    str[6] = '[=10=]';

    printf("%s\n", str);
    free(str);

    return EXIT_SUCCESS;
}

Answer 2

您不能在不重新分配数组占用的内存的情况下向数组添加元素，前提是当前数组还没有 space 新元素。

因此，数组的任何重新分配通常意味着将其存储的元素复制到新的内存范围（当前内存范围只是在内部扩大的情况除外）。

您可以像在 C++ 中那样“手动”执行此操作，或者在 C 中您可以使用标准函数 realloc，如果需要，它会自行执行此类复制。

Answer 3

据我所知，std::vector 在其 capacity 耗尽时也会进行重新分配。在这种情况下，将创建一个容量是先前向量容量两倍的新向量，然后从旧向量复制到新向量中。作为此重新分配的结果，迭代器和对较早向量的引用无效。由于这个原因，std::vector 被认为是 'unstable'。与此相反的是 Boost (https://www.boost.org/doc/libs/1_75_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.stable_vector)

中的 stable_vector

std::vector 的重新分配通常会降低性能。因此，通常需要在矢量上执行 reserve - 在其初始化时 - 如果存在关于矢量最终大小的先验知识。

我们可以在数组末尾插入元素而不复制它的所有内容吗？

Can we insert element at the end of an array without copying all it's content?

c

dynamic-memory-allocation