如何在C语言中复制向量？

Question

在出现C++和向量/列表之前，当需要存储更多数据时，人们是如何扩展数组的大小的？

- Kaije

Answer 1

向量和列表的概念并不仅限于C++。在C语言中也可以实现类似的数据结构，只是语法（和错误处理）会有所不同。例如，LodePNG 实现了一个具有与 std::vector 非常相似的功能的动态数组。使用示例如下：

uivector v = {};
uivector_push_back(&v, 1);
uivector_push_back(&v, 42);
for(size_t i = 0; i < v.size; ++i)
    printf("%d\n", v.data[i]);
uivector_cleanup(&v);

可以看到，使用方法有点冗长，而且需要重复编写代码以支持不同的类型。

nothings/stb 提供了一个更简单的实现，可适用于任何类型：

double *v = 0;
arrpush(v, 1.0);
arrpush(v, 42.0);
for(int i = 0; i < arrlen(v); ++i)
    printf("%g\n", v[i]);
arrfree(v);

它还提供了哈希映射，而它在 C 中用于类型安全容器的技巧也可以应用于其他通用容器。这些方法中的任何一个都可以通过调用 realloc（参见下文）来扩展底层存储，或者通过使用 malloc 分配新存储并使用 free 释放旧存储来扩展底层存储 - 这相当于 std::vector 在 C++ 中增加其内存的方式。然而，很多C代码使用realloc来直接管理内存。

void* newMem = realloc(oldMem, newSize);
if(!newMem) {
    // handle error
}
oldMem = newMem;

注意，realloc 在失败时返回 null，但旧内存仍然有效。在这种情况下，常见（且不正确）的用法会导致内存泄漏：

oldMem = realloc(oldMem, newSize);
if(!oldMem) {
    // handle error
}

相对于std::vector 和上面提到的 C 的等效物，简单的realloc 方法并没有提供 O(1) 平摊保证，虽然如果避免了移动内存时，realloc 有时可能会更有效率。

- Yakov Galka

---

@ybungalobill，嗯... vector::clear() 和 free 在任何方面都不是类似的。 - Charles Salvia

两者都不正确。new调用对象构造和内存分配，delete调用对象删除以及将内存返回给系统。realloc可以用于分配、释放和复制内存，但它不会像C ++中的那样构造对象。此外，请注意malloc、free和realloc与new和delete的行为不同。malloc可能会返回零表示分配失败，而new将抛出异常。还需注意，对空指针使用free将导致取消引用空指针，而对空指针使用delete则不会做任何操作。 - Beanz

通常newSize应该是旧大小的倍数，以获得单个项目附加操作的平摊O(1)时间复杂度。也就是说，为了避免频繁重新分配内存。因此，你需要像vector一样分别记录大小和容量。 - Steve Jessop

@user394242，C++拥有malloc、free和realloc。它们并不常用，因为C++有更方便的解决方案来处理动态内存。 - paldepind

根据我所看到的 C89 标准，"4.10.3.2 free 函数会释放 ptr 所指向的内存空间，也就是将其变为可供进一步分配使用的状态。如果 ptr 是空指针，则不执行任何操作。" - doug65536

Answer 2

很多C项目最终都会实现类似于向量的API。动态数组是如此普遍的需求，因此尽可能地将内存管理抽象出来是很好的。一个典型的C实现可能看起来像：

typedef struct dynamic_array_struct
{
  int* data;
  size_t capacity; /* total capacity */
  size_t size; /* number of elements in vector */
} vector;

接着他们会使用各种API函数调用来操作vector：

int vector_init(vector* v, size_t init_capacity)
{
  v->data = malloc(init_capacity * sizeof(int));
  if (!v->data) return -1;

  v->size = 0;
  v->capacity = init_capacity;

  return 0; /* success */
}

当然，您需要为push_back、insert、resize等编写函数，如果size超过capacity，则这些函数将调用realloc。

vector_resize(vector* v, size_t new_size);

vector_push_back(vector* v, int element);

通常情况下，当需要重新分配内存时，会将容量翻倍以避免频繁地进行重新分配。这通常是 std::vector 内部采用的相同策略，但通常由于 C++ 对象的构造/析构，std::vector 不会调用 realloc。相反，std::vector 可能会分配一个新的缓冲区，然后使用就地 new 进行对象的复制构造/移动构造（placement new）到新的缓冲区中。

在 C 中实现的实际向量可能会使用 void* 指针作为元素，而不是 int，这样代码更加通用。无论如何，这种事情在许多 C 项目中都有实现。有一个 C 语言中示例向量实现，请参见http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c。

- Charles Salvia

---

在这里，您似乎为结构体的数据变量创建了一个指针，但是我在许多其他在线矢量实现中看到，结构体的数据变量由双指针持有。这两种方法之间有什么区别？ - Kai

链接已损坏，请查看以下链接 https://gist.github.com/EmilHernvall/953968/0fef1b1f826a8c3d8cfb74b2915f17d2944ec1d0，这似乎是一种受欢迎的实现。 - Elliott Beach

@WarlikeChimpanzee，你的链接现在也失效了。 - Nicolas

https://eddmann.com/posts/implementing-a-dynamic-vector-array-in-c/ - shacke

