如何複製c中的矢量？

Question

在C++和vector/lists之前的日子裏，他們在需要存儲更多數據時如何擴展數組的大小？

Answer 1

典型的C代碼如下所示：

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

oldMem = newMem; 

注意，如果realloc的失敗則返回零，但舊的記憶仍然有效，這個典型的使用會導致內存泄漏：

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

不幸這很常見;

另請注意，C++ vector/list沒有特別之處。類似的結構可以在C中實現，只是語法（和錯誤處理）看起來不同。例如，請參見LodePNG's用於C的std :: vector的模擬。

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); 

一般，需要重新分配時，capacity被加倍，以避免重新分配所有的時間。這通常與std::vector內部採用的策略相同，但通常情況下，由於C++對象構建/銷燬，std::vector不會調用realloc。相反，std::vector可能會分配一個新緩衝區，然後將構造/移動構造對象（使用放置new）複製到新緩衝區中。

C中的實際向量實現可能使用void*指針作爲元素而不是int，所以代碼更通用。無論如何，這種事情在很多C項目中都有實現。請參閱http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c以獲取C中的示例向量實現。

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); 
} 

而且到這一點，他們會通過在VEC *的地方功能組使用無效*實現封裝，並通過中定義它實際上對用戶隱藏的結構定義C模塊包含一組函數而不是頭部。同樣，他們會隱藏你認爲是私有的功能，把它們從頭文件中刪除，只在C模塊中進行原型設計。

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);