Answer 3

他们会从隐藏定义一个包含实现所必需成员的结构开始。然后提供一组函数来操作结构的内容。

类似这样：

typedef struct vec
{
    unsigned char* _mem;
    unsigned long _elems;
    unsigned long _elemsize;
    unsigned long _capelems;
    unsigned long _reserve;
};

vec* vec_new(unsigned long elemsize)
{
    vec* pvec = (vec*)malloc(sizeof(vec));
    pvec->_reserve = 10;
    pvec->_capelems = pvec->_reserve;
    pvec->_elemsize = elemsize;
    pvec->_elems = 0;
    pvec->_mem = (unsigned char*)malloc(pvec->_capelems * pvec->_elemsize);
    return pvec;
}

void vec_delete(vec* pvec)
{
    free(pvec->_mem);
    free(pvec);
}

void vec_grow(vec* pvec)
{
    unsigned char* mem = (unsigned char*)malloc((pvec->_capelems + pvec->_reserve) * pvec->_elemsize);
    memcpy(mem, pvec->_mem, pvec->_elems * pvec->_elemsize);
    free(pvec->_mem);
    pvec->_mem = mem;
    pvec->_capelems += pvec->_reserve;
}

void vec_push_back(vec* pvec, void* data, unsigned long elemsize)
{
    assert(elemsize == pvec->_elemsize);
    if (pvec->_elems == pvec->_capelems) {
        vec_grow(pvec);
    }
    memcpy(pvec->_mem + (pvec->_elems * pvec->_elemsize), (unsigned char*)data, pvec->_elemsize);
    pvec->_elems++;    
}

unsigned long vec_length(vec* pvec)
{
    return pvec->_elems;
}

void* vec_get(vec* pvec, unsigned long index)
{
    assert(index < pvec->_elems);
    return (void*)(pvec->_mem + (index * pvec->_elemsize));
}

void vec_copy_item(vec* pvec, void* dest, unsigned long index)
{
    memcpy(dest, vec_get(pvec, index), pvec->_elemsize);
}

void playwithvec()
{
    vec* pvec = vec_new(sizeof(int));

    for (int val = 0; val < 1000; val += 10) {
        vec_push_back(pvec, &val, sizeof(val));
    }

    for (unsigned long index = (int)vec_length(pvec) - 1; (int)index >= 0; index--) {
        int val;
        vec_copy_item(pvec, &val, index);
        printf("vec(%d) = %d\n", index, val);
    }

    vec_delete(pvec);
}

除此之外，他们将通过在函数组的位置使用void*来实现封装，并通过在包含函数组的C模块中定义结构体而不是在头文件中来隐藏结构体定义，从而使用户无法看到它。此外，他们会通过在头文件中省略那些你认为应该是私有的函数，并仅在C模块中进行原型设计，来隐藏这些函数。

- Michael Smith

---

写这篇文章花了30分钟，不保证完全准确。 - Michael Smith

Answer 4

你可以查看实现 vc_vector:

struct vc_vector {
  size_t count;
  size_t element_size;
  size_t reserved_size;
  char* data;
  vc_vector_deleter* deleter;
};

...

vc_vector* vc_vector_create_copy(const vc_vector* vector) {
  vc_vector* new_vector = vc_vector_create(vector->reserved_size / vector->count,
                                           vector->element_size,
                                           vector->deleter);
  if (unlikely(!new_vector)) {
    return new_vector;
  }

  if (memcpy(vector->data,
             new_vector->data,
             new_vector->element_size * vector->count) == NULL) {
    vc_vector_release(new_vector);
    new_vector = NULL;
    return new_vector;
  }

  new_vector->count = vector->count;
  return new_vector;
}

使用它：

vc_vector* v1 = vc_vector_create(0, sizeof(int), NULL);
for (int i = 0; i < 10; ++i) {
  vc_vector_push_back(v1, &i);
}

// v1 = 0 1 2 3 4 5 6 7 8 9

vc_vector* v2 = vc_vector_create_copy(v1);

// v2 = 0 1 2 3 4 5 6 7 8 9 (copy of v1)

// to get pointer to int:

const int* v2_data = vc_vector_data(v1);

- farcost

Answer 5

这是我的实现。它基本上是一个包含指向数据的指针、大小（以元素为单位）、总分配空间和存储在向量中的类型大小的结构体，以允许使用void指针。"Original Answer"翻译成"最初的回答"。链接：https://github.com/jakubgorny47/baku-code/tree/master/c_vector

- GPlayer

---

如果您按照其他答案的做法，将代码直接包含在您的答案中，并提供链接，那么这个答案会更好;尤其是因为这个答案发布的时间相对较晚。 - Philip Adler

Answer 6

你可以使用 "Gena" 库。它与纯 C89 中的 stl::vector 十分相似。

从 README 中，它具有以下特点：

• 像使用普通 C 数组一样访问向量元素：vec[k][j]；
• 拥有多维数组；
• 复制向量；
• 在单独的模块中实例化必要的向量类型，而不是每次需要向量时都这样做；
• 您可以选择如何将值传递到向量中以及如何从向量中返回值：按值或按指针。

你可以在这里查看它：

https://github.com/cher-nov/Gena

- user7369463